Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. #include "jsi.h"
  2.  
  3. /* Dynamically grown string buffer */
  4.  
  5. void js_putc(js_State *J, js_Buffer **sbp, int c)
  6. {
  7.         js_Buffer *sb = *sbp;
  8.         if (!sb) {
  9.                 sb = js_malloc(J, sizeof *sb);
  10.                 sb->n = 0;
  11.                 sb->m = sizeof sb->s;
  12.                 *sbp = sb;
  13.         } else if (sb->n == sb->m) {
  14.                 sb = js_realloc(J, sb, (sb->m *= 2) + soffsetof(js_Buffer, s));
  15.                 *sbp = sb;
  16.         }
  17.         sb->s[sb->n++] = c;
  18. }
  19.  
  20. void js_puts(js_State *J, js_Buffer **sb, const char *s)
  21. {
  22.         while (*s)
  23.                 js_putc(J, sb, *s++);
  24. }
  25.  
  26. void js_putm(js_State *J, js_Buffer **sb, const char *s, const char *e)
  27. {
  28.         while (s < e)
  29.                 js_putc(J, sb, *s++);
  30. }
  31.  
  32. /* Use an AA-tree to quickly look up interned strings. */
  33.  
  34. struct js_StringNode
  35. {
  36.         js_StringNode *left, *right;
  37.         int level;
  38.         char string[1];
  39. };
  40.  
  41. static js_StringNode jsS_sentinel = { &jsS_sentinel, &jsS_sentinel, 0, ""};
  42.  
  43. static js_StringNode *jsS_newstringnode(js_State *J, const char *string, const char **result)
  44. {
  45.         int n = strlen(string);
  46.         js_StringNode *node = js_malloc(J, soffsetof(js_StringNode, string) + n + 1);
  47.         node->left = node->right = &jsS_sentinel;
  48.         node->level = 1;
  49.         memcpy(node->string, string, n + 1);
  50.         return *result = node->string, node;
  51. }
  52.  
  53. static js_StringNode *jsS_skew(js_StringNode *node)
  54. {
  55.         if (node->left->level == node->level) {
  56.                 js_StringNode *temp = node;
  57.                 node = node->left;
  58.                 temp->left = node->right;
  59.                 node->right = temp;
  60.         }
  61.         return node;
  62. }
  63.  
  64. static js_StringNode *jsS_split(js_StringNode *node)
  65. {
  66.         if (node->right->right->level == node->level) {
  67.                 js_StringNode *temp = node;
  68.                 node = node->right;
  69.                 temp->right = node->left;
  70.                 node->left = temp;
  71.                 ++node->level;
  72.         }
  73.         return node;
  74. }
  75.  
  76. static js_StringNode *jsS_insert(js_State *J, js_StringNode *node, const char *string, const char **result)
  77. {
  78.         if (node != &jsS_sentinel) {
  79.                 int c = strcmp(string, node->string);
  80.                 if (c < 0)
  81.                         node->left = jsS_insert(J, node->left, string, result);
  82.                 else if (c > 0)
  83.                         node->right = jsS_insert(J, node->right, string, result);
  84.                 else
  85.                         return *result = node->string, node;
  86.                 node = jsS_skew(node);
  87.                 node = jsS_split(node);
  88.                 return node;
  89.         }
  90.         return jsS_newstringnode(J, string, result);
  91. }
  92.  
  93. static void dumpstringnode(js_StringNode *node, int level)
  94. {
  95.         int i;
  96.         if (node->left != &jsS_sentinel)
  97.                 dumpstringnode(node->left, level + 1);
  98.         printf("%d: ", node->level);
  99.         for (i = 0; i < level; ++i)
  100.                 putchar('\t');
  101.         printf("'%s'\n", node->string);
  102.         if (node->right != &jsS_sentinel)
  103.                 dumpstringnode(node->right, level + 1);
  104. }
  105.  
  106. void jsS_dumpstrings(js_State *J)
  107. {
  108.         js_StringNode *root = J->strings;
  109.         printf("interned strings {\n");
  110.         if (root && root != &jsS_sentinel)
  111.                 dumpstringnode(root, 1);
  112.         printf("}\n");
  113. }
  114.  
  115. static void jsS_freestringnode(js_State *J, js_StringNode *node)
  116. {
  117.         if (node->left != &jsS_sentinel) jsS_freestringnode(J, node->left);
  118.         if (node->right != &jsS_sentinel) jsS_freestringnode(J, node->right);
  119.         js_free(J, node);
  120. }
  121.  
  122. void jsS_freestrings(js_State *J)
  123. {
  124.         if (J->strings && J->strings != &jsS_sentinel)
  125.                 jsS_freestringnode(J, J->strings);
  126. }
  127.  
  128. const char *js_intern(js_State *J, const char *s)
  129. {
  130.         const char *result;
  131.         if (!J->strings)
  132.                 J->strings = &jsS_sentinel;
  133.         J->strings = jsS_insert(J, J->strings, s, &result);
  134.         return result;
  135. }
  136.