Thread: 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?

Actually, my list_entry is not doubly linked. I had it doubly linked, but realized it was overkill in this scenario.

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.