Adding upstream version 0.8.0.upstream/0.8.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

43 files changed, 7804 insertions, 0 deletions

diff --git a/third-party/CMakeLists.txt b/third-party/CMakeLists.txt
new file mode 100644
index 0000000..c61ca38
--- /dev/null
+++ b/third-party/CMakeLists.txt
@@ -0,0 +1,4 @@
+set(tommyds "${CMAKE_CURRENT_SOURCE_DIR}/tommyds/tommy.c" PARENT_SCOPE)
+
+set(mustach "${CMAKE_CURRENT_SOURCE_DIR}/mustach/mustach.c" PARENT_SCOPE)
+set_source_files_properties("${CMAKE_CURRENT_SOURCE_DIR}/mustach/mustach.c" PROPERTIES COMPILE_FLAGS "-DNO_EXTENSION_FOR_MUSTACH")
diff --git a/third-party/mustach.h b/third-party/mustach.h
new file mode 100644
index 0000000..b20a61a
--- /dev/null
+++ b/third-party/mustach.h
@@ -0,0 +1,15 @@
+/*
+ * This file is part of RTRlib.
+ *
+ * This file is subject to the terms and conditions of the MIT license.
+ * See the file LICENSE in the top level directory for more details.
+ *
+ * Website: http://rtrlib.realmv6.org/
+ */
+
+/* fix missing include in the mustach header by including it first */
+
+// clang-format off
+#include <stdio.h>
+#include "third-party/mustach/mustach.h"
+// clang-format on
diff --git a/third-party/mustach/AUTHORS b/third-party/mustach/AUTHORS
new file mode 100644
index 0000000..82d2fee
--- /dev/null
+++ b/third-party/mustach/AUTHORS
@@ -0,0 +1,15 @@
+Main author:
+ José Bollo <jobol@nonadev.net>
+
+Contributors:
+ Harold L Marzan
+ Atlas
+ Sami Kerola
+ Tomasz Sieprawski
+ Lailton Fernando Mariano
+
+Thanks to issue submitters:
+ Thierry Fournier
+ Dante Torres
+ Mark Bucciarelli
+ Paul Wisehart
diff --git a/third-party/mustach/LICENSE-2.0.txt b/third-party/mustach/LICENSE-2.0.txt
new file mode 100644
index 0000000..d645695
--- /dev/null
+++ b/third-party/mustach/LICENSE-2.0.txt
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
diff --git a/third-party/mustach/README.md b/third-party/mustach/README.md
new file mode 100644
index 0000000..026fc87
--- /dev/null
+++ b/third-party/mustach/README.md
@@ -0,0 +1,117 @@
+Introduction to Mustach
+=======================
+
+`mustach` is a C implementation of the [mustache](http://mustache.github.io "main site for mustache") template library.
+
+The main site for `mustach` is on [gitlab](https://gitlab.com/jobol/mustach).
+
+The best way to use mustach is to copy the files **mustach.h** and **mustach.c**
+directly into your project and use it.
+
+The current source files are:
+
+- **mustach.c** core implementation of mustache in C
+- **mustach.h** header file for core definitions
+- **mustach-json-c.c** tiny json wrapper of mustach using [json-c](https://github.com/json-c/json-c)
+- **mustach-json-c.h** header file for using the tiny JSON wrapper
+- **mustach-tool.c** simple tool for applying template files to a JSON file
+
+The file **mustach-json-c.c** is the main example of use of **mustach** core
+and it is also a practical implementation that can be used. It uses the library
+json-c. (NOTE for Mac OS: available through homebrew).
+
+HELP REQUESTED TO GIVE EXAMPLE BASED ON OTHER LIBRARIES (ex: janson, ...).
+
+The tool **mustach** is build using `make`,  its usage is:
+
+    mustach json template [template]...
+
+It then outputs the result of applying the templates files to the JSON file.
+
+Portability
+===========
+
+Some system does not provide *open_memstream*. In that case, tell your
+prefered compiler to declare the preprocessor symbol **NO_OPEN_MEMSTREAM**.
+Example:
+
+	gcc -DNO_OPEN_MEMSTREAM
+
+Extensions
+==========
+
+By default, the current implementation provides the following extensions:
+
+Explicit Substitution
+---------------------
+
+This is a core extension implemented in file **mustach.c**.
+
+In somecases the name of the key used for substition begins with a
+character reserved for mustach: one of '#', '^', '/', '&', '{', '>' and '='.
+This extension introduces the special character ':' to explicitly
+tell mustach to just substitute the value. So ':' becomes a new special
+character.
+
+Value Testing
+-------------
+
+This is a tool extension implmented in file **mustach-json-c.c**.
+
+This extension allows you to test the value of the selected key.
+It is allowed to write key=value (matching test) or key=!value
+(not matching test) in any query.
+
+Removing Extensions
+-------------------
+
+When compiling mustach.c or mustach-json-c.c,
+extensions can be removed by defining macros
+using option -D.
+
+The possible macros are:
+
+- `NO_COLON_EXTENSION_FOR_MUSTACH`
+
+  This macro remove the ability to use colon (:)
+  as explicit command for variable substituion.
+  This extension allows to have name starting
+  with one of the mustach character :#^/&{=<
+
+- `NO_EQUAL_VALUE_EXTENSION_FOR_MUSTACH`
+
+  This macro allows the program to check the whether
+  the actual value is equal to an expected value.
+  This is useful in `{{#key=val}}` or `{{^key=val}}`
+  with the corresponding `{{/key=val}}`.
+  It can also be used in `{{key=val}}` but this
+  doesn't seem to be useful.
+
+- `NO_JSON_POINTER_EXTENSION_FOR_MUSTACH`
+
+  This macro removes the possible use of JSON pointers.
+  JSON pointers are defined in IETF RFC 6901.
+  If not set, any key starting with "/" is a JSON pointer.
+  This implies to use the colon to introduce keys.
+  So `NO_COLON_EXTENSION_FOR_MUSTACH` implies
+  `NO_JSON_POINTER_EXTENSION_FOR_MUSTACH`.
+  A special escaping is used for "=" signs when
+  values comparison is enabled: "~=" leaves "=" in the key.
+
+- `NO_ALLOW_EMPTY_TAG`
+
+  Generate the error MUSTACH_ERROR_EMPTY_TAG automatically.
+
+- NO_OBJECT_ITERATION_FOR_MUSTACH
+
+  Disable the object iteration extension. That extension allows
+  to iterate over the keys of an object. The iteration on object
+  is selected by using the selector `{{#key.*}}`. In the context
+  of iterating over object keys, the single key `{{*}}` returns the
+  key and `{{.}}` returns the value.
+
+- `NO_EXTENSION_FOR_MUSTACH`
+
+  This macro disables any current or future
+  extensions.
+
diff --git a/third-party/mustach/mustach.c b/third-party/mustach/mustach.c
new file mode 100644
index 0000000..830e72c
--- /dev/null
+++ b/third-party/mustach/mustach.c
@@ -0,0 +1,327 @@
+/*
+ Author: José Bollo <jobol@nonadev.net>
+ Author: José Bollo <jose.bollo@iot.bzh>
+
+ https://gitlab.com/jobol/mustach
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+     http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#define _GNU_SOURCE
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include <ctype.h>
+
+#include "mustach.h"
+
+#define NAME_LENGTH_MAX   1024
+#define DEPTH_MAX         256
+
+#if !defined(NO_OPEN_MEMSTREAM)
+static FILE *memfile_open(char **buffer, size_t *size)
+{
+	return open_memstream(buffer, size);
+}
+static void memfile_abort(FILE *file, char **buffer, size_t *size)
+{
+	fclose(file);
+	free(*buffer);
+	*buffer = NULL;
+	*size = 0;
+}
+static int memfile_close(FILE *file, char **buffer, size_t *size)
+{
+	int rc;
+
+	/* adds terminating null */
+	rc = fputc(0, file) ? MUSTACH_ERROR_SYSTEM : 0;
+	fclose(file);
+	if (rc == 0)
+		/* removes terminating null of the length */
+		(*size)--;
+	else {
+		free(*buffer);
+		*buffer = NULL;
+		*size = 0;
+	}
+	return rc;
+}
+#else
+static FILE *memfile_open(char **buffer, size_t *size)
+{
+	return tmpfile();
+}
+static void memfile_abort(FILE *file, char **buffer, size_t *size)
+{
+	fclose(file);
+	*buffer = NULL;
+	*size = 0;
+}
+static int memfile_close(FILE *file, char **buffer, size_t *size)
+{
+	int rc;
+	size_t s;
+	char *b;
+
+	s = (size_t)ftell(file);
+	b = malloc(s + 1);
+	if (b == NULL) {
+		rc = MUSTACH_ERROR_SYSTEM;
+		errno = ENOMEM;
+		s = 0;
+	} else {
+		rewind(file);
+		if (1 == fread(b, s, 1, file)) {
+			rc = 0;
+			b[s] = 0;
+		} else {
+			rc = MUSTACH_ERROR_SYSTEM;
+			free(b);
+			b = NULL;
+			s = 0;
+		}
+	}
+	*buffer = b;
+	*size = s;
+	return rc;
+}
+#endif
+
+static int getpartial(struct mustach_itf *itf, void *closure, const char *name, char **result)
+{
+	int rc;
+	FILE *file;
+	size_t size;
+
+	*result = NULL;
+	file = memfile_open(result, &size);
+	if (file == NULL)
+		rc = MUSTACH_ERROR_SYSTEM;
+	else {
+		rc = itf->put(closure, name, 0, file);
+		if (rc < 0)
+			memfile_abort(file, result, &size);
+		else
+			rc = memfile_close(file, result, &size);
+	}
+	return rc;
+}
+
+static int process(const char *template, struct mustach_itf *itf, void *closure, FILE *file, const char *opstr, const char *clstr)
+{
+	char name[NAME_LENGTH_MAX + 1], *partial, c, *tmp;
+	const char *beg, *term;
+	struct { const char *name, *again; size_t length; int emit, entered; } stack[DEPTH_MAX];
+	size_t oplen, cllen, len, l;
+	int depth, rc, emit;
+
+	emit = 1;
+	oplen = strlen(opstr);
+	cllen = strlen(clstr);
+	depth = 0;
+	for(;;) {
+		beg = strstr(template, opstr);
+		if (beg == NULL) {
+			/* no more mustach */
+			if (emit)
+				fwrite(template, strlen(template), 1, file);
+			return depth ? MUSTACH_ERROR_UNEXPECTED_END : 0;
+		}
+		if (emit)
+			fwrite(template, (size_t)(beg - template), 1, file);
+		beg += oplen;
+		term = strstr(beg, clstr);
+		if (term == NULL)
+			return MUSTACH_ERROR_UNEXPECTED_END;
+		template = term + cllen;
+		len = (size_t)(term - beg);
+		c = *beg;
+		switch(c) {
+		case '!':
+		case '=':
+			break;
+		case '{':
+			for (l = 0 ; clstr[l] == '}' ; l++);
+			if (clstr[l]) {
+				if (!len || beg[len-1] != '}')
+					return MUSTACH_ERROR_BAD_UNESCAPE_TAG;
+				len--;
+			} else {
+				if (term[l] != '}')
+					return MUSTACH_ERROR_BAD_UNESCAPE_TAG;
+				template++;
+			}
+			c = '&';
+			/*@fallthrough@*/
+		case '^':
+		case '#':
+		case '/':
+		case '&':
+		case '>':
+#if !defined(NO_EXTENSION_FOR_MUSTACH) && !defined(NO_COLON_EXTENSION_FOR_MUSTACH)
+		case ':':
+#endif
+			beg++; len--;
+		default:
+			while (len && isspace(beg[0])) { beg++; len--; }
+			while (len && isspace(beg[len-1])) len--;
+#if defined(NO_EXTENSION_FOR_MUSTACH) || defined(NO_ALLOW_EMPTY_TAG)
+			if (len == 0)
+				return MUSTACH_ERROR_EMPTY_TAG;
+#endif
+			if (len > NAME_LENGTH_MAX)
+				return MUSTACH_ERROR_TAG_TOO_LONG;
+			memcpy(name, beg, len);
+			name[len] = 0;
+			break;
+		}
+		switch(c) {
+		case '!':
+			/* comment */
+			/* nothing to do */
+			break;
+		case '=':
+			/* defines separators */
+			if (len < 5 || beg[len - 1] != '=')
+				return MUSTACH_ERROR_BAD_SEPARATORS;
+			beg++;
+			len -= 2;
+			for (l = 0; l < len && !isspace(beg[l]) ; l++);
+			if (l == len)
+				return MUSTACH_ERROR_BAD_SEPARATORS;
+			oplen = l;
+			tmp = alloca(oplen + 1);
+			memcpy(tmp, beg, oplen);
+			tmp[oplen] = 0;
+			opstr = tmp;
+			while (l < len && isspace(beg[l])) l++;
+			if (l == len)
+				return MUSTACH_ERROR_BAD_SEPARATORS;
+			cllen = len - l;
+			tmp = alloca(cllen + 1);
+			memcpy(tmp, beg + l, cllen);
+			tmp[cllen] = 0;
+			clstr = tmp;
+			break;
+		case '^':
+		case '#':
+			/* begin section */
+			if (depth == DEPTH_MAX)
+				return MUSTACH_ERROR_TOO_DEEP;
+			rc = emit;
+			if (rc) {
+				rc = itf->enter(closure, name);
+				if (rc < 0)
+					return rc;
+			}
+
+			if (template[0] == '\n')
+				++template;
+
+			stack[depth].name = beg;
+			stack[depth].again = template;
+			stack[depth].length = len;
+			stack[depth].emit = emit;
+			stack[depth].entered = rc;
+			if ((c == '#') == (rc == 0))
+				emit = 0;
+			depth++;
+			break;
+		case '/':
+			/* end section */
+			if (depth-- == 0 || len != stack[depth].length || memcmp(stack[depth].name, name, len))
+				return MUSTACH_ERROR_CLOSING;
+			rc = emit && stack[depth].entered ? itf->next(closure) : 0;
+			if (rc < 0)
+				return rc;
+			if (rc) {
+				template = stack[depth++].again;
+			} else {
+				emit = stack[depth].emit;
+				if (emit && stack[depth].entered)
+					itf->leave(closure);
+			}
+			break;
+		case '>':
+			/* partials */
+			if (emit) {
+				rc = getpartial(itf, closure, name, &partial);
+				if (rc == 0) {
+					rc = process(partial, itf, closure, file, opstr, clstr);
+					free(partial);
+				}
+				if (rc < 0)
+					return rc;
+			}
+			break;
+		default:
+			/* replacement */
+			if (emit) {
+				rc = itf->put(closure, name, c != '&', file);
+				if (rc < 0)
+					return rc;
+			}
+			break;
+		}
+	}
+}
+
+int fmustach(const char *template, struct mustach_itf *itf, void *closure, FILE *file)
+{
+	int rc = itf->start ? itf->start(closure) : 0;
+	if (rc == 0)
+		rc = process(template, itf, closure, file, "{{", "}}");
+	return rc;
+}
+
+int fdmustach(const char *template, struct mustach_itf *itf, void *closure, int fd)
+{
+	int rc;
+	FILE *file;
+
+	file = fdopen(fd, "w");
+	if (file == NULL) {
+		rc = MUSTACH_ERROR_SYSTEM;
+		errno = ENOMEM;
+	} else {
+		rc = fmustach(template, itf, closure, file);
+		fclose(file);
+	}
+	return rc;
+}
+
+int mustach(const char *template, struct mustach_itf *itf, void *closure, char **result, size_t *size)
+{
+	int rc;
+	FILE *file;
+	size_t s;
+
+	*result = NULL;
+	if (size == NULL)
+		size = &s;
+	file = memfile_open(result, size);
+	if (file == NULL)
+		rc = MUSTACH_ERROR_SYSTEM;
+	else {
+		rc = fmustach(template, itf, closure, file);
+		if (rc < 0)
+			memfile_abort(file, result, size);
+		else
+			rc = memfile_close(file, result, size);
+	}
+	return rc;
+}
+
diff --git a/third-party/mustach/mustach.h b/third-party/mustach/mustach.h
new file mode 100644
index 0000000..32288a1
--- /dev/null
+++ b/third-party/mustach/mustach.h
@@ -0,0 +1,120 @@
+/*
+ Author: José Bollo <jobol@nonadev.net>
+ Author: José Bollo <jose.bollo@iot.bzh>
+
+ https://gitlab.com/jobol/mustach
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+     http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#ifndef _mustach_h_included_
+#define _mustach_h_included_
+
+/**
+ * mustach_itf - interface for callbacks
+ *
+ * All of this function should return a negative value to stop
+ * the mustache processing. The returned negative value will be
+ * then returned to the caller of mustach as is.
+ *
+ * The functions enter and next should return 0 or 1.
+ *
+ * All other functions should normally return 0. If it returns
+ * a negative value, it means an error that stop the process
+ * and that is reported to the caller.
+ *
+ * @start: Starts the mustach processing of the closure
+ *         'start' is optional (can be NULL)
+ *
+ * @put: Writes the value of 'name' to 'file' with 'escape' or not
+ *       As an extension (see NO_ALLOW_EMPTY_TAG), the 'name' can be
+ *       the empty string. In that later case an implemntation can
+ *       return MUSTACH_ERROR_EMPTY_TAG to refuse empty names.
+ *
+ * @enter: Enters the section of 'name' if possible.
+ *         Musts return 1 if entered or 0 if not entered.
+ *         When 1 is returned, the function 'leave' will always be called.
+ *         Conversely 'leave' is never called when enter returns 0 or
+ *         a negative value.
+ *         When 1 is returned, the function must activate the first
+ *         item of the section.
+ *
+ * @next: Activates the next item of the section if it exists.
+ *        Musts return 1 when the next item is activated.
+ *        Musts return 0 when there is no item to activate.
+ *
+ * @leave: Leaves the last entered section
+ */
+struct mustach_itf {
+	int (*start)(void *closure);
+	int (*put)(void *closure, const char *name, int escape, FILE *file);
+	int (*enter)(void *closure, const char *name);
+	int (*next)(void *closure);
+	int (*leave)(void *closure);
+};
+
+#define MUSTACH_OK                       0
+#define MUSTACH_ERROR_SYSTEM            -1
+#define MUSTACH_ERROR_UNEXPECTED_END    -2
+#define MUSTACH_ERROR_EMPTY_TAG         -3
+#define MUSTACH_ERROR_TAG_TOO_LONG      -4
+#define MUSTACH_ERROR_BAD_SEPARATORS    -5
+#define MUSTACH_ERROR_TOO_DEEP          -6
+#define MUSTACH_ERROR_CLOSING           -7
+#define MUSTACH_ERROR_BAD_UNESCAPE_TAG  -8
+
+/* compatibility with older bad name */
+#define MUSTACH_ERROR_TOO_DEPTH         MUSTACH_ERROR_TOO_DEEP
+
+/**
+ * fmustach - Renders the mustache 'template' in 'file' for 'itf' and 'closure'.
+ *
+ * @template: the template string to instanciate
+ * @itf:      the interface to the functions that mustach calls
+ * @closure:  the closure to pass to functions called
+ * @file:     the file where to write the result
+ *
+ * Returns 0 in case of success, -1 with errno set in case of system error
+ * a other negative value in case of error.
+ */
+extern int fmustach(const char *template, struct mustach_itf *itf, void *closure, FILE *file);
+
+/**
+ * fmustach - Renders the mustache 'template' in 'fd' for 'itf' and 'closure'.
+ *
+ * @template: the template string to instanciate
+ * @itf:      the interface to the functions that mustach calls
+ * @closure:  the closure to pass to functions called
+ * @fd:       the file descriptor number where to write the result
+ *
+ * Returns 0 in case of success, -1 with errno set in case of system error
+ * a other negative value in case of error.
+ */
+extern int fdmustach(const char *template, struct mustach_itf *itf, void *closure, int fd);
+
+/**
+ * fmustach - Renders the mustache 'template' in 'result' for 'itf' and 'closure'.
+ *
+ * @template: the template string to instanciate
+ * @itf:      the interface to the functions that mustach calls
+ * @closure:  the closure to pass to functions called
+ * @result:   the pointer receiving the result when 0 is returned
+ * @size:     the size of the returned result
+ *
+ * Returns 0 in case of success, -1 with errno set in case of system error
+ * a other negative value in case of error.
+ */
+extern int mustach(const char *template, struct mustach_itf *itf, void *closure, char **result, size_t *size);
+
+#endif
+
diff --git a/third-party/tommyds/AUTHORS b/third-party/tommyds/AUTHORS
new file mode 100644
index 0000000..23071a0
--- /dev/null
+++ b/third-party/tommyds/AUTHORS
@@ -0,0 +1,9 @@
+TommyDS AUTHORS
+===============
+
+The author of TommyDS is Andrea Mazzoleni.
+
+You can contact me sending an email at:
+
+    amadvance@gmail.com
+
diff --git a/third-party/tommyds/HISTORY b/third-party/tommyds/HISTORY
new file mode 100644
index 0000000..ae56bc5
--- /dev/null
+++ b/third-party/tommyds/HISTORY
@@ -0,0 +1,90 @@
+TommyDS HISTORY
+===============
+
+2.2 2018/02
+===========
+ * Removed tommy_list_remove_head_not_empty() as not used and wrongly
+   implemented [Daniel Roethlisberger].
+
+2.1 2016/11
+===========
+ * Added a new hash function for strings: tommy_strhash_u32().
+ * Added a new tree implementation. It's not intended to be fast but useful if
+   you need elements in order.
+ * Fixed some references to TOMMY_ARRAYBLKOF_SIZE, where instead
+   TOMMY_ARRAYBLK_SIZE was incorrectly used [Rocco].
+
+2.0 2014/12
+===========
+ * Fixed a Segmentation Fault bug in the trie_inplace container when inserting
+   duplicate elements.
+ * Faster array and hashlin implementation when accessing elements.
+ * Added new hashtable functions to iterate over all the elements.
+ * Added a new tommy_calloc() function used for allocating initialized memory.
+   If you redefined tommy_malloc(), likely you have to redefine also tommy_calloc().
+ * Reached 100% code coverage in the regression test.      
+ * Different source code organization.
+ * Added benchmark comparison with Binary Search Tesseract by Gregorius van
+   den Hoven.
+
+1.8 2013/12
+===========
+ * Fixed build of tommy_arrayblk in C++.
+ * Changed the default node size of tommy_trie to fit a cache line of 64 bytes.
+ * Added benchmark comparison with STX BTree.
+
+1.7 2013/12
+===========
+ * Extends tommy_hashlin_done() to work also if the hashtable is not empty.
+ * Removes the empty tommy_trie_done() because the real deallocation is done
+   by the allocator.
+
+1.6 2013/11
+===========
+ * Added a new tommy_arrayblk and tommy_arrayblkof types to store elements
+   in an array minimizing memory occupation.
+
+1.5 2013/06
+===========
+ * Fixed inline declaration to allow building with clang.
+ * Added a new tommy_arrayof type to store in an array elements of arbitrary
+   size.
+
+1.4 2013/03
+===========
+ * Added benchmark comparison with Google BTree, and C++ map and unordered_map.
+ * Benchmark for Linux is now compiled with "-O3 -march=pentium4 -mtune=generic",
+   and the Windows one with "/Ox /GL /GS- /arch:SSE2".
+
+1.3 2013/02
+===========
+ * Fixed a Segmentation Fault bug in the hashlin container if exact power
+   of 2 sizes were used.
+ * Removed some warnings with newer gcc.
+ * Minor documentation changes.
+ * Added benchmark comparison with the judy array implementation by Karl Malbrain.
+
+1.2 2012/05
+===========
+ * Minor documentation changes.
+ * In the check application, added a speed comparison with the C qsort()
+   implementation.
+
+1.1 2012/05
+===========
+ * Fixed the tommy_hashdyn_remove() function. Now it shrinks the hashtable if required.
+ * Minor documentation changes.
+
+1.0 2011/03
+===========
+ * First official version of TommyDS.
+ * Added tommy_list_foreach functions.
+
+0.2 2011/03
+===========
+ * Added tommy_array. A dynamic vector.
+
+0.1 2011/01
+===========
+ * First release of Tommy.
+
diff --git a/third-party/tommyds/INSTALL b/third-party/tommyds/INSTALL
new file mode 100644
index 0000000..40e55ff
--- /dev/null
+++ b/third-party/tommyds/INSTALL
@@ -0,0 +1,8 @@
+TommyDS INSTALL
+===============
+
+TommyDS doesn't need any installation.
+
+You have only to import the required .c and .h files into your program
+and use the them.
+
diff --git a/third-party/tommyds/LICENSE b/third-party/tommyds/LICENSE
new file mode 100644
index 0000000..6c86157
--- /dev/null
+++ b/third-party/tommyds/LICENSE
@@ -0,0 +1,24 @@
+Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions
+are met:
+
+1. Redistributions of source code must retain the above copyright
+   notice, this list of conditions and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the above copyright
+   notice, this list of conditions and the following disclaimer in the
+   documentation and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
diff --git a/third-party/tommyds/Makefile b/third-party/tommyds/Makefile
new file mode 100644
index 0000000..a2a3d36
--- /dev/null
+++ b/third-party/tommyds/Makefile
@@ -0,0 +1,219 @@
+#############################################################################
+# Tommy Makefile
+
+# Version of TommyDS
+VERSION = 2.2
+
+# Build options for the check program
+ifdef COVERAGE
+CFLAGS = -O0 -g -fprofile-arcs -ftest-coverage
+else
+CFLAGS = -O3 -march=native -Wall -Wextra -Wshadow -Wuninitialized -Wpadded -Wcast-align -Wcast-qual -g
+endif
+
+# Build options for the benchmark
+# -std=gnu++0x required by Google btree
+BENCHCXXFLAGS = -m32 -O3 -march=native -flto -fpermissive -std=gnu++0x -Wall -g
+
+# Programs
+CC ?= gcc
+CXX ?= g++
+OBJDUMP ?= objdump
+UNAME = $(shell uname)
+
+# Linux
+ifeq ($(UNAME),Linux)
+LIB=-lrt
+BENCHLIB=benchmark/lib/judy/libJudyL.a benchmark/lib/judy/libJudyMalloc.a
+EXE=
+O=.o
+endif
+
+# Darwin
+ifeq ($(UNAME),Darwin)
+LIB=
+EXE=
+O=.o
+endif
+
+# Windows
+ifeq ($(UNAME),)
+BENCHLIB=benchmark/lib/judy/src/judy.lib
+EXE=.exe
+O=.obj
+endif
+
+#CHECK = ./tommybench -n 1000000 -d tommy-hashlin
+CHECK = ./tommycheck
+
+DEP = \
+	tommyds/tommyalloc.c \
+	tommyds/tommyalloc.h \
+	tommyds/tommyarray.c \
+	tommyds/tommyarray.h \
+	tommyds/tommyarrayof.c \
+	tommyds/tommyarrayof.h \
+	tommyds/tommyarrayblk.c \
+	tommyds/tommyarrayblk.h \
+	tommyds/tommyarrayblkof.c \
+	tommyds/tommyarrayblkof.h \
+	tommyds/tommy.c \
+	tommyds/tommy.h \
+	tommyds/tommyhash.c \
+	tommyds/tommyhashdyn.c \
+	tommyds/tommyhashdyn.h \
+	tommyds/tommyhash.h \
+	tommyds/tommyhashlin.c \
+	tommyds/tommyhashlin.h \
+	tommyds/tommyhashtbl.c \
+	tommyds/tommyhashtbl.h \
+	tommyds/tommylist.c \
+	tommyds/tommylist.h \
+	tommyds/tommytrie.c \
+	tommyds/tommytrie.h \
+	tommyds/tommytrieinp.c \
+	tommyds/tommytrieinp.h \
+	tommyds/tommytypes.h \
+	tommyds/tommychain.h
+
+DEPTEST = \
+	check.c \
+	benchmark.cc
+
+all: tommycheck$(EXE)
+
+bench: tommybench$(EXE)
+
+tommy$(O): $(DEP)
+	$(CC) $(CFLAGS) -c tommyds/tommy.c -o tommy$(O)
+	-$(OBJDUMP) -S tommy$(O) > tommy.s
+
+tommycheck$(EXE): check.c tommy$(O)
+	$(CC) $(CFLAGS) check.c tommy$(O) -o tommycheck$(EXE) $(LIB)
+
+tommybench$(EXE): benchmark.cc $(DEP)
+	$(CXX) $(BENCHCXXFLAGS) benchmark.cc -o tommybench$(EXE) $(LIB) $(BENCHLIB)
+
+check: tommycheck$(EXE)
+	./tommycheck$(EXE)
+	echo Check completed with success!
+
+lcov_reset:
+	lcov -d . -z
+	rm -f ./lcov.info
+
+lcov_capture:
+	lcov -d . --capture -o lcov.info
+
+lcov_html:
+	rm -rf ./cov
+	mkdir cov
+	genhtml -o ./cov lcov.info
+
+coverage:
+	$(MAKE) COVERAGE=1 tommycheck$(EXE)
+	$(MAKE) lcov_reset
+	./tommycheck$(EXE)
+	$(MAKE) lcov_capture
+	$(MAKE) lcov_html
+
+valgrind:
+	valgrind \
+		--tool=memcheck \
+		--track-origins=yes \
+		--read-var-info=yes \
+		-v $(CHECK) \
+		2> valgrind.log
+		tail valgrind.log
+
+callgrind:
+	valgrind \
+		--tool=callgrind \
+		--dump-instr=yes \
+		--trace-jump=yes \
+		-v $(CHECK) \
+		2> callgrind.log
+		tail callgrind.log
+
+cachegrind:
+	valgrind \
+		--tool=cachegrind \
+		-v $(CHECK) \
+		2> cachegrind.log
+		tail cachegrind.log
+
+phony:
+
+graph: phony
+	cd benchmark && sh gr_all.sh
+
+doc: phony tommy.doxygen tommy.css $(DEP)
+	rm -rf doc
+	mkdir doc
+	cp -a benchmark/data/def doc/def
+	cp -a benchmark/data/other doc/other
+	cp -a benchmark/data/core_i5_650_3G2_linux doc/core_i5_650_3G2_linux
+	rm -f doc/*/*.lst
+	rm -f doc/*/*.gnu
+	doxygen tommy.doxygen
+	rm -f doc/doxygen.png
+	rm -f doc/tab_*.png
+
+web: phony tommyweb.doxygen tommy.css $(DEP)
+	rm -rf web
+	mkdir web
+	cp -a benchmark/data/def web/def
+	cp -a benchmark/data/other web/other
+	cp -a benchmark/data/core_i5_650_3G2_linux web/core_i5_650_3G2_linux
+	rm -f web/*/*.lst
+	rm -f web/*/*.gnu
+	doxygen tommyweb.doxygen
+	rm -f web/doxygen.png
+	rm -f web/tab_*.png
+
+clean:
+	rm -f *.log *.s *.lst *.o
+	rm -f *.ncb *.suo *.obj
+	rm -f *.gcno *.gcda lcov.info
+	rm -rf Debug Release x64
+	rm -f callgrind.out.*
+	rm -f cachegrind.out.*
+
+distclean: clean
+	rm -f tommybench$(EXE) tommycheck$(EXE)
+
+maintainerclean: distclean
+	rm -rf doc web
+
+DIST=tommyds-$(VERSION)
+
+DISTFILES=\
+	Makefile \
+	README LICENSE AUTHORS INSTALL HISTORY \
+	tommy.doxygen tommy.css tommy-header.html tommy-footer.html \
+	benchmark.vcxproj benchmark.sln \
+	benchmark.geany \
+	benchmark.cc \
+	check.c
+
+dist:
+	mkdir $(DIST)
+	mkdir $(DIST)/tommyds
+	cp $(DISTFILES) $(DIST)
+	cp $(DEP) $(DIST)/tommyds
+	cp $(DEPTEST) $(DIST)
+	cp -R doc $(DIST)
+	cp -R benchmark $(DIST)/benchmark
+	rm -f $(DIST)/benchmark/data/*/*.png
+	rm -rf $(DIST)/benchmark/data/test
+	rm -f $(DIST)/benchmark/arial.ttf
+	rm -f $(DIST).tar.gz
+	tar cfzo $(DIST).tar.gz $(DIST)
+	rm -f $(DIST).zip
+	zip -r $(DIST).zip $(DIST)
+	rm -r $(DIST)
+
+distcheck: dist
+	tar zxvf $(DIST).tar.gz
+	cd $(DIST) && make check
+	rm -rf $(DIST)
diff --git a/third-party/tommyds/README b/third-party/tommyds/README
new file mode 100644
index 0000000..c0fa3ec
--- /dev/null
+++ b/third-party/tommyds/README
@@ -0,0 +1,31 @@
+TommyDS
+=======
+
+TommyDS is a C library of array, hashtables and tries data structures,
+designed for high performance and providing an easy to use interface.
+
+It's faster than all the similar libraries like rbtree, judy, goodledensehash,
+khash, uthash, nedtries and others.
+
+The data structures provided are:
+
+	tommy_list - A double linked list.
+	tommy_array - A linear array. It doesn't fragment
+		the heap.
+	tommy_arrayblk - A blocked linear array. It doesn't fragment
+		the heap and it minimizes the space occupation.
+	tommy_hashtable - A fixed size chained hashtable.
+	tommy_hashdyn - A dynamic chained hashtable.
+	tommy_hashlin - A linear chained hashtable. It doesn't have the
+		problem of the delay when resizing and it doesn't
+		fragment the heap.
+	tommy_trie - A trie optimized for cache utilization.
+	tommy_trie_inplace - A trie completely inplace.
+
+The documentation is available in HTML format in the doc/index.html file,
+and directly in the .h files.
+
+The official site of TommyDS is:
+
+    http://www.tommyds.it
+
diff --git a/third-party/tommyds/tommy.c b/third-party/tommyds/tommy.c
new file mode 100644
index 0000000..a05013a
--- /dev/null
+++ b/third-party/tommyds/tommy.c
@@ -0,0 +1,41 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyhash.c"
+#include "tommyalloc.c"
+#include "tommyarray.c"
+#include "tommyarrayof.c"
+#include "tommyarrayblk.c"
+#include "tommyarrayblkof.c"
+#include "tommylist.c"
+#include "tommytree.c"
+#include "tommytrie.c"
+#include "tommytrieinp.c"
+#include "tommyhashtbl.c"
+#include "tommyhashdyn.c"
+#include "tommyhashlin.c"
+
diff --git a/third-party/tommyds/tommy.h b/third-party/tommyds/tommy.h
new file mode 100644
index 0000000..08b0a75
--- /dev/null
+++ b/third-party/tommyds/tommy.h
@@ -0,0 +1,763 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \mainpage
+ * \section Introduction
+ * Tommy is a C library of array, hashtables and tries data structures,
+ * designed for high performance and providing an easy to use interface.
+ *
+ * It's <b>faster</b> than all the similar libraries like
+ * <a href="http://www.canonware.com/rb/">rbtree</a>,
+ * <a href="http://judy.sourceforge.net/">judy</a>,
+ * <a href="http://code.google.com/p/cpp-btree/">googlebtree</a>,
+ * <a href="http://panthema.net/2007/stx-btree/">stxbtree</a>,
+ * <a href="http://attractivechaos.awardspace.com/">khash</a>,
+ * <a href="http://uthash.sourceforge.net/">uthash</a>,
+ * <a href="http://www.nedprod.com/programs/portable/nedtries/">nedtrie</a>,
+ * <a href="http://code.google.com/p/judyarray/">judyarray</a>,
+ * <a href="http://concurrencykit.org/">concurrencykit</a> and others.
+ * Only <a href="http://code.google.com/p/google-sparsehash/">googledensehash</a> is a real competitor for Tommy.
+ *
+ * The data structures provided are:
+ *
+ * - ::tommy_list - A double linked list.
+ * - ::tommy_array, ::tommy_arrayof - A linear array.
+ * It doesn't fragment the heap.
+ * - ::tommy_arrayblk, ::tommy_arrayblkof - A blocked linear array.
+ * It doesn't fragment the heap and it minimizes the space occupation.
+ * - ::tommy_hashtable - A fixed size chained hashtable.
+ * - ::tommy_hashdyn - A dynamic chained hashtable.
+ * - ::tommy_hashlin - A linear chained hashtable.
+ * It doesn't have the problem of the delay when resizing and
+ * it doesn't fragment the heap.
+ * - ::tommy_trie - A trie optimized for cache utilization.
+ * - ::tommy_trie_inplace - A trie completely inplace.
+ * - ::tommy_tree - A tree to keep elements in order.
+ *
+ * The most interesting are ::tommy_array, ::tommy_hashdyn, ::tommy_hashlin, ::tommy_trie and ::tommy_trie_inplace.
+ *
+ * The official site of TommyDS is <a href="http://www.tommyds.it/">http://www.tommyds.it/</a>,
+ *
+ * \section Use
+ *
+ * All the Tommy containers are used to store pointers to generic objects, associated to an
+ * integer value, that could be a key or a hash value.
+ *
+ * They are semantically equivalent at the C++ <a href="http://www.cplusplus.com/reference/map/multimap/">multimap\<unsigned,void*\></a>
+ * and <a href="http://www.cplusplus.com/reference/unordered_map/unordered_multimap/">unordered_multimap\<unsigned,void*\></a>.
+ *
+ * An object, to be inserted in a container, should contain a node of type ::tommy_node.
+ * Inside this node is present a pointer to the object itself in the tommy_node::data field,
+ * the key used to identify the object in the tommy_node::key field, and other fields used
+ * by the containers.
+ *
+ * This is a typical object declaration:
+ * \code
+ * struct object {
+ *     // other fields
+ *     tommy_node node;
+ * };
+ * \endcode
+ *
+ * To insert an object in a container, you have to provide the address of the embedded node,
+ * the address of the object and the value of the key.
+ * \code
+ * int key_to_insert = 1;
+ * struct object* obj = malloc(sizeof(struct object));
+ * ...
+ * tommy_trie_insert(..., &obj->node, obj, key_to_insert);
+ * \endcode
+ *
+ * To search an object you have to provide the key and call the search function.
+ * \code
+ * int key_to_find = 1;
+ * struct object* obj = tommy_trie_search(..., key_to_find);
+ * if (obj) {
+ *   // found
+ * }
+ * \endcode
+ *
+ * To access all the objects with the same keys you have to iterate over the bucket
+ * assigned at the specified key.
+ * \code
+ * int key_to_find = 1;
+ * tommy_trie_node* i = tommy_trie_bucket(..., key_to_find);
+ *
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     printf("%d\n", obj->value); // process the object
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an object you have to provide the key and call the remove function.
+ * \code
+ * int key_to_remove = 1;
+ * struct object* obj = tommy_trie_remove(..., key_to_remove);
+ * if (obj) {
+ *     // found
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * Dealing with hashtables, instead of the key, you have to provide the hash
+ * value of the object, and a compare function able to differentiate objects with
+ * the same hash value.
+ * To compute the hash value, you can use the generic tommy_hash_u32() function,
+ * or the specialized integer hash function tommy_inthash_u32().
+ *
+ * \section Features
+ *
+ * Tommy is fast and easy to use.
+ *
+ * Tommy is portable to all platforms and operating systems.
+ *
+ * Tommy containers support multiple elements with the same key.
+ *
+ * Tommy containers keep the original insertion order of elements with equal keys.
+ *
+ * Tommy is released with the \ref license "2-clause BSD license".
+ *
+ * See the \ref design page for more details and limitations.
+ *
+ * \section Performance
+ * Here you can see some timings comparing with other notable implementations.
+ * The <i>Hit</i> graph shows the time required for searching random objects
+ * with a key.
+ * The <i>Change</i> graph shows the time required for searching, removing and
+ * reinsert random objects with a different key value.
+ *
+ * Times are expressed in nanoseconds for each element, and <b>lower is better</b>.
+ *
+ * To have some reference numbers, you can check <a href="https://gist.github.com/jboner/2841832">Latency numbers every programmer should know</a>.
+ *
+ * A complete analysis is available in the \ref benchmark page.
+ *
+ * <img src="def/img_random_hit.png"/>
+ *
+ * <img src="def/img_random_change.png"/>
+ *
+ * \page benchmark Tommy Benchmarks
+ *
+ * To evaluate Tommy performances, an extensive benchmark was done,
+ * comparing it to the best libraries of data structures available:
+ *
+ * Specifically we test:
+ *  - ::tommy_hashtable - Fixed size chained hashtable.
+ *  - ::tommy_hashdyn - Dynamic chained hashtable.
+ *  - ::tommy_hashlin - Linear chained hashtable.
+ *  - ::tommy_trie - Trie optimized for cache usage.
+ *  - ::tommy_trie_inplace - Trie completely inplace.
+ *  - <a href="http://www.canonware.com/rb/">rbtree</a> - Red-black tree by Jason Evans.
+ *  - <a href="http://www.nedprod.com/programs/portable/nedtries/">nedtrie</a> - Binary trie inplace by Niall Douglas.
+ *  - <a href="http://attractivechaos.awardspace.com/">khash</a> - Dynamic open addressing hashtable by Attractive Chaos.
+ *  - <a href="http://uthash.sourceforge.net/">uthash</a> - Dynamic chaining hashtable by Troy D. Hanson.
+ *  - <a href="http://judy.sourceforge.net/">judy</a> - Burst trie (JudyL) by Doug Baskins.
+ *  - <a href="http://code.google.com/p/judyarray/">judyarray</a> - Burst trie by Karl Malbrain.
+ *  - <a href="http://code.google.com/p/google-sparsehash/">googledensehash</a> - Dynamic open addressing hashtable by Craig Silverstein at Google.
+ *  - <a href="http://code.google.com/p/cpp-btree/">googlebtree</a> - Btree by Google.
+ *  - <a href="http://panthema.net/2007/stx-btree/">stxbtree</a> - STX Btree by Timo Bingmann.
+ *  - <a href="http://www.cplusplus.com/reference/unordered_map/unordered_map/">c++unordered_map</a> - C++ STL unordered_map<> template.
+ *  - <a href="http://www.cplusplus.com/reference/map/map/">c++map</a> - C++ STL map<> template.
+ *  - <a href="https://sites.google.com/site/binarysearchcube/">tesseract</a> - Binary Search Tesseract by Gregorius van den Hoven.
+ *  - <a href="https://code.google.com/p/sparsehash/source/browse/trunk/experimental/libchash.c">googlelibchash</a> - LibCHash by Craig Silverstein at Google.
+ *  - <a href="https://github.com/fredrikwidlund/libdynamic">libdynamic</a> - Hash set by Fredrik Widlund.
+ *  - <a href="http://concurrencykit.org/">concurrencykit</a> - Non-blocking hash set by Samy Al Bahra.
+ *
+ * Note that <em>googlelibchash</em> and <em>concurrencykit</em> are not shown in the graphs
+ * because they present a lot of spikes. See the \ref notes the end.
+ *
+ * \section thebenchmark The Benchmark
+ *
+ * The benchmark consists in storing a set of N pointers to objects and
+ * searching them using integer keys.
+ *
+ * Compared to the case of mapping integers to integers, mapping pointers to
+ * objects means that the pointers are also dereferenced, to simulate the
+ * object access, resulting in additional cache misses.
+ * This gives an advantage to implementations that store information in the
+ * objects itself, as the additional cache misses are already implicit.
+ *
+ * The test done are:
+ *  - <b>Insert</b> Insert all the objects starting with an empty container.
+ *  - <b>Change</b> Find and remove one object and reinsert it with a different key, repeated for all the objects.
+ *  - <b>Hit</b> Find with success all the objects and dereference them.
+ *  - <b>Miss</b> Find with failure all the objects.
+ *  - <b>Remove</b> Remove all the objects and dereference them.
+ *
+ * The <i>Change</i>, <i>Hit</i> and <i>Miss</i> tests operate always with N
+ * objects in the containers.
+ * The <i>Insert</i> test starts with an empty container, and the <i>Remove</i>
+ * test ends with an empty container.
+ * The objects are always dereferenced, as we are supposing to use them. This
+ * happens even in the remove case, as we are supposing to deallocate them.
+ *
+ * All the objects are preallocated in the heap, and the allocation and deallocation
+ * time is not included in the test.
+ *
+ * The objects contain an integer <i>value</i> field used for consistency checks,
+ * an unused <i>payload</i> field of 16 bytes, and any other data required by the
+ * data structure.
+ *
+ * The objects are identified and stored using integer and unique <i>keys</i>.
+ * The key domain used is <strong>dense</strong>, and it's defined by the set
+ * of N even numbers starting from 0x80000000 to 0x80000000+2*N.
+ *
+ * The use of even numbers allows to have missing keys inside the domain for
+ * the <i>Miss</i> and <i>Change</i> test.
+ * In such tests it's used the key domain defined by the set of N odd numbers
+ * starting from 0x80000000+1 to 0x80000000+2*N+1.
+ * Note that using additional keys at the corners of the domain would have given
+ * an unfair advantage to tries and trees as they implicitly keep track of the
+ * maximum and minimum key value inserted.
+ *
+ * The use of the 0x80000000 base, allow to test a key domain not necessarily
+ * starting at 0. Using a 0 base would have given an unfair advantage to some
+ * implementation handling it as a special case.
+ *
+ * For all the hashtables the keys are hashed using the tommy_inthash_u32()
+ * function that ensures an uniform distribution. This hash function is also
+ * reversible, meaning that no collision is going to be caused by hashing the
+ * keys. For tries and trees the keys are not hashed, and used directly.
+ *
+ * The tests are repeated using keys in <i>Random</i> mode and in <i>Forward</i>
+ * mode. In the forward mode the key values are used in order from the lowest
+ * to the highest.
+ * In the random mode the key values are used in a completely random order.
+ * In the <i>Change</i> test in forward mode, each object is reinserted using
+ * the previous key incremented by 1. In random mode each object is reinserted
+ * using a completely different and uncorrelated key.
+ *
+ * The forward order advantages tries and trees as they use the key directly
+ * and they have a cache advantage on using consecutive keys.
+ * The random order advantages hashtables, as the hash function already
+ * randomizes the key. Usually real uses case are in between, and the random
+ * one is the worst case.
+ *
+ * \section result Results
+ *
+ * The most significant tests depend on your data usage model, but if in doubt,
+ * you can look at <i>Random Hit</i> and <i>Random Change</i>.
+ * They represent the real world worst condition.
+ *
+ * <img src="def/img_random_hit.png"/>
+ *
+ * In the <i>Random Hit</i> graph you can see a vertical split at the 100.000
+ * elements limit. Before this limit the cache of modern processor is able to
+ * contains most of the data, and it allows a very fast access with almost all
+ * data structures.
+ * After this limit, the number of cache misses is the dominant factor, and
+ * the curve depends mainly on the number of cache-miss required.
+ *
+ * rbtree and nedtrie grow as log2(N) as they have two branches on each node,
+ * ::tommy_trie_inplace grows as log4(N), ::tommy_trie as log8(N) and hashtables
+ * are almost constant and don't grow.
+ * For ::tommy_trie_inplace and ::tommy_trie you can change the grow curve
+ * configuring a different number of branches for node.
+ *
+ * <img src="def/img_random_change.png"/>
+ *
+ * The <i>Random Change</i> graph confirms the vertical split at the 100.000
+ * elements limit. It also show that hashtables are almost unbeatable with a
+ * random access.
+ *
+ * \section random Random order
+ * Here you can see the whole <i>Random</i> test results in different platforms.
+ *
+ * In the <i>Random</i> test, hashtables are almost always winning, seconds are
+ * tries, and as last trees.
+ *
+ * The best choices are ::tommy_hashdyn, ::tommy_hashlin, and googledensehash,
+ * with ::tommy_hashlin having the advantage to be real-time friendly and not
+ * increasing the heap fragmentation.
+ * <table border="0">
+ * <tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_insert.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_hit.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_miss.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_change.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_remove.png"/>
+ * </td></tr>
+ * </table>
+ *
+ * \section forward Forward order
+ * Here you can see the whole <i>Forward</i> test results in different platforms.
+ *
+ * In the <i>Forward</i> test, tries are the winners. Hashtables are competitive
+ * until the cache limit, then they lose against tries. Trees are the slowest.
+ *
+ * The best choices are ::tommy_trie and ::tommy_trie_inplace, where ::tommy_trie is
+ * a bit faster, and ::tommy_trie_inplace doesn't require a custom allocator.
+ *
+ * Note that also hashtables are faster in forward order than random. This may
+ * seem a bit surprising as the hash function randomizes the access even with
+ * consecutive keys. This happens because the objects are allocated in consecutive
+ * memory, and accessing them in order, improves the cache utilization, even if
+ * the hashed key is random.
+ *
+ * Note that you can make hashtables to reach tries performance tweaking the hash
+ * function to put near keys allocated nearby.
+ * This is possible if you know in advance the distribution of keys.
+ * For example, in the benchmark you could use something like:
+ * \code
+ * #define hash(v) tommy_inthash_u32(v & ~0xF) + (v & 0xF)
+ * \endcode
+ * and make keys that differ only by the lowest bits to have hashes with the same
+ * property, resulting in objects stored nearby, and improving cache utilization.
+ *
+ * <table border="0">
+ * <tr><td>
+ * <img src="core_i5_650_3G2_linux/img_forward_insert.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_forward_hit.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_forward_miss.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_forward_change.png"/>
+ * </td></tr><tr><td>
+ * <img src="core_i5_650_3G2_linux/img_forward_remove.png"/>
+ * </td></tr>
+ * </table>
+ *
+ * \section size Size
+ * Here you can see the memory usage of the different data structures.
+ * <table border="0">
+ * <tr><td>
+ * <img src="core_i5_650_3G2_linux/img_random_size.png"/>
+ * </td></tr>
+ * </table>
+ *
+ * \section code Code
+ *
+ * The compilers used in the benchmark are:
+ *  - <b>gcc 4.9.2</b> in Linux with options: -O3 -march=nehalem
+ *  - <b>Visual C 2012</b> in Windows with options: /Ox /Oy- /GL /GS- /arch:SSE2
+ *
+ * The following is pseudo code of the benchmark used. In this case it's written
+ * for the C++ unordered_map.
+ *
+ * \code
+ * #define N 10000000 // Number of elements
+ * #define PAYLOAD 16 // Size of the object
+ *
+ * // Basic object inserted in the colletion
+ * struct obj {
+ *     unsigned value; // Key used for searching
+ *     char payload[PAYLOAD];
+ * };
+ *
+ * // Custom hash function to avoid to use the STL one
+ * class custom_hash {
+ * public:
+ *     unsigned operator()(unsigned key) const { return tommy_inthash_u32(key); }
+ * };
+ *
+ * // Map collection from "unsigned" to "pointer to object"
+ * typedef std::unordered_map<unsigned, obj*, custom_hash> bag_t;
+ * bag_t bag;
+ *
+ * // Preallocate objects
+ * obj* OBJ = new obj[N];
+ *
+ * // Keys used for inserting and searching elements
+ * unsigned INSERT[N];
+ * unsigned SEARCH[N];
+ *
+ * // Initialize the keys
+ * for(i=0;i<N;++i) {
+ *     INSERT[i] = 0x80000000 + i * 2;
+ *     SEARCH[i] = 0x80000000 + i * 2;
+ * }
+ *
+ * // If random order is required, shuffle the keys with Fisher-Yates
+ * // The two key orders are not correlated
+ * if (test_random) {
+ *     std::random_shuffle(INSERT, INSERT + N);
+ *     std::random_shuffle(SEARCH, SEARCH + N);
+ * }
+ * \endcode
+ *
+ * \subsection insertion Insert benchmark
+ * \code
+ * for(i=0;i<N;++i) {
+ *     // Setup the element to insert
+ *     unsigned key = INSERT[i];
+ *     obj* element = &OBJ[i];
+ *     element->value = key;
+ *
+ *     // Insert it
+ *     bag[key] = element;
+ * }
+ * \endcode
+ *
+ * \subsection change Change benchmark
+ * \code
+ * for(i=0;i<N;++i) {
+ *     // Search the element
+ *     unsigned key = SEARCH[i];
+ *     bag_t::iterator j = bag.find(key);
+ *     if (j == bag.end())
+ *         abort();
+ *
+ *     // Remove it
+ *     obj* element = j->second;
+ *     bag.erase(j);
+ *
+ *     // Reinsert the element with a new key
+ *     // Use +1 in the key to ensure that the new key is unique
+ *     key = INSERT[i] + 1;
+ *     element->value = key;
+ *     bag[key] = element;
+ * }
+ * \endcode
+ *
+ * \subsection hit Hit benchmark
+ * \code
+ * for(i=0;i<N;++i) {
+ *     // Search the element
+ *     // Use a different key order than insertion
+ *     // Use +1 in the key because we run after the "Change" test
+ *     unsigned key = SEARCH[i] + 1;
+ *     bag_t::const_iterator j = bag.find(key);
+ *     if (j == bag.end())
+ *         abort();
+ *
+ *     // Ensure that it's the correct element.
+ *     // This operation is like using the object after finding it,
+ *     // and likely involves a cache-miss operation.
+ *     obj* element = j->second;
+ *     if (element->value != key)
+ *         abort();
+ * }
+ * \endcode
+ *
+ * \subsection miss Miss benchmark
+ * \code
+ * for(i=0;i<N;++i) {
+ *     // Search the element
+ *     // All the keys are now shifted by +1 by the "Change" test, and we'll find nothing
+ *     unsigned key = SEARCH[i];
+ *     bag_t::const_iterator j = bag.find(key);
+ *     if (j != bag.end())
+ *         abort();
+ * }
+ * \endcode
+ *
+ * \subsection remove Remove benchmark
+ * \code
+ * for(i=0;i<N;++i) {
+ *     // Search the element
+ *     // Use +1 in the key because we run after the "Change" test
+ *     unsigned key = SEARCH[i] + 1;
+ *     bag_t::iterator j = bag.find(key);
+ *     if (j == bag.end())
+ *         abort();
+ *
+ *     // Remove it
+ *     bag.erase(j);
+ *
+ *     // Ensure that it's the correct element.
+ *     obj* element = j->second;
+ *     if (element->value != key)
+ *         abort();
+ * }
+ * \endcode
+ *
+ * \section others Other benchmarks
+ * Here some links to other performance comparison:
+ *
+ * <a href="http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/">Comparison of Hash Table Libraries</a>
+ *
+ * <a href="http://incise.org/hash-table-benchmarks.html">Hash Table Benchmarks</a>
+ *
+ * \section notes Notes
+ *
+ * Here some notes about the data structure tested not part of Tommy.
+ *
+ * \subsection googlelibchash Google C libchash
+ * It's the C implementation located in the <i>experimental/</i> directory of the googlesparsehash archive.
+ * It has very bad performances in the <i>Change</i> test for some N values.
+ * See this <a href="other/googlelibchash_problem.png">graph</a> with a lot of spikes.
+ * The C++ version doesn't suffer of this problem.
+ *
+ * \subsection googledensehash Google C++ densehash
+ * It doesn't release memory on deletion.
+ * To avoid an unfair advantage in the <i>Remove</i> test, we force a periodic
+ * resize calling resize(0) after any deallocation.
+ * The resize is executed when the load factor is lower than 20%.
+ *
+ * \subsection khash khash
+ * It doesn't release memory on deletion. This gives an unfair advantage on the <i>Remove</i> test.
+ *
+ * \subsection nedtrie nedtrie
+ * I've found a crash bug when inserting keys with the 0 value.
+ * The <a href="https://github.com/ned14/nedtries/commit/21039696f27db4ffac70a82f89dc5d00ae74b332">fix</a> of this issue is now in the nedtries github.
+ * We do not use the C++ implementation as it doesn't compile with gcc 4.4.3.
+ *
+ * \subsection judy Judy
+ * Sometimes it has bad performances in some specific platform
+ * and for some specific input data size.
+ * This makes difficult to predict the performance, as it is usually good until
+ * you get one of these cases.
+ * See for example this <a href="other/judy_problem.png">graph</a> with a big replicable spike at 50.000 elements.
+ *
+ * \subsection ck Concurrency Kit
+ * It has very bad performances in the <i>Change</i> test for some N values.
+ * See this <a href="other/ck_problem.png">graph</a> with a lot of spikes.
+ *
+ * \page multiindex Tommy Multi Indexing
+ *
+ * Tommy provides only partial iterator support with the "foreach" functions.
+ * If you need real iterators you have to insert all the objects also in a ::tommy_list,
+ * and use the list as iterator.
+ *
+ * This technique allows to keep track of the insertion order with the list,
+ * and provides more search possibilities using different data structures for
+ * different search keys.
+ *
+ * See the next example, for a objects inserted in a ::tommy_list, and in
+ * two ::tommy_hashdyn using different keys.
+ *
+ * \code
+ * struct object {
+ *     // data fields
+ *     int value_0;
+ *     int value_1;
+ *
+ *     // for containers
+ *     tommy_node list_node; // node for the list
+ *     tommy_node hash_node_0; // node for the first hash
+ *     tommy_node hash_node_1; // node for the second hash
+ * };
+ *
+ * // search function for value_1
+ * int search_1(const void* arg, const void* obj)
+ * {
+ *     return *(const int*)arg != ((const struct object*)obj)->value_1;
+ * }
+ *
+ * tommy_hashdyn hash_0;
+ * tommy_hashdyn hash_1;
+ * tommy_list list;
+ *
+ * // initializes the hash tables and the list
+ * tommy_hashdyn_init(&hash_0);
+ * tommy_hashdyn_init(&hash_1);
+ * tommy_list_init(&list);
+ *
+ * ...
+ *
+ * // creates an object and inserts it
+ * struct object* obj = malloc(sizeof(struct object));
+ * obj->value_0 = ...;
+ * obj->value_1 = ...;
+ * // inserts in the first hash table
+ * tommy_hashdyn_insert(&hash_0, &obj->hash_node_0, obj, tommy_inthash_u32(obj->value_0));
+ * // inserts in the second hash table
+ * tommy_hashdyn_insert(&hash_1, &obj->hash_node_1, obj, tommy_inthash_u32(obj->value_1));
+ * // inserts in the list
+ * tommy_list_insert_tail(&list, &obj->list_node, obj);
+ *
+ * ...
+ *
+ * // searches an object by value_1 and deletes it
+ * int value_to_find = ...;
+ * struct object* obj = tommy_hashdyn_search(&hash_1, search_1, &value_to_find, tommy_inthash_u32(value_to_find));
+ * if (obj) {
+ *     // if found removes all the references
+ *     tommy_hashdyn_remove_existing(&hash_0, &obj->hash_node_0);
+ *     tommy_hashdyn_remove_existing(&hash_1, &obj->hash_node_1);
+ *     tommy_list_remove_existing(&list, &obj->list_node);
+ * }
+ *
+ * ...
+ *
+ * // complex iterator logic
+ * tommy_node* i = tommy_list_head(&list);
+ * while (i != 0) {
+ *    // get the object
+ *    struct object* obj = i->data;
+ *    ...
+ *    // go to the next element
+ *    i = i->next;
+ *    ...
+ *    // go to the prev element
+ *    i = i->prev;
+ *    ...
+ * }
+ *
+ * ...
+ *
+ * // deallocates the objects iterating the list
+ * tommy_list_foreach(&list, free);
+ *
+ * // deallocates the hash tables
+ * tommy_hashdyn_done(&hash_0);
+ * tommy_hashdyn_done(&hash_1);
+ * \endcode
+ *
+ * \page design Tommy Design
+ *
+ * Tommy is designed to fulfill the need of generic data structures for the
+ * C language, providing at the same time high performance and a clean
+ * and easy to use interface.
+ *
+ * \section testing Testing
+ *
+ * Extensive and automated tests with the runtime checker <a href="http://valgrind.org/">valgrind</a>
+ * and the static analyzer <a href="http://clang-analyzer.llvm.org/">clang</a>
+ * are done to ensure the correctness of the library.
+ *
+ * The test has a <a href="http://www.tommyds.it/cov/tommyds/tommyds">code coverage of 100%</a>,
+ * measured with <a href="http://ltp.sourceforge.net/coverage/lcov.php">lcov</a>.
+ *
+ * \section Limitations
+ *
+ * Tommy is not thread safe. You have always to provide thread safety using
+ * locks before calling any Tommy functions.
+ *
+ * Tommy doesn't provide iterators over the implicit order defined by the data
+ * structures. To iterate on elements you must insert them also into a ::tommy_list,
+ * and use the list as iterator. See the \ref multiindex example for more details.
+ * Note that this is a real limitation only for ::tommy_trie, as it's the only
+ * data structure defining an useable order.
+ *
+ * Tommy doesn't provide an error reporting mechanism for a malloc() failure.
+ * You have to provide it redefining malloc() if you expect it to fail.
+ *
+ * Tommy assumes to never have more than 2^32-1 elements in a container.
+ *
+ * \section compromise Compromises
+ *
+ * Finding the right balance between efficency and easy to use required some
+ * comprimises. Most of them are on memory efficency, and were done to avoid to
+ * cripple the interface.
+ *
+ * The following is a list of such decisions.
+ *
+ * \subsection multi_key Multi key
+ * All the Tommy containers support the insertion of multiple elements with
+ * the same key, adding in each node a list of equal elements.
+ *
+ * They are the equivalent at the C++ associative containers <a href="http://www.cplusplus.com/reference/map/multimap/">multimap\<unsigned,void*\></a>
+ * and <a href="http://www.cplusplus.com/reference/unordered_map/unordered_multimap/">unordered_multimap\<unsigned,void*\></a>
+ * that allow duplicates of the same key.
+ *
+ * A more memory conservative approach is to not allow duplicated elements,
+ * removing the need of this list.
+ *
+ * \subsection data_pointer Data pointer
+ * The tommy_node::data field is present to allow search and remove functions to return
+ * directly a pointer to the element stored in the container.
+ *
+ * A more memory conservative approach is to require the user to compute
+ * the element pointer from the embedded node with a fixed displacement.
+ * For an example, see the Linux Kernel declaration of
+ * <a href="http://lxr.free-electrons.com/ident?i=container_of">container_of()</a>.
+ *
+ * \subsection insertion_order Insertion order
+ * The list used for collisions is double linked to allow
+ * insertion of elements at the end of the list to keep the
+ * insertion order of equal elements.
+ *
+ * A more memory conservative approach is to use a single linked list,
+ * inserting elements only at the start of the list, losing the
+ * original insertion order.
+ *
+ * \subsection zero_list Zero terminated list
+ * The 0 terminated format of tommy_node::next is present to provide a forward
+ * iterator terminating in 0. This allows the user to write a simple iteration
+ * loop over the list of elements in the same bucket.
+ *
+ * A more efficient approach is to use a circular list, because operating on nodes
+ * in a circular list doesn't requires to manage the special terminating case when
+ * adding or removing elements.
+ *
+ * \page license Tommy License
+ * Tommy is released with a <i>2-clause BSD license</i>.
+ *
+ * \code
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ * \endcode
+ */
+
+/** \file
+ * All in one include for Tommy.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "tommytypes.h"
+#include "tommyhash.h"
+#include "tommyalloc.h"
+#include "tommyarray.h"
+#include "tommyarrayof.h"
+#include "tommyarrayblk.h"
+#include "tommyarrayblkof.h"
+#include "tommylist.h"
+#include "tommytree.h"
+#include "tommytrie.h"
+#include "tommytrieinp.h"
+#include "tommyhashtbl.h"
+#include "tommyhashdyn.h"
+#include "tommyhashlin.h"
+
+#ifdef __cplusplus
+}
+#endif
+
diff --git a/third-party/tommyds/tommyalloc.c b/third-party/tommyds/tommyalloc.c
new file mode 100644
index 0000000..0da604c
--- /dev/null
+++ b/third-party/tommyds/tommyalloc.c
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyalloc.h"
+
+/******************************************************************************/
+/* allocator */
+
+/**
+ * Basic allocation segment.
+ * Smaller of a memory page, to allow also a little heap overread.
+ * The heap manager may put it in a single memory page.
+ */
+#define TOMMY_ALLOCATOR_BLOCK_SIZE (4096 - 64)
+
+void tommy_allocator_init(tommy_allocator* alloc, tommy_size_t block_size, tommy_size_t align_size)
+{
+	/* setup the minimal alignment */
+	if (align_size < sizeof(void*))
+		align_size = sizeof(void*);
+
+	/* ensure that the block_size keeps the alignment */
+	if (block_size % align_size != 0)
+		block_size += align_size - block_size % align_size;
+
+	alloc->block_size = block_size;
+	alloc->align_size = align_size;
+
+	alloc->count = 0;
+	alloc->free_block = 0;
+	alloc->used_segment = 0;
+}
+
+/**
+ * Reset the allocator and free all.
+ */
+static void allocator_reset(tommy_allocator* alloc)
+{
+	tommy_allocator_entry* block = alloc->used_segment;
+
+	while (block) {
+		tommy_allocator_entry* block_next = block->next;
+		tommy_free(block);
+		block = block_next;
+	}
+
+	alloc->count = 0;
+	alloc->free_block = 0;
+	alloc->used_segment = 0;
+}
+
+void tommy_allocator_done(tommy_allocator* alloc)
+{
+	allocator_reset(alloc);
+}
+
+void* tommy_allocator_alloc(tommy_allocator* alloc)
+{
+	void* ptr;
+
+	/* if no free block available */
+	if (!alloc->free_block) {
+		tommy_uintptr_t off, mis;
+		tommy_size_t size;
+		char* data;
+		tommy_allocator_entry* segment;
+
+		/* default allocation size */
+		size = TOMMY_ALLOCATOR_BLOCK_SIZE;
+
+		/* ensure that we can allocate at least one block */
+		if (size < sizeof(tommy_allocator_entry) + alloc->align_size + alloc->block_size)
+			size = sizeof(tommy_allocator_entry) + alloc->align_size + alloc->block_size;
+
+		data = tommy_cast(char*, tommy_malloc(size));
+		segment = (tommy_allocator_entry*)data;
+
+		/* put in the segment list */
+		segment->next = alloc->used_segment;
+		alloc->used_segment = segment;
+		data += sizeof(tommy_allocator_entry);
+
+		/* align if not aligned */
+		off = (tommy_uintptr_t)data;
+		mis = off % alloc->align_size;
+		if (mis != 0) {
+			data += alloc->align_size - mis;
+			size -= alloc->align_size - mis;
+		}
+
+		/* insert in free list */
+		do {
+			tommy_allocator_entry* free_block = (tommy_allocator_entry*)data;
+			free_block->next = alloc->free_block;
+			alloc->free_block = free_block;
+
+			data += alloc->block_size;
+			size -= alloc->block_size;
+		} while (size >= alloc->block_size);
+	}
+
+	/* remove one from the free list */
+	ptr = alloc->free_block;
+	alloc->free_block = alloc->free_block->next;
+
+	++alloc->count;
+
+	return ptr;
+}
+
+void tommy_allocator_free(tommy_allocator* alloc, void* ptr)
+{
+	tommy_allocator_entry* free_block = tommy_cast(tommy_allocator_entry*, ptr);
+
+	/* put it in the free list */
+	free_block->next = alloc->free_block;
+	alloc->free_block = free_block;
+
+	--alloc->count;
+}
+
+tommy_size_t tommy_allocator_memory_usage(tommy_allocator* alloc)
+{
+	return alloc->count * (tommy_size_t)alloc->block_size;
+}
+
diff --git a/third-party/tommyds/tommyalloc.h b/third-party/tommyds/tommyalloc.h
new file mode 100644
index 0000000..7a9afea
--- /dev/null
+++ b/third-party/tommyds/tommyalloc.h
@@ -0,0 +1,95 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Allocator of fixed size blocks.
+ */
+
+#ifndef __TOMMYALLOC_H
+#define __TOMMYALLOC_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* allocator */
+
+/** \internal
+ * Allocator entry.
+ */
+struct tommy_allocator_entry_struct {
+	struct tommy_allocator_entry_struct* next; /**< Pointer to the next entry. 0 for last. */
+};
+typedef struct tommy_allocator_entry_struct tommy_allocator_entry;
+
+/**
+ * Allocator of fixed size blocks.
+ */
+typedef struct tommy_allocator_struct {
+	struct tommy_allocator_entry_struct* free_block; /**< List of free blocks. */
+	struct tommy_allocator_entry_struct* used_segment; /**< List of allocated segments. */
+	tommy_size_t block_size; /**< Block size. */
+	tommy_size_t align_size; /**< Alignment size. */
+	tommy_count_t count; /**< Number of allocated elements. */
+} tommy_allocator;
+
+/**
+ * Initializes the allocator.
+ * \param alloc Allocator to initialize.
+ * \param block_size Size of the block to allocate.
+ * \param align_size Minimum alignment requirement. No less than sizeof(void*).
+ */
+void tommy_allocator_init(tommy_allocator* alloc, tommy_size_t block_size, tommy_size_t align_size);
+
+/**
+ * Deinitialize the allocator.
+ * It also releases all the allocated memory to the heap.
+ * \param alloc Allocator to deinitialize.
+ */
+void tommy_allocator_done(tommy_allocator* alloc);
+
+/**
+ * Allocates a block.
+ * \param alloc Allocator to use.
+ */
+void* tommy_allocator_alloc(tommy_allocator* alloc);
+
+/**
+ * Deallocates a block.
+ * You must use the same allocator used in the tommy_allocator_alloc() call.
+ * \param alloc Allocator to use.
+ * \param ptr Block to free.
+ */
+void tommy_allocator_free(tommy_allocator* alloc, void* ptr);
+
+/**
+ * Gets the size of allocated memory.
+ * \param alloc Allocator to use.
+ */
+tommy_size_t tommy_allocator_memory_usage(tommy_allocator* alloc);
+
+#endif
+
diff --git a/third-party/tommyds/tommyarray.c b/third-party/tommyds/tommyarray.c
new file mode 100644
index 0000000..a8d946b
--- /dev/null
+++ b/third-party/tommyds/tommyarray.c
@@ -0,0 +1,83 @@
+/*
+ * Copyright (c) 2011, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyarray.h"
+
+/******************************************************************************/
+/* array */
+
+void tommy_array_init(tommy_array* array)
+{
+	tommy_uint_t i;
+
+	/* fixed initial size */
+	array->bucket_bit = TOMMY_ARRAY_BIT;
+	array->bucket_max = 1 << array->bucket_bit;
+	array->bucket[0] = tommy_cast(void**, tommy_calloc(array->bucket_max, sizeof(void*)));
+	for (i = 1; i < TOMMY_ARRAY_BIT; ++i)
+		array->bucket[i] = array->bucket[0];
+
+	array->count = 0;
+}
+
+void tommy_array_done(tommy_array* array)
+{
+	tommy_uint_t i;
+
+	tommy_free(array->bucket[0]);
+	for (i = TOMMY_ARRAY_BIT; i < array->bucket_bit; ++i) {
+		void** segment = array->bucket[i];
+		tommy_free(&segment[((tommy_ptrdiff_t)1) << i]);
+	}
+}
+
+void tommy_array_grow(tommy_array* array, tommy_count_t count)
+{
+	if (array->count >= count)
+		return;
+	array->count = count;
+
+	while (count > array->bucket_max) {
+		void** segment;
+
+		/* allocate one more segment */
+		segment = tommy_cast(void**, tommy_calloc(array->bucket_max, sizeof(void*)));
+
+		/* store it adjusting the offset */
+		/* cast to ptrdiff_t to ensure to get a negative value */
+		array->bucket[array->bucket_bit] = &segment[-(tommy_ptrdiff_t)array->bucket_max];
+
+		++array->bucket_bit;
+		array->bucket_max = 1 << array->bucket_bit;
+	}
+}
+
+tommy_size_t tommy_array_memory_usage(tommy_array* array)
+{
+	return array->bucket_max * (tommy_size_t)sizeof(void*);
+}
+
diff --git a/third-party/tommyds/tommyarray.h b/third-party/tommyds/tommyarray.h
new file mode 100644
index 0000000..c04193f
--- /dev/null
+++ b/third-party/tommyds/tommyarray.h
@@ -0,0 +1,151 @@
+/*
+ * Copyright (c) 2011, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Dynamic array based on segments of exponential growing size.
+ *
+ * This array is able to grow dynamically upon request, without any reallocation.
+ *
+ * The grow operation involves an allocation of a new array segment, without reallocating
+ * the already used memory, and then not increasing the heap fragmentation.
+ * This also implies that the address of the stored elements never change.
+ *
+ * Allocated segments grow in size exponentially.
+ */
+
+#ifndef __TOMMYARRAY_H
+#define __TOMMYARRAY_H
+
+#include "tommytypes.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* array */
+
+/**
+ * Initial and minimal size of the array expressed as a power of 2.
+ * The initial size is 2^TOMMY_ARRAY_BIT.
+ */
+#define TOMMY_ARRAY_BIT 6
+
+/** \internal
+ * Max number of elements as a power of 2.
+ */
+#define TOMMY_ARRAY_BIT_MAX 32
+
+/**
+ * Array container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_array_struct {
+	void** bucket[TOMMY_ARRAY_BIT_MAX]; /**< Dynamic array of buckets. */
+	tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
+	tommy_count_t bucket_max; /**< Number of buckets. */
+	tommy_count_t count; /**< Number of initialized elements in the array. */
+} tommy_array;
+
+/**
+ * Initializes the array.
+ */
+void tommy_array_init(tommy_array* array);
+
+/**
+ * Deinitializes the array.
+ */
+void tommy_array_done(tommy_array* array);
+
+/**
+ * Grows the size up to the specified value.
+ * All the new elements in the array are initialized with the 0 value.
+ */
+void tommy_array_grow(tommy_array* array, tommy_count_t size);
+
+/**
+ * Gets a reference of the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_array_grow().
+ */
+tommy_inline void** tommy_array_ref(tommy_array* array, tommy_count_t pos)
+{
+	tommy_uint_t bsr;
+
+	assert(pos < array->count);
+
+	/* get the highest bit set, in case of all 0, return 0 */
+	bsr = tommy_ilog2_u32(pos | 1);
+
+	return &array->bucket[bsr][pos];
+}
+
+/**
+ * Sets the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_array_grow().
+ */
+tommy_inline void tommy_array_set(tommy_array* array, tommy_count_t pos, void* element)
+{
+	*tommy_array_ref(array, pos) = element;
+}
+
+/**
+ * Gets the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_array_grow().
+ */
+tommy_inline void* tommy_array_get(tommy_array* array, tommy_count_t pos)
+{
+	return *tommy_array_ref(array, pos);
+}
+
+/**
+ * Grows and inserts a new element at the end of the array.
+ */
+tommy_inline void tommy_array_insert(tommy_array* array, void* element)
+{
+	tommy_count_t pos = array->count;
+
+	tommy_array_grow(array, pos + 1);
+
+	tommy_array_set(array, pos, element);
+}
+
+/**
+ * Gets the initialized size of the array.
+ */
+tommy_inline tommy_count_t tommy_array_size(tommy_array* array)
+{
+	return array->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ */
+tommy_size_t tommy_array_memory_usage(tommy_array* array);
+
+#endif
+
diff --git a/third-party/tommyds/tommyarrayblk.c b/third-party/tommyds/tommyarrayblk.c
new file mode 100644
index 0000000..d4dda76
--- /dev/null
+++ b/third-party/tommyds/tommyarrayblk.c
@@ -0,0 +1,82 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyarrayblk.h"
+
+/******************************************************************************/
+/* array */
+
+void tommy_arrayblk_init(tommy_arrayblk* array)
+{
+	tommy_array_init(&array->block);
+
+	array->count = 0;
+}
+
+void tommy_arrayblk_done(tommy_arrayblk* array)
+{
+	tommy_count_t i;
+
+	for (i = 0; i < tommy_array_size(&array->block); ++i)
+		tommy_free(tommy_array_get(&array->block, i));
+
+	tommy_array_done(&array->block);
+}
+
+void tommy_arrayblk_grow(tommy_arrayblk* array, tommy_count_t count)
+{
+	tommy_count_t block_max;
+	tommy_count_t block_mac;
+
+	if (array->count >= count)
+		return;
+	array->count = count;
+
+	block_max = (count + TOMMY_ARRAYBLK_SIZE - 1) / TOMMY_ARRAYBLK_SIZE;
+	block_mac = tommy_array_size(&array->block);
+
+	if (block_mac < block_max) {
+		/* grow the block array */
+		tommy_array_grow(&array->block, block_max);
+
+		/* allocate new blocks */
+		while (block_mac < block_max) {
+			void** ptr = tommy_cast(void**, tommy_calloc(TOMMY_ARRAYBLK_SIZE, sizeof(void*)));
+
+			/* set the new block */
+			tommy_array_set(&array->block, block_mac, ptr);
+
+			++block_mac;
+		}
+	}
+}
+
+tommy_size_t tommy_arrayblk_memory_usage(tommy_arrayblk* array)
+{
+	return tommy_array_memory_usage(&array->block) + tommy_array_size(&array->block) * TOMMY_ARRAYBLK_SIZE * sizeof(void*);
+}
+
diff --git a/third-party/tommyds/tommyarrayblk.h b/third-party/tommyds/tommyarrayblk.h
new file mode 100644
index 0000000..20d0525
--- /dev/null
+++ b/third-party/tommyds/tommyarrayblk.h
@@ -0,0 +1,144 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Dynamic array based on blocks of fixed size.
+ *
+ * This array is able to grow dynamically upon request, without any reallocation.
+ *
+ * The grow operation involves an allocation of a new array block, without reallocating
+ * the already used memory, and then not increasing the heap fragmentation,
+ * and minimize the space occupation.
+ * This also implies that the address of the stored elements never change.
+ *
+ * Allocated blocks are always of the same fixed size of 4 Ki pointers.
+ */
+
+#ifndef __TOMMYARRAYBLK_H
+#define __TOMMYARRAYBLK_H
+
+#include "tommytypes.h"
+#include "tommyarray.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* array */
+
+/**
+ * Elements for each block.
+ */
+#define TOMMY_ARRAYBLK_SIZE (4 * 1024)
+
+/**
+ * Array container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_arrayblk_struct {
+	tommy_array block; /**< Array of blocks. */
+	tommy_count_t count; /**< Number of initialized elements in the array. */
+} tommy_arrayblk;
+
+/**
+ * Initializes the array.
+ */
+void tommy_arrayblk_init(tommy_arrayblk* array);
+
+/**
+ * Deinitializes the array.
+ */
+void tommy_arrayblk_done(tommy_arrayblk* array);
+
+/**
+ * Grows the size up to the specified value.
+ * All the new elements in the array are initialized with the 0 value.
+ */
+void tommy_arrayblk_grow(tommy_arrayblk* array, tommy_count_t size);
+
+/**
+ * Gets a reference of the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_arrayblk_grow().
+ */
+tommy_inline void** tommy_arrayblk_ref(tommy_arrayblk* array, tommy_count_t pos)
+{
+	void** ptr;
+
+	assert(pos < array->count);
+
+	ptr = tommy_cast(void**, tommy_array_get(&array->block, pos / TOMMY_ARRAYBLK_SIZE));
+
+	return &ptr[pos % TOMMY_ARRAYBLK_SIZE];
+}
+
+/**
+ * Sets the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_arrayblk_grow().
+ */
+tommy_inline void tommy_arrayblk_set(tommy_arrayblk* array, tommy_count_t pos, void* element)
+{
+	*tommy_arrayblk_ref(array, pos) = element;
+}
+
+/**
+ * Gets the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_arrayblk_grow().
+ */
+tommy_inline void* tommy_arrayblk_get(tommy_arrayblk* array, tommy_count_t pos)
+{
+	return *tommy_arrayblk_ref(array, pos);
+}
+
+/**
+ * Grows and inserts a new element at the end of the array.
+ */
+tommy_inline void tommy_arrayblk_insert(tommy_arrayblk* array, void* element)
+{
+	tommy_count_t pos = array->count;
+
+	tommy_arrayblk_grow(array, pos + 1);
+
+	tommy_arrayblk_set(array, pos, element);
+}
+
+/**
+ * Gets the initialized size of the array.
+ */
+tommy_inline tommy_count_t tommy_arrayblk_size(tommy_arrayblk* array)
+{
+	return array->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ */
+tommy_size_t tommy_arrayblk_memory_usage(tommy_arrayblk* array);
+
+#endif
+
diff --git a/third-party/tommyds/tommyarrayblkof.c b/third-party/tommyds/tommyarrayblkof.c
new file mode 100644
index 0000000..8a491a0
--- /dev/null
+++ b/third-party/tommyds/tommyarrayblkof.c
@@ -0,0 +1,83 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyarrayblkof.h"
+
+/******************************************************************************/
+/* array */
+
+void tommy_arrayblkof_init(tommy_arrayblkof* array, tommy_size_t element_size)
+{
+	tommy_array_init(&array->block);
+
+	array->element_size = element_size;
+	array->count = 0;
+}
+
+void tommy_arrayblkof_done(tommy_arrayblkof* array)
+{
+	tommy_count_t i;
+
+	for (i = 0; i < tommy_array_size(&array->block); ++i)
+		tommy_free(tommy_array_get(&array->block, i));
+
+	tommy_array_done(&array->block);
+}
+
+void tommy_arrayblkof_grow(tommy_arrayblkof* array, tommy_count_t count)
+{
+	tommy_count_t block_max;
+	tommy_count_t block_mac;
+
+	if (array->count >= count)
+		return;
+	array->count = count;
+
+	block_max = (count + TOMMY_ARRAYBLKOF_SIZE - 1) / TOMMY_ARRAYBLKOF_SIZE;
+	block_mac = tommy_array_size(&array->block);
+
+	if (block_mac < block_max) {
+		/* grow the block array */
+		tommy_array_grow(&array->block, block_max);
+
+		/* allocate new blocks */
+		while (block_mac < block_max) {
+			void** ptr = tommy_cast(void**, tommy_calloc(TOMMY_ARRAYBLKOF_SIZE, array->element_size));
+
+			/* set the new block */
+			tommy_array_set(&array->block, block_mac, ptr);
+
+			++block_mac;
+		}
+	}
+}
+
+tommy_size_t tommy_arrayblkof_memory_usage(tommy_arrayblkof* array)
+{
+	return tommy_array_memory_usage(&array->block) + tommy_array_size(&array->block) * TOMMY_ARRAYBLKOF_SIZE * array->element_size;
+}
+
diff --git a/third-party/tommyds/tommyarrayblkof.h b/third-party/tommyds/tommyarrayblkof.h
new file mode 100644
index 0000000..fce6840
--- /dev/null
+++ b/third-party/tommyds/tommyarrayblkof.h
@@ -0,0 +1,114 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Dynamic array based on blocks of fixed size.
+ *
+ * This array is able to grow dynamically upon request, without any reallocation.
+ *
+ * This is very similar at ::tommy_arrayblk, but it allows to store elements of any
+ * size and not just pointers.
+ *
+ * Note that in this case tommy_arrayblkof_ref() returns a pointer to the element,
+ * that should be used for getting and setting elements in the array,
+ * as generic getter and setter are not available.
+ */
+
+#ifndef __TOMMYARRAYBLKOF_H
+#define __TOMMYARRAYBLKOF_H
+
+#include "tommytypes.h"
+#include "tommyarray.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* array */
+
+/**
+ * Elements for each block.
+ */
+#define TOMMY_ARRAYBLKOF_SIZE (4 * 1024)
+
+/**
+ * Array container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_arrayblkof_struct {
+	tommy_array block; /**< Array of blocks. */
+	tommy_size_t element_size; /**< Size of the stored element in bytes. */
+	tommy_count_t count; /**< Number of initialized elements in the array. */
+} tommy_arrayblkof;
+
+/**
+ * Initializes the array.
+ * \param element_size Size in byte of the element to store in the array.
+ */
+void tommy_arrayblkof_init(tommy_arrayblkof* array, tommy_size_t element_size);
+
+/**
+ * Deinitializes the array.
+ */
+void tommy_arrayblkof_done(tommy_arrayblkof* array);
+
+/**
+ * Grows the size up to the specified value.
+ * All the new elements in the array are initialized with the 0 value.
+ */
+void tommy_arrayblkof_grow(tommy_arrayblkof* array, tommy_count_t size);
+
+/**
+ * Gets a reference of the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_arrayblkof_grow().
+ */
+tommy_inline void* tommy_arrayblkof_ref(tommy_arrayblkof* array, tommy_count_t pos)
+{
+	unsigned char* base;
+
+	assert(pos < array->count);
+
+	base = tommy_cast(unsigned char*, tommy_array_get(&array->block, pos / TOMMY_ARRAYBLKOF_SIZE));
+
+	return base + (pos % TOMMY_ARRAYBLKOF_SIZE) * array->element_size;
+}
+
+/**
+ * Gets the initialized size of the array.
+ */
+tommy_inline tommy_count_t tommy_arrayblkof_size(tommy_arrayblkof* array)
+{
+	return array->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ */
+tommy_size_t tommy_arrayblkof_memory_usage(tommy_arrayblkof* array);
+
+#endif
+
diff --git a/third-party/tommyds/tommyarrayof.c b/third-party/tommyds/tommyarrayof.c
new file mode 100644
index 0000000..80aede7
--- /dev/null
+++ b/third-party/tommyds/tommyarrayof.c
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyarrayof.h"
+
+/******************************************************************************/
+/* array */
+
+void tommy_arrayof_init(tommy_arrayof* array, tommy_size_t element_size)
+{
+	tommy_uint_t i;
+
+	/* fixed initial size */
+	array->element_size = element_size;
+	array->bucket_bit = TOMMY_ARRAYOF_BIT;
+	array->bucket_max = 1 << array->bucket_bit;
+	array->bucket[0] = tommy_calloc(array->bucket_max, array->element_size);
+	for (i = 1; i < TOMMY_ARRAYOF_BIT; ++i)
+		array->bucket[i] = array->bucket[0];
+
+	array->count = 0;
+}
+
+void tommy_arrayof_done(tommy_arrayof* array)
+{
+	tommy_uint_t i;
+
+	tommy_free(array->bucket[0]);
+	for (i = TOMMY_ARRAYOF_BIT; i < array->bucket_bit; ++i) {
+		unsigned char* segment = tommy_cast(unsigned char*, array->bucket[i]);
+		tommy_free(segment + (((tommy_ptrdiff_t)1) << i) * array->element_size);
+	}
+}
+
+void tommy_arrayof_grow(tommy_arrayof* array, tommy_count_t count)
+{
+	if (array->count >= count)
+		return;
+	array->count = count;
+
+	while (count > array->bucket_max) {
+		unsigned char* segment;
+
+		/* allocate one more segment */
+		segment = tommy_cast(unsigned char*, tommy_calloc(array->bucket_max, array->element_size));
+
+		/* store it adjusting the offset */
+		/* cast to ptrdiff_t to ensure to get a negative value */
+		array->bucket[array->bucket_bit] = segment - (tommy_ptrdiff_t)array->bucket_max * array->element_size;
+
+		++array->bucket_bit;
+		array->bucket_max = 1 << array->bucket_bit;
+	}
+}
+
+tommy_size_t tommy_arrayof_memory_usage(tommy_arrayof* array)
+{
+	return array->bucket_max * (tommy_size_t)array->element_size;
+}
+
diff --git a/third-party/tommyds/tommyarrayof.h b/third-party/tommyds/tommyarrayof.h
new file mode 100644
index 0000000..8454838
--- /dev/null
+++ b/third-party/tommyds/tommyarrayof.h
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2013, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Dynamic array based on segments of exponential growing size.
+ *
+ * This array is able to grow dynamically upon request, without any reallocation.
+ *
+ * This is very similar at ::tommy_array, but it allows to store elements of any
+ * size and not just pointers.
+ *
+ * Note that in this case tommy_arrayof_ref() returns a pointer to the element,
+ * that should be used for getting and setting elements in the array,
+ * as generic getter and setter are not available.
+ */
+
+#ifndef __TOMMYARRAYOF_H
+#define __TOMMYARRAYOF_H
+
+#include "tommytypes.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* array */
+
+/**
+ * Initial and minimal size of the array expressed as a power of 2.
+ * The initial size is 2^TOMMY_ARRAYOF_BIT.
+ */
+#define TOMMY_ARRAYOF_BIT 6
+
+/** \internal
+ * Max number of elements as a power of 2.
+ */
+#define TOMMY_ARRAYOF_BIT_MAX 32
+
+/**
+ * Array container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_arrayof_struct {
+	void* bucket[TOMMY_ARRAYOF_BIT_MAX]; /**< Dynamic array of buckets. */
+	tommy_size_t element_size; /**< Size of the stored element in bytes. */
+	tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
+	tommy_count_t bucket_max; /**< Number of buckets. */
+	tommy_count_t count; /**< Number of initialized elements in the array. */
+} tommy_arrayof;
+
+/**
+ * Initializes the array.
+ * \param element_size Size in byte of the element to store in the array.
+ */
+void tommy_arrayof_init(tommy_arrayof* array, tommy_size_t element_size);
+
+/**
+ * Deinitializes the array.
+ */
+void tommy_arrayof_done(tommy_arrayof* array);
+
+/**
+ * Grows the size up to the specified value.
+ * All the new elements in the array are initialized with the 0 value.
+ */
+void tommy_arrayof_grow(tommy_arrayof* array, tommy_count_t size);
+
+/**
+ * Gets a reference of the element at the specified position.
+ * You must be sure that space for this position is already
+ * allocated calling tommy_arrayof_grow().
+ */
+tommy_inline void* tommy_arrayof_ref(tommy_arrayof* array, tommy_count_t pos)
+{
+	unsigned char* ptr;
+	tommy_uint_t bsr;
+
+	assert(pos < array->count);
+
+	/* get the highest bit set, in case of all 0, return 0 */
+	bsr = tommy_ilog2_u32(pos | 1);
+
+	ptr = tommy_cast(unsigned char*, array->bucket[bsr]);
+
+	return ptr + pos * array->element_size;
+}
+
+/**
+ * Gets the initialized size of the array.
+ */
+tommy_inline tommy_count_t tommy_arrayof_size(tommy_arrayof* array)
+{
+	return array->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ */
+tommy_size_t tommy_arrayof_memory_usage(tommy_arrayof* array);
+
+#endif
+
diff --git a/third-party/tommyds/tommychain.h b/third-party/tommyds/tommychain.h
new file mode 100644
index 0000000..b15bc6a
--- /dev/null
+++ b/third-party/tommyds/tommychain.h
@@ -0,0 +1,224 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Chain of nodes.
+ * A chain of nodes is an abstraction used to implements complex list operations
+ * like sorting.
+ *
+ * Do not use this directly. Use lists instead.
+ */
+
+#ifndef __TOMMYCHAIN_H
+#define __TOMMYCHAIN_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* chain */
+
+/**
+ * Chain of nodes.
+ * A chain of nodes is a sequence of nodes with the following properties:
+ * - It contains at least one node. A chains of zero nodes cannot exist.
+ * - The next field of the tail is of *undefined* value.
+ * - The prev field of the head is of *undefined* value.
+ * - All the other inner prev and next fields are correctly set.
+ */
+typedef struct tommy_chain_struct {
+	tommy_node* head; /**< Pointer to the head of the chain. */
+	tommy_node* tail; /**< Pointer to the tail of the chain. */
+} tommy_chain;
+
+/**
+ * Splices a chain in the middle of another chain.
+ */
+tommy_inline void tommy_chain_splice(tommy_node* first_before, tommy_node* first_after, tommy_node* second_head, tommy_node* second_tail)
+{
+	/* set the prev list */
+	first_after->prev = second_tail;
+	second_head->prev = first_before;
+
+	/* set the next list */
+	first_before->next = second_head;
+	second_tail->next = first_after;
+}
+
+/**
+ * Concats two chains.
+ */
+tommy_inline void tommy_chain_concat(tommy_node* first_tail, tommy_node* second_head)
+{
+	/* set the prev list */
+	second_head->prev = first_tail;
+
+	/* set the next list */
+	first_tail->next = second_head;
+}
+
+/**
+ * Merges two chains.
+ */
+tommy_inline void tommy_chain_merge(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
+{
+	tommy_node* first_i = first->head;
+	tommy_node* second_i = second->head;
+
+	/* merge */
+	while (1) {
+		if (cmp(first_i->data, second_i->data) > 0) {
+			tommy_node* next = second_i->next;
+			if (first_i == first->head) {
+				tommy_chain_concat(second_i, first_i);
+				first->head = second_i;
+			} else {
+				tommy_chain_splice(first_i->prev, first_i, second_i, second_i);
+			}
+			if (second_i == second->tail)
+				break;
+			second_i = next;
+		} else {
+			if (first_i == first->tail) {
+				tommy_chain_concat(first_i, second_i);
+				first->tail = second->tail;
+				break;
+			}
+			first_i = first_i->next;
+		}
+	}
+}
+
+/**
+ * Merges two chains managing special degenerated cases.
+ * It's funtionally equivalent at tommy_chain_merge() but faster with already ordered chains.
+ */
+tommy_inline void tommy_chain_merge_degenerated(tommy_chain* first, tommy_chain* second, tommy_compare_func* cmp)
+{
+	/* identify the condition first <= second */
+	if (cmp(first->tail->data, second->head->data) <= 0) {
+		tommy_chain_concat(first->tail, second->head);
+		first->tail = second->tail;
+		return;
+	}
+
+	/* identify the condition second < first */
+	/* here we must be strict on comparison to keep the sort stable */
+	if (cmp(second->tail->data, first->head->data) < 0) {
+		tommy_chain_concat(second->tail, first->head);
+		first->head = second->head;
+		return;
+	}
+
+	tommy_chain_merge(first, second, cmp);
+}
+
+/**
+ * Max number of elements as a power of 2.
+ */
+#define TOMMY_CHAIN_BIT_MAX 32
+
+/**
+ * Sorts a chain.
+ * It's a stable merge sort using power of 2 buckets, with O(N*log(N)) complexity,
+ * similar at the one used in the SGI STL libraries and in the Linux Kernel,
+ * but faster on degenerated cases like already ordered lists.
+ *
+ * SGI STL stl_list.h
+ * http://www.sgi.com/tech/stl/stl_list.h
+ *
+ * Linux Kernel lib/list_sort.c
+ * http://lxr.linux.no/#linux+v2.6.36/lib/list_sort.c
+ */
+tommy_inline void tommy_chain_mergesort(tommy_chain* chain, tommy_compare_func* cmp)
+{
+	/*
+	 * Bit buckets of chains.
+	 * Each bucket contains 2^i nodes or it's empty.
+	 * The chain at address TOMMY_CHAIN_BIT_MAX is an independet variable operating as "carry".
+	 * We keep it in the same "bit" vector to avoid reports from the valgrind tool sgcheck.
+	 */
+	tommy_chain bit[TOMMY_CHAIN_BIT_MAX + 1];
+
+	/**
+	 * Value stored inside the bit bucket.
+	 * It's used to know which bucket is empty of full.
+	 */
+	tommy_count_t counter;
+	tommy_node* node = chain->head;
+	tommy_node* tail = chain->tail;
+	tommy_count_t mask;
+	tommy_count_t i;
+
+	counter = 0;
+	while (1) {
+		tommy_node* next;
+		tommy_chain* last;
+
+		/* carry bit to add */
+		last = &bit[TOMMY_CHAIN_BIT_MAX];
+		bit[TOMMY_CHAIN_BIT_MAX].head = node;
+		bit[TOMMY_CHAIN_BIT_MAX].tail = node;
+		next = node->next;
+
+		/* add the bit, propagating the carry */
+		i = 0;
+		mask = counter;
+		while ((mask & 1) != 0) {
+			tommy_chain_merge_degenerated(&bit[i], last, cmp);
+			mask >>= 1;
+			last = &bit[i];
+			++i;
+		}
+
+		/* copy the carry in the first empty bit */
+		bit[i] = *last;
+
+		/* add the carry in the counter */
+		++counter;
+
+		if (node == tail)
+			break;
+		node = next;
+	}
+
+	/* merge the buckets */
+	i = tommy_ctz_u32(counter);
+	mask = counter >> i;
+	while (mask != 1) {
+		mask >>= 1;
+		if (mask & 1)
+			tommy_chain_merge_degenerated(&bit[i + 1], &bit[i], cmp);
+		else
+			bit[i + 1] = bit[i];
+		++i;
+	}
+
+	*chain = bit[i];
+}
+
+#endif
+
diff --git a/third-party/tommyds/tommyhash.c b/third-party/tommyds/tommyhash.c
new file mode 100644
index 0000000..cc7495d
--- /dev/null
+++ b/third-party/tommyds/tommyhash.c
@@ -0,0 +1,241 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyhash.h"
+
+/******************************************************************************/
+/* hash */
+
+tommy_inline tommy_uint32_t tommy_le_uint32_read(const void* ptr)
+{
+	/* allow unaligned read on Intel x86 and x86_64 platforms */
+#if defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__x86_64__) || defined(_M_X64)
+	/* defines from http://predef.sourceforge.net/ */
+	return *(const tommy_uint32_t*)ptr;
+#else
+	const unsigned char* ptr8 = tommy_cast(const unsigned char*, ptr);
+	return ptr8[0] + ((tommy_uint32_t)ptr8[1] << 8) + ((tommy_uint32_t)ptr8[2] << 16) + ((tommy_uint32_t)ptr8[3] << 24);
+#endif
+}
+
+#define tommy_rot(x, k) \
+	(((x) << (k)) | ((x) >> (32 - (k))))
+
+#define tommy_mix(a, b, c) \
+	do { \
+		a -= c;  a ^= tommy_rot(c, 4);  c += b; \
+		b -= a;  b ^= tommy_rot(a, 6);  a += c; \
+		c -= b;  c ^= tommy_rot(b, 8);  b += a; \
+		a -= c;  a ^= tommy_rot(c, 16);  c += b; \
+		b -= a;  b ^= tommy_rot(a, 19);  a += c; \
+		c -= b;  c ^= tommy_rot(b, 4);  b += a; \
+	} while (0)
+
+#define tommy_final(a, b, c) \
+	do { \
+		c ^= b; c -= tommy_rot(b, 14); \
+		a ^= c; a -= tommy_rot(c, 11); \
+		b ^= a; b -= tommy_rot(a, 25); \
+		c ^= b; c -= tommy_rot(b, 16); \
+		a ^= c; a -= tommy_rot(c, 4);  \
+		b ^= a; b -= tommy_rot(a, 14); \
+		c ^= b; c -= tommy_rot(b, 24); \
+	} while (0)
+
+tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len)
+{
+	const unsigned char* key = tommy_cast(const unsigned char*, void_key);
+	tommy_uint32_t a, b, c;
+
+	a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + init_val;
+
+	while (key_len > 12) {
+		a += tommy_le_uint32_read(key + 0);
+		b += tommy_le_uint32_read(key + 4);
+		c += tommy_le_uint32_read(key + 8);
+
+		tommy_mix(a, b, c);
+
+		key_len -= 12;
+		key += 12;
+	}
+
+	switch (key_len) {
+	case 0 :
+		return c; /* used only when called with a zero length */
+	case 12 :
+		c += tommy_le_uint32_read(key + 8);
+		b += tommy_le_uint32_read(key + 4);
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
+	case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
+	case 9 : c += key[8]; /* fallthrough */
+	case 8 :
+		b += tommy_le_uint32_read(key + 4);
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
+	case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
+	case 5 : b += key[4]; /* fallthrough */
+	case 4 :
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
+	case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
+	case 1 : a += key[0]; /* fallthrough */
+	}
+
+	tommy_final(a, b, c);
+
+	return c;
+}
+
+tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len)
+{
+	const unsigned char* key = tommy_cast(const unsigned char*, void_key);
+	tommy_uint32_t a, b, c;
+
+	a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + (init_val & 0xffffffff);
+	c += init_val >> 32;
+
+	while (key_len > 12) {
+		a += tommy_le_uint32_read(key + 0);
+		b += tommy_le_uint32_read(key + 4);
+		c += tommy_le_uint32_read(key + 8);
+
+		tommy_mix(a, b, c);
+
+		key_len -= 12;
+		key += 12;
+	}
+
+	switch (key_len) {
+	case 0 :
+		return c + ((tommy_uint64_t)b << 32); /* used only when called with a zero length */
+	case 12 :
+		c += tommy_le_uint32_read(key + 8);
+		b += tommy_le_uint32_read(key + 4);
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
+	case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
+	case 9 : c += key[8]; /* fallthrough */
+	case 8 :
+		b += tommy_le_uint32_read(key + 4);
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
+	case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
+	case 5 : b += key[4]; /* fallthrough */
+	case 4 :
+		a += tommy_le_uint32_read(key + 0);
+		break;
+	case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
+	case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
+	case 1 : a += key[0]; /* fallthrough */
+	}
+
+	tommy_final(a, b, c);
+
+	return c + ((tommy_uint64_t)b << 32);
+}
+
+tommy_uint32_t tommy_strhash_u32(tommy_uint64_t init_val, const void* void_key)
+{
+	const unsigned char* key = tommy_cast(const unsigned char*, void_key);
+	tommy_uint32_t a, b, c;
+	tommy_uint32_t m[3] = { 0xff, 0xff00, 0xff0000 };
+
+	a = b = c = 0xdeadbeef + init_val;
+	/* this is different than original lookup3 and the result won't match */
+
+	while (1) {
+		tommy_uint32_t v = tommy_le_uint32_read(key);
+
+		if (tommy_haszero_u32(v)) {
+			if (v & m[0]) {
+				a += v & m[0];
+				if (v & m[1]) {
+					a += v & m[1];
+					if (v & m[2])
+						a += v & m[2];
+				}
+			}
+
+			break;
+		}
+
+		a += v;
+
+		v = tommy_le_uint32_read(key + 4);
+
+		if (tommy_haszero_u32(v)) {
+			if (v & m[0]) {
+				b += v & m[0];
+				if (v & m[1]) {
+					b += v & m[1];
+					if (v & m[2])
+						b += v & m[2];
+				}
+			}
+
+			break;
+		}
+
+		b += v;
+
+		v = tommy_le_uint32_read(key + 8);
+
+		if (tommy_haszero_u32(v)) {
+			if (v & m[0]) {
+				c += v & m[0];
+				if (v & m[1]) {
+					c += v & m[1];
+					if (v & m[2])
+						c += v & m[2];
+				}
+			}
+
+			break;
+		}
+
+		c += v;
+
+		tommy_mix(a, b, c);
+
+		key += 12;
+	}
+
+	/* for lengths that are multiplers of 12 we already have called mix */
+	/* this is different than the original lookup3 and the result won't match */
+
+	tommy_final(a, b, c);
+
+	return c;
+}
+
diff --git a/third-party/tommyds/tommyhash.h b/third-party/tommyds/tommyhash.h
new file mode 100644
index 0000000..738e33d
--- /dev/null
+++ b/third-party/tommyds/tommyhash.h
@@ -0,0 +1,140 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Hash functions for the use with ::tommy_hashtable, ::tommy_hashdyn and ::tommy_hashlin.
+ */
+
+#ifndef __TOMMYHASH_H
+#define __TOMMYHASH_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* hash */
+
+/**
+ * Hash type used in hashtables.
+ */
+typedef tommy_key_t tommy_hash_t;
+
+/**
+ * Hash function with a 32 bits result.
+ * Implementation of the Robert Jenkins "lookup3" hash 32 bits version,
+ * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
+ *
+ * This hash is designed to provide a good overall performance in all platforms,
+ * including 32 bits. If you target only 64 bits, you can use faster hashes,
+ * like SpookyHash or FarmHash.
+ *
+ * \param init_val Initialization value.
+ * Using a different initialization value, you can generate a completely different set of hash values.
+ * Use 0 if not relevant.
+ * \param void_key Pointer to the data to hash.
+ * \param key_len Size of the data to hash.
+ * \note
+ * This function is endianess independent.
+ * \return The hash value of 32 bits.
+ */
+tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len);
+
+/**
+ * Hash function with a 64 bits result.
+ * Implementation of the Robert Jenkins "lookup3" hash 64 bits versions,
+ * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle2().
+ *
+ * This hash is designed to provide a good overall performance in all platforms,
+ * including 32 bits. If you target only 64 bits, you can use faster hashes,
+ * like SpookyHash or FarmHash.
+ *
+ * \param init_val Initialization value.
+ * Using a different initialization value, you can generate a completely different set of hash values.
+ * Use 0 if not relevant.
+ * \param void_key Pointer to the data to hash.
+ * \param key_len Size of the data to hash.
+ * \note
+ * This function is endianess independent.
+ * \return The hash value of 64 bits.
+ */
+tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len);
+
+/**
+ * String hash function with a 32 bits result.
+ * Implementation is based on the the Robert Jenkins "lookup3" hash 32 bits version,
+ * from http://www.burtleburtle.net/bob/hash/doobs.html, function hashlittle().
+ *
+ * This hash is designed to handle strings with an unknown length. If you
+ * know the string length, the other hash functions are surely faster.
+ *
+ * \param init_val Initialization value.
+ * Using a different initialization value, you can generate a completely different set of hash values.
+ * Use 0 if not relevant.
+ * \param void_key Pointer to the string to hash. It has to be 0 terminated.
+ * \note
+ * This function is endianess independent.
+ * \return The hash value of 32 bits.
+ */
+tommy_uint32_t tommy_strhash_u32(tommy_uint64_t init_val, const void* void_key);
+
+/**
+ * Integer reversible hash function for 32 bits.
+ * Implementation of the Robert Jenkins "4-byte Integer Hashing",
+ * from http://burtleburtle.net/bob/hash/integer.html
+ */
+tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
+{
+	key -= key << 6;
+	key ^= key >> 17;
+	key -= key << 9;
+	key ^= key << 4;
+	key -= key << 3;
+	key ^= key << 10;
+	key ^= key >> 15;
+
+	return key;
+}
+
+/**
+ * Integer reversible hash function for 64 bits.
+ * Implementation of the Thomas Wang "Integer Hash Function",
+ * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
+ */
+tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
+{
+	key = ~key + (key << 21);
+	key = key ^ (key >> 24);
+	key = key + (key << 3) + (key << 8);
+	key = key ^ (key >> 14);
+	key = key + (key << 2) + (key << 4);
+	key = key ^ (key >> 28);
+	key = key + (key << 31);
+
+	return key;
+}
+
+#endif
+
diff --git a/third-party/tommyds/tommyhashdyn.c b/third-party/tommyds/tommyhashdyn.c
new file mode 100644
index 0000000..02ef404
--- /dev/null
+++ b/third-party/tommyds/tommyhashdyn.c
@@ -0,0 +1,224 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyhashdyn.h"
+#include "tommylist.h"
+
+/******************************************************************************/
+/* hashdyn */
+
+void tommy_hashdyn_init(tommy_hashdyn* hashdyn)
+{
+	/* fixed initial size */
+	hashdyn->bucket_bit = TOMMY_HASHDYN_BIT;
+	hashdyn->bucket_max = 1 << hashdyn->bucket_bit;
+	hashdyn->bucket_mask = hashdyn->bucket_max - 1;
+	hashdyn->bucket = tommy_cast(tommy_hashdyn_node**, tommy_calloc(hashdyn->bucket_max, sizeof(tommy_hashdyn_node*)));
+
+	hashdyn->count = 0;
+}
+
+void tommy_hashdyn_done(tommy_hashdyn* hashdyn)
+{
+	tommy_free(hashdyn->bucket);
+}
+
+/**
+ * Resize the bucket vector.
+ */
+static void tommy_hashdyn_resize(tommy_hashdyn* hashdyn, tommy_count_t new_bucket_bit)
+{
+	tommy_count_t bucket_bit;
+	tommy_count_t bucket_max;
+	tommy_count_t new_bucket_max;
+	tommy_count_t new_bucket_mask;
+	tommy_hashdyn_node** new_bucket;
+
+	bucket_bit = hashdyn->bucket_bit;
+	bucket_max = hashdyn->bucket_max;
+
+	new_bucket_max = 1 << new_bucket_bit;
+	new_bucket_mask = new_bucket_max - 1;
+
+	/* allocate the new vector using malloc() and not calloc() */
+	/* because data is fully initialized in the update process */
+	new_bucket = tommy_cast(tommy_hashdyn_node**, tommy_malloc(new_bucket_max * sizeof(tommy_hashdyn_node*)));
+
+	/* reinsert all the elements */
+	if (new_bucket_bit > bucket_bit) {
+		tommy_count_t i;
+
+		/* grow */
+		for (i = 0; i < bucket_max; ++i) {
+			tommy_hashdyn_node* j;
+
+			/* setup the new two buckets */
+			new_bucket[i] = 0;
+			new_bucket[i + bucket_max] = 0;
+
+			/* reinsert the bucket */
+			j = hashdyn->bucket[i];
+			while (j) {
+				tommy_hashdyn_node* j_next = j->next;
+				tommy_count_t pos = j->key & new_bucket_mask;
+				if (new_bucket[pos])
+					tommy_list_insert_tail_not_empty(new_bucket[pos], j);
+				else
+					tommy_list_insert_first(&new_bucket[pos], j);
+				j = j_next;
+			}
+		}
+	} else {
+		tommy_count_t i;
+
+		/* shrink */
+		for (i = 0; i < new_bucket_max; ++i) {
+			/* setup the new bucket with the lower bucket*/
+			new_bucket[i] = hashdyn->bucket[i];
+
+			/* concat the upper bucket */
+			tommy_list_concat(&new_bucket[i], &hashdyn->bucket[i + new_bucket_max]);
+		}
+	}
+
+	tommy_free(hashdyn->bucket);
+
+	/* setup */
+	hashdyn->bucket_bit = new_bucket_bit;
+	hashdyn->bucket_max = new_bucket_max;
+	hashdyn->bucket_mask = new_bucket_mask;
+	hashdyn->bucket = new_bucket;
+}
+
+/**
+ * Grow.
+ */
+tommy_inline void hashdyn_grow_step(tommy_hashdyn* hashdyn)
+{
+	/* grow if more than 50% full */
+	if (hashdyn->count >= hashdyn->bucket_max / 2)
+		tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit + 1);
+}
+
+/**
+ * Shrink.
+ */
+tommy_inline void hashdyn_shrink_step(tommy_hashdyn* hashdyn)
+{
+	/* shrink if less than 12.5% full */
+	if (hashdyn->count <= hashdyn->bucket_max / 8 && hashdyn->bucket_bit > TOMMY_HASHDYN_BIT)
+		tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit - 1);
+}
+
+void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash)
+{
+	tommy_count_t pos = hash & hashdyn->bucket_mask;
+
+	tommy_list_insert_tail(&hashdyn->bucket[pos], node, data);
+
+	node->key = hash;
+
+	++hashdyn->count;
+
+	hashdyn_grow_step(hashdyn);
+}
+
+void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node)
+{
+	tommy_count_t pos = node->key & hashdyn->bucket_mask;
+
+	tommy_list_remove_existing(&hashdyn->bucket[pos], node);
+
+	--hashdyn->count;
+
+	hashdyn_shrink_step(hashdyn);
+
+	return node->data;
+}
+
+void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_count_t pos = hash & hashdyn->bucket_mask;
+	tommy_hashdyn_node* node = hashdyn->bucket[pos];
+
+	while (node) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (node->key == hash && cmp(cmp_arg, node->data) == 0) {
+			tommy_list_remove_existing(&hashdyn->bucket[pos], node);
+
+			--hashdyn->count;
+
+			hashdyn_shrink_step(hashdyn);
+
+			return node->data;
+		}
+		node = node->next;
+	}
+
+	return 0;
+}
+
+void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func)
+{
+	tommy_count_t bucket_max = hashdyn->bucket_max;
+	tommy_hashdyn_node** bucket = hashdyn->bucket;
+	tommy_count_t pos;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashdyn_node* node = bucket[pos];
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(data);
+		}
+	}
+}
+
+void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_count_t bucket_max = hashdyn->bucket_max;
+	tommy_hashdyn_node** bucket = hashdyn->bucket;
+	tommy_count_t pos;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashdyn_node* node = bucket[pos];
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(arg, data);
+		}
+	}
+}
+
+tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn)
+{
+	return hashdyn->bucket_max * (tommy_size_t)sizeof(hashdyn->bucket[0])
+	       + tommy_hashdyn_count(hashdyn) * (tommy_size_t)sizeof(tommy_hashdyn_node);
+}
+
diff --git a/third-party/tommyds/tommyhashdyn.h b/third-party/tommyds/tommyhashdyn.h
new file mode 100644
index 0000000..ed4a607
--- /dev/null
+++ b/third-party/tommyds/tommyhashdyn.h
@@ -0,0 +1,296 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Dynamic chained hashtable.
+ *
+ * This hashtable resizes dynamically. It starts with the minimal size of 16 buckets, it doubles
+ * the size then it reaches a load factor greater than 0.5 and it halves the size with a load
+ * factor lower than 0.125.
+ *
+ * All the elements are reallocated in a single resize operation done inside
+ * tommy_hashdyn_insert() or tommy_hashdyn_remove().
+ *
+ * Note that the resize operation takes approximatively 100 [ms] with 1 million of elements,
+ * and 1 [second] with 10 millions. This could be a problem in real-time applications.
+ *
+ * The resize also fragment the heap, as it involves allocating a double-sized table, copy elements,
+ * and deallocating the older table. Leaving a big hole in the heap.
+ *
+ * The ::tommy_hashlin hashtable fixes both problems.
+ *
+ * To initialize the hashtable you have to call tommy_hashdyn_init().
+ *
+ * \code
+ * tommy_hashslin hashdyn;
+ *
+ * tommy_hashdyn_init(&hashdyn);
+ * \endcode
+ *
+ * To insert elements in the hashtable you have to call tommy_hashdyn_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node, the
+ * address of the object, and the hash value of the key to use.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node, and the hash to initialize the tommy_node::key field.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
+ * \endcode
+ *
+ * To find and element in the hashtable you have to call tommy_hashtable_search()
+ * providing a comparison function, its argument, and the hash of the key to search.
+ *
+ * \code
+ * int compare(const void* arg, const void* obj)
+ * {
+ *     return *(const int*)arg != ((const struct object*)obj)->value;
+ * }
+ *
+ * int value_to_find = 1;
+ * struct object* obj = tommy_hashdyn_search(&hashdyn, compare, &value_to_find, tommy_inthash_u32(value_to_find));
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To iterate over all the elements in the hashtable with the same key, you have to
+ * use tommy_hashdyn_bucket() and follow the tommy_node::next pointer until NULL.
+ * You have also to check explicitely for the key, as the bucket may contains
+ * different keys.
+ *
+ * \code
+ * int value_to_find = 1;
+ * tommy_node* i = tommy_hashdyn_bucket(&hashdyn, tommy_inthash_u32(value_to_find));
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     if (obj->value == value_to_find) {
+ *         printf("%d\n", obj->value); // process the object
+ *     }
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an element from the hashtable you have to call tommy_hashdyn_remove()
+ * providing a comparison function, its argument, and the hash of the key to search
+ * and remove.
+ *
+ * \code
+ * struct object* obj = tommy_hashdyn_remove(&hashdyn, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the hashtable you have to remove all the elements, and deinitialize
+ * the hashtable calling tommy_hashdyn_done().
+ *
+ * \code
+ * tommy_hashdyn_done(&hashdyn);
+ * \endcode
+ *
+ * If you need to iterate over all the elements in the hashtable, you can use
+ * tommy_hashdyn_foreach() or tommy_hashdyn_foreach_arg().
+ * If you need a more precise control with a real iteration, you have to insert
+ * all the elements also in a ::tommy_list, and use the list to iterate.
+ * See the \ref multiindex example for more detail.
+ */
+
+#ifndef __TOMMYHASHDYN_H
+#define __TOMMYHASHDYN_H
+
+#include "tommyhash.h"
+
+/******************************************************************************/
+/* hashdyn */
+
+/** \internal
+ * Initial and minimal size of the hashtable expressed as a power of 2.
+ * The initial size is 2^TOMMY_HASHDYN_BIT.
+ */
+#define TOMMY_HASHDYN_BIT 4
+
+/**
+ * Hashtable node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef tommy_node tommy_hashdyn_node;
+
+/**
+ * Hashtable container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_hashdyn_struct {
+	tommy_hashdyn_node** bucket; /**< Hash buckets. One list for each hash modulus. */
+	tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
+	tommy_count_t bucket_max; /**< Number of buckets. */
+	tommy_count_t bucket_mask; /**< Bit mask to access the buckets. */
+	tommy_count_t count; /**< Number of elements. */
+} tommy_hashdyn;
+
+/**
+ * Initializes the hashtable.
+ */
+void tommy_hashdyn_init(tommy_hashdyn* hashdyn);
+
+/**
+ * Deinitializes the hashtable.
+ *
+ * You can call this function with elements still contained,
+ * but such elements are not going to be freed by this call.
+ */
+void tommy_hashdyn_done(tommy_hashdyn* hashdyn);
+
+/**
+ * Inserts an element in the hashtable.
+ */
+void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash);
+
+/**
+ * Searches and removes an element from the hashtable.
+ * You have to provide a compare function and the hash of the element you want to remove.
+ * If the element is not found, 0 is returned.
+ * If more equal elements are present, the first one is removed.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find and remove.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
+
+/**
+ * Gets the bucket of the specified hash.
+ * The bucket is guaranteed to contain ALL the elements with the specified hash,
+ * but it can contain also others.
+ * You can access elements in the bucket following the ::next pointer until 0.
+ * \param hash Hash of the element to find.
+ * \return The head of the bucket, or 0 if empty.
+ */
+tommy_inline tommy_hashdyn_node* tommy_hashdyn_bucket(tommy_hashdyn* hashdyn, tommy_hash_t hash)
+{
+	return hashdyn->bucket[hash & hashdyn->bucket_mask];
+}
+
+/**
+ * Searches an element in the hashtable.
+ * You have to provide a compare function and the hash of the element you want to find.
+ * If more equal elements are present, the first one is returned.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find.
+ * \return The first element found, or 0 if none.
+ */
+tommy_inline void* tommy_hashdyn_search(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_hashdyn_node* i = tommy_hashdyn_bucket(hashdyn, hash);
+
+	while (i) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (i->key == hash && cmp(cmp_arg, i->data) == 0)
+			return i->data;
+		i = i->next;
+	}
+	return 0;
+}
+
+/**
+ * Removes an element from the hashtable.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node);
+
+/**
+ * Calls the specified function for each element in the hashtable.
+ *
+ * You cannot add or remove elements from the inside of the callback,
+ * but can use it to deallocate them.
+ *
+ * \code
+ * tommy_hashdyn hashdyn;
+ *
+ * // initializes the hashtable
+ * tommy_hashdyn_init(&hashdyn);
+ *
+ * ...
+ *
+ * // creates an object
+ * struct object* obj = malloc(sizeof(struct object));
+ *
+ * ...
+ *
+ * // insert it in the hashtable
+ * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value));
+ *
+ * ...
+ *
+ * // deallocates all the objects iterating the hashtable
+ * tommy_hashdyn_foreach(&hashdyn, free);
+ *
+ * // deallocates the hashtable
+ * tommy_hashdyn_done(&hashdyn);
+ * \endcode
+ */
+void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func);
+
+/**
+ * Calls the specified function with an argument for each element in the hashtable.
+ */
+void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_hashdyn_count(tommy_hashdyn* hashdyn)
+{
+	return hashdyn->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_hashdyn_node of the stored elements.
+ */
+tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn);
+
+#endif
+
diff --git a/third-party/tommyds/tommyhashlin.c b/third-party/tommyds/tommyhashlin.c
new file mode 100644
index 0000000..bcf7d98
--- /dev/null
+++ b/third-party/tommyds/tommyhashlin.c
@@ -0,0 +1,334 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyhashlin.h"
+#include "tommylist.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* hashlin */
+
+/**
+ * Reallocation states.
+ */
+#define TOMMY_HASHLIN_STATE_STABLE 0
+#define TOMMY_HASHLIN_STATE_GROW 1
+#define TOMMY_HASHLIN_STATE_SHRINK 2
+
+/**
+ * Set the hashtable in stable state.
+ */
+tommy_inline void tommy_hashlin_stable(tommy_hashlin* hashlin)
+{
+	hashlin->state = TOMMY_HASHLIN_STATE_STABLE;
+
+	/* setup low_mask/max/split to allow tommy_hashlin_bucket_ref() */
+	/* and tommy_hashlin_foreach() to work regardless we are in stable state */
+	hashlin->low_max = hashlin->bucket_max;
+	hashlin->low_mask = hashlin->bucket_mask;
+	hashlin->split = 0;
+}
+
+void tommy_hashlin_init(tommy_hashlin* hashlin)
+{
+	tommy_uint_t i;
+
+	/* fixed initial size */
+	hashlin->bucket_bit = TOMMY_HASHLIN_BIT;
+	hashlin->bucket_max = 1 << hashlin->bucket_bit;
+	hashlin->bucket_mask = hashlin->bucket_max - 1;
+	hashlin->bucket[0] = tommy_cast(tommy_hashlin_node**, tommy_calloc(hashlin->bucket_max, sizeof(tommy_hashlin_node*)));
+	for (i = 1; i < TOMMY_HASHLIN_BIT; ++i)
+		hashlin->bucket[i] = hashlin->bucket[0];
+
+	/* stable state */
+	tommy_hashlin_stable(hashlin);
+
+	hashlin->count = 0;
+}
+
+void tommy_hashlin_done(tommy_hashlin* hashlin)
+{
+	tommy_uint_t i;
+
+	tommy_free(hashlin->bucket[0]);
+	for (i = TOMMY_HASHLIN_BIT; i < hashlin->bucket_bit; ++i) {
+		tommy_hashlin_node** segment = hashlin->bucket[i];
+		tommy_free(&segment[((tommy_ptrdiff_t)1) << i]);
+	}
+}
+
+/**
+ * Grow one step.
+ */
+tommy_inline void hashlin_grow_step(tommy_hashlin* hashlin)
+{
+	/* grow if more than 50% full */
+	if (hashlin->state != TOMMY_HASHLIN_STATE_GROW
+		&& hashlin->count > hashlin->bucket_max / 2
+	) {
+		/* if we are stable, setup a new grow state */
+		/* otherwise continue with the already setup shrink one */
+		/* but in backward direction */
+		if (hashlin->state == TOMMY_HASHLIN_STATE_STABLE) {
+			tommy_hashlin_node** segment;
+
+			/* set the lower size */
+			hashlin->low_max = hashlin->bucket_max;
+			hashlin->low_mask = hashlin->bucket_mask;
+
+			/* allocate the new vector using malloc() and not calloc() */
+			/* because data is fully initialized in the split process */
+			segment = tommy_cast(tommy_hashlin_node**, tommy_malloc(hashlin->low_max * sizeof(tommy_hashlin_node*)));
+
+			/* store it adjusting the offset */
+			/* cast to ptrdiff_t to ensure to get a negative value */
+			hashlin->bucket[hashlin->bucket_bit] = &segment[-(tommy_ptrdiff_t)hashlin->low_max];
+
+			/* grow the hash size */
+			++hashlin->bucket_bit;
+			hashlin->bucket_max = 1 << hashlin->bucket_bit;
+			hashlin->bucket_mask = hashlin->bucket_max - 1;
+
+			/* start from the beginning going forward */
+			hashlin->split = 0;
+		}
+
+		/* grow state */
+		hashlin->state = TOMMY_HASHLIN_STATE_GROW;
+	}
+
+	/* if we are growing */
+	if (hashlin->state == TOMMY_HASHLIN_STATE_GROW) {
+		/* compute the split target required to finish the reallocation before the next resize */
+		tommy_count_t split_target = 2 * hashlin->count;
+
+		/* reallocate buckets until the split target */
+		while (hashlin->split + hashlin->low_max < split_target) {
+			tommy_hashlin_node** split[2];
+			tommy_hashlin_node* j;
+			tommy_count_t mask;
+
+			/* get the low bucket */
+			split[0] = tommy_hashlin_pos(hashlin, hashlin->split);
+
+			/* get the high bucket */
+			split[1] = tommy_hashlin_pos(hashlin, hashlin->split + hashlin->low_max);
+
+			/* save the low bucket */
+			j = *split[0];
+
+			/* reinitialize the buckets */
+			*split[0] = 0;
+			*split[1] = 0;
+
+			/* the bit used to identify the bucket */
+			mask = hashlin->low_max;
+
+			/* flush the bucket */
+			while (j) {
+				tommy_hashlin_node* j_next = j->next;
+				tommy_count_t pos = (j->key & mask) != 0;
+				if (*split[pos])
+					tommy_list_insert_tail_not_empty(*split[pos], j);
+				else
+					tommy_list_insert_first(split[pos], j);
+				j = j_next;
+			}
+
+			/* go forward */
+			++hashlin->split;
+
+			/* if we have finished, change the state */
+			if (hashlin->split == hashlin->low_max) {
+				/* go in stable mode */
+				tommy_hashlin_stable(hashlin);
+				break;
+			}
+		}
+	}
+}
+
+/**
+ * Shrink one step.
+ */
+tommy_inline void hashlin_shrink_step(tommy_hashlin* hashlin)
+{
+	/* shrink if less than 12.5% full */
+	if (hashlin->state != TOMMY_HASHLIN_STATE_SHRINK
+		&& hashlin->count < hashlin->bucket_max / 8
+	) {
+		/* avoid to shrink the first bucket */
+		if (hashlin->bucket_bit > TOMMY_HASHLIN_BIT) {
+			/* if we are stable, setup a new shrink state */
+			/* otherwise continue with the already setup grow one */
+			/* but in backward direction */
+			if (hashlin->state == TOMMY_HASHLIN_STATE_STABLE) {
+				/* set the lower size */
+				hashlin->low_max = hashlin->bucket_max / 2;
+				hashlin->low_mask = hashlin->bucket_mask / 2;
+
+				/* start from the half going backward */
+				hashlin->split = hashlin->low_max;
+			}
+
+			/* start reallocation */
+			hashlin->state = TOMMY_HASHLIN_STATE_SHRINK;
+		}
+	}
+
+	/* if we are shrinking */
+	if (hashlin->state == TOMMY_HASHLIN_STATE_SHRINK) {
+		/* compute the split target required to finish the reallocation before the next resize */
+		tommy_count_t split_target = 8 * hashlin->count;
+
+		/* reallocate buckets until the split target */
+		while (hashlin->split + hashlin->low_max > split_target) {
+			tommy_hashlin_node** split[2];
+
+			/* go backward position */
+			--hashlin->split;
+
+			/* get the low bucket */
+			split[0] = tommy_hashlin_pos(hashlin, hashlin->split);
+
+			/* get the high bucket */
+			split[1] = tommy_hashlin_pos(hashlin, hashlin->split + hashlin->low_max);
+
+			/* concat the high bucket into the low one */
+			tommy_list_concat(split[0], split[1]);
+
+			/* if we have finished, clean up and change the state */
+			if (hashlin->split == 0) {
+				tommy_hashlin_node** segment;
+
+				/* shrink the hash size */
+				--hashlin->bucket_bit;
+				hashlin->bucket_max = 1 << hashlin->bucket_bit;
+				hashlin->bucket_mask = hashlin->bucket_max - 1;
+
+				/* free the last segment */
+				segment = hashlin->bucket[hashlin->bucket_bit];
+				tommy_free(&segment[((tommy_ptrdiff_t)1) << hashlin->bucket_bit]);
+
+				/* go in stable mode */
+				tommy_hashlin_stable(hashlin);
+				break;
+			}
+		}
+	}
+}
+
+void tommy_hashlin_insert(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_hash_t hash)
+{
+	tommy_list_insert_tail(tommy_hashlin_bucket_ref(hashlin, hash), node, data);
+
+	node->key = hash;
+
+	++hashlin->count;
+
+	hashlin_grow_step(hashlin);
+}
+
+void* tommy_hashlin_remove_existing(tommy_hashlin* hashlin, tommy_hashlin_node* node)
+{
+	tommy_list_remove_existing(tommy_hashlin_bucket_ref(hashlin, node->key), node);
+
+	--hashlin->count;
+
+	hashlin_shrink_step(hashlin);
+
+	return node->data;
+}
+
+void* tommy_hashlin_remove(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_hashlin_node** let_ptr = tommy_hashlin_bucket_ref(hashlin, hash);
+	tommy_hashlin_node* node = *let_ptr;
+
+	while (node) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (node->key == hash && cmp(cmp_arg, node->data) == 0) {
+			tommy_list_remove_existing(let_ptr, node);
+
+			--hashlin->count;
+
+			hashlin_shrink_step(hashlin);
+
+			return node->data;
+		}
+		node = node->next;
+	}
+
+	return 0;
+}
+
+void tommy_hashlin_foreach(tommy_hashlin* hashlin, tommy_foreach_func* func)
+{
+	tommy_count_t bucket_max;
+	tommy_count_t pos;
+
+	/* number of valid buckets */
+	bucket_max = hashlin->low_max + hashlin->split;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashlin_node* node = *tommy_hashlin_pos(hashlin, pos);
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(data);
+		}
+	}
+}
+
+void tommy_hashlin_foreach_arg(tommy_hashlin* hashlin, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_count_t bucket_max;
+	tommy_count_t pos;
+
+	/* number of valid buckets */
+	bucket_max = hashlin->low_max + hashlin->split;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashlin_node* node = *tommy_hashlin_pos(hashlin, pos);
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(arg, data);
+		}
+	}
+}
+
+tommy_size_t tommy_hashlin_memory_usage(tommy_hashlin* hashlin)
+{
+	return hashlin->bucket_max * (tommy_size_t)sizeof(hashlin->bucket[0][0])
+	       + hashlin->count * (tommy_size_t)sizeof(tommy_hashlin_node);
+}
+
diff --git a/third-party/tommyds/tommyhashlin.h b/third-party/tommyds/tommyhashlin.h
new file mode 100644
index 0000000..eaf59e6
--- /dev/null
+++ b/third-party/tommyds/tommyhashlin.h
@@ -0,0 +1,350 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Linear chained hashtable.
+ *
+ * This hashtable resizes dynamically and progressively using a variation of the
+ * linear hashing algorithm described in http://en.wikipedia.org/wiki/Linear_hashing
+ *
+ * It starts with the minimal size of 16 buckets, it doubles the size then it
+ * reaches a load factor greater than 0.5 and it halves the size with a load
+ * factor lower than 0.125.
+ *
+ * The progressive resize is good for real-time and interactive applications
+ * as it makes insert and delete operations taking always the same time.
+ *
+ * For resizing it's used a dynamic array that supports access to not contigous
+ * segments.
+ * In this way we only allocate additional table segments on the heap, without
+ * freeing the previous table, and then not increasing the heap fragmentation.
+ *
+ * The resize takes place inside tommy_hashlin_insert() and tommy_hashlin_remove().
+ * No resize is done in the tommy_hashlin_search() operation.
+ *
+ * To initialize the hashtable you have to call tommy_hashlin_init().
+ *
+ * \code
+ * tommy_hashslin hashlin;
+ *
+ * tommy_hashlin_init(&hashlin);
+ * \endcode
+ *
+ * To insert elements in the hashtable you have to call tommy_hashlin_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node, the
+ * address of the object, and the hash value of the key to use.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node, and the hash to initialize the tommy_node::key field.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_hashlin_insert(&hashlin, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
+ * \endcode
+ *
+ * To find and element in the hashtable you have to call tommy_hashtable_search()
+ * providing a comparison function, its argument, and the hash of the key to search.
+ *
+ * \code
+ * int compare(const void* arg, const void* obj)
+ * {
+ *     return *(const int*)arg != ((const struct object*)obj)->value;
+ * }
+ *
+ * int value_to_find = 1;
+ * struct object* obj = tommy_hashlin_search(&hashlin, compare, &value_to_find, tommy_inthash_u32(value_to_find));
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To iterate over all the elements in the hashtable with the same key, you have to
+ * use tommy_hashlin_bucket() and follow the tommy_node::next pointer until NULL.
+ * You have also to check explicitely for the key, as the bucket may contains
+ * different keys.
+ *
+ * \code
+ * int value_to_find = 1;
+ * tommy_node* i = tommy_hashlin_bucket(&hashlin, tommy_inthash_u32(value_to_find));
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     if (obj->value == value_to_find) {
+ *         printf("%d\n", obj->value); // process the object
+ *     }
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an element from the hashtable you have to call tommy_hashlin_remove()
+ * providing a comparison function, its argument, and the hash of the key to search
+ * and remove.
+ *
+ * \code
+ * struct object* obj = tommy_hashlin_remove(&hashlin, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the hashtable you have to remove all the elements, and deinitialize
+ * the hashtable calling tommy_hashlin_done().
+ *
+ * \code
+ * tommy_hashlin_done(&hashlin);
+ * \endcode
+ *
+ * If you need to iterate over all the elements in the hashtable, you can use
+ * tommy_hashlin_foreach() or tommy_hashlin_foreach_arg().
+ * If you need a more precise control with a real iteration, you have to insert
+ * all the elements also in a ::tommy_list, and use the list to iterate.
+ * See the \ref multiindex example for more detail.
+ */
+
+#ifndef __TOMMYHASHLIN_H
+#define __TOMMYHASHLIN_H
+
+#include "tommyhash.h"
+
+/******************************************************************************/
+/* hashlin */
+
+/** \internal
+ * Initial and minimal size of the hashtable expressed as a power of 2.
+ * The initial size is 2^TOMMY_HASHLIN_BIT.
+ */
+#define TOMMY_HASHLIN_BIT 6
+
+/**
+ * Hashtable node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef tommy_node tommy_hashlin_node;
+
+/** \internal
+ * Max number of elements as a power of 2.
+ */
+#define TOMMY_HASHLIN_BIT_MAX 32
+
+/**
+ * Hashtable container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_hashlin_struct {
+	tommy_hashlin_node** bucket[TOMMY_HASHLIN_BIT_MAX]; /**< Dynamic array of hash buckets. One list for each hash modulus. */
+	tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
+	tommy_count_t bucket_max; /**< Number of buckets. */
+	tommy_count_t bucket_mask; /**< Bit mask to access the buckets. */
+	tommy_count_t low_max; /**< Low order max value. */
+	tommy_count_t low_mask; /**< Low order mask value. */
+	tommy_count_t split; /**< Split position. */
+	tommy_count_t count; /**< Number of elements. */
+	tommy_uint_t state; /**< Reallocation state. */
+} tommy_hashlin;
+
+/**
+ * Initializes the hashtable.
+ */
+void tommy_hashlin_init(tommy_hashlin* hashlin);
+
+/**
+ * Deinitializes the hashtable.
+ *
+ * You can call this function with elements still contained,
+ * but such elements are not going to be freed by this call.
+ */
+void tommy_hashlin_done(tommy_hashlin* hashlin);
+
+/**
+ * Inserts an element in the hashtable.
+ */
+void tommy_hashlin_insert(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_hash_t hash);
+
+/**
+ * Searches and removes an element from the hashtable.
+ * You have to provide a compare function and the hash of the element you want to remove.
+ * If the element is not found, 0 is returned.
+ * If more equal elements are present, the first one is removed.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find and remove.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_hashlin_remove(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
+
+/** \internal
+ * Returns the bucket at the specified position.
+ */
+tommy_inline tommy_hashlin_node** tommy_hashlin_pos(tommy_hashlin* hashlin, tommy_hash_t pos)
+{
+	tommy_uint_t bsr;
+
+	/* get the highest bit set, in case of all 0, return 0 */
+	bsr = tommy_ilog2_u32(pos | 1);
+
+	return &hashlin->bucket[bsr][pos];
+}
+
+/** \internal
+ * Returns a pointer to the bucket of the specified hash.
+ */
+tommy_inline tommy_hashlin_node** tommy_hashlin_bucket_ref(tommy_hashlin* hashlin, tommy_hash_t hash)
+{
+	tommy_count_t pos;
+	tommy_count_t high_pos;
+
+	pos = hash & hashlin->low_mask;
+	high_pos = hash & hashlin->bucket_mask;
+
+	/* if this position is already allocated in the high half */
+	if (pos < hashlin->split) {
+		/* The following assigment is expected to be implemented */
+		/* with a conditional move instruction */
+		/* that results in a little better and constant performance */
+		/* regardless of the split position. */
+		/* This affects mostly the worst case, when the split value */
+		/* is near at its half, resulting in a totally unpredictable */
+		/* condition by the CPU. */
+		/* In such case the use of the conditional move is generally faster. */
+
+		/* use also the high bit */
+		pos = high_pos;
+	}
+
+	return tommy_hashlin_pos(hashlin, pos);
+}
+
+/**
+ * Gets the bucket of the specified hash.
+ * The bucket is guaranteed to contain ALL the elements with the specified hash,
+ * but it can contain also others.
+ * You can access elements in the bucket following the ::next pointer until 0.
+ * \param hash Hash of the element to find.
+ * \return The head of the bucket, or 0 if empty.
+ */
+tommy_inline tommy_hashlin_node* tommy_hashlin_bucket(tommy_hashlin* hashlin, tommy_hash_t hash)
+{
+	return *tommy_hashlin_bucket_ref(hashlin, hash);
+}
+
+/**
+ * Searches an element in the hashtable.
+ * You have to provide a compare function and the hash of the element you want to find.
+ * If more equal elements are present, the first one is returned.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find.
+ * \return The first element found, or 0 if none.
+ */
+tommy_inline void* tommy_hashlin_search(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_hashlin_node* i = tommy_hashlin_bucket(hashlin, hash);
+
+	while (i) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (i->key == hash && cmp(cmp_arg, i->data) == 0)
+			return i->data;
+		i = i->next;
+	}
+	return 0;
+}
+
+/**
+ * Removes an element from the hashtable.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_hashlin_remove_existing(tommy_hashlin* hashlin, tommy_hashlin_node* node);
+
+/**
+ * Calls the specified function for each element in the hashtable.
+ *
+ * You cannot add or remove elements from the inside of the callback,
+ * but can use it to deallocate them.
+ *
+ * \code
+ * tommy_hashlin hashlin;
+ *
+ * // initializes the hashtable
+ * tommy_hashlin_init(&hashlin);
+ *
+ * ...
+ *
+ * // creates an object
+ * struct object* obj = malloc(sizeof(struct object));
+ *
+ * ...
+ *
+ * // insert it in the hashtable
+ * tommy_hashlin_insert(&hashlin, &obj->node, obj, tommy_inthash_u32(obj->value));
+ *
+ * ...
+ *
+ * // deallocates all the objects iterating the hashtable
+ * tommy_hashlin_foreach(&hashlin, free);
+ *
+ * // deallocates the hashtable
+ * tommy_hashlin_done(&hashlin);
+ * \endcode
+ */
+void tommy_hashlin_foreach(tommy_hashlin* hashlin, tommy_foreach_func* func);
+
+/**
+ * Calls the specified function with an argument for each element in the hashtable.
+ */
+void tommy_hashlin_foreach_arg(tommy_hashlin* hashlin, tommy_foreach_arg_func* func, void* arg);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_hashlin_count(tommy_hashlin* hashlin)
+{
+	return hashlin->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_hashlin_node of the stored elements.
+ */
+tommy_size_t tommy_hashlin_memory_usage(tommy_hashlin* hashlin);
+
+#endif
+
diff --git a/third-party/tommyds/tommyhashtbl.c b/third-party/tommyds/tommyhashtbl.c
new file mode 100644
index 0000000..007b8ec
--- /dev/null
+++ b/third-party/tommyds/tommyhashtbl.c
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommyhashtbl.h"
+#include "tommylist.h"
+
+#include <string.h> /* for memset */
+
+/******************************************************************************/
+/* hashtable */
+
+void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_count_t bucket_max)
+{
+	if (bucket_max < 16)
+		bucket_max = 16;
+	else
+		bucket_max = tommy_roundup_pow2_u32(bucket_max);
+
+	hashtable->bucket_max = bucket_max;
+	hashtable->bucket_mask = hashtable->bucket_max - 1;
+
+	/* initialize the vector using malloc()+memset() instead of calloc() */
+	/* to ensure that all the memory in really allocated immediately */
+	/* by the OS, and not deferred at later time. */
+	/* this improves performance, because we start with a fully initialized hashtable. */
+	hashtable->bucket = tommy_cast(tommy_hashtable_node**, tommy_malloc(hashtable->bucket_max * sizeof(tommy_hashtable_node*)));
+	memset(hashtable->bucket, 0, hashtable->bucket_max * sizeof(tommy_hashtable_node*));
+
+	hashtable->count = 0;
+}
+
+void tommy_hashtable_done(tommy_hashtable* hashtable)
+{
+	tommy_free(hashtable->bucket);
+}
+
+void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash)
+{
+	tommy_count_t pos = hash & hashtable->bucket_mask;
+
+	tommy_list_insert_tail(&hashtable->bucket[pos], node, data);
+
+	node->key = hash;
+
+	++hashtable->count;
+}
+
+void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node)
+{
+	tommy_count_t pos = node->key & hashtable->bucket_mask;
+
+	tommy_list_remove_existing(&hashtable->bucket[pos], node);
+
+	--hashtable->count;
+
+	return node->data;
+}
+
+void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_count_t pos = hash & hashtable->bucket_mask;
+	tommy_hashtable_node* node = hashtable->bucket[pos];
+
+	while (node) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (node->key == hash && cmp(cmp_arg, node->data) == 0) {
+			tommy_list_remove_existing(&hashtable->bucket[pos], node);
+
+			--hashtable->count;
+
+			return node->data;
+		}
+		node = node->next;
+	}
+
+	return 0;
+}
+
+void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func)
+{
+	tommy_count_t bucket_max = hashtable->bucket_max;
+	tommy_hashtable_node** bucket = hashtable->bucket;
+	tommy_count_t pos;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashtable_node* node = bucket[pos];
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(data);
+		}
+	}
+}
+
+void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_count_t bucket_max = hashtable->bucket_max;
+	tommy_hashtable_node** bucket = hashtable->bucket;
+	tommy_count_t pos;
+
+	for (pos = 0; pos < bucket_max; ++pos) {
+		tommy_hashtable_node* node = bucket[pos];
+
+		while (node) {
+			void* data = node->data;
+			node = node->next;
+			func(arg, data);
+		}
+	}
+}
+
+tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable)
+{
+	return hashtable->bucket_max * (tommy_size_t)sizeof(hashtable->bucket[0])
+	       + tommy_hashtable_count(hashtable) * (tommy_size_t)sizeof(tommy_hashtable_node);
+}
+
diff --git a/third-party/tommyds/tommyhashtbl.h b/third-party/tommyds/tommyhashtbl.h
new file mode 100644
index 0000000..0cb6332
--- /dev/null
+++ b/third-party/tommyds/tommyhashtbl.h
@@ -0,0 +1,280 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Fixed size chained hashtable.
+ *
+ * This hashtable is a standard implementation of a chained hashtable with a fixed size.
+ *
+ * Note that performances starts to degenerate after reaching a load factor greater than 0.75.
+ * The ::tommy_hashdyn and ::tommy_hashlin hashtables fix this problem growing dynamically.
+ *
+ * To initialize the hashtable you have to call tommy_hashtable_init() specifing
+ * the fixed bucket size.
+ *
+ * \code
+ * tommy_hashslin hashtable;
+ *
+ * tommy_hashtable_init(&hashtable, 1024);
+ * \endcode
+ *
+ * To insert elements in the hashtable you have to call tommy_hashtable_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node, the
+ * address of the object, and the hash value of the key to use.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node, and the hash to initialize the tommy_node::key field.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_hashtable_insert(&hashtable, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
+ * \endcode
+ *
+ * To find and element in the hashtable you have to call tommy_hashtable_search()
+ * providing a comparison function, its argument, and the hash of the key to search.
+ *
+ * \code
+ * int compare(const void* arg, const void* obj)
+ * {
+ *     return *(const int*)arg != ((const struct object*)obj)->value;
+ * }
+ *
+ * int value_to_find = 1;
+ * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To iterate over all the elements in the hashtable with the same key, you have to
+ * use tommy_hashtable_bucket() and follow the tommy_node::next pointer until NULL.
+ * You have also to check explicitely for the key, as the bucket may contains
+ * different keys.
+ *
+ * \code
+ * tommy_node* i = tommy_hashtable_bucket(&hashtable, tommy_inthash_u32(value_to_find));
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     if (obj->value == value_to_find) {
+ *         printf("%d\n", obj->value); // process the object
+ *     }
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an element from the hashtable you have to call tommy_hashtable_remove()
+ * providing a comparison function, its argument, and the hash of the key to search
+ * and remove.
+ *
+ * \code
+ * struct object* obj = tommy_hashtable_remove(&hashtable, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the hashtable you have to remove all the elements, and deinitialize
+ * the hashtable calling tommy_hashtable_done().
+ *
+ * \code
+ * tommy_hashtable_done(&hashtable);
+ * \endcode
+ *
+ * If you need to iterate over all the elements in the hashtable, you can use
+ * tommy_hashtable_foreach() or tommy_hashtable_foreach_arg().
+ * If you need a more precise control with a real iteration, you have to insert
+ * all the elements also in a ::tommy_list, and use the list to iterate.
+ * See the \ref multiindex example for more detail.
+ */
+
+#ifndef __TOMMYHASHTBL_H
+#define __TOMMYHASHTBL_H
+
+#include "tommyhash.h"
+
+/******************************************************************************/
+/* hashtable */
+
+/**
+ * Hashtable node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef tommy_node tommy_hashtable_node;
+
+/**
+ * Hashtable container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_hashtable_struct {
+	tommy_hashtable_node** bucket; /**< Hash buckets. One list for each hash modulus. */
+	tommy_count_t bucket_max; /**< Number of buckets. */
+	tommy_count_t bucket_mask; /**< Bit mask to access the buckets. */
+	tommy_count_t count; /**< Number of elements. */
+} tommy_hashtable;
+
+/**
+ * Initializes the hashtable.
+ * \param buckets Minimum number of buckets to allocate. The effective number used is the next power of 2.
+ */
+void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_count_t bucket_max);
+
+/**
+ * Deinitializes the hashtable.
+ *
+ * You can call this function with elements still contained,
+ * but such elements are not going to be freed by this call.
+ */
+void tommy_hashtable_done(tommy_hashtable* hashtable);
+
+/**
+ * Inserts an element in the hashtable.
+ */
+void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash);
+
+/**
+ * Searches and removes an element from the hashtable.
+ * You have to provide a compare function and the hash of the element you want to remove.
+ * If the element is not found, 0 is returned.
+ * If more equal elements are present, the first one is removed.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find and remove.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
+
+/**
+ * Gets the bucket of the specified hash.
+ * The bucket is guaranteed to contain ALL the elements with the specified hash,
+ * but it can contain also others.
+ * You can access elements in the bucket following the ::next pointer until 0.
+ * \param hash Hash of the element to find.
+ * \return The head of the bucket, or 0 if empty.
+ */
+tommy_inline tommy_hashtable_node* tommy_hashtable_bucket(tommy_hashtable* hashtable, tommy_hash_t hash)
+{
+	return hashtable->bucket[hash & hashtable->bucket_mask];
+}
+
+/**
+ * Searches an element in the hashtable.
+ * You have to provide a compare function and the hash of the element you want to find.
+ * If more equal elements are present, the first one is returned.
+ * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
+ * The function should return 0 for equal elements, anything other for different elements.
+ * \param cmp_arg Compare argument passed as first argument of the compare function.
+ * \param hash Hash of the element to find.
+ * \return The first element found, or 0 if none.
+ */
+tommy_inline void* tommy_hashtable_search(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
+{
+	tommy_hashtable_node* i = tommy_hashtable_bucket(hashtable, hash);
+
+	while (i) {
+		/* we first check if the hash matches, as in the same bucket we may have multiples hash values */
+		if (i->key == hash && cmp(cmp_arg, i->data) == 0)
+			return i->data;
+		i = i->next;
+	}
+	return 0;
+}
+
+/**
+ * Removes an element from the hashtable.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node);
+
+/**
+ * Calls the specified function for each element in the hashtable.
+ *
+ * You cannot add or remove elements from the inside of the callback,
+ * but can use it to deallocate them.
+ *
+ * \code
+ * tommy_hashtable hashtable;
+ *
+ * // initializes the hashtable
+ * tommy_hashtable_init(&hashtable, ...);
+ *
+ * ...
+ *
+ * // creates an object
+ * struct object* obj = malloc(sizeof(struct object));
+ *
+ * ...
+ *
+ * // insert it in the hashtable
+ * tommy_hashdyn_insert(&hashtable, &obj->node, obj, tommy_inthash_u32(obj->value));
+ *
+ * ...
+ *
+ * // deallocates all the objects iterating the hashtable
+ * tommy_hashtable_foreach(&hashtable, free);
+ *
+ * // deallocates the hashtable
+ * tommy_hashdyn_done(&hashtable);
+ * \endcode
+ */
+void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func);
+
+/**
+ * Calls the specified function with an argument for each element in the hashtable.
+ */
+void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_hashtable_count(tommy_hashtable* hashtable)
+{
+	return hashtable->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_hashtable_node of the stored elements.
+ */
+tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable);
+
+#endif
+
diff --git a/third-party/tommyds/tommylist.c b/third-party/tommyds/tommylist.c
new file mode 100644
index 0000000..1fa1f24
--- /dev/null
+++ b/third-party/tommyds/tommylist.c
@@ -0,0 +1,60 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommylist.h"
+#include "tommychain.h"
+
+/** \internal
+ * Setup a list.
+ */
+tommy_inline void tommy_list_set(tommy_list* list, tommy_node* head, tommy_node* tail)
+{
+	head->prev = tail;
+	tail->next = 0;
+	*list = head;
+}
+
+void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp)
+{
+	tommy_chain chain;
+	tommy_node* head;
+
+	if (tommy_list_empty(list))
+		return;
+
+	head = tommy_list_head(list);
+
+	/* create a chain from the list */
+	chain.head = head;
+	chain.tail = head->prev;
+
+	tommy_chain_mergesort(&chain, cmp);
+
+	/* restore the list */
+	tommy_list_set(list, chain.head, chain.tail);
+}
+
diff --git a/third-party/tommyds/tommylist.h b/third-party/tommyds/tommylist.h
new file mode 100644
index 0000000..368606a
--- /dev/null
+++ b/third-party/tommyds/tommylist.h
@@ -0,0 +1,381 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Double linked list for collisions into hashtables.
+ *
+ * This list is a double linked list mainly targetted for handling collisions
+ * into an hashtables, but useable also as a generic list.
+ *
+ * The main feature of this list is to require only one pointer to represent the
+ * list, compared to a classic implementation requiring a head an a tail pointers.
+ * This reduces the memory usage in hashtables.
+ *
+ * Another feature is to support the insertion at the end of the list. This allow to store
+ * collisions in a stable order. Where for stable order we mean that equal elements keep
+ * their insertion order.
+ *
+ * To initialize the list, you have to call tommy_list_init(), or to simply assign
+ * to it NULL, as an empty list is represented by the NULL value.
+ *
+ * \code
+ * tommy_list list;
+ *
+ * tommy_list_init(&list); // initializes the list
+ * \endcode
+ *
+ * To insert elements in the list you have to call tommy_list_insert_tail()
+ * or tommy_list_insert_head() for each element.
+ * In the insertion call you have to specify the address of the node and the
+ * address of the object.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_list_insert_tail(&list, &obj->node, obj); // inserts the object
+ * \endcode
+ *
+ * To iterate over all the elements in the list you have to call
+ * tommy_list_head() to get the head of the list and follow the
+ * tommy_node::next pointer until NULL.
+ *
+ * \code
+ * tommy_node* i = tommy_list_head(&list);
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     printf("%d\n", obj->value); // process the object
+ *
+ *     i = i->next; // go to the next element
+ * }
+ * \endcode
+ *
+ * To destroy the list you have to remove all the elements,
+ * as the list is completely inplace and it doesn't allocate memory.
+ * This can be done with the tommy_list_foreach() function.
+ *
+ * \code
+ * // deallocates all the objects iterating the list
+ * tommy_list_foreach(&list, free);
+ * \endcode
+ */
+
+#ifndef __TOMMYLIST_H
+#define __TOMMYLIST_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* list */
+
+/**
+ * Double linked list type.
+ */
+typedef tommy_node* tommy_list;
+
+/**
+ * Initializes the list.
+ * The list is completely inplace, so it doesn't need to be deinitialized.
+ */
+tommy_inline void tommy_list_init(tommy_list* list)
+{
+	*list = 0;
+}
+
+/**
+ * Gets the head of the list.
+ * \return The head node. For empty lists 0 is returned.
+ */
+tommy_inline tommy_node* tommy_list_head(tommy_list* list)
+{
+	return *list;
+}
+
+/**
+ * Gets the tail of the list.
+ * \return The tail node. For empty lists 0 is returned.
+ */
+tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
+{
+	tommy_node* head = tommy_list_head(list);
+
+	if (!head)
+		return 0;
+
+	return head->prev;
+}
+
+/** \internal
+ * Creates a new list with a single element.
+ * \param list The list to initialize.
+ * \param node The node to insert.
+ */
+tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
+{
+	/* one element "circular" prev list */
+	node->prev = node;
+
+	/* one element "0 terminated" next list */
+	node->next = 0;
+
+	*list = node;
+}
+
+/** \internal
+ * Inserts an element at the head of a not empty list.
+ * The element is inserted at the head of the list. The list cannot be empty.
+ * \param list The list. The list cannot be empty.
+ * \param node The node to insert.
+ */
+tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
+{
+	tommy_node* head = tommy_list_head(list);
+
+	/* insert in the "circular" prev list */
+	node->prev = head->prev;
+	head->prev = node;
+
+	/* insert in the "0 terminated" next list */
+	node->next = head;
+
+	*list = node;
+}
+
+/** \internal
+ * Inserts an element at the tail of a not empty list.
+ * The element is inserted at the tail of the list. The list cannot be empty.
+ * \param head The node at the list head. It cannot be 0.
+ * \param node The node to insert.
+ */
+tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
+{
+	/* insert in the "circular" prev list */
+	node->prev = head->prev;
+	head->prev = node;
+
+	/* insert in the "0 terminated" next list */
+	node->next = 0;
+	node->prev->next = node;
+}
+
+/**
+ * Inserts an element at the head of a list.
+ * \param node The node to insert.
+ * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
+ */
+tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
+{
+	tommy_node* head = tommy_list_head(list);
+
+	if (head)
+		tommy_list_insert_head_not_empty(list, node);
+	else
+		tommy_list_insert_first(list, node);
+
+	node->data = data;
+}
+
+/**
+ * Inserts an element at the tail of a list.
+ * \param node The node to insert.
+ * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
+ */
+tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
+{
+	tommy_node* head = tommy_list_head(list);
+
+	if (head)
+		tommy_list_insert_tail_not_empty(head, node);
+	else
+		tommy_list_insert_first(list, node);
+
+	node->data = data;
+}
+
+/**
+ * Removes an element from the list.
+ * You must already have the address of the element to remove.
+ * \note The node content is left unchanged, including the tommy_node::next
+ * and tommy_node::prev fields that still contain pointers at the list.
+ * \param node The node to remove. The node must be in the list.
+ * \return The tommy_node::data field of the node removed.
+ */
+tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
+{
+	tommy_node* head = tommy_list_head(list);
+
+	/* remove from the "circular" prev list */
+	if (node->next)
+		node->next->prev = node->prev;
+	else
+		head->prev = node->prev; /* the last */
+
+	/* remove from the "0 terminated" next list */
+	if (head == node)
+		*list = node->next; /* the new head, in case 0 */
+	else
+		node->prev->next = node->next;
+
+	return node->data;
+}
+
+/**
+ * Concats two lists.
+ * The second list is concatenated at the first list.
+ * \param first The first list.
+ * \param second The second list. After this call the list content is undefined,
+ * and you should not use it anymore.
+ */
+tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
+{
+	tommy_node* first_head;
+	tommy_node* first_tail;
+	tommy_node* second_head;
+
+	/* if the second is empty, nothing to do */
+	second_head = tommy_list_head(second);
+	if (second_head == 0)
+		return;
+
+	/* if the first is empty, copy the second */
+	first_head = tommy_list_head(first);
+	if (first_head == 0) {
+		*first = *second;
+		return;
+	}
+
+	/* tail of the first list */
+	first_tail = first_head->prev;
+
+	/* set the "circular" prev list */
+	first_head->prev = second_head->prev;
+	second_head->prev = first_tail;
+
+	/* set the "0 terminated" next list */
+	first_tail->next = second_head;
+}
+
+/**
+ * Sorts a list.
+ * It's a stable merge sort with O(N*log(N)) worst complexity.
+ * It's faster on degenerated cases like partially ordered lists.
+ * \param cmp Compare function called with two elements.
+ * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather.
+ */
+void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
+
+/**
+ * Checks if empty.
+ * \return If the list is empty.
+ */
+tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
+{
+	return tommy_list_head(list) == 0;
+}
+
+/**
+ * Gets the number of elements.
+ * \note This operation is O(n).
+ */
+tommy_inline tommy_count_t tommy_list_count(tommy_list* list)
+{
+	tommy_count_t count = 0;
+	tommy_node* i = tommy_list_head(list);
+
+	while (i) {
+		++count;
+		i = i->next;
+	}
+
+	return count;
+}
+
+/**
+ * Calls the specified function for each element in the list.
+ *
+ * You cannot add or remove elements from the inside of the callback,
+ * but can use it to deallocate them.
+ *
+ * \code
+ * tommy_list list;
+ *
+ * // initializes the list
+ * tommy_list_init(&list);
+ *
+ * ...
+ *
+ * // creates an object
+ * struct object* obj = malloc(sizeof(struct object));
+ *
+ * ...
+ *
+ * // insert it in the list
+ * tommy_list_insert_tail(&list, &obj->node, obj);
+ *
+ * ...
+ *
+ * // deallocates all the objects iterating the list
+ * tommy_list_foreach(&list, free);
+ * \endcode
+ */
+tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
+{
+	tommy_node* node = tommy_list_head(list);
+
+	while (node) {
+		void* data = node->data;
+		node = node->next;
+		func(data);
+	}
+}
+
+/**
+ * Calls the specified function with an argument for each element in the list.
+ */
+tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_node* node = tommy_list_head(list);
+
+	while (node) {
+		void* data = node->data;
+		node = node->next;
+		func(arg, data);
+	}
+}
+
+#endif
+
diff --git a/third-party/tommyds/tommytree.c b/third-party/tommyds/tommytree.c
new file mode 100644
index 0000000..6b2f1a9
--- /dev/null
+++ b/third-party/tommyds/tommytree.c
@@ -0,0 +1,292 @@
+/*
+ * Copyright (c) 2015, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommytree.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* tree */
+
+void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
+{
+	tree->root = 0;
+	tree->count = 0;
+	tree->cmp = cmp;
+}
+
+static int tommy_tree_delta(tommy_tree_node* root)
+{
+	int left_height = root->prev ? root->prev->key : 0;
+	int right_height = root->next ? root->next->key : 0;
+
+	return left_height - right_height;
+}
+
+/* AVL tree operations */
+static tommy_tree_node* tommy_tree_balance(tommy_tree_node*);
+
+static tommy_tree_node* tommy_tree_rotate_left(tommy_tree_node* root)
+{
+	tommy_tree_node* next = root->next;
+
+	root->next = next->prev;
+
+	next->prev = tommy_tree_balance(root);
+
+	return tommy_tree_balance(next);
+}
+
+static tommy_tree_node* tommy_tree_rotate_right(tommy_tree_node* root)
+{
+	tommy_tree_node* prev = root->prev;
+
+	root->prev = prev->next;
+
+	prev->next = tommy_tree_balance(root);
+
+	return tommy_tree_balance(prev);
+}
+
+static tommy_tree_node* tommy_tree_move_right(tommy_tree_node* root, tommy_tree_node* node)
+{
+	if (!root)
+		return node;
+
+	root->next = tommy_tree_move_right(root->next, node);
+
+	return tommy_tree_balance(root);
+}
+
+static tommy_tree_node* tommy_tree_balance(tommy_tree_node* root)
+{
+	int delta = tommy_tree_delta(root);
+
+	if (delta < -1) {
+		if (tommy_tree_delta(root->next) > 0)
+			root->next = tommy_tree_rotate_right(root->next);
+		return tommy_tree_rotate_left(root);
+	}
+
+	if (delta > 1) {
+		if (tommy_tree_delta(root->prev) < 0)
+			root->prev = tommy_tree_rotate_left(root->prev);
+		return tommy_tree_rotate_right(root);
+	}
+
+	/* recompute key */
+	root->key = 0;
+
+	if (root->prev && root->prev->key > root->key)
+		root->key = root->prev->key;
+
+	if (root->next && root->next->key > root->key)
+		root->key = root->next->key;
+
+	/* count itself */
+	root->key += 1;
+
+	return root;
+}
+
+static tommy_tree_node* tommy_tree_insert_node(tommy_compare_func* cmp, tommy_tree_node* root, tommy_tree_node** let)
+{
+	int c;
+
+	if (!root)
+		return *let;
+
+	c = cmp((*let)->data, root->data);
+
+	if (c < 0) {
+		root->prev = tommy_tree_insert_node(cmp, root->prev, let);
+		return tommy_tree_balance(root);
+	}
+
+	if (c > 0) {
+		root->next = tommy_tree_insert_node(cmp, root->next, let);
+		return tommy_tree_balance(root);
+	}
+
+	/* already present, set the return pointer */
+	*let = root;
+
+	return root;
+}
+
+void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data)
+{
+	tommy_tree_node* insert = node;
+
+	insert->data = data;
+	insert->prev = 0;
+	insert->next = 0;
+	insert->key = 0;
+
+	tree->root = tommy_tree_insert_node(tree->cmp, tree->root, &insert);
+
+	if (insert == node)
+		++tree->count;
+
+	return insert->data;
+}
+
+static tommy_tree_node* tommy_tree_remove_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data, tommy_tree_node** let)
+{
+	int c;
+
+	if (!root)
+		return 0;
+
+	c = cmp(data, root->data);
+
+	if (c < 0) {
+		root->prev = tommy_tree_remove_node(cmp, root->prev, data, let);
+		return tommy_tree_balance(root);
+	}
+
+	if (c > 0) {
+		root->next = tommy_tree_remove_node(cmp, root->next, data, let);
+		return tommy_tree_balance(root);
+	}
+
+	/* found */
+	*let = root;
+
+	return tommy_tree_move_right(root->prev, root->next);
+}
+
+void* tommy_tree_remove(tommy_tree* tree, void* data)
+{
+	tommy_tree_node* node = 0;
+
+	tree->root = tommy_tree_remove_node(tree->cmp, tree->root, data, &node);
+
+	if (!node)
+		return 0;
+
+	--tree->count;
+
+	return node->data;
+}
+
+static tommy_tree_node* tommy_tree_search_node(tommy_compare_func* cmp, tommy_tree_node* root, void* data)
+{
+	int c;
+
+	if (!root)
+		return 0;
+
+	c = cmp(data, root->data);
+
+	if (c < 0)
+		return tommy_tree_search_node(cmp, root->prev, data);
+
+	if (c > 0)
+		return tommy_tree_search_node(cmp, root->next, data);
+
+	return root;
+}
+
+void* tommy_tree_search(tommy_tree* tree, void* data)
+{
+	tommy_tree_node* node = tommy_tree_search_node(tree->cmp, tree->root, data);
+
+	if (!node)
+		return 0;
+
+	return node->data;
+}
+
+void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg)
+{
+	tommy_tree_node* node = tommy_tree_search_node(cmp, tree->root, cmp_arg);
+
+	if (!node)
+		return 0;
+
+	return node->data;
+}
+
+void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node)
+{
+	void* data = tommy_tree_remove(tree, node->data);
+
+	assert(data != 0);
+
+	return data;
+}
+
+static void tommy_tree_foreach_node(tommy_tree_node* root, tommy_foreach_func* func)
+{
+	tommy_tree_node* next;
+
+	if (!root)
+		return;
+
+	tommy_tree_foreach_node(root->prev, func);
+
+	/* make a copy in case func is free() */
+	next = root->next;
+
+	func(root->data);
+
+	tommy_tree_foreach_node(next, func);
+}
+
+void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func)
+{
+	tommy_tree_foreach_node(tree->root, func);
+}
+
+static void tommy_tree_foreach_arg_node(tommy_tree_node* root, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_tree_node* next;
+
+	if (!root)
+		return;
+
+	tommy_tree_foreach_arg_node(root->prev, func, arg);
+
+	/* make a copy in case func is free() */
+	next = root->next;
+
+	func(arg, root->data);
+
+	tommy_tree_foreach_arg_node(next, func, arg);
+}
+
+void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg)
+{
+	tommy_tree_foreach_arg_node(tree->root, func, arg);
+}
+
+tommy_size_t tommy_tree_memory_usage(tommy_tree* tree)
+{
+	return tommy_tree_count(tree) * sizeof(tommy_tree_node);
+}
+
diff --git a/third-party/tommyds/tommytree.h b/third-party/tommyds/tommytree.h
new file mode 100644
index 0000000..55e4006
--- /dev/null
+++ b/third-party/tommyds/tommytree.h
@@ -0,0 +1,228 @@
+/*
+ * Copyright (c) 2015, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * AVL tree.
+ *
+ * This tree is a standard AVL tree implementation that stores elements in the
+ * order defined by the comparison function.
+ *
+ * As difference than other tommy containers, duplicate elements cannot be inserted.
+ *
+ * To initialize a tree you have to call tommy_tree_init() specifing a comparison
+ * function that will define the order in the tree.
+ *
+ * \code
+ * tommy_tree tree;
+ *
+ * tommy_tree_init(&tree, cmp);
+ * \endcode
+ *
+ * To insert elements in the tree you have to call tommy_tree_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node and the
+ * address of the object.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_tree_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_tree_insert(&tree, &obj->node, obj); // inserts the object
+ * \endcode
+ *
+ * To find and element in the tree you have to call tommy_tree_search() providing
+ * the key to search.
+ *
+ * \code
+ * struct object value_to_find = { 1 };
+ * struct object* obj = tommy_tree_search(&tree, &value_to_find);
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To remove an element from the tree you have to call tommy_tree_remove()
+ * providing the key to search and remove.
+ *
+ * \code
+ * struct object value_to_remove = { 1 };
+ * struct object* obj = tommy_tree_remove(&tree, &value_to_remove);
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the tree you have to remove or destroy all the contained elements.
+ * The tree itself doesn't have or need a deallocation function.
+ *
+ * If you need to iterate over all the elements in the tree, you can use
+ * tommy_tree_foreach() or tommy_tree_foreach_arg().
+ * If you need a more precise control with a real iteration, you have to insert
+ * all the elements also in a ::tommy_list, and use the list to iterate.
+ * See the \ref multiindex example for more detail. 
+ */
+
+#ifndef __TOMMYTREE_H
+#define __TOMMYTREE_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* tree */
+
+/**
+ * Tree node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef tommy_node tommy_tree_node;
+
+/**
+ * Tree container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_tree_struct {
+	tommy_tree_node* root; /**< Root node. */
+	tommy_count_t count; /**< Number of elements. */
+	tommy_compare_func* cmp; /**< Comparison function. */
+} tommy_tree;
+
+/**
+ * Initializes the tree.
+ * \param cmp The comparison function that defines the orderin the tree.
+ */
+void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp);
+
+/**
+ * Inserts an element in the tree.
+ * If the element is already present, it's not inserted again.
+ * Check the return value to identify if the element was already present or not.
+ * You have to provide the pointer of the node embedded into the object and
+ * the pointer to the object.
+ * \param node Pointer to the node embedded into the object to insert.
+ * \param data Pointer to the object to insert.
+ * \return The element in the tree. Either the already existing one, or the one just inserted.
+ */
+void* tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data);
+
+/**
+ * Searches and removes an element.
+ * If the element is not found, 0 is returned.
+ * \param data Element used for comparison.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_tree_remove(tommy_tree* tree, void* data);
+
+/**
+ * Searches an element in the tree.
+ * If the element is not found, 0 is returned. 
+ * \param data Element used for comparison.
+ * \return The first element found, or 0 if none.
+ */
+void* tommy_tree_search(tommy_tree* tree, void* data);
+
+/**
+ * Searches an element in the tree with a specific comparison function.
+ *
+ * Like tommy_tree_search() but you can specify a different comparison function.
+ * Note that this function must define a suborder of the original one.
+ *
+ * The ::data argument will be the first argument of the comparison function,
+ * and it can be of a different type of the objects in the tree.
+ */
+void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, void* cmp_arg);
+
+/**
+ * Removes an element from the tree.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_tree_remove_existing(tommy_tree* tree, tommy_tree_node* node);
+
+/**
+ * Calls the specified function for each element in the tree.
+ *
+ * The elements are processed in order.
+ *
+ * You cannot add or remove elements from the inside of the callback,
+ * but can use it to deallocate them.
+ *
+ * \code
+ * tommy_tree tree;
+ *
+ * // initializes the tree
+ * tommy_tree_init(&tree, cmp);
+ *
+ * ...
+ *
+ * // creates an object
+ * struct object* obj = malloc(sizeof(struct object));
+ *
+ * ...
+ *
+ * // insert it in the tree
+ * tommy_tree_insert(&tree, &obj->node, obj);
+ *
+ * ...
+ *
+ * // deallocates all the objects iterating the tree
+ * tommy_tree_foreach(&tree, free);
+ * \endcode
+ */
+void tommy_tree_foreach(tommy_tree* tree, tommy_foreach_func* func);
+
+/**
+ * Calls the specified function with an argument for each element in the tree.
+ */
+void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_tree_count(tommy_tree* tree)
+{
+	return tree->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_tree_node of the stored elements.
+ */
+tommy_size_t tommy_tree_memory_usage(tommy_tree* tree);
+
+#endif
+
diff --git a/third-party/tommyds/tommytrie.c b/third-party/tommyds/tommytrie.c
new file mode 100644
index 0000000..35ac219
--- /dev/null
+++ b/third-party/tommyds/tommytrie.c
@@ -0,0 +1,323 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommytrie.h"
+#include "tommylist.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* trie */
+
+/**
+ * Mask for the inner branches.
+ */
+#define TOMMY_TRIE_TREE_MASK (TOMMY_TRIE_TREE_MAX - 1)
+
+/**
+ * Shift for the first level of branches.
+ */
+#define TOMMY_TRIE_BUCKET_SHIFT (TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT)
+
+/**
+ * Max number of levels.
+ */
+#define TOMMY_TRIE_LEVEL_MAX ((TOMMY_KEY_BIT - TOMMY_TRIE_BUCKET_BIT) / TOMMY_TRIE_TREE_BIT)
+
+/**
+ * Hashtrie tree.
+ * A tree contains TOMMY_TRIE_TREE_MAX ordered pointers to <null/node/tree>.
+ *
+ * Each tree level uses exactly TOMMY_TRIE_TREE_BIT bits from the key.
+ */
+struct tommy_trie_tree_struct {
+	tommy_trie_node* map[TOMMY_TRIE_TREE_MAX];
+};
+typedef struct tommy_trie_tree_struct tommy_trie_tree;
+
+/**
+ * Kinds of an trie node.
+ */
+#define TOMMY_TRIE_TYPE_NODE 0 /**< The node is of type ::tommy_trie_node. */
+#define TOMMY_TRIE_TYPE_TREE 1 /**< The node is of type ::tommy_trie_tree. */
+
+/**
+ * Get and set pointer of trie nodes.
+ *
+ * The pointer type is stored in the lower bit.
+ */
+#define trie_get_type(ptr) (((tommy_uintptr_t)(ptr)) & 1)
+#define trie_get_tree(ptr) ((tommy_trie_tree*)(((tommy_uintptr_t)(ptr)) - TOMMY_TRIE_TYPE_TREE))
+#define trie_set_tree(ptr) (void*)(((tommy_uintptr_t)(ptr)) + TOMMY_TRIE_TYPE_TREE)
+
+void tommy_trie_init(tommy_trie* trie, tommy_allocator* alloc)
+{
+	tommy_uint_t i;
+
+	for (i = 0; i < TOMMY_TRIE_BUCKET_MAX; ++i)
+		trie->bucket[i] = 0;
+
+	trie->count = 0;
+	trie->node_count = 0;
+
+	trie->alloc = alloc;
+}
+
+static void trie_bucket_insert(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* insert, tommy_key_t key)
+{
+	tommy_trie_tree* tree;
+	tommy_trie_node* node;
+	void* ptr;
+	tommy_uint_t i;
+	tommy_uint_t j;
+
+recurse:
+	ptr = *let_ptr;
+
+	/* if null, just insert the node */
+	if (!ptr) {
+		/* setup the node as a list */
+		tommy_list_insert_first(let_ptr, insert);
+		return;
+	}
+
+	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
+		/* repeat the process one level down */
+		let_ptr = &trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+		goto recurse;
+	}
+
+	node = tommy_cast(tommy_trie_node*, ptr);
+
+	/* if it's the same key, insert in the list */
+	if (node->key == key) {
+		tommy_list_insert_tail_not_empty(node, insert);
+		return;
+	}
+
+expand:
+	/* convert to a tree */
+	tree = tommy_cast(tommy_trie_tree*, tommy_allocator_alloc(trie->alloc));
+	++trie->node_count;
+	*let_ptr = tommy_cast(tommy_trie_node*, trie_set_tree(tree));
+
+	/* initialize it */
+	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i)
+		tree->map[i] = 0;
+
+	/* get the position of the two elements */
+	i = (node->key >> shift) & TOMMY_TRIE_TREE_MASK;
+	j = (key >> shift) & TOMMY_TRIE_TREE_MASK;
+
+	/* if they don't collide */
+	if (i != j) {
+		/* insert the already existing element */
+		tree->map[i] = node;
+
+		/* insert the new node */
+		tommy_list_insert_first(&tree->map[j], insert);
+		return;
+	}
+
+	/* expand one more level */
+	let_ptr = &tree->map[i];
+	shift -= TOMMY_TRIE_TREE_BIT;
+	goto expand;
+}
+
+void tommy_trie_insert(tommy_trie* trie, tommy_trie_node* node, void* data, tommy_key_t key)
+{
+	tommy_trie_node** let_ptr;
+
+	node->data = data;
+	node->key = key;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	trie_bucket_insert(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
+
+	++trie->count;
+}
+
+static tommy_trie_node* trie_bucket_remove_existing(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* remove, tommy_key_t key)
+{
+	tommy_trie_node* node;
+	tommy_trie_tree* tree;
+	void* ptr;
+	tommy_trie_node** let_back[TOMMY_TRIE_LEVEL_MAX + 1];
+	tommy_uint_t level;
+	tommy_uint_t i;
+	tommy_uint_t count;
+	tommy_uint_t last;
+
+	level = 0;
+recurse:
+	ptr = *let_ptr;
+
+	if (!ptr)
+		return 0;
+
+	if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
+		tree = trie_get_tree(ptr);
+
+		/* save the path */
+		let_back[level++] = let_ptr;
+
+		/* go down one level */
+		let_ptr = &tree->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+
+		goto recurse;
+	}
+
+	node = tommy_cast(tommy_trie_node*, ptr);
+
+	/* if the node to remove is not specified */
+	if (!remove) {
+		/* remove the first */
+		remove = node;
+
+		/* check if it's really the element to remove */
+		if (remove->key != key)
+			return 0;
+	}
+
+	tommy_list_remove_existing(let_ptr, remove);
+
+	/* if the list is not empty, try to reduce */
+	if (*let_ptr || !level)
+		return remove;
+
+reduce:
+	/* go one level up */
+	let_ptr = let_back[--level];
+
+	tree = trie_get_tree(*let_ptr);
+
+	/* check if there is only one child node */
+	count = 0;
+	last = 0;
+	for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i) {
+		if (tree->map[i]) {
+			/* if we have a sub tree, we cannot reduce */
+			if (trie_get_type(tree->map[i]) != TOMMY_TRIE_TYPE_NODE)
+				return remove;
+			/* if more than one node, we cannot reduce */
+			if (++count > 1)
+				return remove;
+			last = i;
+		}
+	}
+
+	/* here count is never 0, as we cannot have a tree with only one sub node */
+	assert(count == 1);
+
+	*let_ptr = tree->map[last];
+
+	tommy_allocator_free(trie->alloc, tree);
+	--trie->node_count;
+
+	/* repeat until more level */
+	if (level)
+		goto reduce;
+
+	return remove;
+}
+
+void* tommy_trie_remove(tommy_trie* trie, tommy_key_t key)
+{
+	tommy_trie_node* ret;
+	tommy_trie_node** let_ptr;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, 0, key);
+
+	if (!ret)
+		return 0;
+
+	--trie->count;
+
+	return ret->data;
+}
+
+void* tommy_trie_remove_existing(tommy_trie* trie, tommy_trie_node* node)
+{
+	tommy_trie_node* ret;
+	tommy_key_t key = node->key;
+	tommy_trie_node** let_ptr;
+
+	let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
+
+	/* the element removed must match the one passed */
+	assert(ret == node);
+
+	--trie->count;
+
+	return ret->data;
+}
+
+tommy_trie_node* tommy_trie_bucket(tommy_trie* trie, tommy_key_t key)
+{
+	tommy_trie_node* node;
+	void* ptr;
+	tommy_uint_t type;
+	tommy_uint_t shift;
+
+	ptr = trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
+
+	shift = TOMMY_TRIE_BUCKET_SHIFT;
+
+recurse:
+	if (!ptr)
+		return 0;
+
+	type = trie_get_type(ptr);
+
+	switch (type) {
+	case TOMMY_TRIE_TYPE_NODE :
+		node = tommy_cast(tommy_trie_node*, ptr);
+		if (node->key != key)
+			return 0;
+		return node;
+	default :
+	case TOMMY_TRIE_TYPE_TREE :
+		ptr = trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
+		shift -= TOMMY_TRIE_TREE_BIT;
+		goto recurse;
+	}
+}
+
+tommy_size_t tommy_trie_memory_usage(tommy_trie* trie)
+{
+	return tommy_trie_count(trie) * (tommy_size_t)sizeof(tommy_trie_node)
+	       + trie->node_count * (tommy_size_t)TOMMY_TRIE_BLOCK_SIZE;
+}
+
diff --git a/third-party/tommyds/tommytrie.h b/third-party/tommyds/tommytrie.h
new file mode 100644
index 0000000..d82a5f2
--- /dev/null
+++ b/third-party/tommyds/tommytrie.h
@@ -0,0 +1,260 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Trie optimized for cache utilization.
+ *
+ * This trie is a standard implementation that stores elements in the order defined
+ * by the key.
+ *
+ * It needs an external allocator for the inner nodes in the trie.
+ *
+ * You can control the number of branches of each node using the ::TOMMY_TRIE_TREE_MAX
+ * define. More branches imply more speed, but a bigger memory occupation.
+ *
+ * Compared to ::tommy_trie_inplace you have to provide a ::tommy_allocator allocator.
+ * Note that the C malloc() is too slow to futfill this role.
+ *
+ * To initialize the trie you have to call tommy_allocator_init() to initialize
+ * the allocator, and tommy_trie_init() for the trie.
+ *
+ * \code
+ * tommy_allocator alloc;
+ * tommy_trie trie;
+ *
+ * tommy_allocator_init(&alloc, TOMMY_TRIE_BLOCK_SIZE, TOMMY_TRIE_BLOCK_SIZE);
+ *
+ * tommy_trie_init(&trie, &alloc);
+ * \endcode
+ *
+ * To insert elements in the trie you have to call tommy_trie_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node, the
+ * address of the object, and the key value to use.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node, and the key to initialize the tommy_node::key field.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_trie_insert(&trie, &obj->node, obj, obj->value); // inserts the object
+ * \endcode
+ *
+ * To find and element in the trie you have to call tommy_trie_search() providing
+ * the key to search.
+ *
+ * \code
+ * int value_to_find = 1;
+ * struct object* obj = tommy_trie_search(&trie, value_to_find);
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To iterate over all the elements in the trie with the same key, you have to
+ * use tommy_trie_bucket() and follow the tommy_node::next pointer until NULL.
+ *
+ * \code
+ * int value_to_find = 1;
+ * tommy_node* i = tommy_trie_bucket(&trie, value_to_find);
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     printf("%d\n", obj->value); // process the object
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an element from the trie you have to call tommy_trie_remove()
+ * providing the key to search and remove.
+ *
+ * \code
+ * struct object* obj = tommy_trie_remove(&trie, value_to_remove);
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the trie you have to remove all the elements, and deinitialize
+ * the allocator using tommy_allocator_done().
+ *
+ * \code
+ * tommy_allocator_done(&alloc);
+ * \endcode
+ *
+ * Note that you cannot iterate over all the elements in the trie using the
+ * trie itself. You have to insert all the elements also in a ::tommy_list,
+ * and use the list to iterate. See the \ref multiindex example for more detail.
+ */
+
+#ifndef __TOMMYTRIE_H
+#define __TOMMYTRIE_H
+
+#include "tommytypes.h"
+#include "tommyalloc.h"
+
+/******************************************************************************/
+/* trie */
+
+/**
+ * Number of branches on each inner node. It must be a power of 2.
+ * Suggested values are 8, 16 and 32.
+ * Any inner node, excluding leafs, contains a pointer to each branch.
+ *
+ * The default size is choosen to exactly fit a typical cache line of 64 bytes.
+ */
+#define TOMMY_TRIE_TREE_MAX (64 / sizeof(void*))
+
+/**
+ * Trie block size.
+ * You must use this value to initialize the allocator.
+ */
+#define TOMMY_TRIE_BLOCK_SIZE (TOMMY_TRIE_TREE_MAX * sizeof(void*))
+
+/** \internal
+ * Number of bits for each branch.
+ */
+#define TOMMY_TRIE_TREE_BIT TOMMY_ILOG2(TOMMY_TRIE_TREE_MAX)
+
+/** \internal
+ * Number of bits of the first level.
+ */
+#define TOMMY_TRIE_BUCKET_BIT ((TOMMY_KEY_BIT % TOMMY_TRIE_TREE_BIT) + TOMMY_TRIE_TREE_BIT)
+
+/** \internal
+ * Number of branches of the first level.
+ * It's like a inner branch, but bigger to get any remainder bits.
+ */
+#define TOMMY_TRIE_BUCKET_MAX (1 << TOMMY_TRIE_BUCKET_BIT)
+
+/**
+ * Trie node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef tommy_node tommy_trie_node;
+
+/**
+ * Trie container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_trie_struct {
+	tommy_trie_node* bucket[TOMMY_TRIE_BUCKET_MAX]; /**< First tree level. */
+	tommy_count_t count; /**< Number of elements. */
+	tommy_count_t node_count; /**< Number of nodes. */
+	tommy_allocator* alloc; /**< Allocator for internal nodes. */
+} tommy_trie;
+
+/**
+ * Initializes the trie.
+ * You have to provide an allocator initialized with *both* the size and align with TOMMY_TRIE_BLOCK_SIZE.
+ * You can share this allocator with other tries.
+ *
+ * The tries is completely allocated through the allocator, and it doesn't need to be deinitialized.
+ * \param alloc Allocator initialized with *both* the size and align with TOMMY_TRIE_BLOCK_SIZE.
+ */
+void tommy_trie_init(tommy_trie* trie, tommy_allocator* alloc);
+
+/**
+ * Inserts an element in the trie.
+ * You have to provide the pointer of the node embedded into the object,
+ * the pointer to the object and the key to use.
+ * \param node Pointer to the node embedded into the object to insert.
+ * \param data Pointer to the object to insert.
+ * \param key Key to use to insert the object.
+ */
+void tommy_trie_insert(tommy_trie* trie, tommy_trie_node* node, void* data, tommy_key_t key);
+
+/**
+ * Searches and removes the first element with the specified key.
+ * If the element is not found, 0 is returned.
+ * If more equal elements are present, the first one is removed.
+ * This operation is faster than calling tommy_trie_bucket() and tommy_trie_remove_existing() separately.
+ * \param key Key of the element to find and remove.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_trie_remove(tommy_trie* trie, tommy_key_t key);
+
+/**
+ * Gets the bucket of the specified key.
+ * The bucket is guaranteed to contain ALL and ONLY the elements with the specified key.
+ * You can access elements in the bucket following the ::next pointer until 0.
+ * \param key Key of the element to find.
+ * \return The head of the bucket, or 0 if empty.
+ */
+tommy_trie_node* tommy_trie_bucket(tommy_trie* trie, tommy_key_t key);
+
+/**
+ * Searches an element in the trie.
+ * You have to provide the key of the element you want to find.
+ * If more elements with the same key are present, the first one is returned.
+ * \param key Key of the element to find.
+ * \return The first element found, or 0 if none.
+ */
+tommy_inline void* tommy_trie_search(tommy_trie* trie, tommy_key_t key)
+{
+	tommy_trie_node* i = tommy_trie_bucket(trie, key);
+
+	if (!i)
+		return 0;
+
+	return i->data;
+}
+
+/**
+ * Removes an element from the trie.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_trie_remove_existing(tommy_trie* trie, tommy_trie_node* node);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_trie_count(tommy_trie* trie)
+{
+	return trie->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_trie_node of the stored elements.
+ */
+tommy_size_t tommy_trie_memory_usage(tommy_trie* trie);
+
+#endif
+
diff --git a/third-party/tommyds/tommytrieinp.c b/third-party/tommyds/tommytrieinp.c
new file mode 100644
index 0000000..26ec2c3
--- /dev/null
+++ b/third-party/tommyds/tommytrieinp.c
@@ -0,0 +1,270 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tommytrieinp.h"
+
+#include <assert.h> /* for assert */
+
+/******************************************************************************/
+/* trie_inplace */
+
+/**
+ * Mask for the inner branches.
+ */
+#define TOMMY_TRIE_INPLACE_TREE_MASK (TOMMY_TRIE_INPLACE_TREE_MAX - 1)
+
+/**
+ * Shift for the first level of branches.
+ */
+#define TOMMY_TRIE_INPLACE_BUCKET_SHIFT (TOMMY_KEY_BIT - TOMMY_TRIE_INPLACE_BUCKET_BIT)
+
+/**
+ * Create a new list with a single element.
+ */
+tommy_inline tommy_trie_inplace_node* tommy_trie_inplace_list_insert_first(tommy_trie_inplace_node* node)
+{
+	/* one element "circular" prev list */
+	node->prev = node;
+
+	/* one element "0 terminated" next list */
+	node->next = 0;
+
+	return node;
+}
+
+/**
+ * Add an element to an existing list.
+ * \note The element is inserted at the end of the list.
+ */
+tommy_inline void tommy_trie_inplace_list_insert_tail_not_empty(tommy_trie_inplace_node* head, tommy_trie_inplace_node* node)
+{
+	/* insert in the list in the last position */
+
+	/* insert in the "circular" prev list */
+	node->prev = head->prev;
+	head->prev = node;
+
+	/* insert in the "0 terminated" next list */
+	node->next = 0;
+	node->prev->next = node;
+}
+
+/**
+ * Remove an element from the list.
+ */
+tommy_inline void tommy_trie_inplace_list_remove(tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* node)
+{
+	tommy_trie_inplace_node* head = *let_ptr;
+
+	/* remove from the "circular" prev list */
+	if (node->next)
+		node->next->prev = node->prev;
+	else
+		head->prev = node->prev; /* the last */
+
+	/* remove from the "0 terminated" next list */
+	if (head == node)
+		*let_ptr = node->next; /* the new first */
+	else
+		node->prev->next = node->next;
+}
+
+void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace)
+{
+	tommy_uint_t i;
+
+	for (i = 0; i < TOMMY_TRIE_INPLACE_BUCKET_MAX; ++i)
+		trie_inplace->bucket[i] = 0;
+
+	trie_inplace->count = 0;
+}
+
+static void trie_inplace_bucket_insert(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* insert, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+
+	node = *let_ptr;
+	while (node && node->key != key) {
+		let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		node = *let_ptr;
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	/* if null, just insert the node */
+	if (!node) {
+		/* setup the node as a list */
+		*let_ptr = tommy_trie_inplace_list_insert_first(insert);
+	} else {
+		/* if it's the same key, insert in the list */
+		tommy_trie_inplace_list_insert_tail_not_empty(node, insert);
+	}
+}
+
+void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key)
+{
+	tommy_trie_inplace_node** let_ptr;
+	tommy_uint_t i;
+
+	node->data = data;
+	node->key = key;
+	/* clear the child pointers */
+	for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+		node->map[i] = 0;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	trie_inplace_bucket_insert(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
+
+	++trie_inplace->count;
+}
+
+static tommy_trie_inplace_node* trie_inplace_bucket_remove(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* remove, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+	int i;
+	tommy_trie_inplace_node** leaf_let_ptr;
+	tommy_trie_inplace_node* leaf;
+
+	node = *let_ptr;
+	while (node && node->key != key) {
+		let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		node = *let_ptr;
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	if (!node)
+		return 0;
+
+	/* if the node to remove is not specified */
+	if (!remove)
+		remove = node; /* remove the first */
+
+	tommy_trie_inplace_list_remove(let_ptr, remove);
+
+	/* if not change in the node, nothing more to do */
+	if (*let_ptr == node)
+		return remove;
+
+	/* if we have a substitute */
+	if (*let_ptr != 0) {
+		/* copy the child pointers to the new one */
+		node = *let_ptr;
+		for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+			node->map[i] = remove->map[i];
+
+		return remove;
+	}
+
+	/* find a leaf */
+	leaf_let_ptr = 0;
+	leaf = remove;
+
+	/* search backward, statistically we have more zeros than ones */
+	i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
+	while (i >= 0) {
+		if (leaf->map[i]) {
+			leaf_let_ptr = &leaf->map[i];
+			leaf = *leaf_let_ptr;
+			i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
+			continue;
+		}
+		--i;
+	}
+
+	/* if it's itself a leaf */
+	if (!leaf_let_ptr)
+		return remove;
+
+	/* remove the leaf */
+	*leaf_let_ptr = 0;
+
+	/* copy the child pointers */
+	for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
+		leaf->map[i] = remove->map[i];
+
+	/* put it in place */
+	*let_ptr = leaf;
+
+	return remove;
+}
+
+void* tommy_trie_inplace_remove(tommy_trie_inplace* trie_inplace, tommy_key_t key)
+{
+	tommy_trie_inplace_node* ret;
+	tommy_trie_inplace_node** let_ptr;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, 0, key);
+
+	if (!ret)
+		return 0;
+
+	--trie_inplace->count;
+
+	return ret->data;
+}
+
+void* tommy_trie_inplace_remove_existing(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node)
+{
+	tommy_trie_inplace_node* ret;
+	tommy_key_t key = node->key;
+	tommy_trie_inplace_node** let_ptr;
+
+	let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+
+	ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
+
+	/* the element removed must match the one passed */
+	assert(ret == node);
+
+	--trie_inplace->count;
+
+	return ret->data;
+}
+
+tommy_trie_inplace_node* tommy_trie_inplace_bucket(tommy_trie_inplace* trie_inplace, tommy_key_t key)
+{
+	tommy_trie_inplace_node* node;
+	tommy_uint_t shift;
+
+	node = trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
+	shift = TOMMY_TRIE_INPLACE_BUCKET_SHIFT;
+
+	while (node && node->key != key) {
+		node = node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
+		shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
+	}
+
+	return node;
+}
+
+tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace* trie_inplace)
+{
+	return tommy_trie_inplace_count(trie_inplace) * (tommy_size_t)sizeof(tommy_trie_inplace_node);
+}
+
diff --git a/third-party/tommyds/tommytrieinp.h b/third-party/tommyds/tommytrieinp.h
new file mode 100644
index 0000000..9448a50
--- /dev/null
+++ b/third-party/tommyds/tommytrieinp.h
@@ -0,0 +1,239 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Inplace trie.
+ *
+ * This trie is a inplace implementation not needing any external allocation.
+ *
+ * Elements are not stored in order, like ::tommy_trie, because some elements
+ * should be used to represent the inner nodes in the trie.
+ *
+ * You can control the number of branches of each node using the ::TOMMY_TRIE_INPLACE_TREE_MAX define.
+ * More branches imply more speed, but a bigger memory occupation.
+ *
+ * Compared to ::tommy_trie you should use a lower number of branches to limit the unused memory
+ * occupation of the leaf nodes. This imply a lower speed, but without the need of an external allocator.
+ *
+ * To initialize the trie you have to call tommy_trie_inplace_init().
+ *
+ * \code
+ * tommy_trie_inplace trie_inplace;
+ *
+ * tommy_trie_inplace_init(&trie_inplace);
+ * \endcode
+ *
+ * To insert elements in the trie you have to call tommy_trie_inplace_insert() for
+ * each element.
+ * In the insertion call you have to specify the address of the node, the
+ * address of the object, and the key value to use.
+ * The address of the object is used to initialize the tommy_node::data field
+ * of the node, and the key to initialize the tommy_node::key field.
+ *
+ * \code
+ * struct object {
+ *     int value;
+ *     // other fields
+ *     tommy_node node;
+ * };
+ *
+ * struct object* obj = malloc(sizeof(struct object)); // creates the object
+ *
+ * obj->value = ...; // initializes the object
+ *
+ * tommy_trie_inplace_insert(&trie_inplace, &obj->node, obj, obj->value); // inserts the object
+ * \endcode
+ *
+ * To find and element in the trie you have to call tommy_trie_inplace_search() providing
+ * the key to search.
+ *
+ * \code
+ * int value_to_find = 1;
+ * struct object* obj = tommy_trie_inplace_search(&trie_inplace, value_to_find);
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ * To iterate over all the elements in the trie with the same key, you have to
+ * use tommy_trie_inplace_bucket() and follow the tommy_node::next pointer until NULL.
+ *
+ * \code
+ * int value_to_find = 1;
+ * tommy_node* i = tommy_trie_inplace_bucket(&trie_inplace, value_to_find);
+ * while (i) {
+ *     struct object* obj = i->data; // gets the object pointer
+ *
+ *     printf("%d\n", obj->value); // process the object
+ *
+ *     i = i->next; // goes to the next element
+ * }
+ * \endcode
+ *
+ * To remove an element from the trie you have to call tommy_trie_inplace_remove()
+ * providing the key to search and remove.
+ *
+ * \code
+ * struct object* obj = tommy_trie_inplace_remove(&trie_inplace, value_to_remove);
+ * if (obj) {
+ *     free(obj); // frees the object allocated memory
+ * }
+ * \endcode
+ *
+ * To destroy the trie you have only to remove all the elements, as the trie is
+ * completely inplace and it doesn't allocate memory.
+ *
+ * Note that you cannot iterate over all the elements in the trie using the
+ * trie itself. You have to insert all the elements also in a ::tommy_list,
+ * and use the list to iterate. See the \ref multiindex example for more detail.
+ */
+
+#ifndef __TOMMYTRIEINP_H
+#define __TOMMYTRIEINP_H
+
+#include "tommytypes.h"
+
+/******************************************************************************/
+/* trie_inplace */
+
+/**
+ * Number of branches on each node. It must be a power of 2.
+ * Suggested values are 2, 4 and 8.
+ * Any node, including leafs, contains a pointer to each branch.
+ */
+#define TOMMY_TRIE_INPLACE_TREE_MAX 4
+
+/** \internal
+ * Number of bits for each branch.
+ */
+#define TOMMY_TRIE_INPLACE_TREE_BIT TOMMY_ILOG2(TOMMY_TRIE_INPLACE_TREE_MAX)
+
+/** \internal
+ * Number of bits of the first level.
+ */
+#define TOMMY_TRIE_INPLACE_BUCKET_BIT ((TOMMY_KEY_BIT % TOMMY_TRIE_INPLACE_TREE_BIT) + 3 * TOMMY_TRIE_INPLACE_TREE_BIT)
+
+/** \internal
+ * Number of branches of the first level.
+ * It's like a inner branch, but bigger to get any remainder bits.
+ */
+#define TOMMY_TRIE_INPLACE_BUCKET_MAX (1 << TOMMY_TRIE_INPLACE_BUCKET_BIT)
+
+/**
+ * Trie node.
+ * This is the node that you have to include inside your objects.
+ */
+typedef struct tommy_trie_inplace_node_struct {
+	struct tommy_trie_inplace_node_struct* next; /**< Next element. 0 if it's the last. */
+	struct tommy_trie_inplace_node_struct* prev; /**< Circular previous element. */
+	void* data; /**< Pointer to the data. */
+	tommy_key_t key; /**< Used to store the key or the hash. */
+	struct tommy_trie_inplace_node_struct* map[TOMMY_TRIE_INPLACE_TREE_MAX]; /** Branches of the node. */
+} tommy_trie_inplace_node;
+
+/**
+ * Trie container type.
+ * \note Don't use internal fields directly, but access the container only using functions.
+ */
+typedef struct tommy_trie_inplace_struct {
+	tommy_trie_inplace_node* bucket[TOMMY_TRIE_INPLACE_BUCKET_MAX]; /**< First tree level. */
+	tommy_count_t count; /**< Number of elements. */
+} tommy_trie_inplace;
+
+/**
+ * Initializes the trie.
+ *
+ * The tries is completely inplace, and it doesn't need to be deinitialized.
+ */
+void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace);
+
+/**
+ * Inserts an element in the trie.
+ */
+void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key);
+
+/**
+ * Searches and removes the first element with the specified key.
+ * If the element is not found, 0 is returned.
+ * If more equal elements are present, the first one is removed.
+ * This operation is faster than calling tommy_trie_inplace_bucket() and tommy_trie_inplace_remove_existing() separately.
+ * \param key Key of the element to find and remove.
+ * \return The removed element, or 0 if not found.
+ */
+void* tommy_trie_inplace_remove(tommy_trie_inplace* trie_inplace, tommy_key_t key);
+
+/**
+ * Gets the bucket of the specified key.
+ * The bucket is guaranteed to contain ALL and ONLY the elements with the specified key.
+ * You can access elements in the bucket following the ::next pointer until 0.
+ * \param key Key of the element to find.
+ * \return The head of the bucket, or 0 if empty.
+ */
+tommy_trie_inplace_node* tommy_trie_inplace_bucket(tommy_trie_inplace* trie_inplace, tommy_key_t key);
+
+/**
+ * Searches an element in the trie.
+ * You have to provide the key of the element you want to find.
+ * If more elements with the same key are present, the first one is returned.
+ * \param key Key of the element to find.
+ * \return The first element found, or 0 if none.
+ */
+tommy_inline void* tommy_trie_inplace_search(tommy_trie_inplace* trie_inplace, tommy_key_t key)
+{
+	tommy_trie_inplace_node* i = tommy_trie_inplace_bucket(trie_inplace, key);
+
+	if (!i)
+		return 0;
+
+	return i->data;
+}
+
+/**
+ * Removes an element from the trie.
+ * You must already have the address of the element to remove.
+ * \return The tommy_node::data field of the node removed.
+ */
+void* tommy_trie_inplace_remove_existing(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node);
+
+/**
+ * Gets the number of elements.
+ */
+tommy_inline tommy_count_t tommy_trie_inplace_count(tommy_trie_inplace* trie_inplace)
+{
+	return trie_inplace->count;
+}
+
+/**
+ * Gets the size of allocated memory.
+ * It includes the size of the ::tommy_inplace_node of the stored elements.
+ */
+tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace* trie_inplace);
+
+#endif
+
diff --git a/third-party/tommyds/tommytypes.h b/third-party/tommyds/tommytypes.h
new file mode 100644
index 0000000..a52d910
--- /dev/null
+++ b/third-party/tommyds/tommytypes.h
@@ -0,0 +1,424 @@
+/*
+ * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** \file
+ * Generic types.
+ */
+
+#ifndef __TOMMYTYPES_H
+#define __TOMMYTYPES_H
+
+/******************************************************************************/
+/* types */
+
+#include <stddef.h>
+
+#if defined(_MSC_VER)
+typedef unsigned tommy_uint32_t; /**< Generic uint32_t type. */
+typedef unsigned _int64 tommy_uint64_t; /**< Generic uint64_t type. */
+typedef size_t tommy_uintptr_t; /**< Generic uintptr_t type. */
+#else
+#include <stdint.h>
+typedef uint32_t tommy_uint32_t; /**< Generic uint32_t type. */
+typedef uint64_t tommy_uint64_t; /**< Generic uint64_t type. */
+typedef uintptr_t tommy_uintptr_t; /**< Generic uintptr_t type. */
+#endif
+typedef size_t tommy_size_t; /**< Generic size_t type. */
+typedef ptrdiff_t tommy_ptrdiff_t; /**< Generic ptrdiff_t type. */
+typedef int tommy_bool_t; /**< Generic boolean type. */
+
+/**
+ * Generic unsigned integer type.
+ *
+ * It has no specific size, as is used to store only small values.
+ * To make the code more efficient, a full 32 bit integer is used.
+ */
+typedef tommy_uint32_t tommy_uint_t;
+
+/**
+ * Generic unsigned integer for counting objects.
+ *
+ * TommyDS doesn't support more than 2^32-1 objects.
+ */
+typedef tommy_uint32_t tommy_count_t;
+
+/** \internal
+ * Type cast required for the C++ compilation.
+ * When compiling in C++ we cannot convert a void* pointer to another pointer.
+ * In such case we need an explicit cast.
+ */
+#ifdef __cplusplus
+#define tommy_cast(type, value) static_cast<type>(value)
+#else
+#define tommy_cast(type, value) (value)
+#endif
+
+/******************************************************************************/
+/* heap */
+
+/* by default uses malloc/calloc/realloc/free */
+
+/**
+ * Generic malloc(), calloc(), realloc() and free() functions.
+ * Redefine them to what you need. By default they map to the C malloc(), calloc(), realloc() and free().
+ */
+#if !defined(tommy_malloc) || !defined(tommy_calloc) || !defined(tommy_realloc) || !defined(tommy_free)
+#include "rtrlib/lib/alloc_utils_private.h"
+#endif
+#if !defined(tommy_malloc)
+#define tommy_malloc lrtr_malloc
+#endif
+#if !defined(tommy_calloc)
+#define tommy_calloc lrtr_calloc
+#endif
+#if !defined(tommy_realloc)
+#define tommy_realloc lrtr_realloc
+#endif
+#if !defined(tommy_free)
+#define tommy_free lrtr_free
+#endif
+
+/******************************************************************************/
+/* modificators */
+
+/** \internal
+ * Definition of the inline keyword if available.
+ */
+#if !defined(tommy_inline)
+#if defined(_MSC_VER) || defined(__GNUC__)
+#define tommy_inline static __inline
+#else
+#define tommy_inline static
+#endif
+#endif
+
+/** \internal
+ * Definition of the restrict keyword if available.
+ */
+#if !defined(tommy_restrict)
+#if __STDC_VERSION__ >= 199901L
+#define tommy_restrict restrict
+#elif defined(_MSC_VER) || defined(__GNUC__)
+#define tommy_restrict __restrict
+#else
+#define tommy_restrict
+#endif
+#endif
+
+/** \internal
+ * Hints the compiler that a condition is likely true.
+ */
+#if !defined(tommy_likely)
+#if defined(__GNUC__)
+#define tommy_likely(x) __builtin_expect(!!(x), 1)
+#else
+#define tommy_likely(x) (x)
+#endif
+#endif
+
+/** \internal
+ * Hints the compiler that a condition is likely false.
+ */
+#if !defined(tommy_unlikely)
+#if defined(__GNUC__)
+#define tommy_unlikely(x) __builtin_expect(!!(x), 0)
+#else
+#define tommy_unlikely(x) (x)
+#endif
+#endif
+
+/******************************************************************************/
+/* key */
+
+/**
+ * Key type used in indexed data structures to store the key or the hash value.
+ */
+typedef tommy_uint32_t tommy_key_t;
+
+/**
+ * Bits into the ::tommy_key_t type.
+ */
+#define TOMMY_KEY_BIT (sizeof(tommy_key_t) * 8)
+
+/******************************************************************************/
+/* node */
+
+/**
+ * Data structure node.
+ * This node type is shared between all the data structures and used to store some
+ * info directly into the objects you want to store.
+ *
+ * A typical declaration is:
+ * \code
+ * struct object {
+ *     tommy_node node;
+ *     // other fields
+ * };
+ * \endcode
+ */
+typedef struct tommy_node_struct {
+	/**
+	 * Next node.
+	 * The tail node has it at 0, like a 0 terminated list.
+	 */
+	struct tommy_node_struct* next;
+
+	/**
+	 * Previous node.
+	 * The head node points to the tail node, like a circular list.
+	 */
+	struct tommy_node_struct* prev;
+
+	/**
+	 * Pointer to the object containing the node.
+	 * This field is initialized when inserting nodes into a data structure.
+	 */
+	void* data;
+
+	/**
+	 * Key used to store the node.
+	 * With hashtables this field is used to store the hash value.
+	 * With lists this field is not used.
+	 */
+	tommy_key_t key;
+} tommy_node;
+
+/******************************************************************************/
+/* compare */
+
+/**
+ * Compare function for elements.
+ * \param obj_a Pointer to the first object to compare.
+ * \param obj_b Pointer to the second object to compare.
+ * \return <0 if the first element is less than the second, ==0 equal, >0 if greather.
+ *
+ * This function is like the C strcmp().
+ *
+ * \code
+ * struct object {
+ *     tommy_node node;
+ *     int value;
+ * };
+ *
+ * int compare(const void* obj_a, const void* obj_b)
+ * {
+ *     if (((const struct object*)obj_a)->value < ((const struct object*)obj_b)->value)
+ *         return -1;
+ *     if (((const struct object*)obj_a)->value > ((const struct object*)obj_b)->value)
+ *         return 1;
+ *     return 0;
+ * }
+ *
+ * tommy_list_sort(&list, compare);
+ * \endcode
+ *
+ */
+typedef int tommy_compare_func(const void* obj_a, const void* obj_b);
+
+/**
+ * Search function for elements.
+ * \param arg Pointer to the value to search as passed at the search function.
+ * \param obj Pointer to the object to compare to.
+ * \return ==0 if the value matches the element. !=0 if different.
+ *
+ * The first argument is a pointer to the value to search exactly
+ * as it's passed at the search function called.
+ * The second argument is a pointer to the object inside the hashtable to compare.
+ *
+ * The return value has to be 0 if the values are equal. != 0 if they are different.
+ *
+ * \code
+ * struct object {
+ *     tommy_node node;
+ *     int value;
+ * };
+ *
+ * int compare(const void* arg, const void* obj)
+ * {
+ *     const int* value_to_find = arg;
+ *     const struct object* object_to_compare = obj;
+ *
+ *     return *value_to_find != object_to_compare->value;
+ * }
+ *
+ * int value_to_find = 1;
+ * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
+ * if (!obj) {
+ *     // not found
+ * } else {
+ *     // found
+ * }
+ * \endcode
+ *
+ */
+typedef int tommy_search_func(const void* arg, const void* obj);
+
+/**
+ * Foreach function.
+ * \param obj Pointer to the object to iterate.
+ *
+ * A typical example is to use free() to deallocate all the objects in a list.
+ * \code
+ * tommy_list_foreach(&list, (tommy_foreach_func*)free);
+ * \endcode
+ */
+typedef void tommy_foreach_func(void* obj);
+
+/**
+ * Foreach function with an argument.
+ * \param arg Pointer to a generic argument.
+ * \param obj Pointer to the object to iterate.
+ */
+typedef void tommy_foreach_arg_func(void* arg, void* obj);
+
+/******************************************************************************/
+/* bit hacks */
+
+#if defined(_MSC_VER) && !defined(__cplusplus)
+#include <intrin.h>
+#pragma intrinsic(_BitScanReverse)
+#pragma intrinsic(_BitScanForward)
+#endif
+
+/** \internal
+ * Integer log2 for constants.
+ * You can use it only for exact power of 2 up to 256.
+ */
+#define TOMMY_ILOG2(value) ((value) == 256 ? 8 : (value) == 128 ? 7 : (value) == 64 ? 6 : (value) == 32 ? 5 : (value) == 16 ? 4 : (value) == 8 ? 3 : (value) == 4 ? 2 : (value) == 2 ? 1 : 0)
+
+/**
+ * Bit scan reverse or integer log2.
+ * Return the bit index of the most significant 1 bit.
+ *
+ * If no bit is set, the result is undefined.
+ * To force a return 0 in this case, you can use tommy_ilog2_u32(value | 1).
+ *
+ * Other interesting ways for bitscan are at:
+ *
+ * Bit Twiddling Hacks
+ * http://graphics.stanford.edu/~seander/bithacks.html
+ *
+ * Chess Programming BitScan
+ * http://chessprogramming.wikispaces.com/BitScan
+ *
+ * \param value Value to scan. 0 is not allowed.
+ * \return The index of the most significant bit set.
+ */
+tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value)
+{
+#if defined(_MSC_VER)
+	unsigned long count;
+	_BitScanReverse(&count, value);
+	return count;
+#elif defined(__GNUC__)
+	/*
+	 * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31"
+	 *
+	 * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x),
+	 * but generates 31 - (bsr(x) xor 31).
+	 *
+	 * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)",
+	 * to allow the double xor to be optimized out.
+	 */
+	return __builtin_clz(value) ^ 31;
+#else
+	/* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */
+	/* from http://graphics.stanford.edu/~seander/bithacks.html */
+	static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {
+		0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+		8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+	};
+
+	value |= value >> 1;
+	value |= value >> 2;
+	value |= value >> 4;
+	value |= value >> 8;
+	value |= value >> 16;
+
+	return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27];
+#endif
+}
+
+/**
+ * Bit scan forward or trailing zero count.
+ * Return the bit index of the least significant 1 bit.
+ *
+ * If no bit is set, the result is undefined.
+ * \param value Value to scan. 0 is not allowed.
+ * \return The index of the least significant bit set.
+ */
+tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
+{
+#if defined(_MSC_VER)
+	unsigned long count;
+	_BitScanForward(&count, value);
+	return count;
+#elif defined(__GNUC__)
+	return __builtin_ctz(value);
+#else
+	/* Count the consecutive zero bits (trailing) on the right with multiply and lookup */
+	/* from http://graphics.stanford.edu/~seander/bithacks.html */
+	static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = {
+		0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+		31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+	};
+
+	return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27];
+#endif
+}
+
+/**
+ * Rounds up to the next power of 2.
+ * For the value 0, the result is undefined.
+ * \return The smallest power of 2 not less than the specified value.
+ */
+tommy_inline tommy_uint32_t tommy_roundup_pow2_u32(tommy_uint32_t value)
+{
+	/* Round up to the next highest power of 2 */
+	/* from http://graphics.stanford.edu/~seander/bithacks.html */
+
+	--value;
+	value |= value >> 1;
+	value |= value >> 2;
+	value |= value >> 4;
+	value |= value >> 8;
+	value |= value >> 16;
+	++value;
+
+	return value;
+}
+
+/**
+ * Check if the specified word has a byte at 0.
+ * \return 0 or 1.
+ */
+tommy_inline int tommy_haszero_u32(tommy_uint32_t value)
+{
+	return ((value - 0x01010101) & ~value & 0x80808080) != 0;
+}
+#endif
+