v2/chuck_table.cpp

   1 /*----------------------------------------------------------------------------
   2     ChucK Concurrent, On-the-fly Audio Programming Language
   3       Compiler and Virtual Machine
   4
   5     Copyright (c) 2004 Ge Wang and Perry R. Cook.  All rights reserved.
   6       http://chuck.cs.princeton.edu/
   7       http://soundlab.cs.princeton.edu/
   8
   9     This program is free software; you can redistribute it and/or modify
  10     it under the terms of the GNU General Public License as published by
  11     the Free Software Foundation; either version 2 of the License, or
  12     (at your option) any later version.
  13
  14     This program is distributed in the hope that it will be useful,
  15     but WITHOUT ANY WARRANTY; without even the implied warranty of
  16     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17     GNU General Public License for more details.
  18
  19     You should have received a copy of the GNU General Public License
  20     along with this program; if not, write to the Free Software
  21     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  22     U.S.A.
  23 -----------------------------------------------------------------------------*/
  24
  25 //-----------------------------------------------------------------------------
  26 // file: chuck_table.cpp
  27 // desc: ...
  28 //
  29 // copyright (c) 1997 Andrew W. Appel.
  30 //
  31 // author: Andrew Appel (appel@cs.princeton.edu)
  32 // modified: Ge Wang (gewang@cs.princeton.edu)
  33 //           Perry R. Cook (prc@cs.princeton.edu)
  34 // date: Autumn 2002
  35 //-----------------------------------------------------------------------------
  36 #include <stdio.h>
  37 #include <string.h>
  38 #include "chuck_table.h"
  39 #include "chuck_utils.h"
  40
  41 #define TABSIZE 65437
  42
  43
  44 typedef struct binder_ *binder;
  45 struct binder_ {void *key; void *value; binder next; void *prevtop;};
  46 struct TAB_table_ {
  47   unsigned long size;
  48   binder * table;
  49   void * top;
  50   TAB_eq_func eq_func;
  51   TAB_hash_func hash_func;
  52 };
  53
  54
  55 static binder Binder(void *key, void *value, binder next, void *prevtop)
  56 {
  57     binder b = (binder)checked_malloc(sizeof(struct binder_));
  58     b->key = key; b->value=value; b->next=next; b->prevtop = prevtop;
  59     return b;
  60 }
  61
  62
  63 TAB_table TAB_empty(void)
  64 {
  65     return TAB_empty2(TABSIZE);
  66 }
  67
  68
  69 TAB_table TAB_empty2( unsigned long s )
  70 {
  71     TAB_table t = (TAB_table)checked_malloc(sizeof(struct TAB_table_));
  72     unsigned long i;
  73     t->table = (binder *)checked_malloc(sizeof(binder)*s);
  74     t->size = s;
  75     t->top = NULL;
  76     t->eq_func = NULL;
  77     t->hash_func = NULL;
  78     for( i = 0; i < s; i++ )
  79         t->table[i] = NULL;
  80     return t;
  81 }
  82
  83 TAB_table TAB_empty3( TAB_eq_func eq, TAB_hash_func hash, unsigned long s )
  84 {
  85     TAB_table t = TAB_empty2(s);
  86     t->eq_func = eq;
  87     t->hash_func = hash;
  88     return t;
  89 }
  90
  91
  92
  93
  94 void TAB_delete( TAB_table t )
  95 {
  96     unsigned long i;
  97     binder p = NULL, n = NULL;
  98     for(i = 0; i < t->size; i++ )
  99     {
 100         p = t->table[i];
 101         while( p )
 102         {
 103             n = p->next;
 104             free(p);
 105             p = n;
 106         }
 107     }
 108
 109     // free the table
 110     free( t->table );
 111     free( t );
 112 }
 113
 114
 115
 116 /* The cast from pointer to integer in the expression
 117  *   ((unsigned)key) % TABSIZE
 118  * may lead to a warning message.  However, the code is safe,
 119  * and will still operate correctly.  This line is just hashing
 120  * a pointer value into an integer value, and no matter how the
 121  * conversion is done, as long as it is done consistently, a
 122  * reasonable and repeatable index into the table will result.
 123  */
 124
 125 void TAB_enter(TAB_table t, void *key, void *value)
 126 {
 127     long index;
 128     unsigned long hval = (unsigned long)key;
 129     assert(t && key);
 130     if( t->hash_func )
 131         hval = (unsigned long)t->hash_func(key);
 132     index = hval % t->size;
 133     t->table[index] = Binder(key, value, t->table[index], t->top);
 134     t->top = key;
 135 }
 136
 137 void *TAB_look(TAB_table t, void *key)
 138 {
 139     long index;
 140     unsigned long hval = (unsigned long)key;
 141     binder b;
 142     assert(t && key);
 143     if( t->hash_func )
 144         hval = (unsigned long)t->hash_func(key);
 145     index= hval % t->size;
 146     if( !t->eq_func )
 147     {
 148         for(b=t->table[index]; b; b=b->next)
 149             if (b->key==key) return b->value;
 150     }
 151     else
 152     {
 153         for(b=t->table[index]; b; b=b->next)
 154             if (t->eq_func(b->key, key)) return b->value;
 155     }
 156
 157     return NULL;
 158 }
 159
 160 void *TAB_pop(TAB_table t)
 161 {
 162     void *k; binder b; long index;
 163     unsigned long hval;
 164     assert (t);
 165     k = t->top;
 166     assert (k);
 167     hval = (unsigned long)k;
 168     if(t->hash_func) hval = (unsigned long)t->hash_func(k);
 169     index = ((unsigned long)hval) % t->size;
 170     b = t->table[index];
 171     assert(b);
 172     t->table[index] = b->next;
 173     t->top=b->prevtop;
 174     return b->key;
 175 }
 176
 177 void *TAB_topv(TAB_table t)
 178 {
 179     void *k; binder b; long index;
 180     unsigned long hval;
 181     assert(t);
 182     k = t->top;
 183     assert(k);
 184     hval = (unsigned long)k;
 185     if(t->hash_func) hval = (unsigned long)t->hash_func(k);
 186     index = hval % t->size;
 187     b = t->table[index];
 188     assert(b);
 189     return b->value;
 190 }
 191
 192 void TAB_dump(TAB_table t, void (*show)(void *key, void *value))
 193 {
 194     void *k = t->top;
 195     long index = ((unsigned long)k) % t->size;
 196     binder b = t->table[index];
 197     if (b==NULL) return;
 198     t->table[index]=b->next;
 199     t->top=b->prevtop;
 200     show(b->key,b->value);
 201     TAB_dump(t,show);
 202     assert(t->top == b->prevtop && t->table[index]==b->next);
 203     t->top=k;
 204     t->table[index]=b;
 205 }
 206
 207 long str_eq( void * lhs, void * rhs )
 208 {
 209     return !strcmp( (char *)lhs, (char *)rhs );
 210 }
 211
 212 long str_hash( void * str )
 213 {
 214     unsigned long h=0; char *s;
 215     for(s=(char *)str; *s; s++)
 216         h = h*65599 + *s;
 217     return h;
 218 }