Martin Mares wrote:
This is pushing all boundaries, however. That code is horrible.
It's somewhat ugly inside, but an equally strong generic structure build
with templates will be probably even uglier.
Not at all.
So, show your version :-)
(as fast as this one, of course)
Have a nice fortnight
Here you go. In practice one would probably uninline get() and possibly put().
It doesn't do all that your example does (a 15 minute hack), but it is easily expandable. It
also allows a value to belong to two different hash tables (on two different keys) simultaneously.
#include <cassert>
template <typename Key, class Value, class Traits>
class Hashtable
{
public:
class Link {
private:
Link* next;
Value& value()
{
return *static_cast<Value*>(this);
}
friend class Hashtable;
};
public:
explicit Hashtable(int size)
: _size(size)
, _buckets(new Link[size])
{
assert((_size & (_size - 1)) == 0);
}
~Hashtable()
{
delete[] _buckets;
}
Value* get(const Key& key)
{
Link* link = _buckets[Traits::hash(key) & (_size - 1)].next;
while (link && !Traits::equal(key, link->value()))
link = link->next;
if (link)
return &link->value();
return 0;
}
void put(Value& value)
{
// assumes value (or a value with an equal key) is not already in
Link& head = _buckets[Traits::hash(value) & (_size - 1)];
static_cast<Link&>(value).next = &head;
head.next= &value;
}
private:
int _size;
Link* _buckets;
};
// example program
#include <iostream>
#include <string.h>
struct Word;
struct WordHashTraits;
typedef Hashtable<const char*, Word, WordHashTraits> WordHash;
struct Word : WordHash::Link
{
explicit Word(const char* _word) : word(_word), count(0) {}
const char* word;
int count;
};
struct WordHashTraits
{
static unsigned hash(const char* key)
{
// assume this is jenkin's hash.
unsigned h = 0;
while (*key) {
h = (h << 3) | (h >> 29);
h ^= (unsigned char)*key++;
}
return h;
}
static unsigned hash(const Word& value)
{
return hash(value.word);
}
static bool equal(const char* key, const Word& value)
{
return strcmp(key, value.word) == 0;
}
};
int main(int ac, const char** av)
{
WordHash hashtable(16); // make collisions likely
for (int i = 1; i < ac; ++i) {
const char* word = av[i];
Word* word_in_hash = hashtable.get(word);
if (!word_in_hash) {
word_in_hash = new Word(word);
hashtable.put(*word_in_hash);
}
++word_in_hash->count;
std::cout << "word: " << word << " count " << word_in_hash->count << "\n";
}
}
--
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
