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;
}
}
}
