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 #include "tac_plus.h"
  21
  22 struct entry {
  23     char *name;
  24     void *hash;
  25 };
  26
  27 typedef struct entry ENTRY;
  28
  29 /* Calculate hash value from a string */
  30 static int
  31 calculate_hash(name)
  32 char *name;
  33 {
  34     int i;
  35     int len = strlen(name);
  36     int hashval = 0;
  37
  38     for (i = 0; i < len; i++) {
  39         hashval += name[i] * (i + 1);
  40     }
  41     hashval += name[0];
  42     hashval = hashval > 0 ? hashval : -hashval;
  43     return (hashval);
  44 }
  45
  46 /* Lookup a name in a hash table.  Return its node if it exists, NULL
  47    otherwise */
  48 void *
  49 hash_lookup(hashtab, name)
  50 void **hashtab;
  51 char *name;
  52 {
  53     ENTRY *entry;
  54     int hashval = calculate_hash(name);
  55
  56     entry = hashtab[hashval % HASH_TAB_SIZE];
  57
  58     while (entry) {
  59         if (STREQ(name, entry->name))
  60             /* Node exists in table. return it */
  61             return (entry);
  62         entry = entry->hash;
  63     }
  64     return (NULL);
  65 }
  66
  67 /* Add a node to a hash table.  Return node if it exists, NULL
  68    otherwise */
  69 void *
  70 hash_add_entry(hashtab, newentry)
  71 void **hashtab;
  72 ENTRY *newentry;
  73 {
  74     ENTRY *entry;
  75     int hashval;
  76
  77     entry = hash_lookup(hashtab, newentry->name);
  78     if (entry)
  79         return (entry);
  80
  81     /* Node does not exist in table. Add it */
  82     hashval = calculate_hash(newentry->name);
  83     newentry->hash = hashtab[hashval % HASH_TAB_SIZE];
  84     hashtab[hashval % HASH_TAB_SIZE] = newentry;
  85     return (NULL);
  86 }
  87
  88
  89 /* Return an array of pointers to all the entries in a hash table */
  90 void **
  91 hash_get_entries(hashtab)
  92 void **hashtab;
  93 {
  94     int i;
  95     int cnt;
  96     ENTRY *entry;
  97     void **entries, **p;
  98     int n, longest;
  99
 100     longest = 0;
 101     cnt = 0;
 102     for (i = 0; i < HASH_TAB_SIZE; i++) {
 103         entry = hashtab[i];
 104         n = 0;
 105         while (entry) {
 106             cnt++;
 107             n++;
 108             entry = entry->hash;
 109         }
 110         if (n > longest)
 111             longest = n;
 112     }
 113     cnt++;                      /* Add space for NULL entry at end */
 114
 115     p = entries = (void **) tac_malloc(cnt * sizeof(void *));
 116     for (i = 0; i < HASH_TAB_SIZE; i++) {
 117         entry = hashtab[i];
 118         while (entry) {
 119             *p++ = entry;
 120             entry = entry->hash;
 121         }
 122     }
 123     *p++ = NULL;
 124     return (entries);
 125 }