G:/ScriptBasic/source/sym.c

Go to the documentation of this file.
00001 /* 
00002 FILE:   sym.c
00003 HEADER: sym.h
00004 
00005 --GNU LGPL
00006 This library is free software; you can redistribute it and/or
00007 modify it under the terms of the GNU Lesser General Public
00008 License as published by the Free Software Foundation; either
00009 version 2.1 of the License, or (at your option) any later version.
00010 
00011 This library is distributed in the hope that it will be useful,
00012 but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 Lesser General Public License for more details.
00015 
00016 You should have received a copy of the GNU Lesser General Public
00017 License along with this library; if not, write to the Free Software
00018 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019 
00020 TO_HEADER:
00021 #include <stddef.h>
00022 typedef struct _symbol {
00023   char  *name;
00024   void  *value;
00025   struct _symbol *small_son, *big_son;
00026   } Symbol, *pSymbol, **SymbolTable;
00027 
00028 #define SymbolValue(x) (x->value)
00029 // get the pointer to the stored string from the value pointer 
00030 #define SymbolName(x) ((char *)*((char **)( ((unsigned char *)(x)) - offsetof(struct _symbol,value) + offsetof(struct _symbol,name) )))
00031 
00032 */
00033 #include <string.h>
00034 #include <ctype.h>
00035 #include "sym.h"
00036 
00037 static void _to_lower(char *s){
00038   /* return */ /* uncomment this return to make variable names in scriba case sensitive */
00039   while( *s ){
00040     if( isupper(*s) )*s = tolower(*s);
00041     s++;
00042     }
00043   }
00044 
00045 /*
00046 ** HASH function
00047 **
00048 ** I found this function on the page 436. of the dragon book.
00049 **
00050 ** The dragon book:
00051 ** Aho-Sethi-Ulman : Compilers
00052 **      Principles, techniques, and Tools
00053 ** Addison-Wesley Publishing Company 1986
00054 **
00055 ** The only modification what was made by me is the letter 'l'
00056 ** following the 0xf0000000 constant for the specifying it long
00057 ** explicitly. ( The constant PRIME can be found in the file defines.h
00058 ** either, but the redefinition of it is identical. )
00059 */
00060 #define PRIME 211
00061 #define MASK  0xf0000000l
00062 
00063 
00064 static int hashpjw(s)
00065 char   *s;
00066 {
00067   char *p;
00068   unsigned long h = 0, g;
00069   for ( p = s; *p != '\0'; p = p+1 ) {
00070     h = (h << 4) + (*p);
00071     if (g = h&MASK) {
00072       h = h ^ (g >> 24);
00073       h = h ^ g;
00074     }
00075   }
00076   return h % PRIME;
00077 }
00078 
00079 /*POD
00080 =H sym_NewSymbolTable()
00081 
00082 This function creates a new symbol table. Later this symbol table should be used
00083 to store and retrieve symbol information.
00084 /*FUNCTION*/
00085 SymbolTable sym_NewSymbolTable(
00086   void* (*memory_allocating_function)(size_t,void *),
00087   void *pMemorySegment
00088   ){
00089 /*noverbatim
00090 The second argument should point to the memory allocating function that the
00091 symbol table creation process should use. The last argument is an pointer to a memory
00092 segment which is passed to the memory allocation function. The actual arguments of the
00093 memory allocation function fits the allocation function from the package alloc. However the
00094 defintion is general enough to use any other function.
00095 CUT*/
00096   SymbolTable t;
00097   int i;
00098 
00099   if( ! (t = (SymbolTable)memory_allocating_function(PRIME*sizeof(pSymbol),pMemorySegment)) )return NULL;
00100   for( i=0 ; i<PRIME ; i++ )t[i]=NULL;
00101   return t;
00102   }
00103 
00104 
00105 static void sym_FreeSymbolSub(
00106   pSymbol table,
00107   void (*memory_releasing_function)(void *, void *),
00108   void *pMemorySegment
00109   ){
00110   if( ! table )return;
00111   if( table->small_son )
00112     sym_FreeSymbolSub(table->small_son,memory_releasing_function,pMemorySegment);
00113   if( table->big_son )
00114     sym_FreeSymbolSub(table->big_son,memory_releasing_function,pMemorySegment);
00115   if( table->name )
00116     memory_releasing_function(table->name,pMemorySegment);
00117   memory_releasing_function(table,pMemorySegment);
00118   }
00119 
00120 /*POD
00121 =H sym_FreeSymbolTable()
00122 
00123 This function should be used to release the memory allocated for a symbol table.
00124 This function releases all the memory that was allocated during symbol table creation
00125 and during symbol insertion.
00126 
00127 Note that the memory allocated outside the symbol table handling routines is not
00128 released. This means that it is the caller responsibility to relase all memory
00129 that holds the actual values associated with the symbols.
00130 /*FUNCTION*/
00131 void sym_FreeSymbolTable(
00132   SymbolTable table,
00133   void (*memory_releasing_function)(void *,void *),
00134   void *pMemorySegment
00135   ){
00136 /*noverbatim
00137 CUT*/
00138   int i;
00139 
00140   for( i=0 ; i<PRIME ; i++ )
00141     sym_FreeSymbolSub(table[i],memory_releasing_function,pMemorySegment);
00142 
00143   memory_releasing_function(table,pMemorySegment);
00144   }
00145 
00146 static void sym_TraverseSymbolTableSub(
00147   pSymbol table,
00148   void (*call_back_function)(char *SymbolName, void *SymbolValue, void *f),
00149   void *f
00150   ){
00151 
00152   if( ! table )return;
00153   if( table->small_son )
00154     sym_TraverseSymbolTableSub(table->small_son,call_back_function,f);
00155   if( table->big_son )
00156     sym_TraverseSymbolTableSub(table->big_son,call_back_function,f);
00157   if( table->name )
00158     call_back_function(table->name,table->value,f);
00159   }
00160 
00161 /*POD
00162 =H sym_TraverseSymbolTable()
00163 
00164 This function can be used to traverse through all the symbols stored
00165 in a symbol table. The function starts to go through the symbols and
00166 for each symbol calls the function T<call_back_function>.
00167 /*FUNCTION*/
00168 void sym_TraverseSymbolTable(
00169   SymbolTable table,
00170   void (*call_back_function)(char *SymbolName, void *SymbolValue, void *f),
00171   void *f
00172   ){
00173 /*noverbatim
00174 The first argument is the symbol table to traverse. The second argument is the
00175 function to be called for each symbol. This function gets three arguments. The
00176 first is a pointer to the symbol string. The second is the pointer to the symbol
00177 arguments. The third argument is a general pointer which is passed to the
00178 function T<sym_TraverseSymbolTable>.
00179 
00180 Note that the call back function gets the pointer to the symbol arguments and
00181 not the pointer to the pointer to the symbol arguments, and therefore call back
00182 function can not change the actual symbol value pointer.
00183 CUT*/
00184   int i;
00185 
00186   if( !table ) return;
00187   for( i=0 ; i<PRIME ; i++ )
00188     sym_TraverseSymbolTableSub(table[i],call_back_function,f);
00189   }
00190 
00191 /*POD
00192 =H sym_LookupSymbol()
00193 
00194 This function should be used to search a symbol or to insert a new symbol.
00195 
00196 /*FUNCTION*/
00197 void **sym_LookupSymbol(
00198   char *s,                 /* zero terminated string containing the symbol                 */
00199   SymbolTable hashtable,   /* the symbol table                                             */
00200   int insert,              /* should a new empty symbol inserted, or return NULL instead   */
00201   void* (*memory_allocating_function)(size_t, void *),
00202   void (*memory_releasing_function)(void *, void *),
00203   void *pMemorySegment
00204   ){
00205 /*noverbatim
00206 
00207 This function usually returns a pointer to the T<void *> pointer which is
00208 supposed to point to the structure, which actually holds the parameters for
00209 the symbol. When a symbol is not found in the symbol table the parameter T<insert>
00210 is used to decide what to do. If this parameter is zero the function returns T<NULL>.
00211 If this parameter is 1 the function creates a new symbol and returns a pointer to the
00212 T<void *> pointer associated with the symbol.
00213 
00214 If a new symbol is to be inserted and the function returns T<NULL> means that the memory 
00215 allocation function has failed.
00216 
00217 If the new symbol was created and a pointer to the T<void *> pointer is returned the value of
00218 the pointer is T<NULL>. In other words:
00219 
00220 =verbatim
00221 
00222 void **a;
00223 
00224 a = sym_LookupSymbol(s,table,1,mymema,mymemr,p);
00225 
00226 if( a == NULL )error("memory releasing error");
00227 if( *a == NULL )error("symbol not found");
00228 
00229 =noverbatim
00230 
00231 CUT*/
00232   pSymbol *work_pointer;
00233   int k;
00234 
00235   /* convert the string to lower case to make it case insensitive */
00236   _to_lower(s);
00237 
00238   k = hashpjw( s );
00239   work_pointer = &(hashtable[ k ]);
00240   while( *work_pointer && (k=strcmp(s,(*work_pointer)->name)) )
00241     work_pointer= k > 0 ? &((*work_pointer)->big_son)  :
00242         &((*work_pointer)->small_son);
00243 
00244   if( *work_pointer )return &((*work_pointer)->value);
00245 
00246   /* if there is no such symbol and we need not insert it then return NULL */
00247   if( ! insert )return NULL;
00248 
00249   /* there is no such symbol and we have to create it */
00250   /* allocate memory for the symbol entry and the copy of the name */
00251   *work_pointer = (pSymbol)memory_allocating_function( sizeof(Symbol),pMemorySegment);
00252   if( !*work_pointer )return NULL;
00253 
00254   (*work_pointer)->name = (char *)memory_allocating_function( (strlen( s )+1)*sizeof(char),pMemorySegment );
00255   if( !(*work_pointer)->name ) {
00256     memory_releasing_function(*work_pointer,pMemorySegment);
00257     return NULL;
00258     }
00259   strcpy((*work_pointer)->name , s);
00260 
00261   /* value is always NULL for a newly allocated symbol */
00262   (*work_pointer)->value = NULL;
00263 
00264   /* no sons */
00265   (*work_pointer)->big_son =
00266       (*work_pointer)->small_son = NULL;
00267 
00268   return &((*work_pointer)->value);
00269 }
00270 
00271 /*POD
00272 =H sym_DeleteSymbol()
00273 
00274 This function should be used to delete a symbol from the symbol table
00275 
00276 /*FUNCTION*/
00277 int sym_DeleteSymbol(
00278   char *s,                 /* zero terminated string containing the symbol                 */
00279   SymbolTable hashtable,   /* the symbol table                                             */
00280   void (*memory_releasing_function)(void *, void *),
00281   void *pMemorySegment
00282   ){
00283 /*noverbatim
00284 
00285 This function searches the given symbol and if the symbol is found it deletes it from the
00286 symbol table. If the symbol was found in the symbol table the return value is zero. If
00287 the symbol was not found the return value is 1. This may be interpreted by the caller as
00288 an error or as a warning.
00289 
00290 Note that this function only deletes the memory that was part of the symbol table. The
00291 memory allocated by the caller and handled via the pointer T<value> usually returned by
00292 R<sym_LookupSymbol()> should be released by the caller.
00293 
00294 CUT*/
00295   pSymbol *work_pointer,*swp;
00296   pSymbol sym;
00297   int k;
00298 
00299   /* convert the string to lower case to make it case insensitive */
00300   _to_lower(s);
00301 
00302   k = hashpjw( s );
00303   work_pointer = swp = &(hashtable[ k ]);
00304   while( *work_pointer && (k=strcmp(s,(*work_pointer)->name)) )
00305     work_pointer= k > 0 ? &((*work_pointer)->big_son)  :
00306         &((*work_pointer)->small_son);
00307 
00308   /* if the symbol is not in the table there is nothing to do */
00309   if( *work_pointer == NULL )return 1;
00310   sym = *work_pointer;
00311   /* hook off this element */
00312   *work_pointer = NULL;
00313 
00314   if( sym->big_son ){
00315     *work_pointer = sym->big_son;
00316     if(  sym->small_son == NULL ){
00317       memory_releasing_function(sym->name,pMemorySegment);  
00318       memory_releasing_function(sym,pMemorySegment);
00319       return 0;/* there is big_son, but no small_son */
00320       }
00321     }else{
00322     /* if there is no big_son */
00323     if( sym->small_son ){
00324       *work_pointer = sym->small_son;
00325       memory_releasing_function(sym->name,pMemorySegment);  
00326       memory_releasing_function(sym,pMemorySegment);
00327       return 0;/* there is no big_son, small_son hooked */
00328       }
00329     /* there are no sons at all */
00330     memory_releasing_function(sym->name,pMemorySegment);  
00331     memory_releasing_function(sym,pMemorySegment);
00332     return 0;
00333     }
00334 
00335   /* start from the root again and find the new place for the small_son */
00336   work_pointer = swp;
00337   while( *work_pointer && (k=strcmp(sym->small_son->name,(*work_pointer)->name)) )
00338     work_pointer= k > 0 ? &((*work_pointer)->big_son)  :
00339         &((*work_pointer)->small_son);
00340 
00341   /* hook the small son on it */
00342   *work_pointer = sym->small_son;
00343 
00344   /* finally erase the symbol */
00345   memory_releasing_function(sym->name,pMemorySegment);  
00346   memory_releasing_function(sym,pMemorySegment);  
00347   
00348   return 0;
00349 }

Generated on Sun Mar 12 23:56:31 2006 for ScriptBasic by  doxygen 1.4.6-NO