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