_SUPERCHARGING SEQUENTIAL SEARCHES_
by Walter Williams

[LISTING ONE]

/***********************************************************************
 * SS.C -- Sample Sorted Sequential Suffix Search (c) 1989 Walter Williams
 ***********************************************************************/

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#ifndef TRUE
#define TRUE    1
#define FALSE   0
#endif

typedef struct snode_S
    {
    struct snode_S *prev;   /* Address of previous node in list     */
    struct snode_S *next;   /* Address of next node in list         */
    unsigned int pfxlen;    /* Number of characters in prefix       */
    char key[1];            /* First character of key               */
    } snode_T, *snode_TP;

/************************ Function Prototypes ***************************/
snode_TP Search(char *, snode_TP, int *, unsigned int *);
snode_TP Insert(char *, snode_TP);
snode_TP Delete(char *, snode_TP);

/*----------------------------------------------------------------------*/
/* SEARCH() -- Search the list for a pattern key.                       */
/* 'pattern' is a null terminated string containing the key which is    */
/*           the object of the search.                                  */
/* 'list' is the address of a dummy node which contains head and tail   */
/*           pointers for a linked list.                                */
/* 'exact' is the address of a flag which is TRUE for an exact match    */
/*           and FALSE if the pattern is not found.                     */
/* 'match' is the address of an unsigned int to use as a match counter  */
/* The return value is a pointer to the structure containing the        */
/* matching key, or the next largest node if the pattern was not found. */
/*----------------------------------------------------------------------*/

snode_TP Search(char *pattern, snode_TP list, int *exact, unsigned int *match)
    {
    snode_TP cnode;     /* Pointer to current node              */
    char *sp;           /* Suffix pointer                       */
    int tm= 0;          /* Temp storage for match count         */
    /***/
    *exact= FALSE;                      /* Assume unsuccessful search   */
    *match= tm;
    for (cnode= list->next;  cnode != list;  cnode= cnode->next)
        {
                                /* Compare match count to prefix count  */
        if (tm < cnode->pfxlen)
            continue;
        else if (tm > cnode->pfxlen)
            break;
        else /* (tm == cnode->pfxcnt) */
            {
                 /* Compare the actual key suffix, maintain match count */
            sp= cnode->key + cnode->pfxlen;
            while (*pattern == *sp && *sp && *pattern)
                {
                ++sp;
                ++pattern;
                ++tm;
                }
                    /* Done if suffix greater than or equal to pattern  */
            if (*pattern < *sp )
                {
                break;
                }
            else if (*pattern == '\0' && *sp == '\0')
                {
                *match= tm;
                *exact= TRUE;
                break;
                }
            }
        *match= tm;
        }
    return (cnode);
    }

/*--- INSERT() Adds an item to the list.  ---*/
snode_TP Insert(char *pattern, snode_TP list)
    {
    snode_TP cnode;         /* Node we are inserting                    */
    snode_TP nnode;         /* Next node after cnode                    */
    char *sp;               /* Pointer to suffix                        */
    unsigned int match;
    int exact;
    /***/
                                /* Find spot where we insert the node   */
    nnode = Search(pattern, list, &exact, &match);
    if (exact == TRUE)          /* Skip to first non-matching key       */
        {
        nnode = nnode->next;
        while (nnode != list && nnode->key[nnode->pfxlen] == '\0')
            nnode = nnode->next;
        }
                                /* Allocate space for the new node      */
    cnode = (snode_TP) malloc(sizeof(snode_T) + strlen(pattern));
    cnode->pfxlen = match;
    strcpy(cnode->key, pattern);
                                /* Link it into the list ahead of nnode */
    cnode->next = nnode;
    cnode->prev = nnode->prev;
    nnode->prev->next = cnode;
    nnode->prev = cnode;
                                /* Update pfxlen in following node      */
    sp = nnode->key + nnode->pfxlen;
    if (cnode->pfxlen == nnode->pfxlen)
        {                       /* Compare the two suffixes             */
        nnode->pfxlen= 0;
        while (*sp == *pattern && *pattern && *sp)
            {
            ++sp;
            ++pattern;
            ++nnode->pfxlen;
            }
        }
    return (cnode);
    }

/*--- DELETE() Deletes an item from the list ---*/
snode_TP Delete(char *pattern, snode_TP list)
    {
    snode_TP cnode;         /* Node we are deleting                     */
    snode_TP nnode;         /* Next node after cnode                    */
    int exact;              /* Flag set if exact match                  */
    unsigned int match;     /* No. of characters matched in pattern     */
    /***/
                            /* Find the node we want to delete          */
    cnode = Search(pattern, list, &exact, &match);
    if (exact == FALSE)     /* Abort if not an exact match              */
        {
        printf("%s not found\n", pattern);
        nnode= NULL;
        }
    else
        {                   /* Remove it from the list                  */
        cnode->next->prev = cnode->prev;
        cnode->prev->next = cnode->next;
        nnode = cnode->next;/* Save for return value                    */
                            /* Update suffix in following node          */
        if (cnode->pfxlen < cnode->next->pfxlen)
            cnode->next->pfxlen = cnode->pfxlen;
                            /* Release deleted node                     */
        free((char *) cnode);
        printf("%s deleted\n", pattern);
        }
    return (nnode);
    }