NOOB here.
√searched archives
√searched faqs
√googles
√tutorials
I'm attempting to learn about generic linked lists from Kendall Bennett's CTools10 which I'll include below for reference.
my question is this: He defines a bucket but never any variables to store the data. How do I assign data to the bucket if the only variable in the bucket is *next?
Is there an example. of use of this library.
I know I'm in a different world now. I'm trying to turn off my old brain but it's really hard to believe I might have to re-impliment the code for an array every time I want an array of undefined length. Whew. sorry for the ..........fest.
Code:typedef struct LST_BUCKET { struct LST_BUCKET *next; } LST_BUCKET;
//header
Code:/**************************************************************************** * * Copyright (C) 1991 Kendall Bennett. * All rights reserved. * * Filename: $RCSfile: list.h $ * Version: $Revision: 1.7 $ * * Language: ANSI C * Environment: any * * Description: Header file for linked list routines. * * $Id: list.h 1.7 91/12/31 19:41:16 kjb Exp $ * * Revision History: * ----------------- * * $Log: list.h $ * Revision 1.7 91/12/31 19:41:16 kjb * * Modified include files directories. * * Revision 1.6 91/09/27 03:11:04 kjb * Added compatibility with C++. * * Revision 1.5 91/09/26 10:07:42 kjb * Took out extern references * * Revision 1.4 91/09/01 17:18:24 ROOT_DOS * Changed prototype for lst_deletenext(). * * Revision 1.3 91/09/01 15:15:46 ROOT_DOS * Changed search for include files to include current directory * * Added function lst_kill(). * * Revision 1.2 91/08/22 11:06:50 ROOT_DOS * Header file for corresponding revision of source module * * Revision 1.1 91/08/21 14:11:39 ROOT_DOS * Initial revision * ****************************************************************************/ #ifndef __LIST_H #define __LIST_H #ifndef __DEBUG_H #include "debug.h" #endif /*---------------------- Macros and type definitions ----------------------*/ typedef struct LST_BUCKET { struct LST_BUCKET *next; } LST_BUCKET; typedef struct { int count; /* Number of elements currently in list */ LST_BUCKET *head; /* Pointer to head element of list */ LST_BUCKET *z; /* Pointer to last node of list */ LST_BUCKET hz[2]; /* Space for head and z nodes */ } LIST; /* Return a pointer to the user space given the address of the header of * a node. */ #define LST_USERSPACE(h) ((void*)((LST_BUCKET*)(h) + 1)) /* Return a pointer to the header of a node, given the address of the * user space. */ #define LST_HEADER(n) ((LST_BUCKET*)(n) - 1) /* Return a pointer to the user space of the list's head node. This user * space does not actually exist, but it is useful to be able to address * it to enable insertion at the start of the list. */ #define LST_HEAD(l) LST_USERSPACE((l)->head) /* Determine if a list is empty */ #define LST_EMPTY(l) ((l)->count == 0) /*-------------------------- Function Prototypes --------------------------*/ #ifdef __cplusplus extern "C" { #endif void *lst_newnode(int size); void lst_freenode(void *node); LIST *lst_init(void); void lst_kill(LIST *l,void (*freeNode)()); void lst_insertafter(LIST *l,void *node,void *after); void *lst_deletenext(LIST *l,void *node); void *lst_first(LIST *l); void *lst_next(void *prev); void lst_mergesort(LIST *l,int (*cmp_func)()); #ifdef __cplusplus } #endif #endif
Code:/**************************************************************************** * * Copyright (C) 1991 Kendall Bennett. * All rights reserved. * * Filename: $RCSfile: list.c $ * Version: $Revision: 1.9 $ * * Language: ANSI C * Environment: any * * Description: Module to implement linked lists. Includes a routine to * peform a mergesort on the linked list. * * $Id: list.c 1.9 91/12/31 19:40:15 kjb Exp $ * * Revision History: * ----------------- * * $Log: list.c $ * Revision 1.9 91/12/31 19:40:15 kjb * Modified include file directories. * * Revision 1.8 91/10/28 03:17:14 kjb * Ported to the Iris. * * Revision 1.7 91/09/03 18:28:15 ROOT_DOS * Ported to UNIX. * * Revision 1.6 91/09/01 17:31:07 ROOT_DOS * Fixed bug in lst_deletenext(). * * Revision 1.5 91/09/01 17:17:37 ROOT_DOS * Changed lst_deletenext() to return a pointer to the deleted node's * userspace. * * Revision 1.4 91/09/01 16:04:09 ROOT_DOS * Minor cosmetic change * * Revision 1.3 91/09/01 01:49:59 ROOT_DOS * Changed search for include files to search the current directory. * * Added function lst_kill() to delete the nodes in the list, calling a user * supplied function to kill each node. * * Revision 1.2 91/08/21 14:32:02 ROOT_DOS * Optimized the mergesort routine by eliminating passing the end of the * merged list found in merge(), back to the main mergesort() routine. This * eliminated the need to traverse the newly merged list to find the end. * Gives about 10% speed improvement for moderate size lists. * * Revision 1.1 91/08/21 14:10:39 ROOT_DOS * Initial revision * ****************************************************************************/ #include <stdio.h> #include <malloc.h> #include <signal.h> #include "debug.h" #include "list.h" PUBLIC void *lst_newnode(int size) /**************************************************************************** * * Function: lst_newnode * Parameters: size - Amount of memory to allocate for node * Returns: Pointer to the allocated node's user space. * * Description: Allocates the memory required for a node, adding a small * header at the start of the node. We return a reference to * the user space of the node, as if it had been allocated via * malloc(). * ****************************************************************************/ { LST_BUCKET *node; if ( !(node = (LST_BUCKET*)malloc(size + sizeof(LST_BUCKET))) ) { fprintf(stderr,"Not enough memory to allocate list node.\n"); raise(SIGABRT); return NULL; } return LST_USERSPACE(node); /* Return pointer to user space */ } PUBLIC void lst_freenode(void *node) /**************************************************************************** * * Function: lst_freenode * Parameters: node - Node to free. * * Description: Frees a node previously allocated with lst_newnode(). * ****************************************************************************/ { free(LST_HEADER(node)); } PUBLIC LIST *lst_init(void) /**************************************************************************** * * Function: lst_init * Returns: Pointer to a newly created list. * * Description: Initialises a list and returns a pointer to it. * ****************************************************************************/ { LIST *l; if ((l = (LIST*)malloc(sizeof(LIST))) != NULL) { l->count = 0; l->head = &(l->hz[0]); l->z = &(l->hz[1]); l->head->next = l->z->next = l->z; } else { fprintf(stderr,"Insufficient memory to allocate list\n"); raise(SIGABRT); return NULL; } return l; } PUBLIC void lst_kill(LIST *l,void (*freeNode)(void *node)) /**************************************************************************** * * Function: lst_kill * Parameters: l - List to kill * freeNode - Pointer to user routine to free a node * * Description: Kills the list l, by deleting all of the elements contained * within the list one by one and then deleting the list * itself. Note that we call the user supplied routine * (*freeNode)() to free each list node. This allows the user * program to perform any extra processing needed to kill each * node (if each node contains pointers to other items on the * heap for example). If no extra processing is required, just * pass the address of lst_freenode(), ie: * * lst_kill(myList,lst_freenode); * ****************************************************************************/ { LST_BUCKET *n,*p; n = l->head->next; while (n != l->z) { /* Free all nodes in list */ p = n; n = n->next; (*freeNode)(LST_USERSPACE(p)); } free(l); /* Free the list itself */ } PUBLIC void lst_insertafter(LIST *l,void *node,void *after) /**************************************************************************** * * Function: lst_insertafter * Parameters: l - List to insert node into * node - Pointer to user space of node to insert * after - Pointer to user space of node to insert node after * * Description: Inserts a new node into the list after the node 'after'. To * insert a new node at the beginning of the list, user the * macro LST_HEAD in place of 'after'. ie: * * lst_insertafter(mylist,node,LST_HEAD(mylist)); * ****************************************************************************/ { LST_BUCKET *n = LST_HEADER(node),*a = LST_HEADER(after); n->next = a->next; a->next = n; l->count++; } PUBLIC void *lst_deletenext(LIST *l,void *node) /**************************************************************************** * * Function: lst_deletenext * Parameters: l - List to delete node from. * node - Node to delete the next node from * Returns: Pointer to the deleted node's userspace. * * Description: Removes the node AFTER 'node' from the list l. * ****************************************************************************/ { LST_BUCKET *n = LST_HEADER(node); node = LST_USERSPACE(n->next); n->next = n->next->next; l->count--; return node; } PUBLIC void *lst_first(LIST *l) /**************************************************************************** * * Function: lst_first * Parameters: l - List to obtain first node from * Returns: Pointer to first node in list, NULL if list is empty. * * Description: Returns a pointer to the user space of the first node in * the list. If the list is empty, we return NULL. * ****************************************************************************/ { LST_BUCKET *n; n = l->head->next; return (n == l->z ? NULL : LST_USERSPACE(n)); } PUBLIC void *lst_next(void *prev) /**************************************************************************** * * Function: lst_next * Parameters: prev - Previous node in list to obtain next node from * Returns: Pointer to the next node in the list, NULL at end of list. * * Description: Returns a pointer to the user space of the next node in the * list given a pointer to the user space of the previous node. * If we have reached the end of the list, we return NULL. The * end of the list is detected when the next pointer of a node * points back to itself, as does the dummy last node's next * pointer. This enables us to detect the end of the list * without needed access to the list data structure itself. * * NOTE: We do no checking to ensure that 'prev' is NOT a * NULL pointer. * ****************************************************************************/ { LST_BUCKET *n = LST_HEADER(prev); n = n->next; return (n == n->next ? NULL : LST_USERSPACE(n)); } /* Static globals required by merge() */ static LST_BUCKET *z; static int (*cmp)(void*,void*); PRIVATE LST_BUCKET *merge(LST_BUCKET *a,LST_BUCKET *b,LST_BUCKET **end) /**************************************************************************** * * Function: merge * Parameters: a,b - Sublist's to merge * Returns: Pointer to the merged sublists. * * Description: Merges two sorted lists of nodes together into a single * sorted list. * ****************************************************************************/ { LST_BUCKET *c; /* Go through the lists, merging them together in sorted order */ c = z; while (a != z && b != z) { if ((*cmp)(LST_USERSPACE(a),LST_USERSPACE(b)) <= 0) { c->next = a; c = a; a = a->next; } else { c->next = b; c = b; b = b->next; } }; /* If one of the lists is not exhausted, then re-attach it to the end * of the newly merged list */ if (a != z) c->next = a; if (b != z) c->next = b; /* Set *end to point to the end of the newly merged list */ while (c->next != z) c = c->next; *end = c; /* Determine the start of the merged lists, and reset z to point to * itself */ c = z->next; z->next = z; return c; } PUBLIC void lst_mergesort(LIST *l,int (*cmp_func)(void*,void*)) /**************************************************************************** * * Function: lst_mergesort * Parameters: l - List to merge sort * cmp_func - Function to compare two user spaces * * Description: Mergesort's all the nodes in the list. 'cmp' must point to * a comparison function that can compare the user spaces of * two different nodes. 'cmp' should work the same as * strcmp(), in terms of the values it returns. * ****************************************************************************/ { int i,N; LST_BUCKET *a,*b; /* Pointers to sublists to merge */ LST_BUCKET *c; /* Pointer to end of sorted sublists */ LST_BUCKET *head; /* Pointer to dummy head node for list */ LST_BUCKET *todo; /* Pointer to sublists yet to be sorted */ LST_BUCKET *t; /* Temporary */ /* Set up globals required by merge() and pointer to head */ z = l->z; cmp = cmp_func; head = l->head; for (N = 1,a = z; a != head->next; N = N + N) { todo = head->next; c = head; while (todo != z) { /* Build first sublist to be merged, and splice from main list */ a = t = todo; for (i = 1; i < N; i++) t = t->next; b = t->next; t->next = z; t = b; /* Build second sublist to be merged and splice from main list */ for (i = 1; i < N; i++) t = t->next; todo = t->next; t->next = z; /* Merge the two sublists created, and set 'c' to point to the * end of the newly merged sublists. */ c->next = merge(a,b,&t); c = t; } } }
