Re: C++ pushback

[Avi Kivity <avi@argo.co.il>]

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 majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/