/* mapping.hpp -- an associative array that maps strings into arbitrary fixed-length values * by pts@fazekas.hu at Sat Mar 23 16:01:55 CET 2002 */ #ifdef __GNUC__ #ifndef __clang__ #pragma interface #endif #endif #ifndef MAPPING_HPP #define MAPPING_HPP 1 #include "config2.h" #include "gensi.hpp" class Mapping { /** A mapping is an assicative array whose keys are arbitrary binary strings * and its values are arbirary fixed-length data. The Mapping class is * abstract. The longest key which can be stored in a Mapping::Gen has * length `(slen_t)-3'. The caller must verify that she doesn't try to * call us with a longer string. */ class Gen { public: inline virtual ~Gen() {} /** Returns the length of one data value (same for all values, determined * at construction of Gen). */ inline slen_t getDataLen() const { return datalen; } /** Returns the number of keys currently in this Mapping. */ inline slen_t getLength() const { return len; } /** Returns the number of key positions allocated for this Mapping. This * number may or may not have meaning, depending on the implementation. */ inline slen_t getAlloced() const { return len; } /** * Updates or extends the mapping with the specified key/value pair. * @param data must point to an area of length getDataLen(). That * area will be copied (memcpy()) by set(). * @return true if key previously hasn't existed */ virtual bool set(char const*key, slen_t keylen, char const*data) =0; /** @return the address of the data that corresponds to param * `key', or NULLP if `key' was not found. The returned value is valid * until the next modification (.set(), deletee() methods). */ virtual char* get(char const*key, slen_t keylen) =0; /** * Updates mapping with the specified key/value pair. Leaves it unchanged * if the specified key doesn't exist. Calls get() and memcpy() to do the * job. * @param data must point to an area of length getDataLen(). That * area will be copied by set(). * @return true if key previously hasn't existed */ bool update(char const*key, slen_t keylen, char const*data); /** Calls get to do the job. */ inline bool exists(char const*key, slen_t keylen) { return NULLP!=get(key, keylen); } /** * Deletes the specified `key' from the mapping. * @param data must point to an area of length getDataLen(). That * area will be copied by set(). * @return true if key previously hasn't existed */ virtual bool deletee(char const*key, slen_t keylen) =0; /** The user must ensure that she isn't updating the mapping while walking. * @param key (out) is set to NULLP on empty mapping. */ virtual void getFirst(char const*const*& key, slen_t &keylen, char *& data) =0; /** The user must ensure that she isn't updating the mapping while walking. * @param key (out) is set to NULLP if there are no more elements */ virtual void getNext (char const*const*& key, slen_t &keylen, char *& data) =0; protected: slen_t datalen, len, alloced; }; /** Double hashing. Still abstract. */ class DoubleHash: public Gen { public: inline virtual ~DoubleHash() {} /** If it modifies `scale', then it must modify alloced, may modify minlen * and maxused, and must not modify anything else. If it does not modify * `scale', it must not modify anything else. After it returns, * obj_assert() must hold. Must not copy or (re)allocate memory, * rehashing is not done by vi_scale(). rehash() calls vi_scale(), and * rehash() does the real reallocation. */ virtual void vi_scale() =0; /** First hash function. Must return a value in 0..alloced-1 */ virtual slen_t vi_h1(char const*key, slen_t keylen) =0; /** Second hash function. Must return a value in 1..alloced-1, which is * realatively prime to the value returned by vi_h2(). */ virtual slen_t vi_h2(char const*key, slen_t keylen) =0; /** Destruct and free resources used by data. Called by deletee(). */ virtual void vi_dtor(char *data) =0; /** Called by set() and deletee() ?? */ virtual bool set (char const* key, slen_t keylen, char const*data); virtual char*get (char const* key, slen_t keylen); virtual bool deletee (char const* key, slen_t keylen); virtual void getFirst(char const*const*&key, slen_t &keylen, char *& data); virtual void getNext (char const*const*&key, slen_t &keylen, char *& data); /** Delete everything. */ void clear(); protected: void rehash(); /** @return true */ bool obj_assert(); /** `keylen==(slen_t)-1' indicates a place never used, * `keylen==(slen_t)-2' indicates a deleted place * Before changing the value of NEVER_USED, please update the memset(...) * in rehash(). */ BEGIN_STATIC_ENUM1(slen_t) NEVER_USED=(slen_t)-1, DELETED=(slen_t)-2 END_STATIC_ENUM() // static const slen_t NEVER_USED=(slen_t)-1, DELETED=(slen_t)-2; struct Ary { slen_t keylen; /** data is located at keydata, key is located keydata-datalen */ char *keydata; } *ary; /* The minimum number of keys before rehashing. */ slen_t minlen; /* The maximum number of keys before rehashing. */ slen_t maxused; /* The number of used places. A place is used unless it is NEVER_USED */ slen_t used; /** Used by the implementor of vi_scale. */ unsigned scale; }; /** Simple prime modulus double hashing with a factor of around 1.5 * between `alloced' scales. This class is not abstract anymore. */ class DoubleHash15: public DoubleHash { public: DoubleHash15(slen_t datalen_); virtual ~DoubleHash15(); virtual void vi_scale(); /** @return key % Prime */ virtual slen_t vi_h1(char const*key, slen_t keylen); /** @return (key % (Prime-1))+1 */ virtual slen_t vi_h2(char const*key, slen_t keylen); /** No-op. */ virtual void vi_dtor(char *data); }; public: typedef DoubleHash15 H; }; #endif