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.
and the function: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. */ } ;
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: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 ; }
Is there a cleaner way to do this when writing a general purpose list manager?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 ; }
