summaryrefslogtreecommitdiff
path: root/plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h')
-rw-r--r--plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h1379
1 files changed, 1379 insertions, 0 deletions
diff --git a/plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h b/plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h
new file mode 100644
index 0000000000..7729c6504a
--- /dev/null
+++ b/plugins/Dbx_kyoto/src/kyotocabinet/kcmap.h
@@ -0,0 +1,1379 @@
+/*************************************************************************************************
+ * Data mapping structures
+ * Copyright (C) 2009-2012 FAL Labs
+ * This file is part of Kyoto Cabinet.
+ * This program is free software: you can redistribute it and/or modify it under the terms of
+ * the GNU General Public License as published by the Free Software Foundation, either version
+ * 3 of the License, or any later version.
+ * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public License along with this program.
+ * If not, see <http://www.gnu.org/licenses/>.
+ *************************************************************************************************/
+
+
+#ifndef _KCMAP_H // duplication check
+#define _KCMAP_H
+
+#include <kccommon.h>
+#include <kcutil.h>
+
+namespace kyotocabinet { // common namespace
+
+
+/**
+ * Doubly-linked hash map.
+ * @param KEY the key type.
+ * @param VALUE the value type.
+ * @param HASH the hash functor.
+ * @param EQUALTO the equality checking functor.
+ */
+template <class KEY, class VALUE,
+ class HASH = std::hash<KEY>, class EQUALTO = std::equal_to<KEY> >
+class LinkedHashMap {
+ public:
+ class Iterator;
+ private:
+ struct Record;
+ /** The default bucket number of hash table. */
+ static const size_t MAPDEFBNUM = 31;
+ /** The mininum number of buckets to use mmap. */
+ static const size_t MAPZMAPBNUM = 32768;
+ public:
+ /**
+ * Iterator of records.
+ */
+ class Iterator {
+ friend class LinkedHashMap;
+ public:
+ /**
+ * Copy constructor.
+ * @param src the source object.
+ */
+ Iterator(const Iterator& src) : map_(src.map_), rec_(src.rec_) {
+ _assert_(true);
+ }
+ /**
+ * Get the key.
+ */
+ const KEY& key() {
+ _assert_(true);
+ return rec_->key;
+ }
+ /**
+ * Get the value.
+ */
+ VALUE& value() {
+ _assert_(true);
+ return rec_->value;
+ }
+ /**
+ * Assignment operator from the self type.
+ * @param right the right operand.
+ * @return the reference to itself.
+ */
+ Iterator& operator =(const Iterator& right) {
+ _assert_(true);
+ if (&right == this) return *this;
+ map_ = right.map_;
+ rec_ = right.rec_;
+ return *this;
+ }
+ /**
+ * Equality operator with the self type.
+ * @param right the right operand.
+ * @return true if the both are equal, or false if not.
+ */
+ bool operator ==(const Iterator& right) const {
+ _assert_(true);
+ return map_ == right.map_ && rec_ == right.rec_;
+ }
+ /**
+ * Non-equality operator with the self type.
+ * @param right the right operand.
+ * @return false if the both are equal, or true if not.
+ */
+ bool operator !=(const Iterator& right) const {
+ _assert_(true);
+ return map_ != right.map_ || rec_ != right.rec_;
+ }
+ /**
+ * Preposting increment operator.
+ * @return the iterator itself.
+ */
+ Iterator& operator ++() {
+ _assert_(true);
+ rec_ = rec_->next;
+ return *this;
+ }
+ /**
+ * Postpositive increment operator.
+ * @return an iterator of the old position.
+ */
+ Iterator operator ++(int) {
+ _assert_(true);
+ Iterator old(*this);
+ rec_ = rec_->next;
+ return old;
+ }
+ /**
+ * Preposting decrement operator.
+ * @return the iterator itself.
+ */
+ Iterator& operator --() {
+ _assert_(true);
+ if (rec_) {
+ rec_ = rec_->prev;
+ } else {
+ rec_ = map_->last_;
+ }
+ return *this;
+ }
+ /**
+ * Postpositive decrement operator.
+ * @return an iterator of the old position.
+ */
+ Iterator operator --(int) {
+ _assert_(true);
+ Iterator old(*this);
+ if (rec_) {
+ rec_ = rec_->prev;
+ } else {
+ rec_ = map_->last_;
+ }
+ return old;
+ }
+ private:
+ /**
+ * Constructor.
+ * @param map the container.
+ * @param rec the pointer to the current record.
+ */
+ explicit Iterator(LinkedHashMap* map, Record* rec) : map_(map), rec_(rec) {
+ _assert_(map);
+ }
+ /** The container. */
+ LinkedHashMap* map_;
+ /** The current record. */
+ Record* rec_;
+ };
+ /**
+ * Moving Modes.
+ */
+ enum MoveMode {
+ MCURRENT, ///< keep the current position
+ MFIRST, ///< move to the first
+ MLAST ///< move to the last
+ };
+ /**
+ * Default constructor.
+ */
+ explicit LinkedHashMap() :
+ buckets_(NULL), bnum_(MAPDEFBNUM), first_(NULL), last_(NULL), count_(0) {
+ _assert_(true);
+ initialize();
+ }
+ /**
+ * Constructor.
+ * @param bnum the number of buckets of the hash table.
+ */
+ explicit LinkedHashMap(size_t bnum) :
+ buckets_(NULL), bnum_(bnum), first_(NULL), last_(NULL), count_(0) {
+ _assert_(true);
+ if (bnum_ < 1) bnum_ = MAPDEFBNUM;
+ initialize();
+ }
+ /**
+ * Destructor.
+ */
+ ~LinkedHashMap() {
+ _assert_(true);
+ destroy();
+ }
+ /**
+ * Store a record.
+ * @param key the key.
+ * @param value the value.
+ * @param mode the moving mode.
+ * @return the pointer to the value of the stored record.
+ */
+ VALUE *set(const KEY& key, const VALUE& value, MoveMode mode) {
+ _assert_(true);
+ size_t bidx = hash_(key) % bnum_;
+ Record* rec = buckets_[bidx];
+ Record** entp = buckets_ + bidx;
+ while (rec) {
+ if (equalto_(rec->key, key)) {
+ rec->value = value;
+ switch (mode) {
+ default: {
+ break;
+ }
+ case MFIRST: {
+ if (first_ != rec) {
+ if (last_ == rec) last_ = rec->prev;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = NULL;
+ rec->next = first_;
+ first_->prev = rec;
+ first_ = rec;
+ }
+ break;
+ }
+ case MLAST: {
+ if (last_ != rec) {
+ if (first_ == rec) first_ = rec->next;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = last_;
+ rec->next = NULL;
+ last_->next = rec;
+ last_ = rec;
+ }
+ break;
+ }
+ }
+ return &rec->value;
+ } else {
+ entp = &rec->child;
+ rec = rec->child;
+ }
+ }
+ rec = new Record(key, value);
+ switch (mode) {
+ default: {
+ rec->prev = last_;
+ if (!first_) first_ = rec;
+ if (last_) last_->next = rec;
+ last_ = rec;
+ break;
+ }
+ case MFIRST: {
+ rec->next = first_;
+ if (!last_) last_ = rec;
+ if (first_) first_->prev = rec;
+ first_ = rec;
+ break;
+ }
+ }
+ *entp = rec;
+ count_++;
+ return &rec->value;
+ }
+ /**
+ * Remove a record.
+ * @param key the key.
+ * @return true on success, or false on failure.
+ */
+ bool remove(const KEY& key) {
+ _assert_(true);
+ size_t bidx = hash_(key) % bnum_;
+ Record* rec = buckets_[bidx];
+ Record** entp = buckets_ + bidx;
+ while (rec) {
+ if (equalto_(rec->key, key)) {
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ if (rec == first_) first_ = rec->next;
+ if (rec == last_) last_ = rec->prev;
+ *entp = rec->child;
+ count_--;
+ delete rec;
+ return true;
+ } else {
+ entp = &rec->child;
+ rec = rec->child;
+ }
+ }
+ return false;
+ }
+ /**
+ * Migrate a record to another map.
+ * @param key the key.
+ * @param dist the destination map.
+ * @param mode the moving mode.
+ * @return the pointer to the value of the migrated record, or NULL on failure.
+ */
+ VALUE* migrate(const KEY& key, LinkedHashMap* dist, MoveMode mode) {
+ _assert_(dist);
+ size_t hash = hash_(key);
+ size_t bidx = hash % bnum_;
+ Record* rec = buckets_[bidx];
+ Record** entp = buckets_ + bidx;
+ while (rec) {
+ if (equalto_(rec->key, key)) {
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ if (rec == first_) first_ = rec->next;
+ if (rec == last_) last_ = rec->prev;
+ *entp = rec->child;
+ count_--;
+ rec->child = NULL;
+ rec->prev = NULL;
+ rec->next = NULL;
+ bidx = hash % dist->bnum_;
+ Record* drec = dist->buckets_[bidx];
+ entp = dist->buckets_ + bidx;
+ while (drec) {
+ if (dist->equalto_(drec->key, key)) {
+ if (drec->child) rec->child = drec->child;
+ if (drec->prev) {
+ rec->prev = drec->prev;
+ rec->prev->next = rec;
+ }
+ if (drec->next) {
+ rec->next = drec->next;
+ rec->next->prev = rec;
+ }
+ if (dist->first_ == drec) dist->first_ = rec;
+ if (dist->last_ == drec) dist->last_ = rec;
+ *entp = rec;
+ delete drec;
+ switch (mode) {
+ default: {
+ break;
+ }
+ case MFIRST: {
+ if (dist->first_ != rec) {
+ if (dist->last_ == rec) dist->last_ = rec->prev;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = NULL;
+ rec->next = dist->first_;
+ dist->first_->prev = rec;
+ dist->first_ = rec;
+ }
+ break;
+ }
+ case MLAST: {
+ if (dist->last_ != rec) {
+ if (dist->first_ == rec) dist->first_ = rec->next;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = dist->last_;
+ rec->next = NULL;
+ dist->last_->next = rec;
+ dist->last_ = rec;
+ }
+ break;
+ }
+ }
+ return &rec->value;
+ } else {
+ entp = &drec->child;
+ drec = drec->child;
+ }
+ }
+ switch (mode) {
+ default: {
+ rec->prev = dist->last_;
+ if (!dist->first_) dist->first_ = rec;
+ if (dist->last_) dist->last_->next = rec;
+ dist->last_ = rec;
+ break;
+ }
+ case MFIRST: {
+ rec->next = dist->first_;
+ if (!dist->last_) dist->last_ = rec;
+ if (dist->first_) dist->first_->prev = rec;
+ dist->first_ = rec;
+ break;
+ }
+ }
+ *entp = rec;
+ dist->count_++;
+ return &rec->value;
+ } else {
+ entp = &rec->child;
+ rec = rec->child;
+ }
+ }
+ return NULL;
+ }
+ /**
+ * Retrieve a record.
+ * @param key the key.
+ * @param mode the moving mode.
+ * @return the pointer to the value of the corresponding record, or NULL on failure.
+ */
+ VALUE* get(const KEY& key, MoveMode mode) {
+ _assert_(true);
+ size_t bidx = hash_(key) % bnum_;
+ Record* rec = buckets_[bidx];
+ while (rec) {
+ if (equalto_(rec->key, key)) {
+ switch (mode) {
+ default: {
+ break;
+ }
+ case MFIRST: {
+ if (first_ != rec) {
+ if (last_ == rec) last_ = rec->prev;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = NULL;
+ rec->next = first_;
+ first_->prev = rec;
+ first_ = rec;
+ }
+ break;
+ }
+ case MLAST: {
+ if (last_ != rec) {
+ if (first_ == rec) first_ = rec->next;
+ if (rec->prev) rec->prev->next = rec->next;
+ if (rec->next) rec->next->prev = rec->prev;
+ rec->prev = last_;
+ rec->next = NULL;
+ last_->next = rec;
+ last_ = rec;
+ }
+ break;
+ }
+ }
+ return &rec->value;
+ } else {
+ rec = rec->child;
+ }
+ }
+ return NULL;
+ }
+ /**
+ * Remove all records.
+ */
+ void clear() {
+ _assert_(true);
+ if (count_ < 1) return;
+ Record* rec = last_;
+ while (rec) {
+ Record* prev = rec->prev;
+ delete rec;
+ rec = prev;
+ }
+ for (size_t i = 0; i < bnum_; i++) {
+ buckets_[i] = NULL;
+ }
+ first_ = NULL;
+ last_ = NULL;
+ count_ = 0;
+ }
+ /**
+ * Get the number of records.
+ */
+ size_t count() {
+ _assert_(true);
+ return count_;
+ }
+ /**
+ * Get an iterator at the first record.
+ */
+ Iterator begin() {
+ _assert_(true);
+ return Iterator(this, first_);
+ }
+ /**
+ * Get an iterator of the end sentry.
+ */
+ Iterator end() {
+ _assert_(true);
+ return Iterator(this, NULL);
+ }
+ /**
+ * Get an iterator at a record.
+ * @param key the key.
+ * @return the pointer to the value of the corresponding record, or NULL on failure.
+ */
+ Iterator find(const KEY& key) {
+ _assert_(true);
+ size_t bidx = hash_(key) % bnum_;
+ Record* rec = buckets_[bidx];
+ while (rec) {
+ if (equalto_(rec->key, key)) {
+ return Iterator(this, rec);
+ } else {
+ rec = rec->child;
+ }
+ }
+ return Iterator(this, NULL);
+ }
+ /**
+ * Get the reference of the key of the first record.
+ * @return the reference of the key of the first record.
+ */
+ const KEY& first_key() {
+ _assert_(true);
+ return first_->key;
+ }
+ /**
+ * Get the reference of the value of the first record.
+ * @return the reference of the value of the first record.
+ */
+ VALUE& first_value() {
+ _assert_(true);
+ return first_->value;
+ }
+ /**
+ * Get the reference of the key of the last record.
+ * @return the reference of the key of the last record.
+ */
+ const KEY& last_key() {
+ _assert_(true);
+ return last_->key;
+ }
+ /**
+ * Get the reference of the value of the last record.
+ * @return the reference of the value of the last record.
+ */
+ VALUE& last_value() {
+ _assert_(true);
+ return last_->value;
+ }
+ private:
+ /**
+ * Record data.
+ */
+ struct Record {
+ KEY key; ///< key
+ VALUE value; ///< value
+ Record* child; ///< child record
+ Record* prev; ///< previous record
+ Record* next; ///< next record
+ /** constructor */
+ explicit Record(const KEY& k, const VALUE& v) :
+ key(k), value(v), child(NULL), prev(NULL), next(NULL) {
+ _assert_(true);
+ }
+ };
+ /**
+ * Initialize fields.
+ */
+ void initialize() {
+ _assert_(true);
+ if (bnum_ >= MAPZMAPBNUM) {
+ buckets_ = (Record**)mapalloc(sizeof(*buckets_) * bnum_);
+ } else {
+ buckets_ = new Record*[bnum_];
+ for (size_t i = 0; i < bnum_; i++) {
+ buckets_[i] = NULL;
+ }
+ }
+ }
+ /**
+ * Clean up fields.
+ */
+ void destroy() {
+ _assert_(true);
+ Record* rec = last_;
+ while (rec) {
+ Record* prev = rec->prev;
+ delete rec;
+ rec = prev;
+ }
+ if (bnum_ >= MAPZMAPBNUM) {
+ mapfree(buckets_);
+ } else {
+ delete[] buckets_;
+ }
+ }
+ /** Dummy constructor to forbid the use. */
+ LinkedHashMap(const LinkedHashMap&);
+ /** Dummy Operator to forbid the use. */
+ LinkedHashMap& operator =(const LinkedHashMap&);
+ /** The functor of the hash function. */
+ HASH hash_;
+ /** The functor of the equalto function. */
+ EQUALTO equalto_;
+ /** The bucket array. */
+ Record** buckets_;
+ /** The number of buckets. */
+ size_t bnum_;
+ /** The first record. */
+ Record* first_;
+ /** The last record. */
+ Record* last_;
+ /** The number of records. */
+ size_t count_;
+};
+
+
+/**
+ * Memory-saving string hash map.
+ */
+class TinyHashMap {
+ public:
+ class Iterator;
+ private:
+ struct Record;
+ struct RecordComparator;
+ /** The default bucket number of hash table. */
+ static const size_t MAPDEFBNUM = 31;
+ /** The mininum number of buckets to use mmap. */
+ static const size_t MAPZMAPBNUM = 32768;
+ public:
+ /**
+ * Iterator of records.
+ */
+ class Iterator {
+ friend class TinyHashMap;
+ public:
+ /**
+ * Constructor.
+ * @param map the container.
+ * @note This object will not be invalidated even when the map object is updated once.
+ * However, phantom records may be retrieved if they are removed after creation of each
+ * iterator.
+ */
+ explicit Iterator(TinyHashMap* map) : map_(map), bidx_(-1), ridx_(0), recs_() {
+ _assert_(map);
+ step();
+ }
+ /**
+ * Destructor.
+ */
+ ~Iterator() {
+ _assert_(true);
+ free_records();
+ }
+ /**
+ * Get the key of the current record.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the key region of the current record, or NULL on failure.
+ */
+ const char* get_key(size_t* sp) {
+ _assert_(sp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *sp = rec.ksiz_;
+ return rec.kbuf_;
+ }
+ /**
+ * Get the value of the current record.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the value region of the current record, or NULL on failure.
+ */
+ const char* get_value(size_t* sp) {
+ _assert_(sp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *sp = rec.vsiz_;
+ return rec.vbuf_;
+ }
+ /**
+ * Get a pair of the key and the value of the current record.
+ * @param ksp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @param vbp the pointer to the variable into which the pointer to the value region is
+ * assigned.
+ * @param vsp the pointer to the variable into which the size of the value region is
+ * assigned.
+ * @return the pointer to the key region, or NULL on failure.
+ */
+ const char* get(size_t* ksp, const char** vbp, size_t* vsp) {
+ _assert_(ksp && vbp && vsp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *ksp = rec.ksiz_;
+ *vbp = rec.vbuf_;
+ *vsp = rec.vsiz_;
+ return rec.kbuf_;
+ }
+ /**
+ * Step the cursor to the next record.
+ */
+ void step() {
+ _assert_(true);
+ if (++ridx_ >= recs_.size()) {
+ ridx_ = 0;
+ free_records();
+ while (true) {
+ bidx_++;
+ if (bidx_ >= (int64_t)map_->bnum_) return;
+ read_records();
+ if (recs_.size() > 0) break;
+ }
+ }
+ }
+ private:
+ /**
+ * Read records of the current bucket.
+ */
+ void read_records() {
+ char* rbuf = map_->buckets_[bidx_];
+ while (rbuf) {
+ Record rec(rbuf);
+ size_t rsiz = sizeof(rec.child_) + sizevarnum(rec.ksiz_) + rec.ksiz_ +
+ sizevarnum(rec.vsiz_) + rec.vsiz_ + sizevarnum(rec.psiz_);
+ char* nbuf = new char[rsiz];
+ std::memcpy(nbuf, rbuf, rsiz);
+ recs_.push_back(nbuf);
+ rbuf = rec.child_;
+ }
+ }
+ /**
+ * Release recources of the current records.
+ */
+ void free_records() {
+ std::vector<char*>::iterator it = recs_.begin();
+ std::vector<char*>::iterator itend = recs_.end();
+ while (it != itend) {
+ char* rbuf = *it;
+ delete[] rbuf;
+ ++it;
+ }
+ recs_.clear();
+ }
+ /** Dummy constructor to forbid the use. */
+ Iterator(const Iterator&);
+ /** Dummy Operator to forbid the use. */
+ Iterator& operator =(const Iterator&);
+ /** The container. */
+ TinyHashMap* map_;
+ /** The current bucket index. */
+ int64_t bidx_;
+ /** The current record index. */
+ size_t ridx_;
+ /** The current records. */
+ std::vector<char*> recs_;
+ };
+ /**
+ * Sorter of records.
+ */
+ class Sorter {
+ public:
+ /**
+ * Constructor.
+ * @param map the container.
+ * @note This object will be invalidated when the map object is updated once.
+ */
+ explicit Sorter(TinyHashMap* map) : map_(map), ridx_(0), recs_() {
+ _assert_(map);
+ char** buckets = map_->buckets_;
+ size_t bnum = map_->bnum_;
+ for (size_t i = 0; i < bnum; i++) {
+ char* rbuf = buckets[i];
+ while (rbuf) {
+ Record rec(rbuf);
+ recs_.push_back(rbuf);
+ rbuf = *(char**)rbuf;
+ }
+ }
+ std::sort(recs_.begin(), recs_.end(), RecordComparator());
+ }
+ /**
+ * Destructor.
+ */
+ ~Sorter() {
+ _assert_(true);
+ }
+ /**
+ * Get the key of the current record.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the key region of the current record, or NULL on failure.
+ */
+ const char* get_key(size_t* sp) {
+ _assert_(sp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *sp = rec.ksiz_;
+ return rec.kbuf_;
+ }
+ /**
+ * Get the value of the current record.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the value region of the current record, or NULL on failure.
+ */
+ const char* get_value(size_t* sp) {
+ _assert_(sp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *sp = rec.vsiz_;
+ return rec.vbuf_;
+ }
+ /**
+ * Get a pair of the key and the value of the current record.
+ * @param ksp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @param vbp the pointer to the variable into which the pointer to the value region is
+ * assigned.
+ * @param vsp the pointer to the variable into which the size of the value region is
+ * assigned.
+ * @return the pointer to the key region, or NULL on failure.
+ */
+ const char* get(size_t* ksp, const char** vbp, size_t* vsp) {
+ _assert_(ksp && vbp && vsp);
+ if (ridx_ >= recs_.size()) return NULL;
+ Record rec(recs_[ridx_]);
+ *ksp = rec.ksiz_;
+ *vbp = rec.vbuf_;
+ *vsp = rec.vsiz_;
+ return rec.kbuf_;
+ }
+ /**
+ * Step the cursor to the next record.
+ */
+ void step() {
+ _assert_(true);
+ ridx_++;
+ }
+ /** The container. */
+ TinyHashMap* map_;
+ /** The current record index. */
+ size_t ridx_;
+ /** The current records. */
+ std::vector<char*> recs_;
+ };
+ /**
+ * Default constructor.
+ */
+ explicit TinyHashMap() : buckets_(NULL), bnum_(MAPDEFBNUM), count_(0) {
+ _assert_(true);
+ initialize();
+ }
+ /**
+ * Constructor.
+ * @param bnum the number of buckets of the hash table.
+ */
+ explicit TinyHashMap(size_t bnum) : buckets_(NULL), bnum_(bnum), count_(0) {
+ _assert_(true);
+ if (bnum_ < 1) bnum_ = MAPDEFBNUM;
+ initialize();
+ }
+ /**
+ * Destructor.
+ */
+ ~TinyHashMap() {
+ _assert_(true);
+ destroy();
+ }
+ /**
+ * Set the value of a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @param vbuf the pointer to the value region.
+ * @param vsiz the size of the value region.
+ * @note If no record corresponds to the key, a new record is created. If the corresponding
+ * record exists, the value is overwritten.
+ */
+ void set(const char* kbuf, size_t ksiz, const char* vbuf, size_t vsiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && vbuf && vsiz <= MEMMAXSIZ);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ char** entp = buckets_ + bidx;
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) {
+ int32_t oh = (int32_t)sizevarnum(vsiz) - (int32_t)sizevarnum(rec.vsiz_);
+ int64_t psiz = (int64_t)(rec.vsiz_ + rec.psiz_) - (int64_t)(vsiz + oh);
+ if (psiz >= 0) {
+ rec.overwrite(rbuf, vbuf, vsiz, psiz);
+ } else {
+ Record nrec(rec.child_, kbuf, ksiz, vbuf, vsiz, 0);
+ delete[] rbuf;
+ *entp = nrec.serialize();
+ }
+ return;
+ }
+ entp = (char**)rbuf;
+ rbuf = rec.child_;
+ }
+ Record nrec(NULL, kbuf, ksiz, vbuf, vsiz, 0);
+ *entp = nrec.serialize();
+ count_++;
+ }
+ /**
+ * Add a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @param vbuf the pointer to the value region.
+ * @param vsiz the size of the value region.
+ * @return true on success, or false on failure.
+ * @note If no record corresponds to the key, a new record is created. If the corresponding
+ * record exists, the record is not modified and false is returned.
+ */
+ bool add(const char* kbuf, size_t ksiz, const char* vbuf, size_t vsiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && vbuf && vsiz <= MEMMAXSIZ);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ char** entp = buckets_ + bidx;
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) return false;
+ entp = (char**)rbuf;
+ rbuf = rec.child_;
+ }
+ Record nrec(NULL, kbuf, ksiz, vbuf, vsiz, 0);
+ *entp = nrec.serialize();
+ count_++;
+ return true;
+ }
+ /**
+ * Replace the value of a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @param vbuf the pointer to the value region.
+ * @param vsiz the size of the value region.
+ * @return true on success, or false on failure.
+ * @note If no record corresponds to the key, no new record is created and false is returned.
+ * If the corresponding record exists, the value is modified.
+ */
+ bool replace(const char* kbuf, size_t ksiz, const char* vbuf, size_t vsiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && vbuf && vsiz <= MEMMAXSIZ);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ char** entp = buckets_ + bidx;
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) {
+ int32_t oh = (int32_t)sizevarnum(vsiz) - (int32_t)sizevarnum(rec.vsiz_);
+ int64_t psiz = (int64_t)(rec.vsiz_ + rec.psiz_) - (int64_t)(vsiz + oh);
+ if (psiz >= 0) {
+ rec.overwrite(rbuf, vbuf, vsiz, psiz);
+ } else {
+ Record nrec(rec.child_, kbuf, ksiz, vbuf, vsiz, 0);
+ delete[] rbuf;
+ *entp = nrec.serialize();
+ }
+ return true;
+ }
+ entp = (char**)rbuf;
+ rbuf = rec.child_;
+ }
+ return false;
+ }
+ /**
+ * Append the value of a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @param vbuf the pointer to the value region.
+ * @param vsiz the size of the value region.
+ * @note If no record corresponds to the key, a new record is created. If the corresponding
+ * record exists, the given value is appended at the end of the existing value.
+ */
+ void append(const char* kbuf, size_t ksiz, const char* vbuf, size_t vsiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && vbuf && vsiz <= MEMMAXSIZ);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ char** entp = buckets_ + bidx;
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) {
+ size_t nsiz = rec.vsiz_ + vsiz;
+ int32_t oh = (int32_t)sizevarnum(nsiz) - (int32_t)sizevarnum(rec.vsiz_);
+ int64_t psiz = (int64_t)(rec.vsiz_ + rec.psiz_) - (int64_t)(nsiz + oh);
+ if (psiz >= 0) {
+ rec.append(rbuf, oh, vbuf, vsiz, psiz);
+ } else {
+ psiz = nsiz + nsiz / 2;
+ Record nrec(rec.child_, kbuf, ksiz, "", 0, psiz);
+ char* nbuf = nrec.serialize();
+ oh = (int32_t)sizevarnum(nsiz) - 1;
+ psiz = (int64_t)psiz - (int64_t)(nsiz + oh);
+ rec.concatenate(nbuf, rec.vbuf_, rec.vsiz_, vbuf, vsiz, psiz);
+ delete[] rbuf;
+ *entp = nbuf;
+ }
+ return;
+ }
+ entp = (char**)rbuf;
+ rbuf = rec.child_;
+ }
+ Record nrec(NULL, kbuf, ksiz, vbuf, vsiz, 0);
+ *entp = nrec.serialize();
+ count_++;
+ }
+ /**
+ * Remove a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @return true on success, or false on failure.
+ * @note If no record corresponds to the key, false is returned.
+ */
+ bool remove(const char* kbuf, size_t ksiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ char** entp = buckets_ + bidx;
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) {
+ *entp = rec.child_;
+ delete[] rbuf;
+ count_--;
+ return true;
+ }
+ entp = (char**)rbuf;
+ rbuf = rec.child_;
+ }
+ return false;
+ }
+ /**
+ * Retrieve the value of a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the value region of the corresponding record, or NULL on failure.
+ */
+ const char* get(const char* kbuf, size_t ksiz, size_t* sp) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && sp);
+ size_t bidx = hash_record(kbuf, ksiz) % bnum_;
+ char* rbuf = buckets_[bidx];
+ while (rbuf) {
+ Record rec(rbuf);
+ if (rec.ksiz_ == ksiz && !std::memcmp(rec.kbuf_, kbuf, ksiz)) {
+ *sp = rec.vsiz_;
+ return rec.vbuf_;
+ }
+ rbuf = rec.child_;
+ }
+ return NULL;
+ }
+ /**
+ * Remove all records.
+ */
+ void clear() {
+ _assert_(true);
+ if (count_ < 1) return;
+ for (size_t i = 0; i < bnum_; i++) {
+ char* rbuf = buckets_[i];
+ while (rbuf) {
+ Record rec(rbuf);
+ char* child = rec.child_;
+ delete[] rbuf;
+ rbuf = child;
+ }
+ buckets_[i] = NULL;
+ }
+ count_ = 0;
+ }
+ /**
+ * Get the number of records.
+ * @return the number of records.
+ */
+ size_t count() {
+ _assert_(true);
+ return count_;
+ }
+ /**
+ * Get the hash value of a record.
+ * @param kbuf the pointer to the key region.
+ * @param ksiz the size of the key region.
+ * @return the hash value.
+ */
+ static size_t hash_record(const char* kbuf, size_t ksiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ);
+ return hashmurmur(kbuf, ksiz);
+ }
+ private:
+ /**
+ * Record data.
+ */
+ struct Record {
+ /** constructor */
+ Record(char* child, const char* kbuf, uint64_t ksiz,
+ const char* vbuf, uint64_t vsiz, uint64_t psiz) :
+ child_(child), kbuf_(kbuf), ksiz_(ksiz), vbuf_(vbuf), vsiz_(vsiz), psiz_(psiz) {
+ _assert_(kbuf && ksiz <= MEMMAXSIZ && vbuf && vsiz <= MEMMAXSIZ && psiz <= MEMMAXSIZ);
+ }
+ /** constructor */
+ Record(const char* rbuf) :
+ child_(NULL), kbuf_(NULL), ksiz_(0), vbuf_(NULL), vsiz_(0), psiz_(0) {
+ _assert_(rbuf);
+ deserialize(rbuf);
+ }
+ /** overwrite the buffer */
+ void overwrite(char* rbuf, const char* vbuf, size_t vsiz, size_t psiz) {
+ _assert_(rbuf && vbuf && vsiz <= MEMMAXSIZ && psiz <= MEMMAXSIZ);
+ char* wp = rbuf + sizeof(child_) + sizevarnum(ksiz_) + ksiz_;
+ wp += writevarnum(wp, vsiz);
+ std::memcpy(wp, vbuf, vsiz);
+ wp += vsiz;
+ writevarnum(wp, psiz);
+ }
+ /** append a value */
+ void append(char* rbuf, int32_t oh, const char* vbuf, size_t vsiz, size_t psiz) {
+ _assert_(rbuf && vbuf && vsiz <= MEMMAXSIZ && psiz <= MEMMAXSIZ);
+ char* wp = rbuf + sizeof(child_) + sizevarnum(ksiz_) + ksiz_;
+ if (oh > 0) {
+ char* pv = wp + sizevarnum(vsiz_);
+ std::memmove(pv + oh, pv, vsiz_);
+ wp += writevarnum(wp, vsiz_ + vsiz);
+ wp = pv + oh + vsiz_;
+ } else {
+ wp += writevarnum(wp, vsiz_ + vsiz);
+ wp += vsiz_;
+ }
+ std::memcpy(wp, vbuf, vsiz);
+ wp += vsiz;
+ writevarnum(wp, psiz);
+ }
+ /** concatenate two values */
+ void concatenate(char* rbuf, const char* ovbuf, size_t ovsiz,
+ const char* nvbuf, size_t nvsiz, size_t psiz) {
+ _assert_(rbuf && ovbuf && ovsiz <= MEMMAXSIZ && nvbuf && nvsiz <= MEMMAXSIZ);
+ char* wp = rbuf + sizeof(child_) + sizevarnum(ksiz_) + ksiz_;
+ wp += writevarnum(wp, ovsiz + nvsiz);
+ std::memcpy(wp, ovbuf, ovsiz);
+ wp += ovsiz;
+ std::memcpy(wp, nvbuf, nvsiz);
+ wp += nvsiz;
+ writevarnum(wp, psiz);
+ }
+ /** serialize data into a buffer */
+ char* serialize() {
+ _assert_(true);
+ uint64_t rsiz = sizeof(child_) + sizevarnum(ksiz_) + ksiz_ + sizevarnum(vsiz_) + vsiz_ +
+ sizevarnum(psiz_) + psiz_;
+ char* rbuf = new char[rsiz];
+ char* wp = rbuf;
+ *(char**)wp = child_;
+ wp += sizeof(child_);
+ wp += writevarnum(wp, ksiz_);
+ std::memcpy(wp, kbuf_, ksiz_);
+ wp += ksiz_;
+ wp += writevarnum(wp, vsiz_);
+ std::memcpy(wp, vbuf_, vsiz_);
+ wp += vsiz_;
+ writevarnum(wp, psiz_);
+ return rbuf;
+ }
+ /** deserialize a buffer into object */
+ void deserialize(const char* rbuf) {
+ _assert_(rbuf);
+ const char* rp = rbuf;
+ child_ = *(char**)rp;
+ rp += sizeof(child_);
+ rp += readvarnum(rp, sizeof(ksiz_), &ksiz_);
+ kbuf_ = rp;
+ rp += ksiz_;
+ rp += readvarnum(rp, sizeof(vsiz_), &vsiz_);
+ vbuf_ = rp;
+ rp += vsiz_;
+ readvarnum(rp, sizeof(psiz_), &psiz_);
+ }
+ char* child_; ///< region of the child
+ const char* kbuf_; ///< region of the key
+ uint64_t ksiz_; ///< size of the key
+ const char* vbuf_; ///< region of the value
+ uint64_t vsiz_; ///< size of the key
+ uint64_t psiz_; ///< size of the padding
+ };
+ /**
+ * Comparator for records.
+ */
+ struct RecordComparator {
+ /** comparing operator */
+ bool operator ()(char* const& abuf, char* const& bbuf) {
+ const char* akbuf = abuf + sizeof(char**);
+ uint64_t aksiz;
+ akbuf += readvarnum(akbuf, sizeof(aksiz), &aksiz);
+ const char* bkbuf = bbuf + sizeof(char**);
+ uint64_t bksiz;
+ bkbuf += readvarnum(bkbuf, sizeof(bksiz), &bksiz);
+ uint64_t msiz = aksiz < bksiz ? aksiz : bksiz;
+ for (uint64_t i = 0; i < msiz; i++) {
+ if (((uint8_t*)akbuf)[i] != ((uint8_t*)bkbuf)[i])
+ return ((uint8_t*)akbuf)[i] < ((uint8_t*)bkbuf)[i];
+ }
+ return (int32_t)aksiz < (int32_t)bksiz;
+ }
+ };
+ /**
+ * Initialize fields.
+ */
+ void initialize() {
+ _assert_(true);
+ if (bnum_ >= MAPZMAPBNUM) {
+ buckets_ = (char**)mapalloc(sizeof(*buckets_) * bnum_);
+ } else {
+ buckets_ = new char*[bnum_];
+ for (size_t i = 0; i < bnum_; i++) {
+ buckets_[i] = NULL;
+ }
+ }
+ }
+ /**
+ * Clean up fields.
+ */
+ void destroy() {
+ _assert_(true);
+ for (size_t i = 0; i < bnum_; i++) {
+ char* rbuf = buckets_[i];
+ while (rbuf) {
+ Record rec(rbuf);
+ char* child = rec.child_;
+ delete[] rbuf;
+ rbuf = child;
+ }
+ }
+ if (bnum_ >= MAPZMAPBNUM) {
+ mapfree(buckets_);
+ } else {
+ delete[] buckets_;
+ }
+ }
+ /** Dummy constructor to forbid the use. */
+ TinyHashMap(const TinyHashMap&);
+ /** Dummy Operator to forbid the use. */
+ TinyHashMap& operator =(const TinyHashMap&);
+ /** The bucket array. */
+ char** buckets_;
+ /** The number of buckets. */
+ size_t bnum_;
+ /** The number of records. */
+ size_t count_;
+};
+
+
+/**
+ * Memory-saving string array list.
+ */
+class TinyArrayList {
+ public:
+ /**
+ * Default constructor.
+ */
+ explicit TinyArrayList() : recs_() {
+ _assert_(true);
+ }
+ /**
+ * Destructor.
+ */
+ ~TinyArrayList() {
+ _assert_(true);
+ std::deque<char*>::iterator it = recs_.begin();
+ std::deque<char*>::iterator itend = recs_.end();
+ while (it != itend) {
+ delete[] *it;
+ ++it;
+ }
+ }
+ /**
+ * Insert a record at the bottom of the list.
+ * @param buf the pointer to the record region.
+ * @param size the size of the record region.
+ */
+ void push(const char* buf, size_t size) {
+ _assert_(buf && size <= MEMMAXSIZ);
+ size_t rsiz = sizevarnum(size) + size;
+ char* rbuf = new char[rsiz];
+ char* wp = rbuf + writevarnum(rbuf, size);
+ std::memcpy(wp, buf, size);
+ recs_.push_back(rbuf);
+ }
+ /**
+ * Remove a record at the bottom of the list.
+ * @return true if the operation success, or false if there is no record in the list.
+ */
+ bool pop() {
+ _assert_(true);
+ if (recs_.empty()) return false;
+ delete[] recs_.back();
+ recs_.pop_back();
+ return true;
+ }
+ /**
+ * Insert a record at the top of the list.
+ * @param buf the pointer to the record region.
+ * @param size the size of the record region.
+ */
+ void unshift(const char* buf, size_t size) {
+ _assert_(buf && size <= MEMMAXSIZ);
+ size_t rsiz = sizevarnum(size) + size;
+ char* rbuf = new char[rsiz];
+ char* wp = rbuf + writevarnum(rbuf, size);
+ std::memcpy(wp, buf, size);
+ recs_.push_front(rbuf);
+ }
+ /**
+ * Remove a record at the top of the list.
+ * @return true if the operation success, or false if there is no record in the list.
+ */
+ bool shift() {
+ _assert_(true);
+ if (recs_.empty()) return false;
+ delete[] recs_.front();
+ recs_.pop_front();
+ return true;
+ }
+ /**
+ * Insert a record at the position of the given index of the list.
+ * @param buf the pointer to the record region.
+ * @param size the size of the record region.
+ * @param idx the index of the position. It must be equal to or less than the number of
+ * records.
+ */
+ void insert(const char* buf, size_t size, size_t idx) {
+ size_t rsiz = sizevarnum(size) + size;
+ char* rbuf = new char[rsiz];
+ char* wp = rbuf + writevarnum(rbuf, size);
+ std::memcpy(wp, buf, size);
+ recs_.insert(recs_.begin() + idx, rbuf);
+ }
+ /**
+ * Remove a record at the position of the given index of the list.
+ * @param idx the index of the position. It must be less than the number of records.
+ */
+ void remove(size_t idx) {
+ _assert_(true);
+ std::deque<char*>::iterator it = recs_.begin() + idx;
+ delete[] *it;
+ recs_.erase(it);
+ }
+ /**
+ * Retrieve a record at the position of the given index of the list.
+ * @param idx the index of the position. It must be less than the number of records.
+ * @param sp the pointer to the variable into which the size of the region of the return
+ * value is assigned.
+ * @return the pointer to the region of the retrieved record.
+ */
+ const char* get(size_t idx, size_t* sp) {
+ _assert_(sp);
+ const char* rbuf = recs_[idx];
+ uint64_t rsiz;
+ const char* rp = rbuf + readvarnum(rbuf, sizeof(uint64_t), &rsiz);
+ *sp = rsiz;
+ return rp;
+ }
+ /**
+ * Remove all records.
+ */
+ void clear() {
+ _assert_(true);
+ std::deque<char*>::iterator it = recs_.begin();
+ std::deque<char*>::iterator itend = recs_.end();
+ while (it != itend) {
+ delete[] *it;
+ ++it;
+ }
+ recs_.clear();
+ }
+ /**
+ * Get the number of records.
+ * @return the number of records.
+ */
+ size_t count() {
+ _assert_(true);
+ return recs_.size();
+ }
+ private:
+ /** Dummy constructor to forbid the use. */
+ TinyArrayList(const TinyArrayList&);
+ /** Dummy Operator to forbid the use. */
+ TinyArrayList& operator =(const TinyArrayList&);
+ /** The record list. */
+ std::deque<char*> recs_;
+};
+
+
+} // common namespace
+
+#endif // duplication check
+
+// END OF FILE
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-01 02:05:12 +0000