Thread: Advancing a pointer past an incomplete structure.

  1. #1
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,339

    Advancing a pointer past an incomplete structure.

    I'm creating a doubly-linked list that is contained in blocks that are doubly-linked as well.

    When I create a block, (aka, a header), the caller specifies the length of his data that will go into a list entry, and the count of list entries he wants in each block. I obtain storage for the size of the list_header struct, plus the product of (the list_entry struct size + the length the caller supplies) * the count of entries the user wants in his blocks.

    I have a structure for the list header (list_header) and a list entry (list_entry). (I try not to venture too far from reality with my variable names.)

    The list_entry structure is incomplete, in that there is control information at the top, and then a "char data[0]" at the end where the caller's data will go.

    When I preformat a new header block, I chain all the list_entries. My question has to do with calculating the address of the 2nd and subsequent list_entry.

    I know this is pointer arithmetic, but my structure is incomplete, so it's not just a simple entry = entry + 1 to advance to the next one. I resorted to using a void *, and that works, but I would like to know if there is something more proper. Here's my are my 2 structures and the list_create() function that preformat the list entries.

    Code:
    struct list_header {                                                              
       size_t size ;                   /* size of this header block */                
                                       /* the size = sizeof(struct list_header) + */  
                                       /* (sizeof(struct list_entry) * count) */      
       struct list_header * next ;     /* -> to next header block */                  
       struct list_header * prev ;     /* -> to previous header block */              
       struct list_entry * le_first ;  /* -> 1st list entry in this block */          
       size_t le_length ;              /* length of user data in the list entry  */   
       size_t le_used ;                /* # of list entries in use */                 
       size_t le_count ;               /* count of list entries in this block */      
       char data[0] ;                  /* start of list entries */                    
    } ;                                                                               
                                                                                      
    struct list_entry {                                                               
       struct list_entry * next ;      /* next list entry or 0 if last */             
       struct list_header * hdr ;      /* pointer to associated header block */       
       struct flags {                                                                 
          unsigned used : 1 ;          /* list entry is in use  */                    
          unsigned : 31 ;              /* no more bits in use */                      
       } flag ;                                                                       
       char data[0] ;                  /* User data starts here. */                   
    } ;
    and the function:
    Code:
    struct list_header * list_create(size_t length, size_t count) {                                                 
                                                                                                                    
      size_t blocklen ;                                                                                             
      struct list_header * hdr ;                                                                                    
      struct list_entry  * entry ;                                                                                  
      void * next ;                                                                                                 
                                                                                                                    
      // input arg length is the length of the user data only.  We have to add the                                  
      // struct list_entry size to it for size calcs                                                                
                                                                                                                    
      blocklen = sizeof(struct list_header) + ((length + sizeof(struct list_entry)) * count ) ;                     
                                                                                                                    
      hdr = (struct list_header *) malloc(blocklen) ;                                                               
      hdr->size      = blocklen ;                                                                                   
      hdr->le_length = length ;                                                                                     
      hdr->le_count  = count ;                                                                                      
      hdr->next, hdr->prev, hdr->le_used = 0 ;                                                                      
                                                                                                                    
      //  Preformat list entries.                                                                                   
      //printf("Hdr  =%08p, hdr size=%02x, blocklen=%02x\n", hdr, sizeof(struct list_header), blocklen) ;           
      entry = (struct list_entry *) hdr->data ;       // first entry                                                
      hdr->le_first = entry ;                                                                                       
                                                                                                                    
      for  (int i = 0 ; i < count ; i++ ) {                                                                         
      // printf("Entry=%08p, le_length=%d, sizeof(str le)=%d\n", entry, hdr->le_length, sizeof(struct list_entry)); 
         next = (void *) entry + hdr->le_length + sizeof(struct list_entry) ;                                       
         entry->next =  (struct list_entry *) next ;                                                                
         entry->hdr = hdr ;                                                                                         
      // printf("...entry->next=%08p, entry->hdr=%08p\n", entry->next, entry->hdr ) ;                               
         entry = entry->next ;                                                                                      
      }                                                                                                             
      entry->next = 0 ;     // zero out the last one                                                                
      return hdr ;                                                                                                  
    }
    After I wrote the supporting list functions, I went to write a test case to exercise the code, I realized that implementing this scheme is a bit ugly, in that the caller has to reserve enough room in their own structure for the overhead associated with my list implementation, and casting is required when calling my functions.

    Code:
    int main(void) {                                                                
                                                                                    
        struct mylist {                                                             
            char x[sizeof(struct list_entry)] ;                                     
            int number ;                                                            
        } ;                                                                         
        struct mylist * mylistptrs[50] ;                                            
        struct list_header * hdr ;                                                  
                                                                                    
        hdr = list_create( sizeof(struct mylist) - sizeof(struct list_entry), 1) ;  
                                                                                    
        for (int i = 0 ; i < 25 ; i++) {                                            
           mylistptrs[i] = (struct mylist *) list_add(hdr) ;                        
           mylistptrs[i]->number = i+1 ;                                            
           printf("Number is %d\n", mylistptrs[i]->number ) ;                       
        }                                                                           
                                                                                    
                                                                                    
        for (int i = 24 ;  i >= 0  ; i--) {                                         
           printf("Removing number %d\n", mylistptrs[i]->number ) ;                 
           list_remove( (struct list_entry *) mylistptrs[i]) ;                      
        }                                                                           
                                                                                    
        for (int i = 0 ; i < 50 ; i++) {                                            
           mylistptrs[i] = (struct mylist *) list_add(hdr) ;                        
           printf("i=%d, Number is %d\n", i+1, mylistptrs[i]->number ) ;            
        }                                                                           
                                                                                    
        for (int i = 49 ;  i >= 0  ; i--) {                                         
           list_remove((struct list_entry *) mylistptrs[i]) ;                       
        }                                                                           
                                                                                    
        list_destroy(hdr) ;                                                         
                                                                                    
        return 0 ;                                                                  
    }
    Is there a cleaner way to do this when writing a general purpose list manager?
    Mainframe assembler programmer by trade. C coder when I can.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,339
    Actually, my list_entry is not doubly linked. I had it doubly linked, but realized it was overkill in this scenario.
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,670
    So what's the point of list_entry?

    I mean, once you've baked your list_header, you can't then do anything like add and remove a list_entry.

    Having this would allow you to get rid of the messy used flag, as well as permitting regular looking list traversal code.
    Code:
    struct list_header {                                                              
       size_t size ;                   /* size of this header block */
                                       /* the size = sizeof(struct list_header) + */
                                       /* (sizeof(struct list_entry) * count) */
       struct list_header * next ;     /* -> to next header block */
       struct list_header * prev ;     /* -> to previous header block */
       struct list_entry * le_head ;  /* -> the list */
       struct list_entry * le_free ;  /* -> the free list */
       size_t le_length ;              /* length of user data in the list entry  */
       size_t le_used ;                /* # of list entries in use */
       size_t le_count ;               /* count of list entries in this block */
       char data[0] ;                  /* start of list entries */
    } ;
    Regular list traversal follows naturally with
    Code:
    for ( struct list_entry *p = list_header->le_head ; p != NULL ; p = p->next )
    Adding a new node just involves moving a node from l->le_free to somewhere in the list at l->le_head (much like what you would do calling malloc)
    Removing a node removes it from the list and appends it to l->le_free (much like what you would do calling free)

    At least within the limits of the total number of nodes you pre-allocated.

    > next = (void *) entry + hdr->le_length + sizeof(struct list_entry) ;
    You should be getting a warning about arithmetic on a void pointer, which isn't supported since void has no size.
    gcc allows it - c - How void pointer arithmetic is happening in GCC - Stack Overflow
    But it isn't standard conforming.
    Normally you would use a char* if you're doing all the byte counting yourself.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dereferencing pointer to incomplete type
    By jeltedeproft in forum C Programming
    Replies: 2
    Last Post: 12-14-2015, 07:57 AM
  2. dereferencing pointer to incomplete type
    By killermelga in forum C Programming
    Replies: 4
    Last Post: 11-09-2011, 03:20 PM
  3. dereferencing pointer to incomplete type
    By SasDutta in forum C Programming
    Replies: 2
    Last Post: 07-28-2010, 09:32 AM
  4. arithmetic on pointer to an incomplete type?
    By Volair in forum C Programming
    Replies: 4
    Last Post: 11-19-2006, 06:53 PM
  5. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM

Tags for this Thread