test/OOPDemos/hash.c

   1 /*
   2    Copyright © 1997-98, The AROS Development Team. All rights reserved.
   3    $Id$
   4
   5    Desc: Demo of new OOP system - General hashing functions.
   6    Lang: english
   7 */
   8
   9 #include "hash.h"
  10 #include <stdlib.h>
  11
  12 #define SDEBUG 0
  13 #define DEBUG 0
  14 #include "debug.h"
  15 #include <string.h>
  16 #define UB(x) ((UBYTE *)x)
  17
  18 /******************
  19 **  AllocHash()  **
  20 ******************/
  21
  22 /* Allocates a hashtable for given number of entries,
  23 ** so that hash table is no more than 50% full.
  24 ** Initializes table as empty.
  25 */
  26
  27 struct Bucket **NewHash(ULONG entries)
  28 {
  29
  30     /* Calulates hashsize as 2^n - 1 so that htsize >= 2*initial */
  31     ULONG temp = 1;
  32     BYTE i;
  33     ULONG size;
  34     struct Bucket **ht = NULL;
  35
  36     EnterFunc(bug("NewHash(entries=%ld)\n", entries));
  37
  38     /* Find the highest bit in 'initial' */
  39     for (i = 31; i >= 0; i --)
  40     {
  41         if ((temp << i) & entries)
  42             break;
  43     }
  44
  45     D(bug("i: %d\n", i));
  46
  47     /* Make sure table is never more than 50% full */
  48     i ++;
  49
  50     entries = (temp << i);
  51
  52     /* Calulate size in bytes. + 1 because we store the size of the hashtable */
  53     size = UB( &ht[entries + 1] ) - UB( &ht[0] );
  54
  55
  56     ht = malloc(size);
  57     if (ht)
  58     {
  59
  60         /* Clear table */
  61         memset(ht, 0, size);
  62
  63
  64         entries --; /* 2^n - 1 */
  65         ((IPTR *)ht)[0] = entries;
  66
  67         D(bug("ht: %p, mask: %ld\n", ht, entries));
  68
  69
  70         ReturnPtr ("NewHash", struct Bucket **, &ht[1]);
  71     }
  72     ReturnPtr ("NewHash", struct Bucket **, NULL);
  73 }
  74
  75 /*****************
  76 **  FreeHash()  **
  77 *****************/
  78 VOID FreeHash(struct Bucket **ht, VOID (*freebucket)())
  79 {
  80     ULONG i;
  81
  82     EnterFunc(bug("FreeHash(ht=%p, freebucket=%p)\n", ht, freebucket));
  83
  84     D(bug("Hashsize: %ld\n", HashSize(ht) ));
  85
  86
  87     /* Free all buckets */
  88     for (i = 0; i < HashSize(ht); i ++)
  89     {
  90         struct Bucket *b, *next_b;
  91         D(bug("Freeing buckets at entry %ld\n", i));
  92
  93         for (b = ht[i]; b; b = next_b)
  94         {
  95             D(bug("Freeing bucket %p of id %ld\n", b, b->ID));
  96             next_b = b->Next;
  97             D(bug("Calling freebucket\n"));
  98             freebucket(b);
  99             D(bug("Freebucket called\n"));
 100         }
 101     }
 102     free(&ht[-1]);
 103
 104     ReturnVoid("FreeHash");
 105 }
 106
 107 /*******************
 108 **  HashLookup()  **
 109 *******************/
 110 struct Bucket *HashLookupULONG(struct Bucket **ht, IPTR id)
 111 {
 112     struct Bucket *b;
 113
 114     for (b = ht[CalcHash(ht, id)]; b; b = b->Next)
 115     {
 116         if (b->ID == id)
 117             return (b);
 118     }
 119
 120     return (NULL);
 121 }
 122
 123 struct Bucket *HashLookupStr(struct Bucket **ht, IPTR id)
 124 {
 125     struct Bucket *b;
 126     EnterFunc(bug("HashLookupStr(ht=%p, id=%s)\n", ht, (STRPTR)id));
 127     for (b = ht[CalcHashStr(ht, id)]; b; b = b->Next)
 128     {
 129         D(bug("Bucket: %p\n", b));
 130         if (!strcmp((STRPTR)b->ID, (STRPTR)id))
 131             ReturnPtr ("HashLookupStr", struct Bucket *, b);
 132     }
 133     ReturnPtr ("HashLookupStr", struct Bucket *, NULL);
 134 }
 135
 136 /*****************
 137 **  CopyHash()  **
 138 *****************/
 139 BOOL CopyHash(struct Bucket **dest_ht
 140         ,struct Bucket **src_ht
 141         ,struct Bucket * (*copybucket)()
 142         ,APTR data)
 143 {
 144     ULONG i;
 145
 146     EnterFunc(bug("CopyHash(dest_ht=%p, src_ht=%p, copybucket=%p,data = %p)\n",
 147         dest_ht, src_ht, copybucket, data));
 148
 149     for (i = 0; i < HashSize(src_ht); i ++ )
 150     {
 151         struct Bucket *b;
 152
 153         D(bug("idx: %ld\n", i));
 154
 155         for (b = src_ht[i]; b; b = b->Next)
 156         {
 157             /* Rehash bucket into destination hashtable */
 158             struct Bucket *new_b;
 159
 160             D(bug("Bucket: %p\n", b));
 161
 162             new_b = copybucket(b);
 163             if (!new_b)
 164                 ReturnBool ("CopyHash", FALSE);
 165
 166             InsertBucket(dest_ht, new_b);
 167
 168
 169         } /* For each bucket at current entry */
 170
 171     } /* For each entry in source hashtable */
 172
 173     ReturnBool ("CopyHash", TRUE);
 174 }
 175
 176 /*********************
 177 **  InsertBucket()  **
 178 *********************/
 179 VOID InsertBucket(struct Bucket **ht, struct Bucket *b)
 180 {
 181     /* Inserts bucket into hashtable accordibg to the ID */
 182     ULONG idx;
 183
 184     EnterFunc(bug("InsertBucket(ht=%p, b=%p)\n", ht, b));
 185
 186     idx = CalcHash(ht, b->ID);
 187     b->Next = ht[idx];
 188     ht[idx] = b;
 189     D(bug("b->Next=%p\n", b->Next));
 190
 191
 192     ReturnVoid ("InsertBucket");
 193
 194 }
 195
 196 /* id is an interface ID */
 197 ULONG CalcHashULONG(struct Bucket **ht, IPTR id)
 198 {
 199     return  (HashMask(ht) & id);
 200 }
 201
 202 /* id is a (interfaceid << NUM_METHOD_BITS) & methodID */
 203 ULONG CalcHashHM(struct Bucket **ht, IPTR id)
 204 {
 205     return  (HashMask(ht) & (id ^ (id >> NUM_METHOD_BITS)));
 206 }
 207
 208 /* id is a (interfaceid << NUM_METHOD_BITS) & methodID */
 209 ULONG CalcHashStr(struct Bucket **ht, IPTR id)
 210 {
 211     STRPTR str = (STRPTR)id;
 212     ULONG val, i;
 213     for (i = 0, val = 0; (i < MAX_HASH_CHARS) && *str; str ++)
 214         {val += *str; i ++; }
 215
 216     return  (val & HashMask(ht));
 217 }