Forums > Dev

Problems using hashtab_store()

May 15, 2007 | 1:55 am

t_max_err err;
err = hashtab_store(myhashtab, gensym("test"), (t_object *)myobject);
post("error is %i", err); // prints 0

But if called twice, storing different t_object pointers each time, the second t_object instance is getting stomped on, and only the first t_object pointer is stored under the "test" key.

hashtab_print(myhashtab):

slot[247] contains 1 entries
total size is 1 entries
using 1 out of 257 slots
average entries per non-empty slot is 1.000000
maximum entries in a slot is 1

I’d thought that hashtab_store would add the second item as a second entry for the "test" key.

So what’s happening here? I assume I’m misinterpreting how hashtab is implemented – is there any documentation or example available apart from ext_hashtab.h? A search of the externals PDF, the example projects, and this site reveals nothing.


May 15, 2007 | 2:26 am

Hi John,

Keys are required to be unique.

best,
Tim

On May 14, 2007, at 8:55 PM, John Pitcairn wrote:

> t_max_err err;
> err = hashtab_store(myhashtab, gensym("test"), (t_object *)myobject);
> post("error is %i", err); // prints 0
>
> But if called twice, storing different t_object pointers each time,
> the second t_object instance is getting stomped on, and only the
> first t_object pointer is stored under the "test" key.
>
> hashtab_print(myhashtab):
>
> slot[247] contains 1 entries
> total size is 1 entries
> using 1 out of 257 slots
> average entries per non-empty slot is 1.000000
> maximum entries in a slot is 1
>
> I’d thought that hashtab_store would add the second item as a
> second entry for the "test" key.
>
> So what’s happening here? I assume I’m misinterpreting how hashtab
> is implemented – is there any documentation or example available
> apart from ext_hashtab.h? A search of the externals PDF, the
> example projects, and this site reveals nothing.


May 15, 2007 | 3:08 am

Thanks Tim – so that begs the question: if there are multiple "entries" available per "slot", as hashtab_print certainly appears to indicate, is there a way to add/remove an entry for an existing key/slot?

Or do I need to roll my own functionality here, perhaps using a linked list keyed to a hashtab slot?


May 15, 2007 | 3:21 am

On May 14, 2007, at 10:08 PM, John Pitcairn wrote:

> Thanks Tim – so that begs the question: if there are multiple
> "entries" available per "slot", as hashtab_print certainly appears
> to indicate, is there a way to add/remove an entry for an existing
> key/slot?
>
> Or do I need to roll my own functionality here, perhaps using a
> linked list keyed to a hashtab slot?

I think the main thing here is that a slot does not represent a key.
This link might prove useful in understanding what is going on:

http://en.wikipedia.org/wiki/Hash_table

The section labeled "Chaining" will explain Max’s hashtab
implementation. If you take the diagram that they have, index 873 is
a hashtab slot, which contains a linked list with two items in it.

I hope this helps,
Tim


May 15, 2007 | 3:51 am

O … K … so in this case, attempting to store something else under the same key isn’t creating a collision, so the previous item just gets replaced?

If so, hashtab isn’t what I need, and I should probably just look into using an instance of xcoll internally(?)

Thanks for the advice, it’s very appreciated.


May 15, 2007 | 6:33 am

You might want to indeed do what you previously suggested, and store
a linked list at each key. You’d use something like this to add an
entry.

t_linklist *link;
t_hashtab *hash;
t_object *newentry;

hashtab_lookup(hash, gensym("test"), (t_object **)&link);
if (!link) {
link = linklist_new(); // new linked list
hashtab_store(hash, gensym("test"), (t_object *)link);
} else { // check if our new entry is already there
long idx = linklist_objptr2index(link, newentry);
if (idx >= 0) {
// object is already there
return;
}
}
linklist_append(link, newentry);

jb

Am 15.05.2007 um 05:51 schrieb John Pitcairn:

>
> O … K … so in this case, attempting to store something else
> under the same key isn’t creating a collision, so the previous item
> just gets replaced?
>
> If so, hashtab isn’t what I need, and I should probably just look
> into using an instance of xcoll internally(?)
>
> Thanks for the advice, it’s very appreciated.
>


May 15, 2007 | 5:56 pm

Hashtables are many-to-one mappings. Think of them like mathematical
functions: for one input, you have only one output (but many inputs
can map to the same output). If you want to store more than one thing
in the same bucket, you’ll have to manually toss a list into that
bucket the first time and add things to the list thereafter.

I would recommend reading Corman, Lierstein, Rivest and Stein’s
"Introduction to Algorithms" for in depth descriptions of data-types
like the hashtable.

_Mark

On May 14, 2007, at 6:55 PM, John Pitcairn wrote:

>
> t_max_err err;
> err = hashtab_store(myhashtab, gensym("test"), (t_object *)myobject);
> post("error is %i", err); // prints 0
>
> But if called twice, storing different t_object pointers each time,
> the second t_object instance is getting stomped on, and only the
> first t_object pointer is stored under the "test" key.
>
> hashtab_print(myhashtab):
>
> slot[247] contains 1 entries
> total size is 1 entries
> using 1 out of 257 slots
> average entries per non-empty slot is 1.000000
> maximum entries in a slot is 1
>
> I’d thought that hashtab_store would add the second item as a second
> entry for the "test" key.
>
> So what’s happening here? I assume I’m misinterpreting how hashtab
> is implemented – is there any documentation or example available
> apart from ext_hashtab.h? A search of the externals PDF, the example
> projects, and this site reveals nothing.


May 15, 2007 | 11:27 pm

Thanks for the advice Mark & Jeremy. After a night’s sleep I’ve come to the conclusion that an instance of coll definitely isn’t what I want, and my needs will indeed best be served by a hashtaab containing linked lists.

Q: if the hashtab is declared in my object struct definition and initialized in object_new, do I need to dispose of the hashtab with hashtab_chuck() in my object’s free function? If so, what will that also chuck the hashtab’s linked lists without killing the (other) t_objects pointed to? Or should I individually chuck the linked lists, then chuck the hashtab?


May 16, 2007 | 12:07 am

On May 15, 2007, at 4:27 PM, John Pitcairn wrote:

> Q: if the hashtab is declared in my object struct definition and
> initialized in object_new, do I need to dispose of the hashtab with
> hashtab_chuck() in my object’s free function?

Yes.

> If so, what will that also chuck the hashtab’s linked lists without
> killing the (other) t_objects pointed to?

No.

> Or should I individually chuck the linked lists, then chuck the
> hashtab?

Yes.

-Joshua


May 17, 2007 | 3:16 am

Hmm … still a spot of confusion trying to retrieve the hashtab’s keys. I’ve previously stored pointers to two linked lists under the keys "P2" and "test".

Code:

t_symbol *keys;
long keycount;
t_max_err err;
err = hashtab_getkeys(myhashtab, &keycount, (t_symbol ***)&keys);
post("keycount %i, error %i", keycount, err);
hashtab_print(myhashtab);

This posts/prints:

keycount 0, error 0
slot[165] contains 1 entries
slot[247] contains 1 entries
total size is 2 entries
using 2 out of 257 slots
average entries per non-empty slot is 1.000000
maximum entries in a slot is 1


May 17, 2007 | 3:19 am

(continued, the forum ate my last para on post)

I’d assumed I’d get an array of keys as t_symbols in *keys, but it’s empty with keycount 0 and no error. What’s wrong here?


May 17, 2007 | 3:29 am

> err = hashtab_getkeys(myhashtab, &keycount, (t_symbol ***)&keys);

I think you mean (t_symbol **), yes?

best,
Tim


May 17, 2007 | 3:40 am

On May 16, 2007, at 10:29 PM, Timothy Place wrote:

>> err = hashtab_getkeys(myhashtab, &keycount, (t_symbol ***)&keys);
>
> I think you mean (t_symbol **), yes?

Uh, my bad. I recognized your bad cast (and fixed that), but now
realize that it isn’t solution you want. Instead you need to
something akin to this (warning: I’m coding this in the email client)

t_symbol **keys = NULL;
long keycount = 0;

err = hashtab_getkeys(myhashtab, &keycount, &keys);
// … do some stuff …

if(keys)
sysmem_freeptr(keys);

I hope that’s more helpful!
tim


May 17, 2007 | 3:59 am

That’s it, thanks. Coming from a mostly js/php background, the whole pointer-thing in C drives me a little batty in anything beyond simple cases.


May 17, 2007 | 4:05 am

So that keys pointer won’t be automatically freed when my function exits? Is that true for all ** pointers created by any function?


May 22, 2007 | 10:16 am

If you pass a NULL pointer into a function and it returns data, you
are typically (not always, but typically) responsible for disposing
of the data when you’re done with it. This should be documented for
the API in question, although since the docs for hashtab are
currently incomplete, there was no way for you to know! You would
also need to know _which_ memory-freeing function to use, in the
event that you need to free…

In the case of hashtab_getkeys(), you actually need to use freebytes
(), NOT sysmem_freeptr().

jb

Am 17.05.2007 um 06:05 schrieb John Pitcairn:

>
> So that keys pointer won’t be automatically freed when my function
> exits? Is that true for all ** pointers created by any function?


May 22, 2007 | 8:57 pm

Thanks. I had come to the conclusion that since the pointer references an object created by the hashtab lookup function, that object does need to be freed, and freed before the pointer is re-used for another lookup. I’ll use freebytes as you suggest.


May 22, 2007 | 9:04 pm

Yes, free it with freebytes before using it again. Also important,
set it to NULL, and set the long "count" variable to 0 before doing
another lookup. Otherwise, you’ll get the same weird results you were
getting before.

jb

Am 22.05.2007 um 22:57 schrieb John Pitcairn:

>
> Thanks. I had come to the conclusion that since the pointer
> references an object created by the hashtab lookup function, that
> object does need to be freed, and freed before the pointer is re-
> used for another lookup. I’ll use freebytes as you suggest.
>


Viewing 18 posts - 1 through 18 (of 18 total)