Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

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(WvStringParm 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 *wvslots, const void *data, 00053 unsigned hash) const 00054 { 00055 WvListBase::IterBase i(wvslots[hash % numslots]); 00056 WvLink *prev; 00057 00058 i.rewind(); 00059 for (prev = i.cur(); prev->next; prev = i.next()) 00060 { 00061 if (compare(data, prev->next->data)) 00062 break; 00063 } 00064 return prev; 00065 } 00066 00067 00068 void *WvHashTableBase::genfind(WvListBase *wvslots, const void *data, 00069 unsigned hash) const 00070 { 00071 WvLink *prev = prevlink(wvslots, data, hash); 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 += wvslots[i].count(); 00085 return count; 00086 } 00087 00088 00089 bool WvHashTableBase::isempty() const 00090 { 00091 for (unsigned i = 0; i < numslots; i++) 00092 if (! wvslots[i].isempty()) 00093 return false; 00094 return true; 00095 } 00096 00097 00098 WvLink *WvHashTableBase::IterBase::next() 00099 { 00100 link = link->next; 00101 while (!link && tblindex < tbl->numslots - 1) 00102 link = tbl->wvslots[++tblindex].head.next; 00103 return link; 00104 }

Generated on Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7