script: hashed label lookup, 64 deep calls, optional yield at the step limit

2 files changed, 46 insertions, 4 deletions

diff --git a/kon/konscript.c b/kon/konscript.c
index 537080a..093e024 100644
--- a/kon/konscript.c
+++ b/kon/konscript.c
@@ -135,10 +135,14 @@ kon_scriptStatus_t kon_scriptRun(kon_script_t *vm)
 		const kon_cmd_t *c;
 		int next;
 
-		if (vm->pc < 0 || vm->pc >= vm->count || ++steps > 100000) {
+		if (vm->pc < 0 || vm->pc >= vm->count) {
 			vm->status = KON_SCRIPT_ERROR;
 			break;
 		}
+		if (++steps > 100000) {
+			if (!vm->yieldAtLimit) vm->status = KON_SCRIPT_ERROR;
+			break;
+		}
 		c = &vm->cmds[vm->pc];
 		next = vm->pc + 1;
 		vm->cmd = vm->pc;
@@ -394,12 +398,40 @@ static const char *keep(parse_t *p, const lexer_t *l)
 	return out;
 }
 
+static unsigned labelHash(const char *name, int len)
+{
+	unsigned h = 2166136261u;
+	int i;
+
+	for (i = 0; i < len; i++) h = (h ^ (unsigned char)name[i]) * 16777619u;
+	return h;
+}
+
+static int sameLabel(const kon_scriptLabel_t *label, const char *name, int len)
+{
+	return (int)strlen(label->name) == len && strncmp(label->name, name, (size_t)len) == 0;
+}
+
+static int hashed(const kon_scriptBuild_t *b)
+{
+	return b->hash && b->hashSize > 0 && (b->hashSize & (b->hashSize - 1)) == 0 && b->hashSize >= 2 * b->maxLabels;
+}
+
 static int labelAt(const kon_scriptBuild_t *b, const char *name, int len)
 {
 	int i;
 
+	if (hashed(b)) {
+		unsigned mask = (unsigned)b->hashSize - 1, slot = labelHash(name, len) & mask;
+
+		while (b->hash[slot]) {
+			if (sameLabel(&b->labels[b->hash[slot] - 1], name, len)) return b->labels[b->hash[slot] - 1].at;
+			slot = (slot + 1) & mask;
+		}
+		return -1;
+	}
 	for (i = 0; i < b->labelCount; i++) {
-		if ((int)strlen(b->labels[i].name) == len && strncmp(b->labels[i].name, name, (size_t)len) == 0) return b->labels[i].at;
+		if (sameLabel(&b->labels[i], name, len)) return b->labels[i].at;
 	}
 	return -1;
 }
@@ -459,6 +491,12 @@ static void defineLabel(parse_t *p, const lexer_t *l, int len)
 	memcpy(b->labels[b->labelCount].name, l->s + l->start, (size_t)len);
 	b->labels[b->labelCount].name[len] = '\0';
 	b->labels[b->labelCount].at = b->count;
+	if (hashed(b)) {
+		unsigned mask = (unsigned)b->hashSize - 1, slot = labelHash(l->s + l->start, len) & mask;
+
+		while (b->hash[slot]) slot = (slot + 1) & mask;
+		b->hash[slot] = b->labelCount + 1;
+	}
 	b->labelCount++;
 }
 
@@ -712,7 +750,7 @@ static void statement(parse_t *p, const char *line)
 static void run(parse_t *p, const char *source)
 {
 	const char *s = source;
-	char line[1200];
+	char line[4096];
 
 	p->line = 0;
 	p->menu = -1;
@@ -739,6 +777,7 @@ int kon_scriptParse(kon_scriptBuild_t *b, const char *source)
 	parse_t p;
 
 	b->count = b->labelCount = b->poolUsed = 0;
+	if (hashed(b)) memset(b->hash, 0, (size_t)b->hashSize * sizeof *b->hash);
 	b->errorLine = 0;
 	b->error[0] = '\0';
 	if (!source || !b->cmds || b->maxCmds < 0) {
diff --git a/kon/konscript.h b/kon/konscript.h
index f9cfba2..e261c4a 100644
--- a/kon/konscript.h
+++ b/kon/konscript.h
@@ -92,7 +92,7 @@ typedef enum {
 } kon_scriptStatus_t;
 
 #define KON_SCRIPT_MAX_OPTIONS 16
-#define KON_SCRIPT_MAX_CALLS 8
+#define KON_SCRIPT_MAX_CALLS 64
 
 struct kon_script;
 typedef int (*kon_hostFn)(struct kon_script *vm, const kon_cmd_t *cmd, void *user);
@@ -104,6 +104,7 @@ typedef struct kon_script {
 	int switchCount;
 	int32_t *vars;
 	int varCount;
+	int yieldAtLimit; /* 0 makes a script that runs 100000 commands without waiting an ERROR, 1 makes kon_scriptRun give back RUNNING and carry on next call, like RPG Maker does */
 	kon_hostFn host; /* returns nonzero to make the script wait for kon_scriptResume */
 	void *user;
 	kon_scriptStatus_t status;
@@ -182,6 +183,8 @@ typedef struct kon_scriptBuild {
 	int poolSize;
 	kon_scriptLabel_t *labels;
 	int maxLabels;
+	int *hash; /* optional, makes looking up labels fast for big scripts. hashSize is a power of two, at least twice maxLabels */
+	int hashSize;
 
 	int count, labelCount, poolUsed; /* what it made */
 	int errorLine; /* 0 if no error */