jsintern.c

#include "jsi.h"

/* Use an AA-tree to quickly look up interned strings. */

struct js_StringNode
{
	js_StringNode *left, *right;
	int level;
	char string[1];
};

static js_StringNode jsS_sentinel = { &jsS_sentinel, &jsS_sentinel, 0, ""};

static js_StringNode *jsS_newstringnode(js_State *J, const char *string, const char **result)
{
	int n = strlen(string);
	js_StringNode *node = js_malloc(J, offsetof(js_StringNode, string) + n + 1);
	node->left = node->right = &jsS_sentinel;
	node->level = 1;
	memcpy(node->string, string, n + 1);
	return *result = node->string, node;
}

static js_StringNode *jsS_skew(js_StringNode *node)
{
	if (node->left->level == node->level) {
		js_StringNode *temp = node;
		node = node->left;
		temp->left = node->right;
		node->right = temp;
	}
	return node;
}

static js_StringNode *jsS_split(js_StringNode *node)
{
	if (node->right->right->level == node->level) {
		js_StringNode *temp = node;
		node = node->right;
		temp->right = node->left;
		node->left = temp;
		++node->level;
	}
	return node;
}

static js_StringNode *jsS_insert(js_State *J, js_StringNode *node, const char *string, const char **result)
{
	if (node != &jsS_sentinel) {
		int c = strcmp(string, node->string);
		if (c < 0)
			node->left = jsS_insert(J, node->left, string, result);
		else if (c > 0)
			node->right = jsS_insert(J, node->right, string, result);
		else
			return *result = node->string, node;
		node = jsS_skew(node);
		node = jsS_split(node);
		return node;
	}
	return jsS_newstringnode(J, string, result);
}

static void dumpstringnode(js_StringNode *node, int level)
{
	int i;
	if (node->left != &jsS_sentinel)
		dumpstringnode(node->left, level + 1);
	printf("%d: ", node->level);
	for (i = 0; i < level; ++i)
		putchar('\t');
	printf("'%s'\n", node->string);
	if (node->right != &jsS_sentinel)
		dumpstringnode(node->right, level + 1);
}

void jsS_dumpstrings(js_State *J)
{
	js_StringNode *root = J->strings;
	printf("interned strings {\n");
	if (root && root != &jsS_sentinel)
		dumpstringnode(root, 1);
	printf("}\n");
}

static void jsS_freestringnode(js_State *J, js_StringNode *node)
{
	if (node->left != &jsS_sentinel) jsS_freestringnode(J, node->left);
	if (node->right != &jsS_sentinel) jsS_freestringnode(J, node->right);
	js_free(J, node);
}

void jsS_freestrings(js_State *J)
{
	if (J->strings && J->strings != &jsS_sentinel)
		jsS_freestringnode(J, J->strings);
}

const char *js_intern(js_State *J, const char *s)
{
	const char *result;
	if (!J->strings)
		J->strings = &jsS_sentinel;
	J->strings = jsS_insert(J, J->strings, s, &result);
	return result;
}