1| /*
    2|   Copyright (C) 1997-2000 Shigeru Chiba, University of Tsukuba.
    3| 
    4|   Permission to use, copy, distribute and modify this software and   
    5|   its documentation for any purpose is hereby granted without fee,        
    6|   provided that the above copyright notice appear in all copies and that 
    7|   both that copyright notice and this permission notice appear in 
    8|   supporting documentation.
    9| 
   10|   Shigeru Chiba makes no representations about the suitability of this 
   11|   software for any purpose.  It is provided "as is" without express or
   12|   implied warranty.
   13| */
   14| /*
   15|   Copyright (c) 1995, 1996 Xerox Corporation.
   16|   All Rights Reserved.
   17| 
   18|   Use and copying of this software and preparation of derivative works
   19|   based upon this software are permitted. Any copy of this software or
   20|   of any derivative work must include the above copyright notice of
   21|   Xerox Corporation, this paragraph and the one after it.  Any
   22|   distribution of this software or derivative works must comply with all
   23|   applicable United States export control laws.
   24| 
   25|   This software is made available AS IS, and XEROX CORPORATION DISCLAIMS
   26|   ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE
   27|   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   28|   PURPOSE, AND NOTWITHSTANDING ANY OTHER PROVISION CONTAINED HEREIN, ANY
   29|   LIABILITY FOR DAMAGES RESULTING FROM THE SOFTWARE OR ITS USE IS
   30|   EXPRESSLY DISCLAIMED, WHETHER ARISING IN CONTRACT, TORT (INCLUDING
   31|   NEGLIGENCE) OR STRICT LIABILITY, EVEN IF XEROX CORPORATION IS ADVISED
   32|   OF THE POSSIBILITY OF SUCH DAMAGES.
   33| */
   34| 
   35| //  Hash Table
   36| 
   37| #ifndef _hash_h
   38| #define _hash_h
   39| 
   40| #include <iosfwd>
   41| #include "types.h"
   42| 
   43| typedef void* HashValue;
   44| struct HashTableEntry;
   45| 
   46| class HashTable : public LightObject {
   47| public:
   48|     HashTable();
   49|     HashTable(int) {}
   50|     void MakeTable();
   51|     bool IsEmpty();
   52|     void Dump(std::ostream&);
   53|     int AddEntry(char* key, HashValue value, int* index = 0);
   54|     int AddEntry(bool, char* key, int len, HashValue value, int* index = 0);
   55| 
   56|     int AddEntry(char* key, int len, HashValue value, int* index = 0) {
   57|         return AddEntry(TRUE, key, len, value, index);
   58|     }
   59| 
   60|     // allow a duplicated entry to be inserted
   61|     int AddDupEntry(char* key, int len, HashValue value, int* index = 0) {
   62|         return AddEntry(FALSE, key, len, value, index);
   63|     }
   64| 
   65|     bool Lookup(char* key, HashValue* value);
   66|     bool Lookup(char* key, int len, HashValue* value);
   67|     bool LookupEntries(char* key, int len, HashValue* value, int& nth);
   68|     HashValue Peek(int index);
   69|     bool RemoveEntry(char* key);
   70|     bool RemoveEntry(char* key, int len);
   71|     void ReplaceValue(int index, HashValue value);
   72| 
   73| protected:
   74|     char* KeyString(char* key);
   75|     char* KeyString(char* key, int len);
   76| 
   77|     bool Lookup2(char* key, HashValue* val, int* index);
   78|     bool Lookup2(char* key, int len, HashValue* val, int* index);
   79|     static uint NextPrimeNumber(uint number);
   80|     bool GrowTable(int increment);
   81|     unsigned int StringToInt(char*);
   82|     unsigned int StringToInt(char*, int);
   83|     int HashFunc(unsigned int p, int n);
   84| 
   85| protected:
   86|     HashTableEntry      *entries;
   87|     int               Size; // the max number of entries.
   88|                              // should be a prime number
   89|     int        Prime2;
   90| };
   91| 
   92| class BigHashTable : public HashTable {
   93| public:
   94|     BigHashTable();
   95| };
   96| 
   97| #endif /* _hash_h */