[pacman-dev] Database consistency checking (hash tables)

[Xavier]

On Sat, Jul 21, 2007 at 11:31:35AM +0200, Xavier wrote:
> On Fri, Jul 20, 2007 at 11:09:55PM +0200, Xavier wrote:
> > But that really sucks of course :( I hate C.. There is really no clean way
> > to do what I want?
> > I guess I could create a new pkg structure type only for that testdb file,
> > for storing the new requiredby field, or having a second local pkgcache
> > (duplicating every package and storing them in a list, and modifying the
> >  requiredy field there).
> > But the code is already huge compared to the simple things it does.
> > It would make it even more huge :p
> > 
> 
> What I would have done in Java is probably using a HashMap.
> So I did the same in C, I took the implementation of hash tables from there :
> http://www.cl.cam.ac.uk/~cwc22/hashtable/
> and used that instead of my previous newrequiredby hack for storing the new
> requiredby fields :)
> The problem is that the hashtable implementation is bigger than the testdb.c
> file itself..
> 
> But couldn't hash tables also be useful for the rest of the code?
> Having O(1) access to elements instead of the O(n) _alpm_pkg_find() for
> example could be interesting in some cases in my opinion.

Also found out there was a hash table implementation based on kernel list :
http://isis.poly.edu/kulesh/stuff/src/

This does the job as well.