src/hashtab.c

   1 /*
   2  * Copyright (C) 1989-95 GROUPE BULL
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to
   6  * deal in the Software without restriction, including without limitation the
   7  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8  * sell copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  17  * GROUPE BULL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20  *
  21  * Except as contained in this notice, the name of GROUPE BULL shall not be
  22  * used in advertising or otherwise to promote the sale, use or other dealings
  23  * in this Software without prior written authorization from GROUPE BULL.
  24  */
  25
  26 /*****************************************************************************\
  27 * hashtab.c:                                                                  *
  28 *                                                                             *
  29 *  XPM library                                                                *
  30 *                                                                             *
  31 *  Developed by Arnaud Le Hors                                                *
  32 *  this originaly comes from Colas Nahaboo as a part of Wool                  *
  33 *                                                                             *
  34 \*****************************************************************************/
  35
  36 #ifdef HAVE_CONFIG_H
  37 #include <config.h>
  38 #endif
  39 #include "XpmI.h"
  40
  41 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
  42 LFUNC(HashTableGrows, int, (xpmHashTable * table));
  43
  44 static xpmHashAtom
  45 AtomMake(                               /* makes an atom */
  46     char        *name,                  /* WARNING: is just pointed to */
  47     void        *data)
  48 {
  49     xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
  50
  51     if (object) {
  52         object->name = name;
  53         object->data = data;
  54     }
  55     return object;
  56 }
  57
  58 /************************\
  59 *                        *
  60 *  hash table routines   *
  61 *                        *
  62 \************************/
  63
  64 /*
  65  * Hash function definition:
  66  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
  67  *                               hash2 = temporary for hashcode.
  68  * INITIAL_TABLE_SIZE in slots
  69  * HASH_TABLE_GROWS how hash table grows.
  70  */
  71
  72 /* Mock lisp function */
  73 #define HASH_FUNCTION     hash = (hash << 5) - hash + *hp++;
  74 /* #define INITIAL_HASH_SIZE 2017 */
  75 #define INITIAL_HASH_SIZE 256           /* should be enough for colors */
  76 #define HASH_TABLE_GROWS  size = size * 2;
  77
  78 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
  79 #ifdef notdef
  80 #define HASH_FUNCTION   hash <<= 4; hash += *hp++; \
  81     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
  82 #define INITIAL_HASH_SIZE 4095          /* should be 2^n - 1 */
  83 #define HASH_TABLE_GROWS  size = size << 1 + 1;
  84 #endif
  85
  86 /* GNU emacs function */
  87 /*
  88 #define HASH_FUNCTION     hash = (hash << 3) + (hash >> 28) + *hp++;
  89 #define INITIAL_HASH_SIZE 2017
  90 #define HASH_TABLE_GROWS  size = size * 2;
  91 */
  92
  93 /* end of hash functions */
  94
  95 /*
  96  * The hash table is used to store atoms via their NAME:
  97  *
  98  * NAME --hash--> ATOM |--name--> "foo"
  99  *                     |--data--> any value which has to be stored
 100  *
 101  */
 102
 103 /*
 104  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
 105  * (slot points to NULL if it is not defined)
 106  *
 107  */
 108
 109 xpmHashAtom *
 110 xpmHashSlot(
 111     xpmHashTable        *table,
 112     char                *s)
 113 {
 114     xpmHashAtom *atomTable = table->atomTable;
 115     unsigned int hash;
 116     xpmHashAtom *p;
 117     char *hp = s;
 118     char *ns;
 119
 120     hash = 0;
 121     while (*hp) {                       /* computes hash function */
 122         HASH_FUNCTION
 123     }
 124     p = atomTable + hash % table->size;
 125     while (*p) {
 126         ns = (*p)->name;
 127         if (ns[0] == s[0] && strcmp(ns, s) == 0)
 128             break;
 129         p--;
 130         if (p < atomTable)
 131             p = atomTable + table->size - 1;
 132     }
 133     return p;
 134 }
 135
 136 static int
 137 HashTableGrows(xpmHashTable *table)
 138 {
 139     xpmHashAtom *atomTable = table->atomTable;
 140     unsigned int size = table->size;
 141     xpmHashAtom *t, *p;
 142     int i;
 143     unsigned int oldSize = size;
 144
 145     t = atomTable;
 146     HASH_TABLE_GROWS
 147         table->size = size;
 148     table->limit = size / 3;
 149     if (size >= UINT_MAX / sizeof(*atomTable))
 150         return (XpmNoMemory);
 151     atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
 152     if (!atomTable)
 153         return (XpmNoMemory);
 154     table->atomTable = atomTable;
 155     for (p = atomTable + size; p > atomTable;)
 156         *--p = NULL;
 157     for (i = 0, p = t; i < oldSize; i++, p++)
 158         if (*p) {
 159             xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
 160
 161             *ps = *p;
 162         }
 163     XpmFree(t);
 164     return (XpmSuccess);
 165 }
 166
 167 /*
 168  * xpmHashIntern(table, name, data)
 169  * an xpmHashAtom is created if name doesn't exist, with the given data.
 170  */
 171
 172 int
 173 xpmHashIntern(
 174     xpmHashTable        *table,
 175     char                *tag,
 176     void                *data)
 177 {
 178     xpmHashAtom *slot;
 179
 180     if (!*(slot = xpmHashSlot(table, tag))) {
 181         /* undefined, make a new atom with the given data */
 182         if (!(*slot = AtomMake(tag, data)))
 183             return (XpmNoMemory);
 184         if (table->used >= table->limit) {
 185             int ErrorStatus;
 186
 187             if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
 188                 return (ErrorStatus);
 189             table->used++;
 190             return (XpmSuccess);
 191         }
 192         table->used++;
 193     }
 194     return (XpmSuccess);
 195 }
 196
 197 /*
 198  *  must be called before allocating any atom
 199  */
 200
 201 int
 202 xpmHashTableInit(xpmHashTable *table)
 203 {
 204     xpmHashAtom *p;
 205     xpmHashAtom *atomTable;
 206
 207     table->size = INITIAL_HASH_SIZE;
 208     table->limit = table->size / 3;
 209     table->used = 0;
 210     table->atomTable = NULL;
 211     if (table->size >= UINT_MAX / sizeof(*atomTable))
 212         return (XpmNoMemory);
 213     atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
 214     if (!atomTable)
 215         return (XpmNoMemory);
 216     for (p = atomTable + table->size; p > atomTable;)
 217         *--p = NULL;
 218     table->atomTable = atomTable;
 219     return (XpmSuccess);
 220 }
 221
 222 /*
 223  *   frees a hashtable and all the stored atoms
 224  */
 225
 226 void
 227 xpmHashTableFree(xpmHashTable *table)
 228 {
 229     xpmHashAtom *p;
 230     xpmHashAtom *atomTable = table->atomTable;
 231
 232     if (!atomTable)
 233         return;
 234     for (p = atomTable + table->size; p > atomTable;)
 235         if (*--p)
 236             XpmFree(*p);
 237     XpmFree(atomTable);
 238     table->atomTable = NULL;
 239 }