Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

wvhashtable.cc

Go to the documentation of this file.
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Small, efficient, type-safe hash table class.  See wvhashtable.h.
00006  */
00007 #include "wvhashtable.h"
00008 #include "wvstring.h"
00009 
00010 // Note: this hash function is case-insensitive since it ignores the
00011 // bit in ASCII that defines case.  You may want to take advantage of this.
00012 unsigned WvHash(const char *s)
00013 {
00014     unsigned hash = 0, slide, andval;
00015     if (!s) return 0;
00016     
00017     slide = sizeof(hash)*8 - 5;
00018     andval = 0x1F << slide;
00019     
00020     while (*s)
00021         hash = (hash<<5) ^ (*(s++) & 0x1F) ^ ((hash & andval) >> slide);
00022     
00023     return hash;
00024 }
00025 
00026 unsigned WvHash(const WvString &s)
00027 {
00028     return !s ? 0 : WvHash((const char *)s);
00029 }
00030 
00031 // FIXME: does this suck?
00032 unsigned WvHash(const int &i)
00033 {
00034     return i;
00035 }
00036 
00037 
00038 // we do not accept the _numslots value directly.  Instead, we find the
00039 // next number of slots which is >= _numslots and one less then a power
00040 // of 2.  This usually results in a fairly good hash table size.
00041 WvHashTableBase::WvHashTableBase(unsigned _numslots)
00042 {
00043     int slides = 1;
00044     while ((_numslots >>= 1) != 0)
00045         slides++;
00046     numslots = (1 << slides) - 1;
00047 }
00048 
00049 
00050 // never returns NULL.  If the object is not found, the 'previous' link
00051 // is the last one in the list.
00052 WvLink *WvHashTableBase::prevlink(WvListBase *slots, const void *data,
00053                               unsigned hash, Comparator *comp)
00054 {
00055     WvListBase::IterBase i(slots[hash % numslots]);
00056     WvLink *prev;
00057     
00058     i.rewind();
00059     for (prev = i.cur(); prev->next; prev = i.next())
00060     {
00061         if (comp(data, prev->next->data))
00062             break;
00063     }
00064     return prev;
00065 }
00066 
00067 
00068 void *WvHashTableBase::genfind(WvListBase *slots, const void *data,
00069                               unsigned hash, Comparator *comp)
00070 {
00071     WvLink *prev = prevlink(slots, data, hash, comp);
00072     if (prev->next)
00073         return prev->next->data;
00074     else
00075         return NULL;
00076 }
00077 
00078 
00079 size_t WvHashTableBase::count() const
00080 {
00081     size_t count = 0;
00082     
00083     for (unsigned i = 0; i < numslots; i++)
00084         count += slots[i].count();
00085     return count;
00086 }
00087 
00088 
00089 WvLink *WvHashTableBase::IterBase::next()
00090 {
00091     link = link->next;
00092     while (!link && tblindex < tbl->numslots - 1)
00093         link = tbl->slots[++tblindex].head.next;
00094     return link;
00095 }

Generated on Fri Apr 5 15:16:51 2002 for WvStreams by doxygen1.2.15