src/hash.h

   1 /*
   2  * Copyright (C) 2003, 2004, 2005, 2006, 2007
   3  * Robert Lougher <rob@lougher.org.uk>.
   4  *
   5  * This file is part of JamVM.
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2,
  10  * or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  20  */
  21
  22 #include "thread.h"
  23
  24 typedef struct hash_entry {
  25     void *data;
  26     int hash;
  27 } HashEntry;
  28
  29 typedef struct hash_table {
  30     HashEntry *hash_table;
  31     int hash_size;
  32     int hash_count;
  33     VMLock lock;
  34 } HashTable;
  35
  36 extern void resizeHash(HashTable *table, int new_size);
  37 extern void lockHashTable0(HashTable *table, Thread *self);
  38 extern void unlockHashTable0(HashTable *table, Thread *self);
  39
  40 #define initHashTable(table, initial_size, create_lock)                            \
  41 {                                                                                  \
  42     table.hash_table = (HashEntry*)gcMemMalloc(sizeof(HashEntry)*initial_size);    \
  43     memset(table.hash_table, 0, sizeof(HashEntry)*initial_size);                   \
  44     table.hash_size = initial_size;                                                \
  45     table.hash_count = 0;                                                          \
  46     if(create_lock)                                                                \
  47         initVMLock(table.lock);                                                    \
  48 }
  49
  50 #define lockHashTable(table)                                                       \
  51     lockHashTable0(&table, threadSelf());
  52
  53 #define unlockHashTable(table)                                                     \
  54     unlockHashTable0(&table, threadSelf());
  55
  56 #define findHashEntry(table, ptr, ptr2, add_if_absent, scavenge, locked)           \
  57 {                                                                                  \
  58     int hash = HASH(ptr);                                                          \
  59     int i;                                                                         \
  60                                                                                    \
  61     Thread *self;                                                                  \
  62     if(locked) {                                                                   \
  63         self = threadSelf();                                                       \
  64         lockHashTable0(&table, self);                                              \
  65     }                                                                              \
  66                                                                                    \
  67     i = hash & (table.hash_size - 1);                                              \
  68                                                                                    \
  69     for(;;) {                                                                      \
  70         ptr2 = table.hash_table[i].data;                                           \
  71         if((ptr2 == NULL) || (COMPARE(ptr, ptr2, hash, table.hash_table[i].hash))) \
  72             break;                                                                 \
  73                                                                                    \
  74         i = (i+1) & (table.hash_size - 1);                                         \
  75     }                                                                              \
  76                                                                                    \
  77     if(ptr2) {                                                                     \
  78         ptr2 = FOUND(ptr2);                                                        \
  79     } else                                                                         \
  80         if(add_if_absent) {                                                        \
  81             table.hash_table[i].hash = hash;                                       \
  82             ptr2 = table.hash_table[i].data = PREPARE(ptr);                        \
  83                                                                                    \
  84             if(ptr2) {                                                             \
  85                 table.hash_count++;                                                \
  86                 if((table.hash_count * 4) > (table.hash_size * 3)) {               \
  87                     int new_size;                                                  \
  88                     if(scavenge) {                                                 \
  89                         HashEntry *entry = table.hash_table;                       \
  90                         int cnt = table.hash_count;                                \
  91                         for(; cnt; entry++) {                                      \
  92                             void *data = entry->data;                              \
  93                             if(data) {                                             \
  94                                 if(SCAVENGE(data)) {                               \
  95                                     entry->data = NULL;                            \
  96                                     table.hash_count--;                            \
  97                                 }                                                  \
  98                                 cnt--;                                             \
  99                             }                                                      \
 100                         }                                                          \
 101                         if((table.hash_count * 3) > (table.hash_size * 2))         \
 102                             new_size = table.hash_size*2;                          \
 103                         else                                                       \
 104                             new_size = table.hash_size;                            \
 105                     } else                                                         \
 106                         new_size = table.hash_size*2;                              \
 107                                                                                    \
 108                     resizeHash(&table, new_size);                                  \
 109                 }                                                                  \
 110             }                                                                      \
 111         }                                                                          \
 112                                                                                    \
 113     if(locked)                                                                     \
 114         unlockHashTable0(&table, self);                                            \
 115 }
 116
 117 #define deleteHashEntry(table, ptr, locked)                                        \
 118 {                                                                                  \
 119     int hash = HASH(ptr);                                                          \
 120     void *ptr2;                                                                    \
 121     int i;                                                                         \
 122                                                                                    \
 123     Thread *self;                                                                  \
 124     if(locked) {                                                                   \
 125         self = threadSelf();                                                       \
 126         lockHashTable0(&table, self);                                              \
 127     }                                                                              \
 128                                                                                    \
 129     i = hash & (table.hash_size - 1);                                              \
 130                                                                                    \
 131     for(;;) {                                                                      \
 132         ptr2 = table.hash_table[i].data;                                           \
 133         if((ptr2 == NULL) || (COMPARE(ptr, ptr2, hash, table.hash_table[i].hash))) \
 134             break;                                                                 \
 135                                                                                    \
 136         i = (i+1) & (table.hash_size - 1);                                         \
 137     }                                                                              \
 138                                                                                    \
 139     if(ptr2)                                                                       \
 140         table.hash_table[i].data = DELETED;                                        \
 141                                                                                    \
 142     if(locked)                                                                     \
 143         unlockHashTable0(&table, self);                                            \
 144 }
 145
 146 #define hashIterate(table)                                                         \
 147 {                                                                                  \
 148     HashEntry *entry = table.hash_table;                                           \
 149     int cnt = table.hash_count;                                                    \
 150                                                                                    \
 151     while(cnt) {                                                                   \
 152         void *data = entry++->data;                                                \
 153         if(data) {                                                                 \
 154             ITERATE(data);                                                         \
 155             cnt--;                                                                 \
 156         }                                                                          \
 157     }                                                                              \
 158 }
 159
 160 #define hashIterateP(table)                                                        \
 161 {                                                                                  \
 162     HashEntry *entry = table.hash_table;                                           \
 163     int cnt = table.hash_count;                                                    \
 164                                                                                    \
 165     while(cnt) {                                                                   \
 166         void **data_pntr = &entry++->data;                                         \
 167         if(*data_pntr) {                                                           \
 168             ITERATE(data_pntr);                                                    \
 169             cnt--;                                                                 \
 170         }                                                                          \
 171     }                                                                              \
 172 }
 173
 174 #define gcFreeHashTable(table)                                                     \
 175     gcMemFree(table.hash_table);
 176
 177 #define freeHashTable(table)                                                       \
 178     gcMemFree(table.hash_table);
 179