1#include "jsi.h"
2
3/* Dynamically grown string buffer */
4
5void 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
20void js_puts(js_State *J, js_Buffer **sb, const char *s)
21{
22 while (*s)
23 js_putc(J, sb, *s++);
24}
25
26void 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
34struct js_StringNode
35{
36 js_StringNode *left, *right;
37 int level;
38 char string[1];
39};
40
41static js_StringNode jsS_sentinel = { &jsS_sentinel, &jsS_sentinel, 0, ""};
42
43static 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
53static 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
64static 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
76static 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
93static 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
106void 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
115static 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
122void jsS_freestrings(js_State *J)
123{
124 if (J->strings && J->strings != &jsS_sentinel)
125 jsS_freestringnode(J, J->strings);
126}
127
128const 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