Name

sll_add_item, sll_add_item_reverse, sll_collapse, sll_count, sll_get, sll_get2, sll_gets, sll_index, sll_index2, sll_inds, sll_inds2, sll_make, sll_rmlist, sll_rmlist2, sll_rm_item, sll_sort sll_sort_strkey

Synopsis

     #include 
     #include "sll.h"

     cc file.c -lsll

Description

The libsll.a library provides functions to store and retrieve elements in a singly linked list, in memory. They keys and data may be anything, though the default data types are strings.

Data Structure

The singly linked list is terminated with next == NULL. The list lives in malloc'ed space. It is assumed that key and datum live in malloc'ed space. sll_rmlist() requires this behavior.

struct sll {
    struct sll *next;		/* Next in list. */
    void *key;			/* Cast it to a real type. */
    void *datum;		/* Cast it to a real type. */
};

Routines

Add an item to the end of the list, preserving order. Returns NULL if not passed a list, or out of RAM. This function requires time proportional to the length of the list.

struct sll *sll_add_item_reverse(struct sll **sllt, void *key, void *dat);

Add an item (quickly) to the begining of the list, reversing order. Parameters, key and dat may be NULL. This function inserts items in constant time.

struct sll *sll_collapse(struct sll *twod);

Collapse a two dimensional list to a one dimensional list. The first two columns are put into key and datum of the new list. The entries must be strings (since the values must be duplicated, and the size is otherwise not known). The first row of the two dimensional list is ignored, as it is likely the header row from a select. See cgi_iselect(), cgi_osql() and cgi_psql() For example:

struct sll *sp, *np;
sp = cgi_psql("select name, id from names where name like '%smith';");
np = sll_collapse(sp);
cgi_iselect("Names", np);

Count the entries in a list. This function requires time proportional to the length of the list.

struct sll *sll_get(struct sll **sllt, const void *key, int (*compar) (const void *, const void *));

Find an entry. If compar is NULL, then the keys are assumed to be C style null terminated strings. This function requires time proportional to the length of the list.

char *sll_gets(struct sll *sllp, const char *key);

Find an entry. Keys and datum must be C style strings. This function requires time proportional to the length of the list.

struct sll *sll_get2(struct sll *sllt, int col, const void *key, int (*compar)(const void *, const void *));

Find an entry in a 2-D array in the key field of given column. Return the whole 1-D list where found. If compar is NULL, use strcmp.

struct sll *sll_index(struct sll *sllt, int n);

Return the nth entry in a list. This is similar to indexing into a single dimensioned array. NULL is returned if there is an error. This function requires time proportional to the length of the list.

struct sll *sll_index2(struct sll *sllt, int n, int m);

Get an entry in a list of lists by indicies. This is essentially a two dimensional array. Return the mth entry into the nth list. The outside list, indexed by n has the inside list in the key field. NULL is returned if there is an error. This function requires time proportional to the length of the lists.

char *sll_inds(const struct sll *sllt, int n);

Return the nth entry in a list. This is similar to indexing into a single dimensioned array. The key field is returned, and is expected to be a char * (string). NULL is returned if there is an error. This routine is a convenience for lists generated by cgi_osql, for when you are operating on a single row. This function requires time proportional to the length of the list.

struct sll *sll_inds2(const struct sll *sllt, int n, int m);

Get an entry in a list of lists by indicies. This is essentially a two dimensional array. Return the mth entry into the nth list. The outside list, indexed by n has the inside list in the key field. The key field is returned, and is expected to be a char * (string). NULL is returned if there is an error. This routine is a convenience for lists generated by cgi_osql. This function requires time proportional to the length of the lists.

struct sll *sll_make(void);

Create a new, blank sll node. Return NULL if out of RAM. This function creates an entry in constant time.

void sll_rmlist(struct sll *sllp);

Delete a sll list, recursively. All key and datum elements are assumed to be pointers to space allocated by malloc(3). However, if the element contains sub elements, such as other lists, the space allocated by the sub elements should be free'ed first. This routine requires time proportional to the length of the list.

void sll_rmlist2(struct sll *sllp);

Delete a sll list, recursively. The list is assumed to be a list of lists. If a key is not NULL, it is assumed to be an sll list, and it is deleted entirely. All datum elements are assumed to be pointers to space allocated by malloc(3). This routine requires time proportional to the length of the list(s).

int sll_rm_item(struct sll **sllt, void *key, int (*compar) (const void *, const void *));

Delete one element of a list. Returns TRUE for good, FALSE for error (element not found). If compar is NULL, then the keys are assumed to be C style null terminated strings. All key and datum elements are assumed to be pointers to space allocated by malloc(3). However, if the element contains sub elements, such as other lists, the space allocated by the sub elements should be free'ed first. This routine requires time proportional to the length of the list.

struct sll *sll_sort(struct sll **sllt, int (*compar) (const void *, const void *));

This function is not yet implemented. Sort a list. If the list cannot be sorted, the list is unchanged. If compar is NULL, then the keys are assumed to be C style null terminated strings. This routine requires time proportional to the logarithm of the length of the list.

struct sll *sll_sort_strkey(struct sll **sllt);

Sort a list. If the list cannot be sorted, the list is unchanged. The keys must be strings. This routine requires time proportional to the logarithm of the length of the list.

Example

Typically, you have a list with a static anchor.

int compare(mykey *key, mykey *key2) { return key2 - key1; }
static struct sll *my_list = NULL;
my_list = sll_make();                   /* Create the list. */
sll_additem(&my_list, my_key, my_datum); /* Add an item. */
my_item = sll_finditem(&my_list, compare, my_key); /* Find an item. */
sll_rmlist(my_list);                    /* Done with list. */
my_list = NULL;

Diagnostics

Routines that return pointers return NULL if an error is encountered.

Files

/usr/local/lib/libsll.a
/usr/local/include/sll.h

See Also

strings(3), libccgi

Author

Bugs

sll_get should take a simple sll pointer, rather than a double pointer. Compatibility prevents this.

sll_rmlist should take an indirect sll pointer, rather than a simple pointer. It should set the head of the list to NULL. Compatibility prevents this.

A function to remove multiple dimensioned lists should be written.