home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume26 / tripwire / part03 / tripwire-1.0 / src / list.c
C/C++ Source or Header  |  1993-04-19  |  17KB  |  759 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Id: list.c,v 1.3 92/11/03 04:49:45 genek Exp $";
  3. #endif
  4.  
  5. /*
  6.  * list.c
  7.  *
  8.  *    generic linked list routines.
  9.  *
  10.  *    These routines generally use a (struct list **) as an argument
  11.  *    (ie: a pointer to a pointer to the head of the list).  This way,
  12.  *    a NULL list pointer will automatically be malloc()'d into existence.
  13.  *
  14.  *    These routines started as extremely simple routines.  Unfortunately, the
  15.  *    O(n) search times made Tripwire extremely slow.  So, v3.1 of
  16.  *    the linked list routines incorporate a hash table into each of
  17.  *    the list structures.  *whew*  It's faster, but it's not simple
  18.  *    anymore.  (The addition of back pointers didn't help either...)
  19.  *
  20.  *    Why?  Well, we need to preserve order for the list of generated files.
  21.  *    So, a hash table won't do, and a simple linked list is too slow.
  22.  *
  23.  *    However, the neat thing is that the object-oriented nature of
  24.  *    the list routines is preserved.
  25.  *
  26.  * Gene Kim
  27.  * Purdue University
  28.  */
  29.  
  30. #include "../include/config.h"
  31. #include <stdio.h>
  32. #ifdef STDLIBH
  33. #include <stdlib.h>
  34. #endif
  35. #include <assert.h>
  36. #ifdef MALLOCH
  37. # include <malloc.h>
  38. #endif
  39. #ifdef STRINGH
  40. #include <string.h>
  41. #else
  42. #include <strings.h>
  43. #endif
  44. #include "../include/list.h"
  45.  
  46. /* prototypes */
  47. static unsigned int string_hash ();
  48.  
  49. static int listdebug = 0;
  50.  
  51. #define LISTDEBUG(x) if (listdebug >= (x))
  52.  
  53. /*
  54.  * list_set(pc_name, pc_value, prioirty, pp_list)
  55.  *
  56.  *    insert structure with (name=pc_name) and (value=pc_value)
  57.  *    into the specified list
  58.  */
  59.  
  60. void
  61. list_set(pc_name, pc_value, priority, pp_list)
  62.     int priority;
  63.     char *pc_name, *pc_value;
  64.     struct list **pp_list;
  65. {
  66.     struct list_elem *p;
  67.     struct list_hash *phash, *qhash;
  68.     int    clobber = 0;
  69.     struct list_elem *head;
  70.     unsigned int hindex;            /* hash index */
  71.     struct list_hash *hentry;
  72.  
  73.     /* get the hash value */
  74.     hindex = string_hash(pc_name);
  75.  
  76.     /* were we handed a NULL list pointer? */
  77.     if (*pp_list == NULL)
  78.     goto INSERT;
  79.     else
  80.     head = (*pp_list)->p_head;
  81.  
  82.     hentry = &( ((*pp_list)->hashtable)[hindex]);
  83.  
  84.     /*
  85.      * 1) if pc_name is already in the list, then we compare priority
  86.      *        levels.  replace only if new priority is higher than
  87.      *        existing priority.
  88.      *
  89.      * 2) if pc_name is not on the list, then we just add it to the
  90.      *        end of the list
  91.      */
  92.  
  93.     /* walk through hash chain */
  94.     for (phash = hentry; phash && phash->used; qhash = phash,
  95.                             phash = phash->next) {
  96.     if (strcmp(phash->key, pc_name) == 0) {
  97.         /*
  98.          * if existing priority is equal or less than this one,
  99.          * then go ahead and clobber it.
  100.          */
  101.         p = phash->lptr;
  102.         if (p->priority <= priority) {
  103.  
  104. LISTDEBUG(10)
  105. fprintf(stderr, "list_set(): '%s' variable already found.  Clobbering...\n",
  106.                 pc_name);
  107.  
  108.         clobber++;
  109.         goto INSERT;
  110.         }                /* end if clobber */
  111.         else {
  112.  
  113. LISTDEBUG(10)
  114. fprintf(stderr, "list_set(): variable already found, but not clobbering...\n");
  115.     
  116.         return;
  117.         }                /* end if not clobber */
  118.     }
  119.     }
  120.     /* back up one if we're not at head of chain */
  121.     if (phash == (struct list_hash *) NULL)
  122.     phash = qhash;
  123.  
  124. INSERT:
  125.     /* insert the element into the list */
  126.  
  127.     /*         do we first need to create the list object? */
  128.     if (*pp_list == NULL) {
  129.  
  130.     int i;
  131.     struct list *pl;
  132.  
  133.     /* create the list structure pointer */
  134.     if ((pl = *pp_list = (struct list *) malloc(sizeof(struct list)))
  135.                     == NULL) {
  136.         fprintf(stderr, "list_insert(): malloc() failed!\n");
  137.         exit(1);
  138.     }
  139.  
  140.     /* create the pointers inside the structure */
  141.     if ((p = (struct list_elem *) malloc(sizeof(struct list_elem)))
  142.                     == NULL) {
  143.         fprintf(stderr, "list_insert(): malloc() failed!\n");
  144.         exit(1);
  145.     }
  146.     /* cauterize the prev pointer */
  147.     p->prev = NULL;
  148.     p->varname = NULL;
  149.  
  150.     /* attach to list structure */
  151.     pl->p_head = head = pl->p_tail = p;
  152.     head->next = NULL;
  153.  
  154.     /* initialize the hash table */
  155.     for (i = 0; i < LIST_HASHSZ; i++) {
  156.         hentry = &( ((*pp_list)->hashtable)[i]);
  157.         hentry->key = (char *) NULL;
  158.         hentry->used = 0;
  159.         hentry->lptr = (struct list_elem *) NULL;
  160.         hentry->next = (struct list_hash *) NULL;
  161.     }
  162.  
  163.     /* get correct hash bucket */
  164.     hentry = &( ((*pp_list)->hashtable)[hindex]);
  165.     }
  166.     else if (clobber) {
  167.         free(p->varname);
  168.         free(p->varvalue);
  169.     }
  170.     else
  171.     {
  172.     /* add a list entry at tail of list */
  173.     p = (*pp_list)->p_tail;
  174.  
  175.     if ((p->next = (struct list_elem *)
  176.                 malloc(sizeof(struct list_elem))) == NULL) {
  177.  
  178.         fprintf(stderr, "list_insert(): malloc() failed!\n");
  179.         exit(1);
  180.     }
  181.  
  182.     /* attach the prev pointer */
  183.     p->next->prev = p;
  184.  
  185.     /* now the rest */
  186.     p = p->next;
  187.     p->next = NULL;
  188.  
  189.     /* bind to tail */
  190.     (*pp_list)->p_tail = p;
  191.  
  192.     if (phash->used) {
  193.         /* now create the hash chain entry */
  194.         /*    do we need a new structure to chain on? */
  195.         if ((qhash = (struct list_hash *) malloc(sizeof(struct list_hash)))
  196.                     == NULL) {
  197.         fprintf(stderr, "list_insert(): malloc() failed!\n");
  198.         exit(1);
  199.         }
  200.         qhash->used = 0;
  201.         qhash->next = NULL;
  202.  
  203.         phash->next = qhash;
  204.         hentry = phash = qhash;
  205.     }
  206.     }
  207.  
  208.     /* start filling in fields */
  209.     if ((p->varname = (char *) malloc((unsigned) (strlen(pc_name) + 1)))
  210.                 == NULL) {
  211.     fprintf(stderr, "list_insert(): malloc() failed!\n");
  212.     exit(1);
  213.     }
  214.     (void) strcpy(p->varname, pc_name);
  215.     if ((p->varvalue = (char *) malloc((unsigned) (strlen(pc_value) + 1)))
  216.                 == NULL) {
  217.     fprintf(stderr, "list_insert(): malloc() failed!\n");
  218.     exit(1);
  219.     }
  220.     (void) strcpy(p->varvalue, pc_value);
  221.     p->flag = 0;
  222.     p->priority = 0;
  223.  
  224.     /* fill in hash chain structure */
  225.     hentry->key = p->varname;
  226.     if (hentry->used == 0)
  227.     hentry->used++;
  228.     assert(hentry->used == 1);
  229.     hentry->lptr = p;
  230.     hentry->next = NULL;
  231.  
  232.     return;
  233.  
  234. }
  235.  
  236. /*
  237.  * char *
  238.  * list_lookup(pc_name, pp_list)
  239.  *
  240.  *    return the string value assigned to the environment value named
  241.  *    pc_name in the specified list.
  242.  *
  243.  *    you must copy the contents of the (char *).
  244.  */
  245.  
  246. char *
  247. list_lookup(pc_name, pp_list)
  248.     char *pc_name;
  249.     struct list **pp_list;
  250. {
  251.     struct list_elem *p;
  252.     struct list_hash *phash;
  253.     char    *s;
  254.     unsigned int hindex;
  255.     struct list_hash *hentry;
  256.  
  257.     /*
  258.      * 1) if *pp_list is NULL, then we know it's emtpy
  259.      * 2) if it's not in the hash table, then return NULL
  260.      * 3) search hash table chain
  261.      */
  262.  
  263.     /* check for empty list */
  264.     if (*pp_list == NULL) {
  265.     return NULL;
  266.     }
  267.  
  268.     /* look in hash table */
  269.     hindex = string_hash(pc_name);
  270.     hentry = &(((*pp_list)->hashtable)[hindex]);
  271.  
  272.     if (hentry->used == 0) {
  273.     return NULL;
  274.     }
  275.  
  276.     /* now search through hash chain */
  277.     for (phash = hentry; phash; phash = phash->next) {
  278.     if (strcmp(phash->key, pc_name) == 0) {
  279.         p = phash->lptr;
  280.         /*
  281.         s = (char *) malloc((unsigned) (strlen(p->varvalue) + 1));
  282.         (void) strcpy(s, p->varvalue);
  283.         */
  284.         s = p->varvalue;
  285.         return s;
  286.     }
  287.     }
  288.     return NULL;
  289. }
  290.  
  291. /*
  292.  * int
  293.  * list_isthere(pc_name, pp_list)
  294.  *
  295.  *    returns (1) if pc_name is in the specified list.
  296.  *    else returns (0).
  297.  */
  298.  
  299. int
  300. list_isthere(pc_name, pp_list)
  301.     char *pc_name;
  302.     struct list **pp_list;
  303. {
  304.     struct list_hash *phash;
  305.     unsigned int hindex;
  306.     struct list_hash *hentry;
  307.  
  308.     /*
  309.      * 1) if *pp_list is NULL, then we know it's emtpy
  310.      * 2) if it's not in the hash table, then return NULL
  311.      * 3) search hash table chain
  312.      */
  313.  
  314.     /* check for empty list */
  315.     if (*pp_list == NULL) {
  316.     return 0;
  317.     }
  318.  
  319.     /* look in hash table */
  320.     hindex = string_hash(pc_name);
  321.     hentry = &(((*pp_list)->hashtable)[hindex]);
  322.  
  323.     if (hentry->used == 0) {
  324.     return 0;
  325.     }
  326.  
  327.     /* now search through hash chain */
  328.     for (phash = hentry; phash; phash = phash->next) {
  329.     if (strcmp(phash->key, pc_name) == 0) {
  330.         return 1;
  331.     }
  332.     }
  333.     return 0;
  334. }
  335.  
  336. /*
  337.  * list_unset(pc_name, pp_list)
  338.  *    remove the list entry with (varname == pcname) from the
  339.  *    environment
  340.  */
  341.  
  342. void
  343. list_unset(pc_name, pp_list)
  344.     char *pc_name;
  345.     struct list **pp_list;
  346. {
  347.     struct list_hash *phash, *qhash = (struct list_hash *) NULL;
  348.     struct list_elem *plist;
  349.     unsigned int hindex;
  350.     struct list_hash *hentry;
  351.  
  352.     if (*pp_list == NULL)
  353.     return;
  354.  
  355.     /*
  356.      * 1) if pc_name isn't found in the hash chain, return
  357.      * 2) if found, remove the element from the list, and then remove
  358.      *        from hash chain.
  359.      *        check to see if we're the only element on the hash chain,
  360.      *        too.
  361.      */
  362.  
  363.     /* look in hash table */
  364.     hindex = string_hash(pc_name);
  365.     hentry = &(((*pp_list)->hashtable)[hindex]);
  366.  
  367.     /* if not in hash table, return */
  368.     if (hentry->used == 0) {
  369.  
  370. LISTDEBUG(0)
  371. fprintf(stderr, "list_unset(): couldn't find '%s' in environment\n", pc_name);
  372.  
  373.     return;
  374.     }
  375.  
  376.     /* find the element, but playing pointer tag w/two pointers */
  377.     for (phash = hentry; phash; qhash = phash, phash = phash->next) {
  378.     assert(qhash == NULL || qhash->next == phash);
  379.     if (strcmp(phash->key, pc_name) == 0) {
  380.         /* remove the element from the list */
  381.         plist = phash->lptr;
  382.  
  383.         /* prev->next = this->next
  384.          * next->prev = this->prev
  385.          */
  386.  
  387.         /* are we at the head of the list? */
  388.         if (plist->prev) {
  389.         plist->prev->next = plist->next;
  390.         }
  391.         /* are we at the end of the list? */
  392.         if (plist->next) {
  393.         plist->next->prev = plist->prev;
  394.         }
  395.         free((char *) plist);
  396.  
  397.         /* now remove from hash chain */
  398.         /* if it was at top of list */
  399.         if (qhash == NULL) {
  400.         hentry->used = 0;
  401.         hentry->next = (struct list_hash *) NULL;
  402.         } else {
  403.         qhash->next = phash->next;
  404.         free((char *) phash);
  405.         }
  406.         return;
  407.     }
  408.     }
  409.  
  410.  
  411.     return;
  412. }
  413.  
  414. /*
  415.  * list_setflag(pc_name, flag, pp_list)
  416.  *
  417.  *    OR the the specified flag to the existing flag value.
  418.  */
  419.  
  420. int
  421. list_setflag(pc_name, flag, pp_list)
  422.     char *pc_name;
  423.     int    flag;
  424.     struct list **pp_list;
  425. {
  426.     struct list_elem *plist;
  427.     struct list_hash *phash, *hentry;
  428.     unsigned int hindex;
  429.  
  430.     if (*pp_list == NULL)
  431.     return -1;
  432.  
  433.     /*
  434.      * 1) look in hash table for entry.  if not found, return with error.
  435.      * 2) walk down hash chain until entry is found, then modify the
  436.      *        list entry
  437.      */
  438.  
  439.     /* look in hash table */
  440.     hindex = string_hash(pc_name);
  441.     hentry = &(((*pp_list)->hashtable)[hindex]);
  442.  
  443.     /* walk down chain */
  444.     for (phash = hentry; phash && phash->used; phash = phash->next) {
  445.     if (strcmp(phash->key, pc_name) == 0) {
  446.         plist = phash->lptr;
  447.         plist->flag |= flag;
  448.         return 0;
  449.     }
  450.     }
  451.  
  452.     return 0;
  453. }
  454.  
  455. /*
  456.  * list_getflag(pc_name, pp_list)
  457.  *    return the flag value embedded in structure.
  458.  */
  459.  
  460. int
  461. list_getflag(pc_name, pp_list)
  462.     char *pc_name;
  463.     struct list **pp_list;
  464. {
  465.  
  466.     struct list_elem *plist;
  467.     struct list_hash *phash, *hentry;
  468.     unsigned int hindex;
  469.  
  470.     if (*pp_list == NULL)
  471.     return -1;
  472.  
  473.     /*
  474.      * 1) look in hash table for entry.  if not found, return with error.
  475.      * 2) walk down hash chain until entry is found, then modify the
  476.      *        list entry
  477.      */
  478.  
  479.     /* look in hash table */
  480.     hindex = string_hash(pc_name);
  481.     hentry = &(((*pp_list)->hashtable)[hindex]);
  482.  
  483.     /* walk down chain */
  484.     for (phash = hentry; phash && phash->used; phash = phash->next) {
  485.     if (strcmp(phash->key, pc_name) == 0) {
  486.         plist = phash->lptr;
  487.         return plist->flag;
  488.     }
  489.     }
  490.  
  491.     return -1;
  492. }
  493.  
  494. /*
  495.  * list_print()
  496.  *    print out the entire contents of the linked list
  497.  */
  498.  
  499. void
  500. list_print(pp_list)
  501.     struct list **pp_list;
  502. {
  503.     struct list_elem    *p;
  504.     struct list_elem *head;
  505.  
  506.     /* check to see if list is empty */
  507.     if (*pp_list == NULL)
  508.     return;
  509.     
  510.     head = (*pp_list)->p_head;
  511.  
  512.     /* walk down entire list */
  513.     for (p = head; p; p = p->next) {
  514.     printf("%-40s\t%20s %d\n", p->varname, p->varvalue, p->flag);
  515.     }
  516.     return;
  517. }
  518.  
  519. /*
  520.  * list_reset()
  521.  *    
  522.  *    given a pointer to a list, delete the entire list, and set the
  523.  *    pointer to NULL;
  524.  */
  525.  
  526. void
  527. list_reset (pp_list)
  528.     struct list **pp_list;
  529. {
  530.     struct list_elem *p, *q;
  531.     struct list_hash *phash, *qhash;
  532.     int i;
  533.  
  534.     if (*pp_list == NULL)
  535.     return;
  536.  
  537.     /* walk down the list, deleting the element that we just came from */
  538.     for (p = (*pp_list)->p_head; p; q = p, p = p->next, free((char *) q)) ;
  539.  
  540.     /* walk down the hash table, and remove its hash chain */
  541.     for (i = 0; i < LIST_HASHSZ; i++) {
  542.     phash = &(((*pp_list)->hashtable)[i]);
  543.     if (phash->used) {
  544.         /* don't delete the first entry!  it's static! */
  545.         for (phash = phash->next; phash; qhash = phash,
  546.                 phash = qhash->next, free((char *) qhash)) ;
  547.     }
  548.     }
  549.  
  550.     /* now free up the list structure */
  551.     free((char *) *pp_list);
  552.  
  553.     /* now invalidate the list structure pointer */
  554.     *pp_list = NULL;
  555.  
  556.     return;
  557. }
  558.  
  559.  
  560. /*
  561.  * list_init ()
  562.  * list_open (struct list **pp_list)
  563.  * list_get  (struct list **pp_list)
  564.  * list_close(struct list **pp_list)
  565.  *
  566.  *    this allows the retrieval of individual list elements through
  567.  *    successive calls to list_get().
  568.  *
  569.  *    0)    list_init() initializes the tables.
  570.  *    1)     list_open() creates a table entry with *pp_head as the key
  571.  *    2)     any calls to list_get() will get the next element.  the
  572.  *            index is stored in the table, with *pp_head as the
  573.  *            key.
  574.  *    3)     list_close() removes the table entry, with *pp_head as the
  575.  *            key.
  576.  */
  577.  
  578. #define LIST_TABLE_SZ    16
  579. struct list_table_entry {
  580.     struct list *p_key;            /* pointer to head is used as key */
  581.     struct list_elem *p_pindex;        /* pointer to current element */
  582. };
  583.  
  584. static struct list_table_entry list_table[LIST_TABLE_SZ];
  585.  
  586. int
  587. list_init()
  588. {
  589.     int i;
  590.     struct list_table_entry *p;
  591.  
  592.     /* clear all keys and indexes */
  593.     for (i = 0; i < LIST_TABLE_SZ; i++) {
  594.     p = &list_table[i];
  595.     p->p_key = NULL;
  596.     p->p_pindex = NULL;
  597.     }
  598.     return 0;
  599. }
  600.  
  601. /*
  602.  * list_open(struct list **pp_list)
  603.  *
  604.  *    create a table entry with *pp_head as a key.
  605.  *    returns (-1) if an entry with the specified key was already
  606.  *        in the table, else (0).
  607.  */
  608.  
  609. int
  610. list_open (pp_list)
  611.     struct list **pp_list;
  612. {
  613.     int i;
  614.     struct list_table_entry *p;
  615.  
  616.     /* is the list NULL? */
  617.     if (*pp_list == NULL) {
  618.     return 0;                /* we'll fake it later on */
  619.     }
  620.  
  621.     /* is there already an entry with a matching key?  is there any
  622.      * an empty table entry for us?
  623.      */
  624.     for (i = 0; i < LIST_TABLE_SZ; i++) {
  625.     p = &list_table[i];
  626.     if (p->p_key == NULL)
  627.          break;
  628.     if (p->p_key == *pp_list)
  629.          break;
  630.     }                        /* end for loop */
  631.  
  632.     /*
  633.      * return with error if there was a collision.  (if the index rolled
  634.      * all the way to the top, and its index value was non-null, then
  635.      * we overflowed the table.)
  636.      */
  637.     if (i == LIST_TABLE_SZ && p->p_key != NULL)
  638.     return -1;
  639.  
  640.     /*
  641.      * create the table entry.  assertion: p already points to an empty
  642.      * table entry.   Have index point to the head.
  643.      */
  644.     p->p_key = *pp_list;
  645.     p->p_pindex = (*pp_list)->p_head;
  646.  
  647.     return 0;
  648. }
  649.  
  650. /*
  651.  * struct list_elem *
  652.  * list_get(struct list **pp_list)
  653.  *
  654.  *    get the next entry in the specified list (using *pp_list as the key),
  655.  *        and bump the internal pointer to the next element, ready
  656.  *        for the next call to list_get().
  657.  *    we return NULL if we're sitting on the tail end of the list.
  658.  */
  659.  
  660. struct list_elem *
  661. list_get (pp_list)
  662.     struct list **pp_list;
  663. {
  664.     int i;
  665.     struct list_table_entry *p, *q;
  666.     struct list_elem *p_elem;
  667.  
  668.     /* fake it if you pass it a NULL */
  669.     if (*pp_list == NULL) {
  670.     return NULL;
  671.     }
  672.  
  673.     /* find entry with matching key */
  674.     for (i = 0; i < LIST_TABLE_SZ; i++) {
  675.     p = &list_table[i];
  676.     if (p->p_key == *pp_list)
  677.          break;
  678.     }                        /* end for loop */
  679.  
  680.     /* bounds checking.  if we rolled through the entire array, then
  681.      * we never found the key!
  682.      */
  683.  
  684.     if (i == LIST_TABLE_SZ)
  685.     return NULL;
  686.  
  687.     /* are we already at the end of the list? */
  688.  
  689.     if (p->p_pindex == NULL)
  690.     return NULL;
  691.  
  692.     /* if not, return a pointer to the current list element, and increment
  693.      * the table pointer.
  694.      */
  695.  
  696.     p_elem = p->p_pindex;
  697.     q = p;
  698.     q->p_pindex = q->p_pindex->next;        /* walk through pointer */
  699.  
  700.     return p_elem;
  701. }
  702.  
  703. /*
  704.  * list_close(struct list **pp_list)
  705.  *    
  706.  *     remove the table entry with (*pp_list) as the key.
  707.  *    return -1 if entry not found.  else 0.
  708.  */
  709.  
  710. int
  711. list_close (pp_list)
  712.     struct list **pp_list;
  713. {
  714.     int i;
  715.     struct list_table_entry *p;
  716.  
  717.     /* fake it if you pass it a NULL */
  718.     if (*pp_list == NULL) {
  719.     return 0;
  720.     }
  721.  
  722.     /* find entry with matching key */
  723.     for (i = 0; i < LIST_TABLE_SZ; i++) {
  724.     p = &list_table[i];
  725.     if (p->p_key == *pp_list)
  726.          break;
  727.     }                        /* end for loop */
  728.  
  729.     /* bounds checking.  if we rolled through the entire array, then
  730.      * we never found the key!
  731.      */
  732.  
  733.     if (i == LIST_TABLE_SZ)
  734.     return -1;
  735.  
  736.     /* remove the entry.  assertion:  p is pointing to our entry */
  737.     p->p_key = NULL;
  738.     p->p_pindex = NULL;
  739.  
  740.     return 0;
  741. }
  742.  
  743. static unsigned int
  744. string_hash (string)
  745.     char *string;
  746. {
  747.     unsigned int hindex;
  748.     char *pc = string;
  749.  
  750.     hindex = *pc;
  751.     while (*pc) {
  752.     hindex = ((hindex << 9) ^ *pc++) % LIST_HASHSZ;
  753.     /*
  754.     hindex = ((hindex << 7) | (string[i] + len)) % LIST_HASHSZ;
  755.     */
  756.     }
  757.     return hindex;
  758. }
  759.