libsablot/src/engine/hash.h

   1 /*
   2  * The contents of this file are subject to the Mozilla Public
   3  * License Version 1.1 (the "License"); you may not use this file
   4  * except in compliance with the License. You may obtain a copy of
   5  * the License at http://www.mozilla.org/MPL/
   6  *
   7  * Software distributed under the License is distributed on an "AS
   8  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
   9  * implied. See the License for the specific language governing
  10  * rights and limitations under the License.
  11  *
  12  * The Original Code is the Sablotron XSLT Processor.
  13  *
  14  * The Initial Developer of the Original Code is Ginger Alliance Ltd.
  15  * Portions created by Ginger Alliance are Copyright (C) 2000-2002
  16  * Ginger Alliance Ltd. All Rights Reserved.
  17  *
  18  * Contributor(s):
  19  *      Bob Jenkins <bob_jenkins@burtleburtle.net>
  20  *
  21  * Alternatively, the contents of this file may be used under the
  22  * terms of the GNU General Public License Version 2 or later (the
  23  * "GPL"), in which case the provisions of the GPL are applicable
  24  * instead of those above.  If you wish to allow use of your
  25  * version of this file only under the terms of the GPL and not to
  26  * allow others to use your version of this file under the MPL,
  27  * indicate your decision by deleting the provisions above and
  28  * replace them with the notice and other provisions required by
  29  * the GPL.  If you do not delete the provisions above, a recipient
  30  * may use your version of this file under either the MPL or the
  31  * GPL.
  32  */
  33
  34 /*
  35  * based on hash function and code by Bob Jenkins, <bob_jenkins@burtleburtle.net>, 1996.
  36  */
  37
  38 #if !defined(HashHIncl)
  39 #define HashHIncl
  40
  41 // GP: clean
  42
  43 #include "base.h"
  44 #include "datastr.h"
  45 #include "arena.h"
  46
  47 class Processor;
  48 class SabArena;
  49
  50 //
  51 //      HashItem
  52 //      an item in the hash table. Contains part of the unique ID, the key and associated stuff (a void*).
  53 //
  54
  55 class HashItem : public SabArenaMember
  56 {
  57 public:
  58     HashItem(const char *key_, oolong code_, const void *stuff_, int age_, SabArena *arena_)
  59         : key( (char*)key_, arena_ ), code( code_ ), stuff( stuff_ ),
  60           age( age_ ), next( NULL )
  61     {};
  62     const SabArenaStr key;
  63     oolong code;
  64     const void *stuff;
  65     int age;
  66     HashItem *next;
  67 };
  68
  69 //
  70 //      HashItemList
  71 //      used for the list of buckets
  72 //
  73
  74 class HashItemList : public PList<HashItem*>
  75 {
  76     friend class HashTable;
  77     HashItemList( int logSize_ )
  78         : PList<HashItem*>( logSize_ )
  79     {}
  80 };
  81
  82 //
  83 //      HashTable
  84 //      Simple hash table. It can grow, the items have a unique ID which allows quick lookup
  85 //      of the key as well as the associated value.
  86 //
  87
  88 class HashTable
  89 {
  90 public:
  91     // initialize the hash
  92     HashTable(SabArena *arena_, int logSize_);
  93
  94      // destroy the hash
  95     ~HashTable();
  96
  97     // insert an item, returning its id (if found as well as if not)
  98     void insert(const Str& key, HashId& id, const void *data = NULL );
  99
 100     void insert(const char *key, HashId& id, const void *data = NULL )
 101     {
 102         insert(Str(key), id, data);
 103     };
 104
 105     HashId insert(const Str& key);
 106
 107     HashId insert(const char *key, const void *data = NULL )
 108     {
 109         return insert(Str(key));
 110     };
 111
 112
 113
 114     // look up an item, returning ITEM_NOT_FOUND and data==NULL if not found
 115     HashId lookup(const Str& key, const void **data = NULL ) const;
 116
 117     // return the key for a given id, asserting it exists
 118     const Str& getKey(HashId id) const;
 119
 120     void initialize();
 121     void destroy(Sit S);
 122
 123 #ifdef _DEBUG
 124     void dump() const;
 125 #endif
 126
 127 protected:
 128     oolong codeToIndex(oolong code) const;
 129     HashItem* expandWatching(oolong hashed);
 130     Bool lookupOrPreceding(const Str& key, oolong hashed, HashItem *&p) const;
 131     HashItemList buckets;   // the list of buckets
 132     SabArena *theArena;            // the arena to be used for hash items
 133     Processor *proc;
 134     int visitedBuckets,
 135         itemsCount,
 136         logSize;
 137     void report(Sit S, MsgType type, MsgCode code, const Str& arg1, const Str& arg2);
 138 private:
 139     Str *_theEmptyKey; /* __PH__ */
 140 };
 141
 142 #endif //HashHIncl