/usr/include/dawgdic/link-table.h is in libdawgdic-dev 0.4.5-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #ifndef DAWGDIC_LINK_TABLE_H
#define DAWGDIC_LINK_TABLE_H
#include "base-types.h"
#include "dictionary-unit.h"
#include <vector>
namespace dawgdic {
class LinkTable {
public:
explicit LinkTable() : hash_table_() {}
// Initializes a hash table.
void Init(SizeType table_size) {
PairType initial_pair(0, 0);
std::vector<PairType> table(table_size, initial_pair);
hash_table_.swap(table);
}
// Finds an offset that corresponds to a given index.
BaseType Find(BaseType index) const {
BaseType hash_id = FindId(index);
return hash_table_[hash_id].second;
}
// Inserts an index with its offset.
void Insert(BaseType index, BaseType offset) {
BaseType hash_id = FindId(index);
hash_table_[hash_id].first = index;
hash_table_[hash_id].second = offset;
}
private:
typedef std::pair<BaseType, BaseType> PairType;
std::vector<PairType> hash_table_;
// Disallows copies.
LinkTable(const LinkTable &);
LinkTable &operator=(const LinkTable &);
// Finds an Id from an upper table.
BaseType FindId(BaseType index) const {
BaseType hash_id = Hash(index) % hash_table_.size();
while (hash_table_[hash_id].first != 0) {
if (index == hash_table_[hash_id].first) {
return hash_id;
}
hash_id = (hash_id + 1) % hash_table_.size();
}
return hash_id;
}
// 32-bit mix function.
// http://www.concentric.net/~Ttwang/tech/inthash.htm
static BaseType Hash(BaseType key) {
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >> 12);
key = key + (key << 2);
key = key ^ (key >> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >> 16);
return key;
}
};
} // namespace dawgdic
#endif // DAWGDIC_LINK_TABLE_H
|