vvp/symbols.cc

   1 /*
   2  * Copyright (c) 2001 Stephen Williams (steve@icarus.com)
   3  *
   4  *    This source code is free software; you can redistribute it
   5  *    and/or modify it in source code form under the terms of the GNU
   6  *    General Public License as published by the Free Software
   7  *    Foundation; either version 2 of the License, or (at your option)
   8  *    any later version.
   9  *
  10  *    This program is distributed in the hope that it will be useful,
  11  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *    GNU General Public License for more details.
  14  *
  15  *    You should have received a copy of the GNU General Public License
  16  *    along with this program; if not, write to the Free Software
  17  *    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  18  */
  19 #ifdef HAVE_CVS_IDENT
  20 #ident "$Id: symbols.cc,v 1.12 2004/10/04 01:10:59 steve Exp $"
  21 #endif
  22
  23 # include  "symbols.h"
  24 # include  <string.h>
  25 # include  <stdlib.h>
  26 #ifdef HAVE_MALLOC_H
  27 # include  <malloc.h>
  28 #endif
  29 # include  <assert.h>
  30
  31 /*
  32  * The keys of the symbol table are null terminated strings. Keep them
  33  * in a string buffer, with the strings separated by a single null,
  34  * for compact use of memory. This also makes it easy to delete the
  35  * entire lot of keys, simply by deleting the heaps.
  36  *
  37  * The key_strdup() function below allocates the strings from this
  38  * buffer, possibly making a new buffer if needed.
  39  */
  40 struct key_strings {
  41       struct key_strings*next;
  42       char data[64*1024 - sizeof(struct key_strings*)];
  43 };
  44
  45 struct symbol_table_s {
  46       struct tree_node_*root;
  47       struct key_strings*str_chunk;
  48       unsigned str_used;
  49 };
  50
  51 static char*key_strdup(struct symbol_table_s*tab, const char*str)
  52 {
  53       unsigned len = strlen(str);
  54       assert( (len+1) <= sizeof tab->str_chunk->data );
  55
  56       if ( (len+1) > (sizeof tab->str_chunk->data - tab->str_used) ) {
  57             key_strings*tmp = new key_strings;
  58             tmp->next = tab->str_chunk;
  59             tab->str_chunk = tmp;
  60             tab->str_used = 0;
  61       }
  62
  63       char*res = tab->str_chunk->data + tab->str_used;
  64       tab->str_used += len + 1;
  65       strcpy(res, str);
  66       return res;
  67 }
  68
  69 /*
  70  * This is a B-Tree data structure, where there are nodes and
  71  * leaves.
  72  *
  73  * Nodes have a bunch of pointers to children. Each child pointer has
  74  * associated with it a key that is the largest key referenced by that
  75  * child. So, if the key being searched for has a value <= the first
  76  * key of a node, then the value is in the first child.
  77  *
  78  * leaves have a sorted table of key-value pairs. The search can use a
  79  * simple binary search to find an item. Each key represents an item.
  80  */
  81
  82 const unsigned leaf_width = 254;
  83 const unsigned node_width = 508;
  84
  85 struct tree_node_ {
  86       bool leaf_flag;
  87       unsigned count;
  88       struct tree_node_*parent;
  89
  90       union {
  91             struct {
  92                   char*key;
  93                   symbol_value_t val;
  94             } leaf[leaf_width];
  95
  96             struct tree_node_*child[node_width];
  97       };
  98
  99 };
 100
 101 static inline char* node_last_key(struct tree_node_*node)
 102 {
 103       while (node->leaf_flag == false)
 104             node = node->child[node->count-1];
 105
 106       return node->leaf[node->count-1].key;
 107 }
 108
 109 /*
 110  * Allocate a new symbol table means creating the table structure and
 111  * a root node, and initializing the pointers and members of the root
 112  * node.
 113  */
 114 symbol_table_t new_symbol_table(void)
 115 {
 116       symbol_table_t tbl = new struct symbol_table_s;
 117       tbl->root = new struct tree_node_;
 118       tbl->root->leaf_flag = false;
 119       tbl->root->count = 0;
 120       tbl->root->parent = 0;
 121
 122       tbl->str_chunk = new key_strings;
 123       tbl->str_chunk->next = 0;
 124       tbl->str_used = 0;
 125
 126       return tbl;
 127 }
 128
 129 static void delete_symbol_node(struct tree_node_*cur)
 130 {
 131       if (! cur->leaf_flag) {
 132             for (unsigned idx = 0 ;  idx < cur->count ;  idx += 1)
 133                   delete_symbol_node(cur->child[idx]);
 134       }
 135
 136       delete cur;
 137 }
 138
 139 void delete_symbol_table(symbol_table_t tab)
 140 {
 141       delete_symbol_node(tab->root);
 142       while (tab->str_chunk) {
 143             key_strings*tmp = tab->str_chunk;
 144             tab->str_chunk = tmp->next;
 145             delete tmp;
 146       }
 147
 148       delete tab;
 149 }
 150
 151 /* Do as split_leaf_ does, but for nodes. */
 152 static void split_node_(struct tree_node_*cur)
 153 {
 154         unsigned int idx, idx1, idx2, tmp;
 155         struct tree_node_ *new_node;
 156
 157         assert(!cur->leaf_flag);
 158         if (cur->parent)  assert(! cur->parent->leaf_flag);
 159
 160         while (cur->count == node_width)
 161         {
 162                 /* Create a new node to hold half the data from cur. */
 163                 new_node = new struct tree_node_;
 164                 new_node->leaf_flag = false;
 165                 new_node->count = cur->count / 2;
 166                 if (cur->parent)
 167                         /* cur is not root; new_node becomes sibling. */
 168                         new_node->parent = cur->parent;
 169
 170                 /* Move the last half of the data from the end of the old node
 171                    to the beginning of the new node. At the same time, reduce
 172                    the size of the old node. */
 173                 idx1 = new_node->count;
 174                 idx2 = cur->count;
 175                 while (idx1 > 0) {
 176                       idx1 -= 1;
 177                       idx2 -= 1;
 178                       new_node->child[idx1] = cur->child[idx2];
 179                       new_node->child[idx1]->parent = new_node;
 180                       cur->count -= 1;
 181                 }
 182
 183                 assert(new_node->count > 0);
 184                 assert(cur->count > 0);
 185
 186                 if (cur->parent == 0) {
 187                         /* cur is root. Move first half of children to
 188                            another new node, and put the two new nodes
 189                            in cur. The plan here is to make cur into
 190                            the new root and split its contents into 2
 191                            children. */
 192
 193                       new_node->parent = cur;
 194                       struct tree_node_*new2_node = new struct tree_node_;
 195                       new2_node->leaf_flag = false;
 196                       new2_node->count = cur->count;
 197                       new2_node->parent = cur;
 198                       for (idx = 0; idx < cur->count; idx += 1) {
 199                             new2_node->child[idx] = cur->child[idx];
 200                             new2_node->child[idx]->parent = new2_node;
 201                       }
 202                       cur->child[0] = new2_node;
 203                       cur->child[1] = new_node;
 204                       cur->count = 2;
 205                         /* no more ancestors, stop the while loop */
 206                       break;
 207                 }
 208
 209                 /* cur is not root. hook new_node to cur->parent. */
 210                 idx = 0;
 211                 while (cur->parent->child[idx] != cur) {
 212                         assert(idx < cur->parent->count);
 213                         idx += 1;
 214                 }
 215
 216                 idx += 1;
 217
 218                 for (tmp = cur->parent->count ;  tmp > idx ;  tmp -= 1)
 219                         cur->parent->child[tmp] = cur->parent->child[tmp-1];
 220
 221                 cur->parent->child[idx] = new_node;
 222                 cur->parent->count += 1;
 223
 224                 /* check the ancestor */
 225                 cur = cur->parent;
 226         }
 227 }
 228
 229 /*
 230  * This function takes a leaf node and splits in into two. Move half
 231  * the leaf keys into the new node, and add the new leaf into the
 232  * parent node.
 233  */
 234 static struct tree_node_* split_leaf_(struct tree_node_*cur)
 235 {
 236       assert(cur->leaf_flag);
 237       assert(cur->parent);
 238       assert(! cur->parent->leaf_flag);
 239
 240         /* Create a new leaf to hold half the data from the old leaf. */
 241       struct tree_node_*new_leaf = new struct tree_node_;
 242       new_leaf->leaf_flag = true;
 243       new_leaf->count = cur->count / 2;
 244       new_leaf->parent = cur->parent;
 245
 246         /* Move the last half of the data from the end of the old leaf
 247            to the beginning of the new leaf. At the same time, reduce
 248            the size of the old leaf. */
 249       unsigned idx1 = new_leaf->count;
 250       unsigned idx2 = cur->count;
 251       while (idx1 > 0) {
 252             idx1 -= 1;
 253             idx2 -= 1;
 254             new_leaf->leaf[idx1] = cur->leaf[idx2];
 255             cur->count -= 1;
 256       }
 257
 258       assert(new_leaf->count > 0);
 259       assert(cur->count > 0);
 260
 261       unsigned idx = 0;
 262       while (cur->parent->child[idx] != cur) {
 263             assert(idx < cur->parent->count);
 264             idx += 1;
 265       }
 266
 267       idx += 1;
 268
 269       for (unsigned tmp = cur->parent->count ;  tmp > idx ;  tmp -= 1)
 270             cur->parent->child[tmp] = cur->parent->child[tmp-1];
 271
 272       cur->parent->child[idx] = new_leaf;
 273       cur->parent->count += 1;
 274
 275       if (cur->parent->count == node_width)
 276             split_node_(cur->parent);
 277
 278       return new_leaf;
 279 }
 280
 281
 282 /*
 283  * This function searches tree recursively for the key. If the value
 284  * is not found (and we are at a leaf) then set the key with the given
 285  * value. If the key is found, set the value only if the force_flag is
 286  * true.
 287  */
 288
 289 static symbol_value_t find_value_(symbol_table_t tbl, struct tree_node_*cur,
 290                                  const char*key, symbol_value_t val,
 291                                  bool force_flag)
 292 {
 293       if (cur->leaf_flag) {
 294
 295             unsigned idx = 0;
 296             for (;;) {
 297                     /* If we run out of keys in the leaf, then add
 298                        this at the end of the leaf. */
 299                   if (idx == cur->count) {
 300                         cur->leaf[idx].key = key_strdup(tbl, key);
 301                         cur->leaf[idx].val = val;
 302                         cur->count += 1;
 303                         if (cur->count == leaf_width)
 304                               split_leaf_(cur);
 305
 306                         return val;
 307                   }
 308
 309                   int rc = strcmp(key, cur->leaf[idx].key);
 310
 311                     /* If we found the key already in the table, then
 312                        set the new value and break. */
 313                   if (rc == 0) {
 314                         if (force_flag)
 315                               cur->leaf[idx].val = val;
 316                         return cur->leaf[idx].val;
 317                   }
 318
 319                     /* If this key goes before the current key, then
 320                        push all the following entries back and add
 321                        this key here. */
 322                   if (rc < 0) {
 323                         for (unsigned tmp = cur->count; tmp > idx; tmp -= 1)
 324                               cur->leaf[tmp] = cur->leaf[tmp-1];
 325
 326                         cur->leaf[idx].key = key_strdup(tbl, key);
 327                         cur->leaf[idx].val = val;
 328                         cur->count += 1;
 329                         if (cur->count == leaf_width)
 330                               split_leaf_(cur);
 331
 332                         return val;
 333                   }
 334
 335                   idx += 1;
 336             }
 337
 338       } else {
 339               /* Do a binary search within the inner node. */
 340             unsigned min = 0;
 341             unsigned max = cur->count;
 342             unsigned idx = max/2;
 343             for (;;) {
 344                   int rc = strcmp(key, node_last_key(cur->child[idx]));
 345                   if (rc == 0) {
 346                         return find_value_(tbl, cur->child[idx],
 347                                            key, val, force_flag);
 348                   }
 349
 350                   if (rc > 0) {
 351                         min = idx + 1;
 352                         if (min == cur->count)
 353                               return find_value_(tbl, cur->child[idx],
 354                                                  key, val, force_flag);
 355                         if (min == max)
 356                               return find_value_(tbl, cur->child[max],
 357                                                  key, val, force_flag);
 358
 359                         idx = min + (max-min)/2;
 360
 361                   } else  {
 362                         max = idx;
 363                         if (idx == min)
 364                               return find_value_(tbl, cur->child[idx],
 365                                                  key, val, force_flag);
 366                         idx = min + (max-min)/2;
 367                   }
 368             }
 369       }
 370
 371       assert(0);
 372       { symbol_value_t tmp;
 373         tmp.num = 0;
 374         return tmp;
 375       }
 376 }
 377
 378 void sym_set_value(symbol_table_t tbl, const char*key, symbol_value_t val)
 379 {
 380       if (tbl->root->count == 0) {
 381               /* Handle the special case that this is the very first
 382                  value in the symbol table. Create the first leaf node
 383                  and initialize the pointers. */
 384             struct tree_node_*cur = new struct tree_node_;
 385             cur->leaf_flag = true;
 386             cur->parent = tbl->root;
 387             cur->count = 1;
 388             cur->leaf[0].key = key_strdup(tbl, key);
 389             cur->leaf[0].val = val;
 390
 391             tbl->root->count = 1;
 392             tbl->root->child[0] = cur;
 393       } else {
 394             find_value_(tbl, tbl->root, key, val, true);
 395       }
 396 }
 397
 398 symbol_value_t sym_get_value(symbol_table_t tbl, const char*key)
 399 {
 400       symbol_value_t def;
 401       def.num = 0;
 402
 403       if (tbl->root->count == 0) {
 404               /* Handle the special case that this is the very first
 405                  value in the symbol table. Create the first leaf node
 406                  and initialize the pointers. */
 407             struct tree_node_*cur = new struct tree_node_;
 408             cur->leaf_flag = true;
 409             cur->parent = tbl->root;
 410             cur->count = 1;
 411             cur->leaf[0].key = key_strdup(tbl, key);
 412             cur->leaf[0].val = def;
 413
 414             tbl->root->count = 1;
 415             tbl->root->child[0] = cur;
 416             return cur->leaf[0].val;
 417       } else {
 418             return find_value_(tbl, tbl->root, key, def, false);
 419       }
 420 }
 421
 422
 423 /*
 424  * $Log: symbols.cc,v $
 425  * Revision 1.12  2004/10/04 01:10:59  steve
 426  *  Clean up spurious trailing white space.
 427  *
 428  * Revision 1.11  2003/02/09 23:33:26  steve
 429  *  Spelling fixes.
 430  *
 431  * Revision 1.10  2002/08/12 01:35:08  steve
 432  *  conditional ident string using autoconfig.
 433  *
 434  * Revision 1.9  2002/07/15 00:21:42  steve
 435  *  Fix initialization of symbol table string heap.
 436  *
 437  * Revision 1.8  2002/07/09 03:20:51  steve
 438  *  Fix split of root btree node.
 439  *
 440  * Revision 1.7  2002/07/05 04:40:59  steve
 441  *  Symbol table uses more efficient key string allocator,
 442  *  and remove all the symbol tables after compile is done.
 443  *
 444  * Revision 1.6  2002/07/05 02:50:58  steve
 445  *  Remove the vpi object symbol table after compile.
 446  *
 447  * Revision 1.5  2002/05/29 05:37:35  steve
 448  *  Use binary search to speed up deep lookups.
 449  *
 450  * Revision 1.4  2001/11/02 04:48:03  steve
 451  *  Implement split_node for symbol table (hendrik)
 452  *
 453  * Revision 1.3  2001/05/09 04:23:19  steve
 454  *  Now that the interactive debugger exists,
 455  *  there is no use for the output dump.
 456  *
 457  * Revision 1.2  2001/03/18 00:37:55  steve
 458  *  Add support for vpi scopes.
 459  *
 460  * Revision 1.1  2001/03/11 00:29:39  steve
 461  *  Add the vvp engine to cvs.
 462  *
 463  */
 464