1 /* mapping.hpp -- an associative array that maps strings into arbitrary fixed-length values 2 * by pts@fazekas.hu at Sat Mar 23 16:01:55 CET 2002 3 */ 4 5 #ifdef __GNUC__ 6 #ifndef __clang__ 7 #pragma interface 8 #endif 9 #endif 10 11 #ifndef MAPPING_HPP 12 #define MAPPING_HPP 1 13 14 #include "config2.h" 15 #include "gensi.hpp" 16 17 class Mapping { 18 /** A mapping is an assicative array whose keys are arbitrary binary strings 19 * and its values are arbirary fixed-length data. The Mapping class is 20 * abstract. The longest key which can be stored in a Mapping::Gen has 21 * length `(slen_t)-3'. The caller must verify that she doesn't try to 22 * call us with a longer string. 23 */ 24 class Gen { 25 public: ~Gen()26 inline virtual ~Gen() {} 27 /** Returns the length of one data value (same for all values, determined 28 * at construction of Gen). 29 */ getDataLen() const30 inline slen_t getDataLen() const { return datalen; } 31 /** Returns the number of keys currently in this Mapping. */ getLength() const32 inline slen_t getLength() const { return len; } 33 /** Returns the number of key positions allocated for this Mapping. This 34 * number may or may not have meaning, depending on the implementation. 35 */ getAlloced() const36 inline slen_t getAlloced() const { return len; } 37 /** 38 * Updates or extends the mapping with the specified key/value pair. 39 * @param data must point to an area of length getDataLen(). That 40 * area will be copied (memcpy()) by set(). 41 * @return true if key previously hasn't existed 42 */ 43 virtual bool set(char const*key, slen_t keylen, char const*data) =0; 44 /** @return the address of the data that corresponds to param 45 * `key', or NULLP if `key' was not found. The returned value is valid 46 * until the next modification (.set(), deletee() methods). 47 */ 48 virtual char* get(char const*key, slen_t keylen) =0; 49 /** 50 * Updates mapping with the specified key/value pair. Leaves it unchanged 51 * if the specified key doesn't exist. Calls get() and memcpy() to do the 52 * job. 53 * @param data must point to an area of length getDataLen(). That 54 * area will be copied by set(). 55 * @return true if key previously hasn't existed 56 */ 57 bool update(char const*key, slen_t keylen, char const*data); 58 59 /** Calls get to do the job. */ exists(char const * key,slen_t keylen)60 inline bool exists(char const*key, slen_t keylen) { return NULLP!=get(key, keylen); } 61 62 /** 63 * Deletes the specified `key' from the mapping. 64 * @param data must point to an area of length getDataLen(). That 65 * area will be copied by set(). 66 * @return true if key previously hasn't existed 67 */ 68 virtual bool deletee(char const*key, slen_t keylen) =0; 69 70 /** The user must ensure that she isn't updating the mapping while walking. 71 * @param key (out) is set to NULLP on empty mapping. 72 */ 73 virtual void getFirst(char const*const*& key, slen_t &keylen, char *& data) =0; 74 /** The user must ensure that she isn't updating the mapping while walking. 75 * @param key (out) is set to NULLP if there are no more elements 76 */ 77 virtual void getNext (char const*const*& key, slen_t &keylen, char *& data) =0; 78 79 protected: 80 slen_t datalen, len, alloced; 81 }; 82 83 /** Double hashing. Still abstract. */ 84 class DoubleHash: public Gen { 85 public: ~DoubleHash()86 inline virtual ~DoubleHash() {} 87 /** If it modifies `scale', then it must modify alloced, may modify minlen 88 * and maxused, and must not modify anything else. If it does not modify 89 * `scale', it must not modify anything else. After it returns, 90 * obj_assert() must hold. Must not copy or (re)allocate memory, 91 * rehashing is not done by vi_scale(). rehash() calls vi_scale(), and 92 * rehash() does the real reallocation. 93 */ 94 virtual void vi_scale() =0; 95 /** First hash function. Must return a value in 0..alloced-1 */ 96 virtual slen_t vi_h1(char const*key, slen_t keylen) =0; 97 /** Second hash function. Must return a value in 1..alloced-1, which is 98 * realatively prime to the value returned by vi_h2(). 99 */ 100 virtual slen_t vi_h2(char const*key, slen_t keylen) =0; 101 /** Destruct and free resources used by data. Called by deletee(). */ 102 virtual void vi_dtor(char *data) =0; 103 104 /** Called by set() and deletee() ?? */ 105 virtual bool set (char const* key, slen_t keylen, char const*data); 106 virtual char*get (char const* key, slen_t keylen); 107 virtual bool deletee (char const* key, slen_t keylen); 108 virtual void getFirst(char const*const*&key, slen_t &keylen, char *& data); 109 virtual void getNext (char const*const*&key, slen_t &keylen, char *& data); 110 /** Delete everything. */ 111 void clear(); 112 protected: 113 void rehash(); 114 /** @return true */ 115 bool obj_assert(); 116 /** `keylen==(slen_t)-1' indicates a place never used, 117 * `keylen==(slen_t)-2' indicates a deleted place 118 * Before changing the value of NEVER_USED, please update the memset(...) 119 * in rehash(). 120 */ 121 BEGIN_STATIC_ENUM1(slen_t) NEVER_USED=(slen_t)-1, DELETED=(slen_t)-2 END_STATIC_ENUM() 122 // static const slen_t NEVER_USED=(slen_t)-1, DELETED=(slen_t)-2; 123 struct Ary { 124 slen_t keylen; 125 /** data is located at keydata, key is located keydata-datalen */ 126 char *keydata; 127 } *ary; 128 /* The minimum number of keys before rehashing. */ 129 slen_t minlen; 130 /* The maximum number of keys before rehashing. */ 131 slen_t maxused; 132 /* The number of used places. A place is used unless it is NEVER_USED */ 133 slen_t used; 134 /** Used by the implementor of vi_scale. */ 135 unsigned scale; 136 }; 137 138 /** Simple prime modulus double hashing with a factor of around 1.5 139 * between `alloced' scales. This class is not abstract anymore. 140 */ 141 class DoubleHash15: public DoubleHash { 142 public: 143 DoubleHash15(slen_t datalen_); 144 virtual ~DoubleHash15(); 145 virtual void vi_scale(); 146 /** @return key % Prime */ 147 virtual slen_t vi_h1(char const*key, slen_t keylen); 148 /** @return (key % (Prime-1))+1 */ 149 virtual slen_t vi_h2(char const*key, slen_t keylen); 150 /** No-op. */ 151 virtual void vi_dtor(char *data); 152 }; 153 public: 154 typedef DoubleHash15 H; 155 }; 156 157 #endif 158