Back to index

plt-scheme  4.2.1
wb_hash.cxx
Go to the documentation of this file.
00001 /*
00002  * File:             wb_hash.cc
00003  * Purpose:   Hash table implementation
00004  * Author:           Julian Smart
00005  * Created:   1993
00006  * Updated:   August 1994
00007  * Copyright: (c) 2004-2009 PLT Scheme Inc.
00008  * Copyright: (c) 1993, AIAI, University of Edinburgh
00009  */
00010 
00011 #pragma implementation "wx_hash.h"
00012 
00013 #if defined(_MSC_VER)
00014 # include "wx.h"
00015 #else
00016 # ifdef wx_xt
00017 #  define  Uses_wxHashTable
00018 #  include "wx.h"
00019 # else
00020 #  include "common.h"
00021 #  include "wx_list.h"
00022 #  include "wx_hash.h"
00023 #  include "wx_types.h"
00024 # endif
00025 #endif
00026 
00027 #include <string.h>
00028 #include <stdarg.h>
00029 
00030 wxHashTable::wxHashTable (int, int size)
00031  : wxObject(WXGC_NO_CLEANUP)
00032 {
00033   int i;
00034   wxList **ll;
00035 
00036   __type = wxTYPE_HASH_TABLE;
00037   n = size;
00038   current_position = -1;
00039   current_node = NULL;
00040 
00041   ll = new WXGC_PTRS wxList *[size];
00042   hash_table = ll;
00043   for (i = 0; i < size; i++) {
00044     hash_table[i] = NULL;
00045   }
00046 }
00047 
00048 wxHashTable::~wxHashTable (void)
00049 {
00050   int i;
00051   for (i = 0; i < n; i++) {
00052     if (hash_table[i]) {
00053       wxList *l;
00054       l = hash_table[i];
00055       DELETE_OBJ l;
00056     }
00057   }
00058 }
00059 
00060 wxList *wxHashTable::GetList(int position, KeyType ktype, Bool makeit)
00061 {
00062   wxList *l;
00063 
00064   l = hash_table[position];
00065 
00066   if (!l) {
00067     if (makeit) {
00068       l = new WXGC_PTRS wxList(ktype, FALSE);
00069       hash_table[position] = l;
00070     }
00071   }
00072   
00073   return l;
00074 }
00075 
00076 void wxHashTable::Put(long key, wxObject * object)
00077 {
00078   wxList *l;
00079 
00080   l = GetList(MakeKey(key));
00081 
00082   l->Append(key, object);
00083 }
00084 
00085 void wxHashTable::Put(const char *key, wxObject * object)
00086 {
00087   wxList *l;
00088 
00089   l = GetList(MakeKey(key), wxKEY_STRING);
00090 
00091   l->Append(key, object);
00092 }
00093 
00094 wxObject *wxHashTable::Get(long key)
00095 {
00096   wxList *l;
00097 
00098   l = GetList(MakeKey(key), wxKEY_INTEGER, FALSE);
00099 
00100   if (l) {
00101     wxNode *node;
00102     node = l->Find(key);
00103     if (node)
00104       return node->Data();
00105   }
00106 
00107   return NULL;
00108 }
00109 
00110 wxObject *wxHashTable::Get(const char *key)
00111 {
00112   wxList *l;
00113 
00114   l = GetList(MakeKey(key), wxKEY_STRING, FALSE);
00115 
00116   if (l) {
00117     wxNode *node;
00118     node = l->Find (key);
00119     if (node)
00120       return node->Data();
00121   }
00122 
00123   return NULL;
00124 }
00125 
00126 wxObject *wxHashTable::Delete(long key)
00127 {
00128   wxList *l;
00129 
00130   l = GetList(MakeKey(key), wxKEY_INTEGER, FALSE);
00131 
00132   if (l) {
00133     wxNode *node;
00134     node = l->Find(key);
00135     if (node) {
00136       wxObject *data;
00137       data = node->Data();
00138       l->DeleteNode(node);
00139       return data;
00140     }
00141   }
00142   return NULL;
00143 }
00144 
00145 wxObject *wxHashTable::Delete(const char *key)
00146 {
00147   wxList *l;
00148 
00149   l = GetList(MakeKey(key), wxKEY_STRING, FALSE);
00150 
00151   if (l) {
00152     wxNode *node;
00153     node = l->Find(key);
00154     if (node) {
00155       wxObject *data;
00156       data = node->Data();
00157       l->DeleteNode(node);
00158       return data;
00159     }
00160   }
00161 
00162   return NULL;
00163 }
00164 
00165 int wxHashTable::MakeKey(const char *string)
00166 {
00167   long int_key = 0;
00168 
00169   while (*string) {
00170     int_key += (unsigned char) *string++;
00171   }
00172 
00173   if (int_key < 0)
00174     int_key = -int_key;
00175 
00176   return int_key % n;
00177 }
00178 
00179 int wxHashTable::MakeKey(long int_key)
00180 {
00181   if (int_key < 0)
00182     int_key = -int_key;
00183 
00184   return int_key % n;
00185 }
00186 
00187 void wxHashTable::BeginFind (void)
00188 {
00189   current_position = -1;
00190   current_node = NULL;
00191 }
00192 
00193 wxNode *wxHashTable::Next (void)
00194 {
00195   wxNode *found = NULL;
00196   Bool end = FALSE;
00197   while (!end && !found) {
00198     if (!current_node) {
00199       current_position++;
00200       if (current_position >= n) {
00201        current_position = -1;
00202        current_node = NULL;
00203        end = TRUE;
00204       } else {
00205        wxList *l;
00206        l = hash_table[current_position];
00207        if (l) {
00208          current_node = l->First();
00209          found = current_node;
00210        }
00211       }
00212     } else {
00213       current_node = current_node->Next ();
00214       found = current_node;
00215     }
00216   }
00217   return found;
00218 }
00219 
00220 void wxHashTable::DeleteContents (Bool flag)
00221 {
00222   int i;
00223   for (i = 0; i < n; i++) {
00224     if (hash_table[i]) {
00225       wxList *l;
00226       l = hash_table[i];
00227       l->DeleteContents(flag);
00228     }
00229   }
00230 }
00231 
00232 void wxHashTable::Clear (void)
00233 {
00234   int i;
00235   for (i = 0; i < n; i++) {
00236     if (hash_table[i])  {
00237       wxList *l;
00238       l = hash_table[i];
00239       l->Clear();
00240     }
00241   }
00242 }
00243 
00244 
00245 
00246 /* This is a hash table implementation which does not lock the objects
00247    from garbage collection. */
00248 
00249 #ifdef MZ_PRECISE_GC
00250 typedef long *nlWidgetRef;
00251 # define nl_malloc_bucket_array(size) GC_malloc(size)
00252 # define nlGET_WIDGET(x) (*(long *)(x))
00253 # define nlGET_OBJECT(x) (((wxObject **)(x))[1])
00254 # define nlALLOC_WIDGET(w) { long *p; p = (long *)GC_malloc_atomic(sizeof(long)); w = p; }
00255 # define nlALLOC_OBJECT(o) { void *p; p = GC_malloc_weak_box(NULL, NULL, 0); o = (wxObject *)p; }
00256 #else
00257 # define nl_malloc_bucket_array(size) GC_malloc_atomic(size)
00258 typedef long nlWidgetRef;
00259 # define nlGET_WIDGET(x) x
00260 # define nlGET_OBJECT(x) x
00261 # define nlALLOC_WIDGET(w) /* empty */
00262 # define nlALLOC_OBJECT(w) /* empty */
00263 #endif
00264 
00265 typedef struct Bucket {
00266   nlWidgetRef widget;
00267   wxObject *object;
00268 } Bucket;
00269 
00270 /* because widgets are likely to be word-aligned */
00271 #define HASH(w) ((((unsigned long)w) >> 2) % numbuckets)
00272 
00273 #define FILL_FACTOR 2 /* inverted max fraction of hash table implying reash */
00274 
00275 wxNonlockingHashTable::wxNonlockingHashTable()
00276 {
00277   long i;
00278   Bucket *bs;
00279 
00280   numbuckets = 1001;
00281   bs = (Bucket *)nl_malloc_bucket_array(sizeof(Bucket) * numbuckets);
00282   buckets = bs;
00283   for (i = 0; i < numbuckets; i++) {
00284     buckets[i].widget = 0;
00285   }
00286   numwidgets = numused = 0;
00287 }
00288 
00289 wxNonlockingHashTable::~wxNonlockingHashTable()
00290 {
00291 }
00292 
00293 void wxNonlockingHashTable::Put(long widget, wxObject *object)
00294 {
00295   long i;
00296 
00297   if (FILL_FACTOR * numused >= numbuckets) {
00298     /* Rehash */
00299     Bucket *oldbuckets = buckets, *bs;
00300     long oldnumbuckets = numbuckets;
00301 
00302     if (FILL_FACTOR * numwidgets >= numbuckets)
00303       numbuckets = (numbuckets * FILL_FACTOR) + 1;
00304     /* else, just need to rehash after many deletions */
00305 
00306     bs = (Bucket *)nl_malloc_bucket_array(sizeof(Bucket) * numbuckets);
00307     buckets = bs;
00308     for (i = 0; i < numbuckets; i++) {
00309       buckets[i].widget = 0;
00310     }
00311 
00312     numwidgets = numused = 0;
00313     for (i = 0; i < oldnumbuckets; i++) {
00314       if (oldbuckets[i].widget && oldbuckets[i].object)
00315        Put(nlGET_WIDGET(oldbuckets[i].widget), nlGET_OBJECT(oldbuckets[i].object));
00316     }
00317   }
00318 
00319   i = HASH(widget);
00320   while (buckets[i].widget && buckets[i].object
00321         && (nlGET_WIDGET(buckets[i].widget) != widget)) {
00322     i = (i + 1) % numbuckets;
00323   }
00324   if (!buckets[i].widget)
00325     numused++;
00326   nlALLOC_WIDGET(buckets[i].widget);
00327   nlGET_WIDGET(buckets[i].widget) = widget;
00328   nlALLOC_OBJECT(buckets[i].object);
00329   nlGET_OBJECT(buckets[i].object) = object;
00330   numwidgets++;
00331 }
00332 
00333 wxObject *wxNonlockingHashTable::Get(long widget)
00334 {
00335   long i;
00336 
00337   i = HASH(widget);
00338   while (buckets[i].widget && (nlGET_WIDGET(buckets[i].widget) != widget)) {
00339     i = (i + 1) % numbuckets;
00340   }
00341 
00342   if (buckets[i].widget 
00343       && (nlGET_WIDGET(buckets[i].widget) == widget)
00344       && buckets[i].object) {
00345     wxObject *r;
00346     r = nlGET_OBJECT(buckets[i].object);
00347     return r;
00348   }
00349 
00350   return NULL;
00351 }
00352 
00353 void wxNonlockingHashTable::Delete(long widget)
00354 {
00355   long i;
00356 
00357   i = HASH(widget);
00358   while (buckets[i].widget && (nlGET_WIDGET(buckets[i].widget) != widget)) {
00359     i = (i + 1) % numbuckets;
00360   }
00361 
00362   if (buckets[i].widget && (nlGET_WIDGET(buckets[i].widget) == widget)) {
00363     buckets[i].object = NULL;
00364     --numwidgets;
00365     /* Don't decrement numused, since the widget half is still set;
00366        we should re-hash after enough deletions */
00367   }
00368 }
00369 
00370 /* not particularly fast... */
00371 void wxNonlockingHashTable::DeleteObject(wxObject *o)
00372 {
00373   long i;
00374   
00375   for (i = 0; i < numbuckets; i++) {
00376     if (buckets[i].widget && buckets[i].object && nlGET_OBJECT(buckets[i].object) == o)
00377       Delete(nlGET_WIDGET(buckets[i].widget));
00378   }
00379 }
00380