MPC.3.5.LINUX/structures/name_table.c

   1 /********************************************************************
   2
   3         name-table.c - the functions used for name table handling. The
   4         name table is a binary tree. The node's left child has the name
   5         alphabetically before the name in the node, and the right child
   6         has the name which is alphabetically after the name in the node.
   7
   8   Niksa Orlic, 2004-04-25
   9
  10 ********************************************************************/
  11
  12 #include "../util/strings.h"
  13 #include "../util/error.h"
  14 //#include "../util/message.h"
  15 #include "type_list.h"
  16 #include "string_list.h"
  17 #include "type.h"
  18 #include "identifier.h"
  19 #include "name_table.h"
  20 #include "../classgen/bytecode.h"
  21 #include "block.h"
  22 #include "unit.h"
  23 #include "../util/memory.h"
  24
  25 #include <string.h>
  26 #include <stdlib.h>
  27
  28
  29 /*
  30         Create an empty name table.
  31 */
  32 name_table *name_table_create()
  33 {
  34         name_table *new_item;
  35         new_item = (name_table*) mem_alloc(sizeof(name_table));
  36
  37         if (new_item == NULL)
  38                 die(1);
  39
  40         new_item->left_child = NULL;
  41         new_item->right_child = NULL;
  42         new_item->name = NULL;
  43         new_item->descriptor = NULL;
  44
  45         new_item->last = new_item;
  46         new_item->next = NULL;
  47
  48         return new_item;
  49 }
  50
  51
  52 /*
  53         Destroy an allocated name table and free all memory.
  54 */
  55 void name_table_destroy(name_table *item)
  56 {
  57         if (item == NULL)
  58                 return;
  59
  60         if (item->name != NULL)
  61                 string_destroy(item->name);
  62
  63         if (item->descriptor != NULL)
  64                 identifier_destroy(item->descriptor);
  65
  66         if (item->left_child != NULL)
  67                 name_table_destroy(item->left_child);
  68
  69         if (item->right_child != NULL)
  70                 name_table_destroy(item->right_child);
  71 }
  72
  73 /*
  74 name_table *name_table_duplicate(name_table *item)
  75 {
  76         name_table *new_item = mem_alloc(sizeof(name_table));
  77
  78         new_item->descriptor = identifier_duplicate(item->descriptor);
  79         new_item->name = string_duplicate(item->name);
  80
  81         if (item->left_child != NULL)
  82                 new_item->left_child = name_table_duplicate(item->left_child);
  83         else
  84                 new_item->left_child = NULL;
  85
  86         if (item->right_child != NULL)
  87                 new_item->right_child = name_table_duplicate(item->right_child);
  88         else
  89                 new_item->right_child = NULL;
  90
  91         return new_item;
  92 }*/
  93
  94
  95 /*
  96         Inserts an entry into the name table. The string and the descriptor are
  97         not copied, only pointers to the string and descriptor are copied.
  98 */
  99 void name_table_insert(name_table *root, string *name,
 100                                            identifier *descriptor)
 101 {
 102         int string_compare;
 103         name_table *item, *new_item;
 104
 105         if (root == NULL)
 106                 return;
 107
 108         if (root->name == NULL)
 109         {
 110                 /* the root item is empty, insert the value
 111                    into the root item */
 112
 113                 root->name = name;
 114                 root->descriptor = descriptor;
 115                 return;
 116         }
 117
 118
 119         /* go through the tree to the first free element */
 120         item = root;
 121
 122         do
 123         {
 124                 string_compare = STRING_COMPARE(string_get_cstr(name), string_get_cstr(item->name));
 125
 126                 if (string_compare == 0)
 127                 {
 128                         /* an error occured, just return */
 129                         return;
 130                 }
 131
 132                 if (string_compare < 0)
 133                 {
 134                         if (item->left_child == NULL)
 135                                 break;
 136
 137                         item = item->left_child;
 138                 }
 139
 140                 if (string_compare > 0)
 141                 {
 142                         if (item->right_child == NULL)
 143                                 break;
 144
 145                         item = item->right_child;
 146                 }
 147         } while (1); /* until the break is called */
 148
 149         new_item = name_table_create();
 150         new_item->name = name;
 151         new_item->descriptor = descriptor;
 152         new_item->next = NULL;
 153
 154         root->last->next = new_item;
 155         root->last = new_item;
 156
 157         if (string_compare < 0)
 158                 item->left_child = new_item;
 159
 160         if (string_compare > 0)
 161                 item->right_child = new_item;
 162
 163 }
 164
 165
 166 /*
 167         Searches name table for an element with a given name.
 168         Return the identifier descriptor if found or NULL if
 169         not found.
 170 */
 171 identifier* name_table_find(name_table *item, string *name)
 172 {
 173         int string_compare;
 174
 175         while ((item != NULL) && (item->name != NULL))
 176         {
 177                 string_compare = STRING_COMPARE(string_get_cstr(name), string_get_cstr(item->name));
 178
 179                 if (string_compare == 0)
 180                         return item->descriptor;
 181
 182                 if (string_compare < 0)
 183                         item = item->left_child;
 184
 185                 if (string_compare > 0)
 186                         item = item->right_child;
 187
 188         }
 189
 190         return NULL;
 191 }
 192
 193 identifier *name_table_find_cstr(name_table *item, char *name)
 194 {
 195         int string_compare;
 196
 197         while ((item != NULL) && (item->name != NULL))
 198         {
 199                 string_compare = STRING_COMPARE(name, string_get_cstr(item->name));
 200
 201                 if (string_compare == 0)
 202                         return item->descriptor;
 203
 204                 if (string_compare < 0)
 205                         item = item->left_child;
 206
 207                 if (string_compare > 0)
 208                         item = item->right_child;
 209
 210         }
 211
 212         return NULL;
 213 }