home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1990 / 12 / williams.asc < prev   
Text File  |  1990-11-15  |  6KB  |  159 lines
  1. _SUPERCHARGING SEQUENTIAL SEARCHES_
  2. by Walter Williams
  3.  
  4. [LISTING ONE]
  5.  
  6. /***********************************************************************
  7.  * SS.C -- Sample Sorted Sequential Suffix Search (c) 1989 Walter Williams
  8.  ***********************************************************************/
  9.  
  10. #include <stdio.h>
  11. #include <string.h>
  12. #include <malloc.h>
  13.  
  14. #ifndef TRUE
  15. #define TRUE    1
  16. #define FALSE   0
  17. #endif
  18.  
  19. typedef struct snode_S
  20.     {
  21.     struct snode_S *prev;   /* Address of previous node in list     */
  22.     struct snode_S *next;   /* Address of next node in list         */
  23.     unsigned int pfxlen;    /* Number of characters in prefix       */
  24.     char key[1];            /* First character of key               */
  25.     } snode_T, *snode_TP;
  26.  
  27. /************************ Function Prototypes ***************************/
  28. snode_TP Search(char *, snode_TP, int *, unsigned int *);
  29. snode_TP Insert(char *, snode_TP);
  30. snode_TP Delete(char *, snode_TP);
  31.  
  32. /*----------------------------------------------------------------------*/
  33. /* SEARCH() -- Search the list for a pattern key.                       */
  34. /* 'pattern' is a null terminated string containing the key which is    */
  35. /*           the object of the search.                                  */
  36. /* 'list' is the address of a dummy node which contains head and tail   */
  37. /*           pointers for a linked list.                                */
  38. /* 'exact' is the address of a flag which is TRUE for an exact match    */
  39. /*           and FALSE if the pattern is not found.                     */
  40. /* 'match' is the address of an unsigned int to use as a match counter  */
  41. /* The return value is a pointer to the structure containing the        */
  42. /* matching key, or the next largest node if the pattern was not found. */
  43. /*----------------------------------------------------------------------*/
  44.  
  45. snode_TP Search(char *pattern, snode_TP list, int *exact, unsigned int *match)
  46.     {
  47.     snode_TP cnode;     /* Pointer to current node              */
  48.     char *sp;           /* Suffix pointer                       */
  49.     int tm= 0;          /* Temp storage for match count         */
  50.     /***/
  51.     *exact= FALSE;                      /* Assume unsuccessful search   */
  52.     *match= tm;
  53.     for (cnode= list->next;  cnode != list;  cnode= cnode->next)
  54.         {
  55.                                 /* Compare match count to prefix count  */
  56.         if (tm < cnode->pfxlen)
  57.             continue;
  58.         else if (tm > cnode->pfxlen)
  59.             break;
  60.         else /* (tm == cnode->pfxcnt) */
  61.             {
  62.                  /* Compare the actual key suffix, maintain match count */
  63.             sp= cnode->key + cnode->pfxlen;
  64.             while (*pattern == *sp && *sp && *pattern)
  65.                 {
  66.                 ++sp;
  67.                 ++pattern;
  68.                 ++tm;
  69.                 }
  70.                     /* Done if suffix greater than or equal to pattern  */
  71.             if (*pattern < *sp )
  72.                 {
  73.                 break;
  74.                 }
  75.             else if (*pattern == '\0' && *sp == '\0')
  76.                 {
  77.                 *match= tm;
  78.                 *exact= TRUE;
  79.                 break;
  80.                 }
  81.             }
  82.         *match= tm;
  83.         }
  84.     return (cnode);
  85.     }
  86.  
  87. /*--- INSERT() Adds an item to the list.  ---*/
  88. snode_TP Insert(char *pattern, snode_TP list)
  89.     {
  90.     snode_TP cnode;         /* Node we are inserting                    */
  91.     snode_TP nnode;         /* Next node after cnode                    */
  92.     char *sp;               /* Pointer to suffix                        */
  93.     unsigned int match;
  94.     int exact;
  95.     /***/
  96.                                 /* Find spot where we insert the node   */
  97.     nnode = Search(pattern, list, &exact, &match);
  98.     if (exact == TRUE)          /* Skip to first non-matching key       */
  99.         {
  100.         nnode = nnode->next;
  101.         while (nnode != list && nnode->key[nnode->pfxlen] == '\0')
  102.             nnode = nnode->next;
  103.         }
  104.                                 /* Allocate space for the new node      */
  105.     cnode = (snode_TP) malloc(sizeof(snode_T) + strlen(pattern));
  106.     cnode->pfxlen = match;
  107.     strcpy(cnode->key, pattern);
  108.                                 /* Link it into the list ahead of nnode */
  109.     cnode->next = nnode;
  110.     cnode->prev = nnode->prev;
  111.     nnode->prev->next = cnode;
  112.     nnode->prev = cnode;
  113.                                 /* Update pfxlen in following node      */
  114.     sp = nnode->key + nnode->pfxlen;
  115.     if (cnode->pfxlen == nnode->pfxlen)
  116.         {                       /* Compare the two suffixes             */
  117.         nnode->pfxlen= 0;
  118.         while (*sp == *pattern && *pattern && *sp)
  119.             {
  120.             ++sp;
  121.             ++pattern;
  122.             ++nnode->pfxlen;
  123.             }
  124.         }
  125.     return (cnode);
  126.     }
  127.  
  128. /*--- DELETE() Deletes an item from the list ---*/
  129. snode_TP Delete(char *pattern, snode_TP list)
  130.     {
  131.     snode_TP cnode;         /* Node we are deleting                     */
  132.     snode_TP nnode;         /* Next node after cnode                    */
  133.     int exact;              /* Flag set if exact match                  */
  134.     unsigned int match;     /* No. of characters matched in pattern     */
  135.     /***/
  136.                             /* Find the node we want to delete          */
  137.     cnode = Search(pattern, list, &exact, &match);
  138.     if (exact == FALSE)     /* Abort if not an exact match              */
  139.         {
  140.         printf("%s not found\n", pattern);
  141.         nnode= NULL;
  142.         }
  143.     else
  144.         {                   /* Remove it from the list                  */
  145.         cnode->next->prev = cnode->prev;
  146.         cnode->prev->next = cnode->next;
  147.         nnode = cnode->next;/* Save for return value                    */
  148.                             /* Update suffix in following node          */
  149.         if (cnode->pfxlen < cnode->next->pfxlen)
  150.             cnode->next->pfxlen = cnode->pfxlen;
  151.                             /* Release deleted node                     */
  152.         free((char *) cnode);
  153.         printf("%s deleted\n", pattern);
  154.         }
  155.     return (nnode);
  156.     }
  157.  
  158.  
  159.