|
From: Christoph B. <bar...@or...> - 2007-07-22 21:20:47
|
Am Samstag, 21. Juli 2007 schrieb Nicholas Nethercote:
> On Fri, 20 Jul 2007, Christoph Bartoschek wrote:
> > Yes, I am currently working on a m_hashtable.c that uses open adressing
> > with linear probing. Each table entry stores a pointer to the item.
>
> I would recommend that you look at the interface in pub_tool_oset.h. I
> designed it pretty carefully, and made it quite generic. Eg. you can even
> use an OSet to represent ranges. If you could make the hash table
> implementation use the same interface we could even consider removing the
> AVL tree implementation and use the hash table as the OSet.
After reading the header of m_hashtable.c carefully I abandoned my plans to
change it further.
The current code implements a hash map with a UInt key. On the other hand the
execution context code uses a hash set. There are good reasons to separate
both ways to use a hash table. Both Java and C++ use two classes to implement
a hash set and a hash map. They do not try to use one class that covers both
functionalities.
On the other hand linear probing seems to be no choice now. The current hash
table interface exposes the chaining implementation such that clients can
optimize for speed.
A hash map or a hash set can not replace an AVL implementation because it is
not possible to have sorted access or to use range searches.
If I find time, I am going to change my implementation of the execution
context to a hash list with linear probing because it allows me to get rid of
the next pointer in each context. (Valgrind still uses 6GB for all execution
contexts in my application). However I see no direct way to embed execution
contexts into the hashtable:
struct ExeContext {
struct ExeContext * parent; //calling frame
Addr ip;
};
To support such a thing one would need a way to distinguish an empty entry
from a used one and during resize an empty that is already moved from an
unmoved one. Are there ip values that are not possible? Or values for parent?
I guess I can use the fact that all pointers are 4/8 byte aligned but maybe
there is a better way.
Greetings
Christoph
|