src/tree.c

   1 /*
   2 ** tree.c
   3 ** TecCGraf - PUC-Rio
   4 */
   5
   6 char *rcs_tree="$Id: tree.c,v 1.13 1995/01/12 14:19:04 roberto Exp $";
   7
   8
   9 #include <string.h>
  10
  11 #include "mem.h"
  12 #include "lua.h"
  13 #include "tree.h"
  14 #include "table.h"
  15
  16
  17 #define lua_strcmp(a,b) (a[0]<b[0]?(-1):(a[0]>b[0]?(1):strcmp(a,b)))
  18
  19
  20 typedef struct StringNode {
  21   struct StringNode *next;
  22   TaggedString ts;
  23 } StringNode;
  24
  25 static StringNode *string_root = NULL;
  26
  27 static TreeNode *constant_root = NULL;
  28
  29 /*
  30 ** Insert a new constant/variable at the tree.
  31 */
  32 static TreeNode *tree_create (TreeNode **node, char *str)
  33 {
  34  if (*node == NULL)
  35  {
  36   *node = (TreeNode *) luaI_malloc(sizeof(TreeNode)+strlen(str));
  37   (*node)->left = (*node)->right = NULL;
  38   strcpy((*node)->ts.str, str);
  39   (*node)->ts.marked = 0;
  40   (*node)->ts.hash = 0;
  41   (*node)->varindex = (*node)->constindex = NOT_USED;
  42   return *node;
  43  }
  44  else
  45  {
  46   int c = lua_strcmp(str, (*node)->ts.str);
  47   if (c < 0)
  48    return tree_create(&(*node)->left, str);
  49   else if (c > 0)
  50    return tree_create(&(*node)->right, str);
  51   else
  52    return *node;
  53  }
  54 }
  55
  56 TaggedString *lua_createstring (char *str)
  57 {
  58   StringNode *newString;
  59   if (str == NULL) return NULL;
  60   lua_pack();
  61   newString = (StringNode *)luaI_malloc(sizeof(StringNode)+strlen(str));
  62   newString->ts.marked = 0;
  63   newString->ts.hash = 0;
  64   strcpy(newString->ts.str, str);
  65   newString->next = string_root;
  66   string_root = newString;
  67   return &(newString->ts);
  68 }
  69
  70
  71 TreeNode *lua_constcreate (char *str)
  72 {
  73  return tree_create(&constant_root, str);
  74 }
  75
  76
  77 /*
  78 ** Garbage collection function.
  79 ** This function traverse the string list freeing unindexed strings
  80 */
  81 Long lua_strcollector (void)
  82 {
  83   StringNode *curr = string_root, *prev = NULL;
  84   Long counter = 0;
  85   while (curr)
  86   {
  87     StringNode *next = curr->next;
  88     if (!curr->ts.marked)
  89     {
  90       if (prev == NULL) string_root = next;
  91       else prev->next = next;
  92       luaI_free(curr);
  93       ++counter;
  94     }
  95     else
  96     {
  97       curr->ts.marked = 0;
  98       prev = curr;
  99     }
 100     curr = next;
 101   }
 102   return counter;
 103 }
 104
 105 /*
 106 ** Return next variable.
 107 */
 108 static TreeNode *tree_next (TreeNode *node, char *str)
 109 {
 110  if (node == NULL) return NULL;
 111  else if (str == NULL) return node;
 112  else
 113  {
 114   int c = lua_strcmp(str, node->ts.str);
 115   if (c == 0)
 116    return node->left != NULL ? node->left : node->right;
 117   else if (c < 0)
 118   {
 119    TreeNode *result = tree_next(node->left, str);
 120    return result != NULL ? result : node->right;
 121   }
 122   else
 123    return tree_next(node->right, str);
 124  }
 125 }
 126
 127 TreeNode *lua_varnext (char *n)
 128 {
 129   TreeNode *result;
 130   char *name = n;
 131   while (1)
 132   { /* repeat until a valid (non nil) variable */
 133     result = tree_next(constant_root, name);
 134     if (result == NULL) return NULL;
 135     if (result->varindex != NOT_USED &&
 136         s_tag(result->varindex) != LUA_T_NIL)
 137       return result;
 138     name = result->ts.str;
 139   }
 140 }
 141