workbench/devs/ram_handler/HashTable.c

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