Thread: Following CTools

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    6

    Following CTools

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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Look at lst_newnode. You have to pass that function the size of whatever you want to store; it goes and gets the memory, does the paperwork to put it in the list, and returns you the pointer to the memory you asked for. That's where you stuff your data.

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    6

    Thumbs down

    ok. possibly this is a bad noobish example? 'caus I understand very little of that function. let me see if I can get through it.

    Code:
    PUBLIC void *lst_newnode(int size)
    PUBLIC: this appears to be an ansi C thing because while I know it in java. I've never seen it inC
    void: so in otherwords returning void doesn't always mean returning nothing? sometimes you can return an untyped,must be casted pointer?


    Code:
    if ( !(node = (LST_BUCKET*)malloc(size + sizeof(LST_BUCKET))) )
    this appears to be if the allocation for the new node is not the same size as a typical node, bail out

    Code:
    raise(SIGABRT);
    abort the current process.. no clue how I personally would deduce that that needs to go there, but I get it kinda.


    Code:
    return NULL;
    gotcha


    Code:
    return LST_USERSPACE(node);			/* Return pointer to user space */
    ok so this function returns an untyped pointer.




    Code:
    PUBLIC void *lst_newnode(int size)
    
    {
    
    	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 */
    
    }

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by EstateMatt View Post
    ok. possibly this is a bad noobish example? 'caus I understand very little of that function. let me see if I can get through it.

    Code:
    PUBLIC void *lst_newnode(int size)
    PUBLIC: this appears to be an ansi C thing because while I know it in java. I've never seen it inC
    The all caps means that what's-his-name that wrote it made it up. Presumably there's a #define in the common header that says what this means.

    void: so in otherwords returning void doesn't always mean returning nothing? sometimes you can return an untyped,must be casted pointer?
    Read it again: the return type is void * -- which as you noticed is a "pointer to anything". And "must be casted" is misleading -- a void * can be translated invisibly into any kind of pointer you want (if foo is an int *, and bar is a void *, you can do foo=bar no problem); however, to dereference it, you do have to say what kind of pointer it is. (Otherwise the system won't know how much memory to get, and what to do with it once it has it.)

    Code:
    if ( !(node = (LST_BUCKET*)malloc(size + sizeof(LST_BUCKET))) )
    this appears to be if the allocation for the new node is not the same size as a typical node, bail out
    Not exactly. There's no size checking here; malloc asks for an amount of memory equal to the amount the user wants (size) plus the amount necessary for the paperwork (sizeof(LST_BUCKET)). If it doesn't get anything at all, then bail out.

    Code:
    raise(SIGABRT);
    abort the current process.. no clue how I personally would deduce that that needs to go there, but I get it kinda.
    Well, what else are you going to do? What's-his-name decided that there's nothing better to do than die horribly, so that's what we do.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    PUBLIC is a macro that probably expands to nothing - whilst PRIVATE or NONPUBLIC would expand to static (which means that code outside of the source is not able to link to that function).

    Code:
    if ( !(node = (LST_BUCKET*)malloc(size + sizeof(LST_BUCKET))) )
    If we didn't get the memory (node == NULL) then bail out - we CAN NOT continue here if we can't allocate memory.

    It is obviously a decision that depends on the type of application and several other circumstances, whether you for example just return NULL or abort the application (or for that matter, do something different). In small applications, I usually write a "bailout" function that takes a string as parameter, and does "exit(1)" after printing the string. Sometimes it's better to leave the decision whether to quit/continue to some other part of the code, which can for example tell the user in a better way that we couldn't store the data - maybe there is some other app that can be shut down to free some memory, for example?

    Yes, it's a void *, so it's returning a "pointer to anything and nothing" in the sense that it can point to anything, but you can't access that pointer until you turn it into something else.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Jun 2008
    Posts
    6
    thank you so much guys. that's extremely extremely helpful. Obviously (to you) this void = pointer to anything thing makes code for datastructres infinitely more reusable so it's very important

Popular pages Recent additions subscribe to a feed