[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