1 files changed, 131 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c b/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c
new file mode 100644
index 00000000..b7707a8e
--- /dev/null
+++ b/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c
@@ -0,0 +1,131 @@
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "kstring.h"
+
+#ifdef __APPLE__
+#define HAVE_STRNSTR
+#endif
+
+#ifdef __linux__
+#define HAVE_MEMMEM
+#endif
+
+static int str_len = 1024*1024*128;
+static int pat_len = 30;
+static int alphabet = 2;
+static int repeat = 50;
+
+char *gen_data(int len, int a)
+{
+	char *data;
+	int i;
+	long x;
+	srand48(11);
+	data = malloc(len);
+	for (i = 0; i < len; ++i)
+		data[i] = (int)(a * drand48()) + '!';
+	data[str_len - 1] = 0;
+	return data;
+}
+// http://srcvault.scali.eu.org/cgi-bin/Syntax/c/BoyerMoore.c
+char *BoyerMoore( unsigned char *data, unsigned int dataLength, unsigned char *string, unsigned int strLength )
+{
+	unsigned int skipTable[256], i;
+	unsigned char *search;
+	register unsigned char lastChar;
+
+	if (strLength == 0)
+		return NULL;
+
+	for (i = 0; i < 256; i++)
+		skipTable[i] = strLength;
+	search = string;
+	i = --strLength;
+	do {
+		skipTable[*search++] = i;
+	} while (i--);
+	lastChar = *--search;
+	search = data + strLength;
+	dataLength -= strLength+(strLength-1);
+	while ((int)dataLength > 0 ) {
+		unsigned int skip;
+		skip = skipTable[*search];
+		search += skip;
+		dataLength -= skip;
+		skip = skipTable[*search];
+		search += skip;
+		dataLength -= skip;
+		skip = skipTable[*search];
+		if (*search != lastChar) {
+			search += skip;
+			dataLength -= skip;
+			continue;
+		}
+		i = strLength;
+		do {
+			if (i-- == 0) return search;
+		} while (*--search == string[i]);
+		search += (strLength - i + 1);
+		dataLength--;
+	}
+	return NULL;
+}
+
+int main()
+{
+	char *data;
+	int i;
+	clock_t t;
+	t = clock();
+	data = gen_data(str_len, alphabet);
+	fprintf(stderr, "Generate data in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	{
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = kmemmem(data, str_len, data + y, pat_len, 0);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+	if (1) {
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = BoyerMoore(data, str_len, data + y, pat_len);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+#ifdef HAVE_STRNSTR
+	if (1) {
+		char *tmp;
+		t = clock(); srand48(1331);
+		tmp = calloc(pat_len+1, 1);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			memcpy(tmp, data + y, pat_len);
+			ret = strnstr(data, tmp, str_len);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);		
+	}
+#endif
+#ifdef HAVE_MEMMEM
+	if (1) {
+		t = clock(); srand48(1331);
+		for (i = 0; i < repeat; ++i) {
+			int y = lrand48() % (str_len - pat_len);
+			char *ret;
+			ret = memmem(data, str_len, data + y, pat_len);
+//			printf("%d, %d\n", (int)(ret - data), y);
+		}
+		fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC);
+	}
+#endif
+	return 0;
+}