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. >