/*************************************************************************************************
* 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