[chuck-users] implementing a set (was object / class hacking)
Robert Poor
rdpoor at gmail.com
Wed Sep 30 17:28:10 EDT 2009
Hans:
To simultaneously stand my ground and display my ignorance:
I've written several flavors of hash tables in my life, but I'm not
sure how the Stroustrup code sample helps in this case. If you are
suggesting that I hack the Chuck source code, you should know that I
do entertain such ideas from time to time, but I usually come back to
my senses within 25::samp -- it's just not on my list of priorities.
A "written entirely in ChucK" solution -- albeit non-optimal in
execution speed -- is good enough for my needs. I'm more into
optimizing my days than my milliseconds.
Thanks, though.
- Rob
On 30 Sep 2009, at 14:01, Hans Aberg wrote:
> On 30 Sep 2009, at 22:12, Robert Poor wrote:
>
>> To clarify: I'd like to implement a set for storing a collection of
>> homogenous objects. Specifically, I need to be able to test for
>> the presence of an object in the set, add an object to the set (if
>> not already present), delete a object from the set, and iterate
>> over all the objects in the set. This last requirements, sadly,
>> eliminates Chuck's "associative arrays".
>>
>> It's worth pointing out that:
>>
>> arbitraryobject.toString()
>>
>> will generate a string of the form "ClassName:hexLocation".
>> Assuming that Chuck NEVER (ever) relocates a live object in memory
>> (Chuck has a reference counting GC, not a copying GC, true?), that
>> string could be useful as a unique ID. But Chuck lacks the string
>> operations to reduce a string into a hash key.
>
> Bjarne Stroustrup, "The C++ Programming Language", 3.1.3, has a
> simple hash function:
> name* look(const char* p, int ins=0);
> name* insert(const char* s) { look(s, 1); }
>
> struct name {
> char* string;
> name* next;
> double value;
> }
>
> const TBLSZ = 23;
> name* table[TBLSZ];
>
> name* look(const char* p, int ins=0) {
> int ii = 0;
> const char* pp = p;
> while (*pp) ii = ii<<1 ^ *pp++; // Hash function using eor: ii<<1;
> ii ^= *pp++;
>
> if (ii < 0) ii = -ii; // Reduce to array range.
> ii %= TBLSZ;
>
> for (name* n = table[ii]; n; n = n->next) // Search
> if (strcmp(p, n->string) == 0) return n;
>
> if (ins == 0) error("name not found");
>
> name* nn = new name; // Insert
> nn->string = new char[strlen(p) + 1];
> strcpy(nn->string, p);
> nn->value = 1;
> nn->next = table[ii];
> table[ii] = nn;
> return nn;
> }
>
> Hans
More information about the chuck-users
mailing list