Create hash key from pointer addresses

Discussion of Common Lisp
Post Reply
SigmaX
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Create hash key from pointer addresses

Post by SigmaX » Fri Aug 06, 2010 3:56 am

I'm rewriting an algorithm in CL that was originally designed in C. It involves running functions on the addresses of the children of binary tree nodes to generate hash keys.

I've got control over the hashing function via Ingvar Mattson's generic hash table implementation.

The problem now is how to actually generate hash keys that are the same for isomorphic tree nodes. So how can I do this in Lisp?

CFFI gives me access to pointer addresses of foreign objects, but I can't run it on a reference to a local struct.

Any ideas?
Thanks,
Siggy

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Create hash key from pointer addresses

Post by ramarren » Fri Aug 06, 2010 4:44 am

Most CL implementations use a copying garbage collector, which means that during collection objects can be moved an hence addresses to Lisp side objects will not remain valid.

Anyway, I am not quite sure what you need exactly, but a standard hash table can be keyed with complex objects using EQUAL designator as test argument, which will descend into conses, but keep structure identity.

There is also SXHASH function which will reduce any Lisp object to a number which could be used as hash key, or a fragment of one.

SigmaX
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Re: Create hash key from pointer addresses

Post by SigmaX » Fri Aug 06, 2010 7:57 am

Ah, okay. Didn't know it had garbage collection, though that explains a lot.

I'll look into the designator and SXHASH. May be what I need.

Thanks for the pointers! Er. No pun intended. Honest!

Siggy

SigmaX
Posts: 19
Joined: Tue Jul 27, 2010 9:29 am
Location: Santa Fe, NM

Re: Create hash key from pointer addresses

Post by SigmaX » Fri Aug 06, 2010 8:23 am

Okay, I think I'm going to use the equal designator. I'd tried it before and found that it doesn't descend into structs, but forgot to try it with lists (which is funny, 'cuz I was using lists at first). I think it'll actually be easier this way, since I don't want it to actually descend deep into my binary tree.

Thanks!
Siggy

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Create hash key from pointer addresses

Post by ramarren » Fri Aug 06, 2010 8:30 am

Specification for EQUAL and EQUALP, which is also a valid hash table test, does explain in detail how they compute the "sameness" for objects. The latter descends into many more kinds of objects, including structures.

Post Reply