home *** CD-ROM | disk | FTP | other *** search
/ cs.rhul.ac.uk / www.cs.rhul.ac.uk.zip / www.cs.rhul.ac.uk / pub / rdp / rdp_cs3470.tar / rdp_supp / symbol.c < prev    next >
C/C++ Source or Header  |  1998-05-07  |  17KB  |  555 lines
  1. /*******************************************************************************
  2. *
  3. * RDP release 1.50 by Adrian Johnstone (A.Johnstone@rhbnc.ac.uk) 20 December 1997
  4. *
  5. * symbol.c - a hash coded symbol table
  6. *
  7. * This file may be freely distributed. Please mail improvements to the author.
  8. *
  9. *******************************************************************************/
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include "textio.h"
  14. #include "memalloc.h"
  15. #include "symbol.h"
  16.  
  17. /* define some shorthand casts */
  18. #define TABLE ((symbol_table *) table)
  19. #define SYMBOL ((symbol_ *) symbol)
  20.  
  21. static char * symbol_root_string = "Root"; 
  22.  
  23. typedef struct scope_data_node
  24. {
  25.   char * id; 
  26. }symbol_scope_data; 
  27.  
  28. typedef struct symbol_node
  29. {
  30.   struct symbol_node
  31.   * next_hash,                /* next symbol in hash list */
  32.   * * last_hash,              /* pointer to next pointer of last_symbol in hash list */
  33.   * next_scope,               /* next symbol in scope list */
  34.   * scope;                    /* pointer to the scope symbol */
  35.   unsigned hash;              /* hash value for quick searching */
  36. }symbol_; 
  37.  
  38. typedef struct symbol_table_node
  39. {
  40.   char * name;                /* an identifying string */
  41.   symbol_ * * table;          /* table of pointers to hash lists */
  42.   symbol_ * current;          /* pointers to chain of scope lists */
  43.   symbol_ * scopes;           /* pointer to first scope list */
  44.   unsigned hash_size;         /* number of buckets in symbol table */
  45.   unsigned hash_prime;        /* hashing prime: hashsize and hashprime should be coprime */
  46.   int(* compare)(void * left, void * right); 
  47.   unsigned(* hash)(unsigned prime, void * data); 
  48.   void(* print)(const void * symbol); 
  49.   struct symbol_table_node * next;  /* pointer to last declared symbol table */
  50. }symbol_table; 
  51.  
  52. static symbol_table * symbol_tables = NULL; 
  53.  
  54. int symbol_compare_double(void * left, void * right)
  55. {
  56.   if (*((double *) left)== *((double *) right))
  57.     return 0; 
  58.   else if (*((double *) left)> *((double *) right))
  59.     return 1;
  60.   else
  61.     return - 1; 
  62. }
  63.  
  64. int symbol_compare_double_reverse(void * left, void * right)
  65. {
  66.   if (*((double *) left)== *((double *) right))
  67.     return 0; 
  68.   else if (*((double *) left)> *((double *) right))
  69.     return - 1; 
  70.   else
  71.     return 1; 
  72. }
  73.  
  74. int symbol_compare_long(void * left, void * right)
  75. {
  76.   if (*((long *) left)== *((long *) right))
  77.     return 0;
  78.   else if (*((long *) left)> *((long *) right))
  79.     return 1; 
  80.   else
  81.     return - 1; 
  82. }
  83.  
  84. int symbol_compare_long_reverse(void * left, void * right)
  85. {
  86.   if (*((long *) left)== *((long *) right))
  87.     return 0; 
  88.   else if (*((long *) left)> *((long *) right))
  89.     return - 1;
  90.   else
  91.     return 1; 
  92. }
  93.  
  94. int symbol_compare_string(void * left, void * right)
  95. {
  96.   char * left_str = *(char * *) left; 
  97.   char * right_str = *(char * *) right; 
  98.   
  99.   return strcmp(left_str, right_str); 
  100. }
  101.  
  102. int symbol_compare_string_reverse(void * left, void * right)
  103. {
  104.   char * left_str = *(char * *) left; 
  105.   char * right_str = *(char * *) right; 
  106.   
  107.   return strcmp(right_str, left_str);
  108. }
  109.  
  110. void * symbol_find(const void * table, void * key, size_t key_size, size_t symbol_size, void * scope, enum SYMBOL_FIND_OP op)
  111. {
  112.   void * temp;
  113.   
  114.   switch (op)
  115.   {
  116.     case SYMBOL_ANY: 
  117.     if ((temp = symbol_lookup_key(table, key, scope))== NULL)
  118.       return symbol_insert_key(table, key, key_size, symbol_size);
  119.     else
  120.       return temp;
  121.  
  122.     case SYMBOL_NEW:
  123.     if ((temp = symbol_lookup_key(table, key, scope))!= NULL)
  124.     {
  125.       text_message(TEXT_ERROR_ECHO, "Doubly defined symbol \'");
  126.       symbol_print_symbol(table, temp);
  127.       text_printf("\'\n");
  128.       return temp;
  129.     }
  130.     else
  131.       return symbol_insert_key(table, key, key_size, symbol_size);
  132.  
  133.     case SYMBOL_OLD:
  134.     if ((temp = symbol_lookup_key(table, key, scope))== NULL)
  135.     {
  136.       temp = symbol_insert_key(table, key, key_size, symbol_size);
  137.       text_message(TEXT_ERROR_ECHO, "Undefined symbol \'");
  138.       symbol_print_symbol(table, temp);
  139.       text_printf("\'\n");
  140.     }
  141.     return temp;
  142.  
  143.     default:
  144.     text_message(TEXT_FATAL, "internal error: illegal opcode supplied to symbol_find()");
  145.     return NULL;              /* actually this will never be executed, of course */
  146.   }
  147. }
  148.  
  149. void symbol_free_symbol(void * symbol)
  150. {
  151.   symbol_ * sym = SYMBOL - 1;
  152.  
  153.   /* first unlink: code copied from symbol_unlink with extra check */
  154.   if (sym->last_hash != NULL)
  155.     *(sym->last_hash)= sym->next_hash;  /* point previous pointer to next symbol */
  156.  
  157.   if (sym->next_hash != NULL) /* if this isn't the end of the list */
  158.     sym->next_hash->last_hash = sym->last_hash;
  159.  
  160.   mem_free(sym);              /* free the memory */
  161. }
  162.  
  163. void * symbol_get_scope(const void * table) /* return current scope */
  164. {
  165.   return TABLE->current + 1;
  166. }
  167.  
  168. unsigned symbol_hash_mem(unsigned hash_prime, void * data)
  169. {                             /* hash a string */
  170.   unsigned hashnumber = 0; 
  171.   unsigned count = *(unsigned *) data; 
  172.   char * string = *(char * *)((unsigned *) data + 1); 
  173.   
  174.   if (string != NULL)         /* Don't try and scan a vacuous string */
  175.     while (count-- > 0)       /* run up string */
  176.     hashnumber = * string++ + hash_prime * hashnumber; 
  177.   return hashnumber; 
  178. }
  179.  
  180. unsigned symbol_hash_string(unsigned hash_prime, void * data)
  181. {                             /* hash a string */
  182.   unsigned hashnumber = 0; 
  183.   char * str = *(char * *) data; 
  184.   
  185.   if (str != NULL)            /* Don't try and scan a vacuous string */
  186.     while (* str != 0)        /* run up string */
  187.     hashnumber = * str++ + hash_prime * hashnumber; 
  188.   return hashnumber; 
  189. }
  190.  
  191. unsigned symbol_hash_double(unsigned hash_prime, void * data)
  192. {                             /* hash a string */
  193.   return(unsigned)((long) hash_prime * *((long *) data)); 
  194. }
  195.  
  196. unsigned symbol_hash_long(unsigned hash_prime, void * data)
  197. {                             /* hash a string */
  198.   return(unsigned)((long) hash_prime * *((long *) data)); 
  199. }
  200.  
  201. void * symbol_insert_key(const void * table, void * key, size_t key_size, size_t symbol_size) /* lookup key in table. Return NULL if not found */
  202. {
  203.   void * sym = symbol_new_symbol(symbol_size);
  204.   
  205.   if (key_size > symbol_size)
  206.     text_message(TEXT_FATAL, "programmer error - key_size > symbol_size in symbol_insert_key\n"); 
  207.   
  208.   memcpy(sym, key, key_size);
  209.   
  210.   return symbol_insert_symbol(table, sym);
  211. }
  212.  
  213. void * symbol_insert_symbol(const void * table, void * symbol) /* insert a symbol at head of hash list */
  214. {
  215.   unsigned hash_index; 
  216.   symbol_ * s = SYMBOL - 1;
  217.   
  218.   s->hash =(* TABLE->hash)(TABLE->hash_prime, symbol);
  219.   hash_index = s->hash % TABLE->hash_size;
  220.   
  221.   s->next_hash = TABLE->table[hash_index];  /* point s at old hash list head */
  222.   TABLE->table[hash_index]= s;  /* point hash list at s */
  223.   
  224.   s->last_hash = & TABLE->table[hash_index];  /* point last hash at index pointer */
  225.   
  226.   if (s->next_hash != NULL)   /* if this wasn't the start of a new list ... */
  227.     (s->next_hash)->last_hash = &(s->next_hash);  /* ...point old list next back at s */
  228.   
  229.   /* now insert in scope list */
  230.   s->next_scope = TABLE->current->next_scope;
  231.   TABLE->current->next_scope = s;
  232.   
  233.   s->scope = TABLE->current;  /* set up pointer to scope block */
  234.   
  235.   return symbol; 
  236. }
  237.  
  238. void * symbol_lookup_key(const void * table, void * key, void * scope) /* lookup a symbol by id. Return NULL is not found */
  239. {
  240.   unsigned hash =(* TABLE->hash)(TABLE->hash_prime, key); 
  241.   symbol_ * p = TABLE->table[hash % TABLE->hash_size]; 
  242.   
  243.   /* look for symbol with same hash and a true compare */
  244.   while (p != NULL &&         /* hash!=p->hash && */(* TABLE->compare)(key, p + 1)!= 0)
  245.     p = p->next_hash; 
  246.   
  247.   if (p == NULL) return NULL;  /* Not found at all */
  248.     
  249.   if (scope != NULL && p->scope != scope) return NULL;  /* Not found in this scope level */
  250.     
  251.   return p + 1; 
  252. }
  253.  
  254. void * symbol_new_scope(void * table, char * id)
  255. {
  256.   symbol_scope_data * p =(symbol_scope_data *) symbol_new_symbol(sizeof(symbol_scope_data));  /* create new scope element */
  257.   symbol_ * s =(symbol_ *) p - 1; 
  258.   
  259.   p->id = id; 
  260.   s->next_hash = TABLE->scopes; 
  261.   TABLE->current = TABLE->scopes = s; 
  262.   if (s->next_hash != NULL)
  263.     (s->next_hash)->last_hash = &(s->next_hash); 
  264.   return p; 
  265. }
  266.  
  267. void * symbol_new_symbol(size_t size) /* allocate a new symbol node */
  268. {                             /* allocate space: crash if heap is full */
  269.   void * temp1 = mem_calloc(sizeof(symbol_)+ size, 1); 
  270.   void * temp2 =(symbol_ *) temp1 + 1; 
  271.   
  272.   return temp2; 
  273. }
  274.  
  275. void * symbol_new_table(char * name, 
  276. const unsigned symbol_hashsize, 
  277. const unsigned symbol_hashprime, 
  278. int(* compare)(void * left, void * right), 
  279. unsigned(* hash)(unsigned hash_prime, void * symbol), 
  280. void(* print)(const void * symbol)) /* create a new symbol table */
  281. {
  282.   symbol_table * temp =(symbol_table *) mem_malloc(sizeof(symbol_table)); 
  283.   symbol_scope_data * scope =(symbol_scope_data *) symbol_new_symbol(sizeof(symbol_scope_data)); 
  284.   unsigned count; 
  285.   
  286.   scope->id = symbol_root_string; 
  287.   temp->name = name; 
  288.   temp->hash_size = symbol_hashsize; 
  289.   temp->hash_prime = symbol_hashprime; 
  290.   temp->compare = compare; 
  291.   temp->hash = hash; 
  292.   temp->print = print; 
  293.   temp->table =(symbol_ * *) mem_malloc(symbol_hashsize * sizeof(symbol_ *)); 
  294.   
  295.   for (count = 0; count < symbol_hashsize; count++)
  296.     temp->table[count]= NULL; 
  297.   
  298.   temp->current = temp->scopes =(symbol_ *) scope - 1; 
  299.   
  300.   /* now hook into list of tables */
  301.   temp->next = symbol_tables; 
  302.   symbol_tables = temp; 
  303.   
  304.   return temp; 
  305. }
  306.  
  307. void * symbol_next_symbol(void * table, void * symbol) /* lookup along table from s for next identical ID. Return NULL if not found */
  308. {
  309.   symbol_ * p = SYMBOL - 1; 
  310.   
  311.   p = p->next_hash; 
  312.   while (p != NULL &&(* TABLE->compare)(symbol, p + 1)!= 0)
  313.     p = p->next_hash; 
  314.   
  315.   return p == NULL ? p: p + 1; 
  316. }
  317.  
  318. void * symbol_next_symbol_in_scope(void * symbol) /* Return next symbol in scope chain. Return NULL if at end */
  319. {
  320.   symbol_ * s =(symbol_ *)(((symbol_ *) symbol - 1)->next_scope); 
  321.   
  322.   return s == NULL ? NULL: s + 1; 
  323. }
  324.  
  325. void symbol_print_all_table(void) /* diagnostic dump of all symbol tables */
  326. {
  327.   symbol_table * temp = symbol_tables; 
  328.   
  329.   while (temp != NULL)
  330.   {
  331.     symbol_print_table(temp); 
  332.     temp = temp->next; 
  333.   }
  334. }
  335.  
  336. void symbol_print_all_table_statistics(const unsigned histogram_size) /* dump all bucket usage histograms */
  337. {
  338.   symbol_table * temp = symbol_tables; 
  339.   
  340.   while (temp != NULL)
  341.   {
  342.     symbol_print_table_statistics(temp, histogram_size); 
  343.     temp = temp->next; 
  344.   }
  345. }
  346.  
  347. void symbol_print_scope(const void * table, void * sym)
  348. {
  349.   sym = symbol_next_symbol_in_scope(sym); 
  350.   
  351.   while (sym != NULL)
  352.   {
  353.     (* TABLE->print)(sym); 
  354.     text_printf("\n"); 
  355.     
  356.     sym = symbol_next_symbol_in_scope(sym); 
  357.   }
  358. }
  359.  
  360. void symbol_print_string(const void * symbol)
  361. {
  362.   text_printf("%s", symbol == NULL ? "Null symbol": *((char * *) symbol)); 
  363. }
  364.  
  365. void symbol_print_symbol(const void * table, const void * symbol)
  366. {
  367.   (* TABLE->print)(symbol); 
  368. }
  369.  
  370. void symbol_print_table(const void * table) /* dump symbol table */
  371. {                             /* diagnostic dump of symbol table */
  372.   unsigned temp; 
  373.   symbol_ * p = TABLE->scopes; 
  374.   
  375.   text_message(TEXT_INFO, "Symbol table \'%s\': dump by hash bucket\n\n", TABLE->name); 
  376.   for (temp = 0; temp < TABLE->hash_size; temp++)
  377.   {
  378.     symbol_ * p = TABLE->table[temp]; 
  379.     
  380.     text_printf("*** Bucket %u:\n", temp); 
  381.     while (p != NULL)
  382.     {
  383.       (* TABLE->print)(p + 1); 
  384.       text_printf("\n"); 
  385.       p = p->next_hash; 
  386.     }
  387.   }
  388.   text_printf("\n"); 
  389.   
  390.   text_message(TEXT_INFO, "Symbol table \'%s\' dump by scope chain\n", TABLE->name); 
  391.   while (p != NULL)
  392.   {
  393.     symbol_print_scope(table, p + 1); 
  394.     p = p->next_hash; 
  395.   }
  396.   text_printf("\n"); 
  397. }
  398.  
  399. void symbol_print_table_statistics(const void * table, const unsigned histogram_size) /* dump symbol statistics */
  400. {                             /* diagnostic dump of symbol table */
  401.   unsigned temp_unsigned; 
  402.   int symbols = 0, 
  403.   mean = 0; 
  404.   
  405.   int * histogram =(int *) mem_calloc(histogram_size, sizeof(int)); 
  406.   
  407.   for (temp_unsigned = 0; temp_unsigned < TABLE->hash_size; temp_unsigned++)
  408.   {
  409.     symbol_ * p = TABLE->table[temp_unsigned]; 
  410.     unsigned count = 0; 
  411.     
  412.     while (p != NULL)
  413.     {
  414.       symbols++; 
  415.       count++; 
  416.       p = p->next_hash; 
  417.     }
  418.     histogram[count < histogram_size - 1 ? count: histogram_size - 1]++;  /* bump histogram bucket */
  419.   }
  420.   
  421.   text_message(TEXT_INFO, "\nSymbol table `%s\' has %u buckets and contains %i symbols\n", TABLE->name, TABLE->hash_size, symbols); 
  422.   
  423.   /* Now calculate mean utilisation */
  424.   
  425.   for (temp_unsigned = 0; temp_unsigned < histogram_size; temp_unsigned++)
  426.   {
  427.     text_printf("%3i bucket%s %i symbol%s\n", 
  428.     histogram[temp_unsigned], histogram[temp_unsigned]== 1 ? "  has ": "s have", 
  429.     temp_unsigned, temp_unsigned == 1 ? "": temp_unsigned == histogram_size - 1 ? "s or more": "s"); 
  430.     mean +=(temp_unsigned + 1)* histogram[temp_unsigned]; 
  431.   }
  432.   text_message(TEXT_INFO, "\nMean list length is %f\n", ((float) mean /(float) TABLE->hash_size)- 1); 
  433.   
  434.   mem_free(histogram);        /* release memory used for histogram */
  435. }
  436.  
  437. void symbol_print_double(const void * symbol)
  438. {
  439.   if (symbol == NULL)
  440.     text_printf("Null symbol"); 
  441.   else
  442.     text_printf("%lf", *((double *) symbol)); 
  443. }
  444.  
  445. void symbol_print_long(const void * symbol)
  446. {
  447.   if (symbol == NULL)
  448.     text_printf("Null symbol"); 
  449.   else
  450.     text_printf("%lu", *((long *) symbol)); 
  451. }
  452.  
  453. void symbol_set_scope(void * table, void * symbol)
  454. {
  455.   symbol_ * s = SYMBOL - 1; 
  456.   
  457.   TABLE->current = s; 
  458. }
  459.  
  460. /* Sort a scope region. Don't change positions in the hash table:
  461.    just move pointers in the scope chain */
  462. void symbol_sort_scope(void * table, void * symbol)
  463. {
  464.   typedef struct sort_list_type
  465.   {
  466.     symbol_ * s; 
  467.     struct sort_list_type * next; 
  468.     struct sort_list_type * * last; 
  469.   }sort_list; 
  470.   
  471.   symbol_ * s = SYMBOL - 1; 
  472.   
  473.   sort_list * sorted =(sort_list *) mem_malloc(sizeof(sort_list)); 
  474.   sort_list * temp_sorted; 
  475.   symbol_ * temp_scope; 
  476.   
  477.   if (s->next_scope == NULL)  /* attempt to sort empty list */
  478.     return; 
  479.   
  480.   if (s->next_scope->next_scope == NULL) /* attempt to sort list of one */
  481.     return; 
  482.   
  483.   /* put first symbol in scope on sorted list */
  484.   sorted->s = s->next_scope; 
  485.   sorted->last = & sorted; 
  486.   
  487.   /* put a sentinel on the end */
  488.   sorted->next =(sort_list *) mem_calloc(sizeof(sort_list), 1); 
  489.   sorted->next->last = & sorted->next; 
  490.   
  491.   /* first create sorted list by insertion sort on sort_list */
  492.   temp_scope = s->next_scope->next_scope;  /* point temp_scope at second element */
  493.   while (temp_scope != NULL)  /* iterate over entire scope list */
  494.   {
  495.     sort_list * new_sorted; 
  496.     
  497.     /* find place in sorted list for insertion */
  498.     temp_sorted = sorted; 
  499.     while (temp_sorted->next != NULL)
  500.     {
  501.       if ((* TABLE->compare)(temp_scope + 1, temp_sorted->s + 1)< 0)
  502.         break; 
  503.       temp_sorted = temp_sorted->next; 
  504.     }
  505.     
  506.     /* now insert new sorted node before the one pointed to by temp_sorted */
  507.     new_sorted =(sort_list *) mem_malloc(sizeof(sort_list));  /* create node */
  508.     new_sorted->s = temp_scope;  /* point at current scope symbol */
  509.     new_sorted->next = temp_sorted;  /* look forwards... */
  510.     new_sorted->last = temp_sorted->last;  /* and backwards */
  511.     *(temp_sorted->last)= new_sorted;  /* make temp's predecessor look at us */
  512.     temp_sorted->last = & new_sorted->next;  /* and make temp look at us */
  513.     
  514.     temp_scope = temp_scope->next_scope;  /* step to next element in scope list */
  515.   }
  516.   
  517.   /* now rebuild scope pointers in scope range: the list should be the right length already! */
  518.   temp_sorted = sorted; 
  519.   temp_scope = s; 
  520.   while (temp_sorted != NULL) /* iterate over sorted list */
  521.   {
  522.     sort_list * free_sorted = temp_sorted; 
  523.     
  524.     temp_scope->next_scope = temp_sorted->s;  /* point next scope to this sorted symbol */
  525.     temp_sorted = temp_sorted->next;  /* move to next sorted symbol */
  526.     mem_free(free_sorted);    /* free as we go */
  527.     temp_scope = temp_scope->next_scope;  /* move to next sorted scope element */
  528.   }
  529. }
  530.  
  531. void symbol_unlink_scope(void * symbol)
  532. {
  533.   symbol_ * s = SYMBOL - 1; 
  534.   
  535.   s = s->next_scope; 
  536.   
  537.   while (s != NULL)
  538.   {
  539.     symbol_unlink_symbol(s + 1); 
  540.     s = s->next_scope; 
  541.   }
  542. }
  543.  
  544. void symbol_unlink_symbol(void * symbol) /* remove a symbol from the hash chain */
  545. {
  546.   symbol_ * s = SYMBOL - 1; 
  547.   
  548.   *(s->last_hash)= s->next_hash;  /* point previous pointer to next symbol */
  549.   
  550.   if (s->next_hash != NULL)   /* if this isn't the end of the list */
  551.     s->next_hash->last_hash = s->last_hash; 
  552. }
  553.  
  554. /* End of symbol.c */
  555.