hash.c

   1 /*
   2    Copyright (c) 1995-1998 by Cisco systems, Inc.
   3
   4    Permission to use, copy, modify, and distribute this software for
   5    any purpose and without fee is hereby granted, provided that this
   6    copyright and permission notice appear on all copies of the
   7    software and supporting documentation, the name of Cisco Systems,
   8    Inc. not be used in advertising or publicity pertaining to
   9    distribution of the program without specific prior permission, and
  10    notice be given in supporting documentation that modification,
  11    copying and distribution is by permission of Cisco Systems, Inc.
  12
  13    Cisco Systems, Inc. makes no representations about the suitability
  14    of this software for any purpose.  THIS SOFTWARE IS PROVIDED ``AS
  15    IS'' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
  16    WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17    FITNESS FOR A PARTICULAR PURPOSE.
  18 */
  19
  20
  21 #include "tac_plus.h"
  22
  23 #include "hash.h"
  24 #include "utils.h"
  25
  26
  27 struct entry {
  28     char *name;
  29     void *hash;
  30 };
  31
  32 static int calculate_hash TAC_ARGS((const char *name));
  33
  34 /* Calculate hash value from a string */
  35 static int
  36 calculate_hash(name)
  37 const char *name;
  38 {
  39     int i;
  40     int len = strlen(name);
  41     int hashval = 0;
  42
  43     for (i = 0; i < len; i++) {
  44         hashval += name[i] * (i + 1);
  45     }
  46     hashval += name[0];
  47     hashval = hashval > 0 ? hashval : -hashval;
  48     return (hashval);
  49 }
  50
  51 void *hash_lookup TAC_ARGS((void **hashtab, const char *name));
  52
  53 /* Lookup a name in a hash table.  Return its node if it exists, NULL
  54    otherwise */
  55 void *
  56 hash_lookup(hashtab, name)
  57 void **hashtab;
  58 const char *name;
  59 {
  60     ENTRY *entry;
  61     int hashval = calculate_hash(name);
  62
  63     entry = hashtab[hashval % HASH_TAB_SIZE];
  64
  65     while (entry) {
  66         if (STREQ(name, entry->name))
  67             /* Node exists in table. return it */
  68             return (entry);
  69         entry = entry->hash;
  70     }
  71     return (NULL);
  72 }
  73
  74 void *hash_add_entry TAC_ARGS((void **hashtab, ENTRY *newentry));
  75
  76 /* Add a node to a hash table.  Return node if it exists, NULL
  77    otherwise */
  78 void *
  79 hash_add_entry(hashtab, newentry)
  80 void **hashtab;
  81 ENTRY *newentry;
  82 {
  83     ENTRY *entry;
  84     int hashval;
  85
  86     entry = hash_lookup(hashtab, newentry->name);
  87     if (entry)
  88         return (entry);
  89
  90     /* Node does not exist in table. Add it */
  91     hashval = calculate_hash(newentry->name);
  92     newentry->hash = hashtab[hashval % HASH_TAB_SIZE];
  93     hashtab[hashval % HASH_TAB_SIZE] = newentry;
  94     return (NULL);
  95 }
  96
  97
  98 void **hash_get_entries TAC_ARGS((void **hashtab));
  99
 100 /* Return an array of pointers to all the entries in a hash table */
 101 void **
 102 hash_get_entries(hashtab)
 103 void **hashtab;
 104 {
 105     int i;
 106     int cnt;
 107     ENTRY *entry;
 108     void **entries, **p;
 109     int n, longest;
 110
 111     longest = 0;
 112     cnt = 0;
 113     for (i = 0; i < HASH_TAB_SIZE; i++) {
 114         entry = hashtab[i];
 115         n = 0;
 116         while (entry) {
 117             cnt++;
 118             n++;
 119             entry = entry->hash;
 120         }
 121         if (n > longest)
 122             longest = n;
 123     }
 124     cnt++;                      /* Add space for NULL entry at end */
 125
 126     p = entries = (void **) tac_malloc(cnt * sizeof(void *));
 127     for (i = 0; i < HASH_TAB_SIZE; i++) {
 128         entry = hashtab[i];
 129         while (entry) {
 130             *p++ = entry;
 131             entry = entry->hash;
 132         }
 133     }
 134     *p++ = NULL;
 135     return (entries);
 136 }