another memory issue

Discussion in 'Mac Programming' started by farmerdoug, Feb 1, 2010.

  1. farmerdoug macrumors 6502a

    Joined:
    Sep 16, 2008
    #1
    This sorting routing does not work.
    Code:
    void sort ( char ****array, int n, int p, int q) //number of items to sort p, q are rows and columns
    {
    	
    	char temp_page[10][45][12];
    	int size = 10*45*12;
    	
    	int j, k;
    	
    	for(j= (n - 1); j >= 0; j-- ) 
    		for(k = 1; k <= j; k++)	
    			if(atoi(array[k - 1][p][q]) > atoi(array[k][p][q]) )
    			{	
    				memcpy(temp_page,array[k - 1],sizeof(char)*size);
    				memcpy(array[k - 1],array[k],sizeof(char)*size);
    				memcpy(array[k],temp_page,sizeof(char)*size);	
    			}	
    
    	for (j = 0; j < n; j++)
    		printf("%s \n", array[j][0][3]);
    
    }
    
    
    I finally figured out that it probably fails because memory for array is not allocated in one block but in a series of loops that requires array to be addressed as array[j][k]. Am I right?
     
  2. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #2
    Back in this thread:
    http://forums.macrumors.com/showthread.php?t=844474

    I showed how to do this with a pointer swap. The great thing about all of those pointers is doing a swap is super cheap, no big copies are necessary. Try it that way and see how it goes.

    -Lee
     
  3. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #3
    another memory issue.

    I looked through your code. I'm right in that it sorts every number? That's not what I am doing. I am sorting according to one element in the array; the array with the maximum value in that element goes to the top.
     
  4. lloyddean macrumors 6502a

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #4
    RandomStringPresenter

    farmerdoug,

    In order to properly assist you it would really, really, REALLY help if you provided the sample data AND describe WHAT you're trying to accomplish.

    Or tell me to stop asking and I'll ignore any future request for assistance from you. It hurts me to to see you pounding your head against the door jam like this and not being able to help.
     
  5. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #5
    The example under the first edit should be most similar to your code here. It finds the "page" with the highest value as you described originally, and moves that page to the beginning. You could iterate this to do a page bubble sort. There are many sort algorithms faster than this one, but the swap will work for any of them.

    -Lee
     
  6. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #6
    Your first routine is what I am using with a bubble but it doesn't sort properly. I think its because my memory allocation is not compatible with the memcpy.

    I've have been told many times that I am too terse. It's a bad habit. But in this case, I plead mostly not guilty. You have the code and what I am trying to do. True saying sort is not the same as saying sorting on an element in the code but I thought that was obvious. I also thought that the last line about memory allocation would have been easily tied to the use of memcpy.

    I'm not trying to be difficult; the help I get on this forum has taught me a lot and save me many hours. I'll try harder but I'm an old dog. Please don't stop at least looking at my posts.
    Doug
     
  7. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #7
    The first example of mine in that last thread had fixed size, contiguous arrays. The second is like what you've been doing (assuming this is like your other examples, we have no idea how array is allocated because you didn't post a complete, compilable example), with each dimension allocated separately. In this case, the memory is not contiguous, so you cannot do a big memcpy, etc. If you've allocated each dimension, then you can just do a pointer swap using an assignment statement instead of memcpy'ing things around.

    What lloyddean, myself, and others have asked for in the past is not the tiny bit of code where you are having problems, but a complete, compilable example that exhibits the problem, and the data file(s) you are using that produce the behavior you're having problems with. In the past you stated:
    Which may be the case, but if you can't even send a stripped down example of code with the problem that can be compiled and run, with even a sample data file, it just means that we are often guessing at the problem. Often, even if you include the whole subroutine where you think the problem lies, this is not enough for us to completely debug the problem. Misallocation elsewhere, etc. can lead to problems. If we can compile and run the code, chances are we can very quickly identify the problem. Otherwise we're just trying to analyze the code, and it may not even be the code with the problem.

    In any event, you should be able to just declare a temp char***, assign array[k-1] to it, then assign array[k] to array[k-1], then assign your temp char*** to array[k]. Since these are each just pointers, you can just assign them around, you don't have to copy large chunks of memory.

    -Lee
     
  8. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #8
    lee

    The code is gigantic as is a data file; it's also confidential. I just can't post it. I try and post enough but obviously not enough. What I think is obvious obviously isn't. I made some changes but they are on another machine which has resulted in warnings I don't understand. The code is on another machine; I'll sent it later.

    Always grateful,
    doug
     
  9. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #9
    another memory issue.

    I want to be able to use memcpy to move an array around. Therefore it must be stored in continuous memory. So I did the following:
    Code:
    
    #define pages 2000
    #define rows 10
    #define cols 45
    
    char * allocate_memory (char *array);
    
    char * allocate_memory (char *array)
    
    {
    	
    
    int size;
    
    	size = pages*rows*cols;	
    	
    if( (array = (char*)calloc(size,element*sizeof(char)) == NULL))
    	{	
    	printf("no memory");
    	return(0);
    	}	
    	return ((char *) array);
    }
    
    
    When I compile this I get a warning" : assignment makes pointer from integer with out a cast" at the if statement

    I don't understand why. I think I have provided enough code to answer the question. If not please let me know what you think may be helpful.
     
  10. lloyddean macrumors 6502a

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #10
    First of all this can't be what you're actually trying to compile since you haven't defined 'element' in what you did provide. Be that as it may you probably meant to write:

    Code:
    if( (array = (char*)calloc(size,element*sizeof(char))) == NULL)
     
  11. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #11
    Yes, thanks. That took care of that warning. I thought it would take care of some of the other 107 warnings I got when I changed the code but no luck. I may call on you again.

    doug

    If I've properly allocated memory for array, what gives here? I get a cast to pointer from integer of different size warning at the second if statement.

    Code:
    #define pages 2000
    #define rows 10
    #define cols 45
    #define element 12
    
    char * allocate_memory (char *array);
    
    char * allocate_memory (char *array)
    
    {
    	
    
    int size;
    int k,p,q;
    	size = pages*rows*cols;	
    	
    if( (array = (char*)calloc(size,element*sizeof(char))) == NULL)
    	{	
    	printf("no memory");
    	return(0);
    	}	
    
    if(atoi((char*)array[(k-1)*pages + p*rows + q*cols]) > atoi((char*)array[k*pages + p*rows + q*cols] ));
    	
    return ((char *) array);
    }
    
    
     
  12. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #12
    Code:
    array[(k-1)*pages + p*rows + q*cols]
    Is applying [] to a char *. This will evaluate to a char. You then cast to a char *, and pass this to atoi. You're basically getting a character value out of array, then casting that 1-byte value to a pointer, then passing it to something expecting a char *.

    I think you want:
    Code:
    atoi(&array[(k-1)*pages + p*rows + q*cols])...
    This will get the address at that offset of array. You could also do:
    Code:
    atoi(array+(k-1)*pages + p*rows + q*cols)...
    to use pointer addition, which will evaluate to a char * instead of using [].

    -Lee
     
  13. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #13
    Lee.

    Thanks,
    That removed the warning and highlighted some holes in my knowledge (some of many, I'm sure). It would have worked for an array of ints, yes? Would another method of allocating the memory make the syntax correct?
     
  14. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #14
    If it was a char **, then [] would evaluate to a char *, so that would work. So in a sense, yes, a different allocation scheme/data type would work in that situation. It would not work for an array of ints. An int is not a *, even if it's the same size on some platforms.

    When you have a datatype that is a * (or multiple *s), when you apply [], think of it as taking one * away from the type, and that's what the expression will evaluate to. So if you apply [][][] to a char ****, you get a char *. When you apply &, you add a *. So:
    Code:
    char x = 'c';
    char *w = NULL;
    w=&x;
    
    Takes a char, x, and gives you the address in memory it's being stored, yielding a char *. In C, char * is "overloaded" to not just mean the pointer to a single character, or the base of an array of characters, but a "C string", a pointer to an array of characters that is terminated with a null character, '\0'. This makes dealing with char *s a bit more involved, because you need to know what you're going to find at the end of the pointer (a single char, a fixed size array of char, or a "C string").

    -Lee
     
  15. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #15
    bleeding

    So did I shoot myself in the foot? I know how to access an element but how do I move the entire array with one memcpy call.
     
  16. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #16
    This should still be achievable, it is just going to require more math than a pointer swap, etc.

    It would look like:
    Code:
    //array is a giant block of memory containing numpages*rows*cols*element chars
    char tmp[rows][cols][element];
    int pagesize = rows*cols*element;
    int pageto = 5;
    int pagefrom = 6;
    memcpy(tmp,array+pageto*pagesize,pagesize);
    memcpy(array+pageto*pagesize,array+pagefrom*pagesize,pagesize);
    memcpy(array+pagefrom*pagesize,tmp,pagesize);
    
    -Lee
     
  17. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #17
    Lee

    In C, char * is "overloaded" to not just mean the pointer to a single character, or the base of an array of characters, but a "C string", a pointer to an array of characters that is terminated with a null character, '\0'. This makes dealing with char *s a bit more involved, because you need to know what you're going to find at the end of the pointer (a single char, a fixed size array of char, or a "C string").


    So I think the issue must be that I assumed when I was loading the array with elements that they were terminated by a '\0' when it seems from they way the program failed that they weren't.

    The code now executes but its not sorting properly. Lets see what I can do. Its temping to just keep posting problems and let you write the code but I'll keep temptation at bay for a while.

    doug
     
  18. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #18
    Lee

    Lee,
    I couldn't get your memcpy to work either as is or after various trials and error. The trouble seems to be that I can move anything into tmp.

    Code:
    
    void sort ( char* array, int n, int p, int q) //number of items to sort p, q are rows and columns
    {
    	
    	char *tmp;
    	int size = rows*cols*element;
    	
    	int j, k;
    	tmp = (char*)calloc(size,sizeof(char));
    		
    	for (j = 0; j < n; j++)
    		printf("%s \n",&array[j*pages+ 0*rows + 0*cols]);
    	
    	for(j= (n - 1); j >= 0; j-- ) 
    		for(k = 1; k <= j; k++)
    		{	//printf("%d %d \n", atoi(array[k - 1][p][q]), atoi(array[k][p][q]));
    			//printf("%s %s\n",&array[(k-1)*pages+ 0*rows[3], &array[(k)*pages+ 0*rows[3]);
    			if(atoi(array[(k-1)][p][q]) > atoi(array[k][p][q]))
    			{	
    			//	printf("%s %s\n",&array[(k-1)*pages+ 0*rows[3], &array[(k)*pages+ 0*rows[3]);
    				memcpy(tmp,array[k-1],size);
    		//		printf("here %s\n", (char *)tmp[0][3]);
    				memcpy(array[k-1],array[k],size);
    				memcpy(array[k],tmp,size);
    			//	printf("%s %s\n",&array[(k-1)*pages+ 0*rows[3], &array[(k)*pages+ 0*rows[3]);	
    				}
    //		printf("\n");
    		}	
    	//for (j = 0; j < n; j++)
    	//	printf("%s \n",&array[j*pages+ 0*rows + 0*cols]);
    
    }
    
    Be warned, I am now writing a search algorithm. :)

    doug.
     
  19. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #19
    When array is char *, i don't even know what this is going to do:
    Code:
    array[(k-1)][p][q]
    I'm not sure if this will compile, and if it will I don't know what the results will be.

    I think you need something like:
    Code:
    char *tmp = NULL;
    int pagesize = rows*cols*element;
    int rowsize = cols*element;
    tmp = (char*)calloc(pagesize,sizeof(char));
    ....
    pageOne = 
    if( atoi(array+(k-1)*pagesize+p*rowsize+q*element) > atoi(array+k*pagesize+p*rowsize+q*element) ) {
      memcpy(tmp,array+(k-1)*pagesize,pagesize);
      memcpy(array+(k-1)*pagesize,array+k*pagesize,pagesize);
      memcpy(array+k*pagesize,tmp,pagesize);
    }
    ...
    free(tmp);
    ...
    
    If you're going to dynamically allocate tmp in this subroutine, you must free it or you will leak memory.

    I don't know if the code you posted would compile at all. I don't think you can perform [] on a char, which is what you were doing before (then applying [] again on its result). If you want to use [] on array, you'll get a char. If you need its memory address, apply &. I would say, even though I normally hate it and advise against it, that using pointer addition will work out better here than doing all of the math inside the [], then applying & to the result to get a char * pointing to a particular element, page, etc.

    I also don't know about your bubble sort implementation here, but in terms of the mechanics what i posted above should cover it.

    -Lee
     
  20. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #20
    Lee

    My apologies. Working two jobs; can't think things straight. What didn't work was your code

    char tmp[rows][cols][element];
    int pagesize = rows*cols*element;
    int pageto = 5;
    int pagefrom = 6;
    memcpy(tmp,array+pageto*pagesize,pagesize);
    memcpy(array+pageto*pagesize,array+pagefrom*pagesize,pagesize);
    memcpy(array+pagefrom*pagesize,tmp,pagesize);

    The second memcpy works but not the ones involving tmp. I tried a number of configurations for tmp including allocating memory as per your lasted suggestion.
     
  21. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #21
    I didn't run that code, but I feel like tmp should be the base of the array. If you declare tmp as a char * instead, and malloc/calloc pagesize bytes, that should definitely work.

    -Lee
     
  22. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #22
    Why bytes not char? A byte has to be defined.

    Now I have the same code as last night allocating memory for tmp. And temp is being loaded. Par for the course. Still now sorting but I don't think that's a memory issue.
    thanks
    doug
     
  23. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #23
    Lee and everybody else

    It is a memory issue.

    Here's the code. The output and explanation follows

    Code:
    
    #define pages 2000
    #define rows 10
    #define cols 45
    #define element 12
    
    char * allocate_memory (char *array)
    
    {
    		
    	
    	if( (array = (char *) calloc(pages*rows*cols*element,sizeof(char))) == NULL)
    	{	
    		printf("no memory");
    		return(0);
    	}	
    		return ((char *) array);
    }
    
    void sort ( char* array, int n, int p, int q) //n = number of items to sort p, q are specific row and column
    {
    	
    	char *tmp;
    	int size = rows*cols*element;
    	int j, i,k;
    	tmp = (char*)calloc(size,sizeof(char));
    for ( i = 0; i < n; i++)
    		printf("%s  \n ",  &array[i*pages +0*rows + 3*cols]);
    	
    	printf("\n");
    	
    	for(j= (n - 1); j >= 0; j-- ) 
    		for(k = 1; k <= j; k++)	
    			if(atoi(array + (k - 1)*pages + p *rows + q*cols) > atoi(array + (k)*pages + p *rows + q*cols) )
    			{	printf("\n");
    				memcpy(tmp,array+ (k - 1)*pages,sizeof(char)*size);
    				memcpy(array+(k - 1)*pages,array+(k*pages),sizeof(char)*size);
    				memcpy(array+k*pages,tmp,sizeof(char)*size);	
    				for ( i = 0; i < n; i++)
    					printf("%s  \n ",  &array[i*pages +0*rows + 3*cols]);									
    			}	
    	
    	
    }
    
    
    
    
    This is the input.
    13228
    52649
    1243
    2496
    13166
    759

    When the first two elements are compared, the second is larger so nothing is done. When the second and third elements are compared, the second being larger is switched with the third. But also the third was moved to the four position and number 13166 disappeared altogether. It only gets worse from there.
    13228
    1243
    52649
    1243
    2496
    759

    13228
    1243
    1243
    52649
    1243
    2496

    13228
    1243
    1243
    1243
    52649
    1243
     
  24. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #24
    Not sure if this is the only problem, but instead of:
    Code:
    memcpy(tmp,array+ (k - 1)*pages,sizeof(char)*size);
    change *pages to *size. pages is 2000, size is 5300. There could be other things going on, but this is not likely to be helping.

    -Lee
     
  25. farmerdoug thread starter macrumors 6502a

    Joined:
    Sep 16, 2008
    #25
    You're right

    I saw that on the subway. It doesn't help but there are other things going on.
    I going to try some more tests.
     

Share This Page