workbench/devs/ram_handler/HashTable.c

   1 /*
   2     Copyright © 1995-2007, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     An Hash Table implementation.
   6 */
   7
   8 #include  "HashTable.h"
   9
  10 #include <exec/types.h>
  11 #include <exec/memory.h>
  12 #include <proto/alib.h>
  13 #include <proto/exec.h>
  14
  15 #define  DEBUG 0
  16 #include <aros/debug.h>
  17
  18 #ifdef UtilityBase
  19     #undef UtilityBase
  20 #endif
  21 #define UtilityBase rambase->utilitybase
  22
  23 extern STRPTR Strdup(struct rambase *rambase, STRPTR string);
  24 extern void Strfree(struct rambase *rambase, STRPTR string);
  25
  26 typedef struct _HashNode
  27 {
  28     struct Node  node;
  29     void        *key;
  30     struct List  requests;
  31 } HashNode;
  32
  33 static HashNode *find(struct rambase *rambase, HashTable *ht,
  34                       const void *key, struct List *list);
  35
  36 HashTable *HashTable_new(struct rambase *rambase, ULONG size,
  37                          ULONG (*hash)(struct rambase *rambase,
  38                                        const void *key),
  39                          int (*compare)(struct rambase *rambase,
  40                                         const void *key1,
  41                                         const void *key2),
  42                          void (*delete)(struct rambase *rambase,
  43                                         void *key,
  44                                         struct List *list))
  45 {
  46     ULONG       i;              /* Loop variable */
  47     HashTable *ht = AllocVec(sizeof(HashTable), MEMF_ANY);
  48
  49     if (ht == NULL)
  50     {
  51         return NULL;
  52     }
  53
  54     ht->size = size;
  55     ht->nElems = 0;
  56     ht->array = AllocVec(sizeof(struct List)*size, MEMF_ANY);
  57
  58     if (ht->array == NULL)
  59     {
  60         FreeVec(ht);
  61
  62         return NULL;
  63     }
  64
  65     ht->hash = hash;
  66     ht->compare = compare;
  67     ht->delete = delete;
  68
  69     for (i = 0; i < size; i++)
  70     {
  71         NewList(&ht->array[i]);
  72     }
  73
  74     return ht;
  75 }
  76
  77
  78 /* TODO: Fix the double list thing, remove the (void *) hack */
  79 void HashTable_delete(struct rambase *rambase, HashTable *ht)
  80 {
  81     ULONG i;
  82
  83     for (i = 0; i < ht->size; i++)
  84     {
  85         while (!IsListEmpty(&ht->array[i]))
  86         {
  87             HashNode *hn = (HashNode *)RemHead(&ht->array[i]);
  88
  89             ht->delete(rambase, hn->key, (void *)&hn->requests);
  90             FreeVec(hn);
  91         }
  92     }
  93
  94     FreeVec(ht);
  95 }
  96
  97
  98 void HashTable_insert(struct rambase *rambase, HashTable *ht, void *key,
  99                       struct Receiver *rr)
 100 {
 101     ULONG      pos;
 102     HashNode *hn;
 103
 104     pos = ht->hash(rambase, key) % ht->size;
 105
 106     hn = find(rambase, ht, key, &ht->array[pos]);
 107
 108     if (hn == NULL)
 109     {
 110         /* There was no previous request for this entity */
 111         hn = AllocVec(sizeof(HashNode), MEMF_ANY);
 112
 113         if (hn == NULL)
 114         {
 115             return;
 116         }
 117
 118         hn->key = Strdup(rambase, key);
 119
 120         if (hn->key == NULL)
 121         {
 122             FreeVec(hn);
 123             return;
 124         }
 125
 126         NewList(&hn->requests);
 127         AddHead(&ht->array[pos], &hn->node);
 128     }
 129
 130     AddHead(&hn->requests, &rr->node);
 131
 132     ht->nElems++;
 133 }
 134
 135
 136 void HashTable_remove(struct rambase *rambase, HashTable *ht, void *key)
 137 {
 138     HashNode    *hn;
 139     ULONG        pos;
 140     struct Node *tempNode;
 141     struct List *list;
 142
 143     pos = ht->hash(rambase, key) % ht->size;
 144     list = &ht->array[pos];
 145
 146     ForeachNodeSafe(list, hn, tempNode)
 147     {
 148         if (ht->compare(rambase, key, hn->key) == 0)
 149         {
 150             Remove(&hn->node);
 151             ht->delete(rambase, hn->key, (void *)&hn->requests);
 152             FreeVec(hn);
 153             break;
 154         }
 155     }
 156 }
 157
 158
 159 static HashNode *find(struct rambase *rambase, HashTable *ht,
 160                       const void *key, struct List *list)
 161 {
 162     HashNode *hn;               /* Loop variable */
 163
 164     ForeachNode(list, hn)
 165     {
 166         if (ht->compare(rambase, key, hn->key) == 0)
 167         {
 168             return hn;
 169         }
 170     }
 171
 172     return NULL;
 173 }
 174
 175
 176 struct List *HashTable_find(struct rambase *rambase, HashTable *ht,
 177                             const void *key)
 178 {
 179     HashNode *hn;
 180     ULONG     pos;
 181
 182     pos = ht->hash(rambase, key) % ht->size;
 183     hn = find(rambase, ht, key, &ht->array[pos]);
 184
 185     if (hn != NULL)
 186         return &hn->requests;
 187
 188     return NULL;
 189 }
 190
 191
 192 inline ULONG HashTable_size(HashTable *ht)
 193 {
 194     return ht->nElems;
 195 }
 196