rom/oop/hash.c

   1 /*
   2     Copyright © 1995-2001, The AROS Development Team. All rights reserved.
   3    $Id$
   4
   5    Desc: Common code for handling hashing.
   6    Lang: english
   7 */
   8
   9 #include "hash.h"
  10 #include "intern.h"
  11
  12 #include <proto/exec.h>
  13 #include <exec/memory.h>
  14 #include <stdlib.h>
  15
  16 #undef SDEBUG
  17 #undef DEBUG
  18 #define SDEBUG 0
  19 #define DEBUG 0
  20 #include <aros/debug.h>
  21
  22 #include <string.h>
  23
  24 #define UB(x) ((UBYTE *)x)
  25
  26 /******************
  27 **  AllocHash()  **
  28 ******************/
  29
  30 /* Allocates a hashtable for given number of entries,
  31 ** so that hash table is no more than 50% full.
  32 ** Initializes table as empty.
  33 */
  34
  35 struct HashTable *NewHash(ULONG entries, UBYTE type, struct IntOOPBase *OOPBase)
  36 {
  37
  38
  39     ULONG temp = 1;
  40     BYTE i;
  41     ULONG size;
  42     struct HashTable *ht;
  43
  44     EnterFunc(bug("NewHash(entries=%ld, type=%ld)\n", entries, type));
  45
  46     /* Allocate hashtable struct */
  47
  48
  49     ht = AllocMem(sizeof (struct HashTable), MEMF_ANY);
  50     if (ht)
  51     {
  52         /* Allocate table of size 2^n - 1       */
  53         /* Find the highest bit in 'initial'    */
  54         for (i = 31; i >= 0; i --)
  55         {
  56             if ((temp << i) & entries)
  57                 break;
  58         }
  59
  60         D(bug("i: %d\n", i));
  61
  62         /* Make sure table is never more than 50% full */
  63         i ++;
  64
  65         entries = (temp << i);
  66         entries --; /* 2^n - 1 */
  67
  68         /* Get table size */
  69         size = UB( &ht[entries] ) - UB( &ht[0] );
  70
  71         /* Allocate the table */
  72         ht->Table = AllocVec(size, MEMF_ANY|MEMF_CLEAR);
  73         if (ht)
  74         {
  75             ht->HashMask = entries - 1;
  76             ht->Type     = type;
  77
  78             /* Initialize the hashtable's Lookup and CalcHash
  79             ** accordint to if we want to hash integers or strings
  80             */
  81             switch (type)
  82             {
  83             case HT_INTEGER:
  84                 ht->Lookup      = HashLookupULONG;
  85                 ht->CalcHash    = CalcHashULONG;
  86                 break;
  87
  88             case HT_STRING:
  89                 ht->Lookup      = HashLookupStr;
  90                 ht->CalcHash    = CalcHashStr;
  91                 break;
  92             }
  93
  94
  95
  96             ReturnPtr ("NewHash", struct HashTable *, ht);
  97         }
  98         FreeMem(ht, sizeof (struct HashTable));
  99     }
 100     ReturnPtr ("NewHash", struct HashTable *, NULL);
 101 }
 102
 103 /*****************
 104 **  FreeHash()  **
 105 *****************/
 106 VOID FreeHash(struct HashTable *ht, VOID (*freebucket)(), struct IntOOPBase *OOPBase)
 107 {
 108     ULONG i;
 109
 110     EnterFunc(bug("FreeHash(ht=%p, freebucket=%p)\n", ht, freebucket));
 111
 112     D(bug("Hashsize: %ld\n", HashSize(ht) ));
 113
 114
 115     /* Free all buckets */
 116     for (i = 0; i < HashSize(ht); i ++)
 117     {
 118         struct Bucket *b, *next_b;
 119         D(bug("Freeing buckets at entry %ld\n", i));
 120
 121         for (b = ht->Table[i]; b; b = next_b)
 122         {
 123             next_b = b->Next;
 124             /* USe usersupplied func to free bucket */
 125             freebucket(b, OOPBase);
 126         }
 127     }
 128     /* Free the table */
 129     FreeVec(ht->Table);
 130     /* Free the hashtable struct */
 131     FreeMem(ht, sizeof (struct HashTable));
 132
 133     ReturnVoid("FreeHash");
 134 }
 135
 136 /*******************
 137 **  HashLookup()  **
 138 *******************/
 139 struct Bucket *HashLookupULONG(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase)
 140 {
 141     struct Bucket *b;
 142     EnterFunc(bug("HashLookupULONG(ht=%p, id=%ld)\n", ht, id));
 143     /* Function for looking up integers in the table */
 144     for (b = ht->Table[CalcHashULONG(ht, id)]; b; b = b->Next)
 145     {
 146         D(bug("Current bucket: %p of id %ld\n", b, b->ID));
 147         if (b->ID == id)
 148             ReturnPtr ("HashLookupULONG", struct Bucket *, b);
 149     }
 150
 151     ReturnPtr ("HashLookupULONG", struct Bucket *, NULL);
 152 }
 153
 154 struct Bucket *HashLookupStr(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase)
 155 {
 156     struct Bucket *b;
 157
 158     /* Function for looking up strings in the table */
 159     EnterFunc(bug("HashLookupStr(ht=%p, id=%s)\n", ht, (STRPTR)id));
 160     for (b = ht->Table[CalcHashStr(ht, id)]; b; b = b->Next)
 161     {
 162         D(bug("Bucket: %p\n", b));
 163         D(bug("ID: %p\n", b->ID));
 164         D(bug("ID: %s\n", b->ID));
 165         if (!strcmp((STRPTR)b->ID, (STRPTR)id))
 166             ReturnPtr ("HashLookupStr", struct Bucket *, b);
 167     }
 168     ReturnPtr ("HashLookupStr", struct Bucket *, NULL);
 169 }
 170
 171 /*****************
 172 **  CopyHash()  **
 173 *****************/
 174 BOOL CopyHash(struct HashTable *dest_ht
 175         ,struct HashTable *src_ht
 176         ,struct Bucket * (*copybucket)()
 177         ,APTR data
 178         ,struct IntOOPBase *OOPBase     )
 179 {
 180     ULONG i;
 181
 182     /* Copies all buckets of src_ht into dest_ht */
 183
 184     EnterFunc(bug("CopyHash(dest_ht=%p, src_ht=%p, copybucket=%p,data = %p)\n",
 185         dest_ht, src_ht, copybucket, data));
 186
 187     /* for each entry in the table */
 188     for (i = 0; i < HashSize(src_ht); i ++ )
 189     {
 190         struct Bucket *b;
 191
 192         D(bug("idx: %ld\n", i));
 193
 194         /* for each bucket at curent entry */
 195         for (b = src_ht->Table[i]; b; b = b->Next)
 196         {
 197             /* Rehash bucket into destination hashtable */
 198             struct Bucket *new_b;
 199
 200             D(bug("Bucket: %p\n", b));
 201
 202             /* use user-supllied func to copy the bucket */
 203             new_b = copybucket(b, data, OOPBase);
 204             if (!new_b)
 205                 ReturnBool ("CopyHash", FALSE);
 206
 207             /* insert the new bucket into detsination table */
 208             InsertBucket(dest_ht, new_b, OOPBase);
 209
 210
 211         } /* For each bucket at current entry */
 212
 213     } /* For each entry in source hashtable */
 214
 215     ReturnBool ("CopyHash", TRUE);
 216 }
 217
 218 /*********************
 219 **  InsertBucket()  **
 220 *********************/
 221 VOID InsertBucket(struct HashTable *ht, struct Bucket *b, struct IntOOPBase *OOPBase)
 222 {
 223     /* Inserts bucket into hashtable according to its ID */
 224     ULONG idx;
 225
 226     EnterFunc(bug("InsertBucket(ht=%p, b=%p)\n", ht, b));
 227
 228     idx = ht->CalcHash(ht, b->ID);
 229     b->Next = ht->Table[idx];
 230     ht->Table[idx] = b;
 231     D(bug("b->Next=%p\n", b->Next));
 232
 233     ReturnVoid ("InsertBucket");
 234
 235 }
 236
 237 VOID RemoveBucket(struct  HashTable *ht, struct Bucket *b)
 238 {
 239     ULONG idx;
 240     struct Bucket *last_b = NULL,
 241                   *cur_b;
 242     idx = ht->CalcHash(ht, b->ID);
 243
 244     /* Search for bucket to remove */
 245     for (cur_b = ht->Table[idx]; cur_b; cur_b = cur_b->Next)
 246     {
 247         if (cur_b == b)
 248         {
 249             /* Bucket found */
 250             if (last_b)
 251             {
 252                 /* Remove bucket from chain */
 253                 last_b->Next = cur_b->Next;
 254
 255                 /* Not really neccessar, but ... */
 256                 b->Next = NULL;
 257             }
 258             else
 259             {
 260                 /* We are removing the first bucket */
 261                 ht->Table[idx] = cur_b->Next;
 262             }
 263         }
 264
 265         last_b = cur_b;
 266
 267     } /* for (each bucket at idx) */
 268
 269 }
 270
 271
 272 ULONG CalcHashULONG(struct HashTable *ht, IPTR id)
 273 {
 274     /* Return idx into hashtable for an integer */
 275     return  (id % HashMask(ht));
 276 }
 277
 278 static ULONG CalcHashStr_KR(struct HashTable *ht, IPTR id)
 279 {
 280     STRPTR str = (STRPTR)id;
 281     ULONG val, i;
 282     /* Return idx into hashtable for a string */
 283     for (i = 0, val = 0; (i < MAX_HASH_CHARS) && *str; str ++)
 284         {val += *str; i ++; }
 285
 286     return  (val & HashSize(ht));
 287 }
 288
 289 static ULONG CalcHashStr_DJB2(struct HashTable *ht, IPTR id)
 290 {
 291     STRPTR str = (STRPTR)id;
 292     ULONG val, i;
 293     /* Return idx into hashtable for a string */
 294     for (i = 0, val = 0; (i < MAX_HASH_CHARS) && *str; str ++)
 295         {val = ((val << 5) + val) ^ *str; i ++; }
 296
 297     return  (val & HashSize(ht));
 298 }
 299
 300 ULONG CalcHashStr_SDBM(struct HashTable *ht, IPTR id)
 301 {
 302     STRPTR str = (STRPTR)id;
 303     ULONG val, i;
 304     /* Return idx into hashtable for a string */
 305     for (i = 0, val = 0; (i < MAX_HASH_CHARS) && *str; str ++)
 306         {val = *str + (val << 6) + (val << 16) - val; i ++; }
 307
 308     return  (val & HashSize(ht));
 309 }
 310
 311 ULONG CalcHashStr_Org(struct HashTable *ht, IPTR id)
 312 {
 313     STRPTR str = (STRPTR)id;
 314     ULONG val, i;
 315     /* Return idx into hashtable for a string */
 316     for (i = 0, val = 0; (i < MAX_HASH_CHARS) && *str; str ++)
 317         {val += *str; i ++; }
 318
 319     return  (val & HashSize(ht));
 320 }
 321
 322 ULONG CalcHashStr(struct HashTable *ht, IPTR id)
 323 {
 324     return CalcHashStr_KR(ht, id);
 325 }
 326
 327 /* Prints contents of a hastable */
 328 VOID print_table(struct HashTable *ht, struct IntOOPBase *OOPBase)
 329 {
 330     ULONG idx;
 331     ULONG filled=0;
 332
 333     for (idx = 0; idx < HashSize(ht); idx ++)
 334     {
 335         struct Bucket *b;
 336         BOOL ok = FALSE;
 337         D(bug("idx %ld: ", idx));
 338         for (b = ht->Table[idx]; b; b = b->Next)
 339         {
 340       ok = TRUE;
 341 #if DEBUG
 342             if (ht->Type == HT_INTEGER)
 343                 bug("%ld ", b->ID);
 344             else
 345                 bug("%s(%ld) ", (STRPTR)b->ID, ((struct iid_bucket *)b)->refcount);
 346 #endif
 347         }
 348         D(bug("\n"));
 349     if (ok) filled++;
 350
 351     }
 352     D(bug("HashTable fill ratio: %d %%\n", filled * 100 / HashSize(ht)));
 353     return;
 354
 355 }