diff options
Diffstat (limited to '3rdparty')
| -rw-r--r-- | 3rdparty/ezxml/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | 3rdparty/ezxml/ezxml.c | 1015 | ||||
| -rw-r--r-- | 3rdparty/ezxml/ezxml.h | 167 | ||||
| -rw-r--r-- | 3rdparty/stb_ds.h | 1895 |
4 files changed, 0 insertions, 3081 deletions
diff --git a/3rdparty/ezxml/CMakeLists.txt b/3rdparty/ezxml/CMakeLists.txt deleted file mode 100644 index db024d9..0000000 --- a/3rdparty/ezxml/CMakeLists.txt +++ /dev/null @@ -1,4 +0,0 @@ -cmake_minimum_required(VERSION 3.2) -project(ezxml) - -add_library(ezxml STATIC ezxml.c) diff --git a/3rdparty/ezxml/ezxml.c b/3rdparty/ezxml/ezxml.c deleted file mode 100644 index 82b11fb..0000000 --- a/3rdparty/ezxml/ezxml.c +++ /dev/null @@ -1,1015 +0,0 @@ -/* ezxml.c - * - * Copyright 2004-2006 Aaron Voisine <aaron@voisine.org> - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be included - * in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -#include <stdlib.h> -#include <stdio.h> -#include <stdarg.h> -#include <string.h> -#include <ctype.h> -#include <unistd.h> -#include <sys/types.h> -#ifndef EZXML_NOMMAP -#include <sys/mman.h> -#endif // EZXML_NOMMAP -#include <sys/stat.h> -#include "ezxml.h" - -#define EZXML_WS "\t\r\n " // whitespace -#define EZXML_ERRL 128 // maximum error string length - -typedef struct ezxml_root *ezxml_root_t; -struct ezxml_root { // additional data for the root tag - struct ezxml xml; // is a super-struct built on top of ezxml struct - ezxml_t cur; // current xml tree insertion point - char *m; // original xml string - size_t len; // length of allocated memory for mmap, -1 for malloc - char *u; // UTF-8 conversion of string if original was UTF-16 - char *s; // start of work area - char *e; // end of work area - char **ent; // general entities (ampersand sequences) - char ***attr; // default attributes - char ***pi; // processing instructions - short standalone; // non-zero if <?xml standalone="yes"?> - char err[EZXML_ERRL]; // error string -}; - -char *EZXML_NIL[] = { NULL }; // empty, null terminated array of strings - -// returns the first child tag with the given name or NULL if not found -ezxml_t ezxml_child(ezxml_t xml, const char *name) -{ - xml = (xml) ? xml->child : NULL; - while (xml && strcmp(name, xml->name)) xml = xml->sibling; - return xml; -} - -// returns the Nth tag with the same name in the same subsection or NULL if not -// found -ezxml_t ezxml_idx(ezxml_t xml, int idx) -{ - for (; xml && idx; idx--) xml = xml->next; - return xml; -} - -// returns the value of the requested tag attribute or NULL if not found -const char *ezxml_attr(ezxml_t xml, const char *attr) -{ - int i = 0, j = 1; - ezxml_root_t root = (ezxml_root_t)xml; - - if (! xml || ! xml->attr) return NULL; - while (xml->attr[i] && strcmp(attr, xml->attr[i])) i += 2; - if (xml->attr[i]) return xml->attr[i + 1]; // found attribute - - while (root->xml.parent) root = (ezxml_root_t)root->xml.parent; // root tag - for (i = 0; root->attr[i] && strcmp(xml->name, root->attr[i][0]); i++); - if (! root->attr[i]) return NULL; // no matching default attributes - while (root->attr[i][j] && strcmp(attr, root->attr[i][j])) j += 3; - return (root->attr[i][j]) ? root->attr[i][j + 1] : NULL; // found default -} - -// same as ezxml_get but takes an already initialized va_list -ezxml_t ezxml_vget(ezxml_t xml, va_list ap) -{ - char *name = va_arg(ap, char *); - int idx = -1; - - if (name && *name) { - idx = va_arg(ap, int); - xml = ezxml_child(xml, name); - } - return (idx < 0) ? xml : ezxml_vget(ezxml_idx(xml, idx), ap); -} - -// Traverses the xml tree to retrieve a specific subtag. Takes a variable -// length list of tag names and indexes. The argument list must be terminated -// by either an index of -1 or an empty string tag name. Example: -// title = ezxml_get(library, "shelf", 0, "book", 2, "title", -1); -// This retrieves the title of the 3rd book on the 1st shelf of library. -// Returns NULL if not found. -ezxml_t ezxml_get(ezxml_t xml, ...) -{ - va_list ap; - ezxml_t r; - - va_start(ap, xml); - r = ezxml_vget(xml, ap); - va_end(ap); - return r; -} - -// returns a null terminated array of processing instructions for the given -// target -const char **ezxml_pi(ezxml_t xml, const char *target) -{ - ezxml_root_t root = (ezxml_root_t)xml; - int i = 0; - - if (! root) return (const char **)EZXML_NIL; - while (root->xml.parent) root = (ezxml_root_t)root->xml.parent; // root tag - while (root->pi[i] && strcmp(target, root->pi[i][0])) i++; // find target - return (const char **)((root->pi[i]) ? root->pi[i] + 1 : EZXML_NIL); -} - -// set an error string and return root -ezxml_t ezxml_err(ezxml_root_t root, char *s, const char *err, ...) -{ - va_list ap; - int line = 1; - char *t, fmt[EZXML_ERRL]; - - for (t = root->s; t < s; t++) if (*t == '\n') line++; - snprintf(fmt, EZXML_ERRL, "[error near line %d]: %s", line, err); - - va_start(ap, err); - vsnprintf(root->err, EZXML_ERRL, fmt, ap); - va_end(ap); - - return &root->xml; -} - -// Recursively decodes entity and character references and normalizes new lines -// ent is a null terminated array of alternating entity names and values. set t -// to '&' for general entity decoding, '%' for parameter entity decoding, 'c' -// for cdata sections, ' ' for attribute normalization, or '*' for non-cdata -// attribute normalization. Returns s, or if the decoded string is longer than -// s, returns a malloced string that must be freed. -char *ezxml_decode(char *s, char **ent, char t) -{ - char *e, *r = s, *m = s; - long b, c, d, l; - - for (; *s; s++) { // normalize line endings - while (*s == '\r') { - *(s++) = '\n'; - if (*s == '\n') memmove(s, (s + 1), strlen(s)); - } - } - - for (s = r; ; ) { - while (*s && *s != '&' && (*s != '%' || t != '%') && !isspace(*s)) s++; - - if (! *s) break; - else if (t != 'c' && ! strncmp(s, "&#", 2)) { // character reference - if (s[2] == 'x') c = strtol(s + 3, &e, 16); // base 16 - else c = strtol(s + 2, &e, 10); // base 10 - if (! c || *e != ';') { s++; continue; } // not a character ref - - if (c < 0x80) *(s++) = c; // US-ASCII subset - else { // multi-byte UTF-8 sequence - for (b = 0, d = c; d; d /= 2) b++; // number of bits in c - b = (b - 2) / 5; // number of bytes in payload - *(s++) = (0xFF << (7 - b)) | (c >> (6 * b)); // head - while (b) *(s++) = 0x80 | ((c >> (6 * --b)) & 0x3F); // payload - } - - memmove(s, strchr(s, ';') + 1, strlen(strchr(s, ';'))); - } - else if ((*s == '&' && (t == '&' || t == ' ' || t == '*')) || - (*s == '%' && t == '%')) { // entity reference - for (b = 0; ent[b] && strncmp(s + 1, ent[b], strlen(ent[b])); - b += 2); // find entity in entity list - - if (ent[b++]) { // found a match - if ((c = strlen(ent[b])) - 1 > (e = strchr(s, ';')) - s) { - l = (d = (s - r)) + c + strlen(e); // new length - r = (r == m) ? strcpy(malloc(l), r) : realloc(r, l); - e = strchr((s = r + d), ';'); // fix up pointers - } - - memmove(s + c, e + 1, strlen(e)); // shift rest of string - strncpy(s, ent[b], c); // copy in replacement text - } - else s++; // not a known entity - } - else if ((t == ' ' || t == '*') && isspace(*s)) *(s++) = ' '; - else s++; // no decoding needed - } - - if (t == '*') { // normalize spaces for non-cdata attributes - for (s = r; *s; s++) { - if ((l = strspn(s, " "))) memmove(s, s + l, strlen(s + l) + 1); - while (*s && *s != ' ') s++; - } - if (--s >= r && *s == ' ') *s = '\0'; // trim any trailing space - } - return r; -} - -// called when parser finds start of new tag -void ezxml_open_tag(ezxml_root_t root, char *name, char **attr) -{ - ezxml_t xml = root->cur; - - if (xml->name) xml = ezxml_add_child(xml, name, strlen(xml->txt)); - else xml->name = name; // first open tag - - xml->attr = attr; - root->cur = xml; // update tag insertion point -} - -// called when parser finds character content between open and closing tag -void ezxml_char_content(ezxml_root_t root, char *s, size_t len, char t) -{ - ezxml_t xml = root->cur; - char *m = s; - size_t l; - - if (! xml || ! xml->name || ! len) return; // sanity check - - s[len] = '\0'; // null terminate text (calling functions anticipate this) - len = strlen(s = ezxml_decode(s, root->ent, t)) + 1; - - if (! *(xml->txt)) xml->txt = s; // initial character content - else { // allocate our own memory and make a copy - xml->txt = (xml->flags & EZXML_TXTM) // allocate some space - ? realloc(xml->txt, (l = strlen(xml->txt)) + len) - : strcpy(malloc((l = strlen(xml->txt)) + len), xml->txt); - strcpy(xml->txt + l, s); // add new char content - if (s != m) free(s); // free s if it was malloced by ezxml_decode() - } - - if (xml->txt != m) ezxml_set_flag(xml, EZXML_TXTM); -} - -// called when parser finds closing tag -ezxml_t ezxml_close_tag(ezxml_root_t root, char *name, char *s) -{ - if (! root->cur || ! root->cur->name || strcmp(name, root->cur->name)) - return ezxml_err(root, s, "unexpected closing tag </%s>", name); - - root->cur = root->cur->parent; - return NULL; -} - -// checks for circular entity references, returns non-zero if no circular -// references are found, zero otherwise -int ezxml_ent_ok(char *name, char *s, char **ent) -{ - int i; - - for (; ; s++) { - while (*s && *s != '&') s++; // find next entity reference - if (! *s) return 1; - if (! strncmp(s + 1, name, strlen(name))) return 0; // circular ref. - for (i = 0; ent[i] && strncmp(ent[i], s + 1, strlen(ent[i])); i += 2); - if (ent[i] && ! ezxml_ent_ok(name, ent[i + 1], ent)) return 0; - } -} - -// called when the parser finds a processing instruction -void ezxml_proc_inst(ezxml_root_t root, char *s, size_t len) -{ - int i = 0, j = 1; - char *target = s; - - s[len] = '\0'; // null terminate instruction - if (*(s += strcspn(s, EZXML_WS))) { - *s = '\0'; // null terminate target - s += strspn(s + 1, EZXML_WS) + 1; // skip whitespace after target - } - - if (! strcmp(target, "xml")) { // <?xml ... ?> - if ((s = strstr(s, "standalone")) && ! strncmp(s + strspn(s + 10, - EZXML_WS "='\"") + 10, "yes", 3)) root->standalone = 1; - return; - } - - if (! root->pi[0]) *(root->pi = malloc(sizeof(char **))) = NULL; //first pi - - while (root->pi[i] && strcmp(target, root->pi[i][0])) i++; // find target - if (! root->pi[i]) { // new target - root->pi = realloc(root->pi, sizeof(char **) * (i + 2)); - root->pi[i] = malloc(sizeof(char *) * 3); - root->pi[i][0] = target; - root->pi[i][1] = (char *)(root->pi[i + 1] = NULL); // terminate pi list - root->pi[i][2] = strdup(""); // empty document position list - } - - while (root->pi[i][j]) j++; // find end of instruction list for this target - root->pi[i] = realloc(root->pi[i], sizeof(char *) * (j + 3)); - root->pi[i][j + 2] = realloc(root->pi[i][j + 1], j + 1); - strcpy(root->pi[i][j + 2] + j - 1, (root->xml.name) ? ">" : "<"); - root->pi[i][j + 1] = NULL; // null terminate pi list for this target - root->pi[i][j] = s; // set instruction -} - -// called when the parser finds an internal doctype subset -short ezxml_internal_dtd(ezxml_root_t root, char *s, size_t len) -{ - char q, *c, *t, *n = NULL, *v, **ent, **pe; - int i, j; - - pe = memcpy(malloc(sizeof(EZXML_NIL)), EZXML_NIL, sizeof(EZXML_NIL)); - - for (s[len] = '\0'; s; ) { - while (*s && *s != '<' && *s != '%') s++; // find next declaration - - if (! *s) break; - else if (! strncmp(s, "<!ENTITY", 8)) { // parse entity definitions - c = s += strspn(s + 8, EZXML_WS) + 8; // skip white space separator - n = s + strspn(s, EZXML_WS "%"); // find name - *(s = n + strcspn(n, EZXML_WS)) = ';'; // append ; to name - - v = s + strspn(s + 1, EZXML_WS) + 1; // find value - if ((q = *(v++)) != '"' && q != '\'') { // skip externals - s = strchr(s, '>'); - continue; - } - - for (i = 0, ent = (*c == '%') ? pe : root->ent; ent[i]; i++); - ent = realloc(ent, (i + 3) * sizeof(char *)); // space for next ent - if (*c == '%') pe = ent; - else root->ent = ent; - - *(++s) = '\0'; // null terminate name - if ((s = strchr(v, q))) *(s++) = '\0'; // null terminate value - ent[i + 1] = ezxml_decode(v, pe, '%'); // set value - ent[i + 2] = NULL; // null terminate entity list - if (! ezxml_ent_ok(n, ent[i + 1], ent)) { // circular reference - if (ent[i + 1] != v) free(ent[i + 1]); - ezxml_err(root, v, "circular entity declaration &%s", n); - break; - } - else ent[i] = n; // set entity name - } - else if (! strncmp(s, "<!ATTLIST", 9)) { // parse default attributes - t = s + strspn(s + 9, EZXML_WS) + 9; // skip whitespace separator - if (! *t) { ezxml_err(root, t, "unclosed <!ATTLIST"); break; } - if (*(s = t + strcspn(t, EZXML_WS ">")) == '>') continue; - else *s = '\0'; // null terminate tag name - for (i = 0; root->attr[i] && strcmp(n, root->attr[i][0]); i++); - - while (*(n = ++s + strspn(s, EZXML_WS)) && *n != '>') { - if (*(s = n + strcspn(n, EZXML_WS))) *s = '\0'; // attr name - else { ezxml_err(root, t, "malformed <!ATTLIST"); break; } - - s += strspn(s + 1, EZXML_WS) + 1; // find next token - c = (strncmp(s, "CDATA", 5)) ? "*" : " "; // is it cdata? - if (! strncmp(s, "NOTATION", 8)) - s += strspn(s + 8, EZXML_WS) + 8; - s = (*s == '(') ? strchr(s, ')') : s + strcspn(s, EZXML_WS); - if (! s) { ezxml_err(root, t, "malformed <!ATTLIST"); break; } - - s += strspn(s, EZXML_WS ")"); // skip white space separator - if (! strncmp(s, "#FIXED", 6)) - s += strspn(s + 6, EZXML_WS) + 6; - if (*s == '#') { // no default value - s += strcspn(s, EZXML_WS ">") - 1; - if (*c == ' ') continue; // cdata is default, nothing to do - v = NULL; - } - else if ((*s == '"' || *s == '\'') && // default value - (s = strchr(v = s + 1, *s))) *s = '\0'; - else { ezxml_err(root, t, "malformed <!ATTLIST"); break; } - - if (! root->attr[i]) { // new tag name - root->attr = (! i) ? malloc(2 * sizeof(char **)) - : realloc(root->attr, - (i + 2) * sizeof(char **)); - root->attr[i] = malloc(2 * sizeof(char *)); - root->attr[i][0] = t; // set tag name - root->attr[i][1] = (char *)(root->attr[i + 1] = NULL); - } - - for (j = 1; root->attr[i][j]; j += 3); // find end of list - root->attr[i] = realloc(root->attr[i], - (j + 4) * sizeof(char *)); - - root->attr[i][j + 3] = NULL; // null terminate list - root->attr[i][j + 2] = c; // is it cdata? - root->attr[i][j + 1] = (v) ? ezxml_decode(v, root->ent, *c) - : NULL; - root->attr[i][j] = n; // attribute name - } - } - else if (! strncmp(s, "<!--", 4)) s = strstr(s + 4, "-->"); // comments - else if (! strncmp(s, "<?", 2)) { // processing instructions - if ((s = strstr(c = s + 2, "?>"))) - ezxml_proc_inst(root, c, s++ - c); - } - else if (*s == '<') s = strchr(s, '>'); // skip other declarations - else if (*(s++) == '%' && ! root->standalone) break; - } - - free(pe); - return ! *root->err; -} - -// Converts a UTF-16 string to UTF-8. Returns a new string that must be freed -// or NULL if no conversion was needed. -char *ezxml_str2utf8(char **s, size_t *len) -{ - char *u; - size_t l = 0, sl, max = *len; - long c, d; - int b, be = (**s == '\xFE') ? 1 : (**s == '\xFF') ? 0 : -1; - - if (be == -1) return NULL; // not UTF-16 - - u = malloc(max); - for (sl = 2; sl < *len - 1; sl += 2) { - c = (be) ? (((*s)[sl] & 0xFF) << 8) | ((*s)[sl + 1] & 0xFF) //UTF-16BE - : (((*s)[sl + 1] & 0xFF) << 8) | ((*s)[sl] & 0xFF); //UTF-16LE - if (c >= 0xD800 && c <= 0xDFFF && (sl += 2) < *len - 1) { // high-half - d = (be) ? (((*s)[sl] & 0xFF) << 8) | ((*s)[sl + 1] & 0xFF) - : (((*s)[sl + 1] & 0xFF) << 8) | ((*s)[sl] & 0xFF); - c = (((c & 0x3FF) << 10) | (d & 0x3FF)) + 0x10000; - } - - while (l + 6 > max) u = realloc(u, max += EZXML_BUFSIZE); - if (c < 0x80) u[l++] = c; // US-ASCII subset - else { // multi-byte UTF-8 sequence - for (b = 0, d = c; d; d /= 2) b++; // bits in c - b = (b - 2) / 5; // bytes in payload - u[l++] = (0xFF << (7 - b)) | (c >> (6 * b)); // head - while (b) u[l++] = 0x80 | ((c >> (6 * --b)) & 0x3F); // payload - } - } - return *s = realloc(u, *len = l); -} - -// frees a tag attribute list -void ezxml_free_attr(char **attr) { - int i = 0; - char *m; - - if (! attr || attr == EZXML_NIL) return; // nothing to free - while (attr[i]) i += 2; // find end of attribute list - m = attr[i + 1]; // list of which names and values are malloced - for (i = 0; m[i]; i++) { - if (m[i] & EZXML_NAMEM) free(attr[i * 2]); - if (m[i] & EZXML_TXTM) free(attr[(i * 2) + 1]); - } - free(m); - free(attr); -} - -// parse the given xml string and return an ezxml structure -ezxml_t ezxml_parse_str(char *s, size_t len) -{ - ezxml_root_t root = (ezxml_root_t)ezxml_new(NULL); - char q, e, *d, **attr, **a = NULL; // initialize a to avoid compile warning - int l, i, j; - - root->m = s; - if (! len) return ezxml_err(root, NULL, "root tag missing"); - root->u = ezxml_str2utf8(&s, &len); // convert utf-16 to utf-8 - root->e = (root->s = s) + len; // record start and end of work area - - e = s[len - 1]; // save end char - s[len - 1] = '\0'; // turn end char into null terminator - - while (*s && *s != '<') s++; // find first tag - if (! *s) return ezxml_err(root, s, "root tag missing"); - - for (; ; ) { - attr = (char **)EZXML_NIL; - d = ++s; - - if (isalpha(*s) || *s == '_' || *s == ':' || *s < '\0') { // new tag - if (! root->cur) - return ezxml_err(root, d, "markup outside of root element"); - - s += strcspn(s, EZXML_WS "/>"); - while (isspace(*s)) *(s++) = '\0'; // null terminate tag name - - if (*s && *s != '/' && *s != '>') // find tag in default attr list - for (i = 0; (a = root->attr[i]) && strcmp(a[0], d); i++); - - for (l = 0; *s && *s != '/' && *s != '>'; l += 2) { // new attrib - attr = (l) ? realloc(attr, (l + 4) * sizeof(char *)) - : malloc(4 * sizeof(char *)); // allocate space - attr[l + 3] = (l) ? realloc(attr[l + 1], (l / 2) + 2) - : malloc(2); // mem for list of maloced vals - strcpy(attr[l + 3] + (l / 2), " "); // value is not malloced - attr[l + 2] = NULL; // null terminate list - attr[l + 1] = ""; // temporary attribute value - attr[l] = s; // set attribute name - - s += strcspn(s, EZXML_WS "=/>"); - if (*s == '=' || isspace(*s)) { - *(s++) = '\0'; // null terminate tag attribute name - q = *(s += strspn(s, EZXML_WS "=")); - if (q == '"' || q == '\'') { // attribute value - attr[l + 1] = ++s; - while (*s && *s != q) s++; - if (*s) *(s++) = '\0'; // null terminate attribute val - else { - ezxml_free_attr(attr); - return ezxml_err(root, d, "missing %c", q); - } - - for (j = 1; a && a[j] && strcmp(a[j], attr[l]); j +=3); - attr[l + 1] = ezxml_decode(attr[l + 1], root->ent, (a - && a[j]) ? *a[j + 2] : ' '); - if (attr[l + 1] < d || attr[l + 1] > s) - attr[l + 3][l / 2] = EZXML_TXTM; // value malloced - } - } - while (isspace(*s)) s++; - } - - if (*s == '/') { // self closing tag - *(s++) = '\0'; - if ((*s && *s != '>') || (! *s && e != '>')) { - if (l) ezxml_free_attr(attr); - return ezxml_err(root, d, "missing >"); - } - ezxml_open_tag(root, d, attr); - ezxml_close_tag(root, d, s); - } - else if ((q = *s) == '>' || (! *s && e == '>')) { // open tag - *s = '\0'; // temporarily null terminate tag name - ezxml_open_tag(root, d, attr); - *s = q; - } - else { - if (l) ezxml_free_attr(attr); - return ezxml_err(root, d, "missing >"); - } - } - else if (*s == '/') { // close tag - s += strcspn(d = s + 1, EZXML_WS ">") + 1; - if (! (q = *s) && e != '>') return ezxml_err(root, d, "missing >"); - *s = '\0'; // temporarily null terminate tag name - if (ezxml_close_tag(root, d, s)) return &root->xml; - if (isspace(*s = q)) s += strspn(s, EZXML_WS); - } - else if (! strncmp(s, "!--", 3)) { // xml comment - if (! (s = strstr(s + 3, "--")) || (*(s += 2) != '>' && *s) || - (! *s && e != '>')) return ezxml_err(root, d, "unclosed <!--"); - } - else if (! strncmp(s, "![CDATA[", 8)) { // cdata - if ((s = strstr(s, "]]>"))) - ezxml_char_content(root, d + 8, (s += 2) - d - 10, 'c'); - else return ezxml_err(root, d, "unclosed <![CDATA["); - } - else if (! strncmp(s, "!DOCTYPE", 8)) { // dtd - for (l = 0; *s && ((! l && *s != '>') || (l && (*s != ']' || - *(s + strspn(s + 1, EZXML_WS) + 1) != '>'))); - l = (*s == '[') ? 1 : l) s += strcspn(s + 1, "[]>") + 1; - if (! *s && e != '>') - return ezxml_err(root, d, "unclosed <!DOCTYPE"); - d = (l) ? strchr(d, '[') + 1 : d; - if (l && ! ezxml_internal_dtd(root, d, s++ - d)) return &root->xml; - } - else if (*s == '?') { // <?...?> processing instructions - do { s = strchr(s, '?'); } while (s && *(++s) && *s != '>'); - if (! s || (! *s && e != '>')) - return ezxml_err(root, d, "unclosed <?"); - else ezxml_proc_inst(root, d + 1, s - d - 2); - } - else return ezxml_err(root, d, "unexpected <"); - - if (! s || ! *s) break; - *s = '\0'; - d = ++s; - if (*s && *s != '<') { // tag character content - while (*s && *s != '<') s++; - if (*s) ezxml_char_content(root, d, s - d, '&'); - else break; - } - else if (! *s) break; - } - - if (! root->cur) return &root->xml; - else if (! root->cur->name) return ezxml_err(root, d, "root tag missing"); - else return ezxml_err(root, d, "unclosed tag <%s>", root->cur->name); -} - -// Wrapper for ezxml_parse_str() that accepts a file stream. Reads the entire -// stream into memory and then parses it. For xml files, use ezxml_parse_file() -// or ezxml_parse_fd() -ezxml_t ezxml_parse_fp(FILE *fp) -{ - ezxml_root_t root; - size_t l, len = 0; - char *s; - - if (! (s = malloc(EZXML_BUFSIZE))) return NULL; - do { - len += (l = fread((s + len), 1, EZXML_BUFSIZE, fp)); - if (l == EZXML_BUFSIZE) s = realloc(s, len + EZXML_BUFSIZE); - } while (s && l == EZXML_BUFSIZE); - - if (! s) return NULL; - root = (ezxml_root_t)ezxml_parse_str(s, len); - root->len = -1; // so we know to free s in ezxml_free() - return &root->xml; -} - -// A wrapper for ezxml_parse_str() that accepts a file descriptor. First -// attempts to mem map the file. Failing that, reads the file into memory. -// Returns NULL on failure. -ezxml_t ezxml_parse_fd(int fd) -{ - ezxml_root_t root; - struct stat st; - size_t l; - void *m; - - if (fd < 0) return NULL; - fstat(fd, &st); - -#ifndef EZXML_NOMMAP - l = (st.st_size + sysconf(_SC_PAGESIZE) - 1) & ~(sysconf(_SC_PAGESIZE) -1); - if ((m = mmap(NULL, l, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0)) != - MAP_FAILED) { - madvise(m, l, MADV_SEQUENTIAL); // optimize for sequential access - root = (ezxml_root_t)ezxml_parse_str(m, st.st_size); - madvise(m, root->len = l, MADV_NORMAL); // put it back to normal - } - else { // mmap failed, read file into memory -#endif // EZXML_NOMMAP - l = read(fd, m = malloc(st.st_size), st.st_size); - root = (ezxml_root_t)ezxml_parse_str(m, l); - root->len = -1; // so we know to free s in ezxml_free() -#ifndef EZXML_NOMMAP - } -#endif // EZXML_NOMMAP - return &root->xml; -} - -// a wrapper for ezxml_parse_fd that accepts a file name -ezxml_t ezxml_parse_file(const char *file) -{ - int fd = open(file, O_RDONLY, 0); - ezxml_t xml = ezxml_parse_fd(fd); - - if (fd >= 0) close(fd); - return xml; -} - -// Encodes ampersand sequences appending the results to *dst, reallocating *dst -// if length excedes max. a is non-zero for attribute encoding. Returns *dst -char *ezxml_ampencode(const char *s, size_t len, char **dst, size_t *dlen, - size_t *max, short a) -{ - const char *e; - - for (e = s + len; s != e; s++) { - while (*dlen + 10 > *max) *dst = realloc(*dst, *max += EZXML_BUFSIZE); - - switch (*s) { - case '\0': return *dst; - case '&': *dlen += sprintf(*dst + *dlen, "&"); break; - case '<': *dlen += sprintf(*dst + *dlen, "<"); break; - case '>': *dlen += sprintf(*dst + *dlen, ">"); break; - case '"': *dlen += sprintf(*dst + *dlen, (a) ? """ : "\""); break; - case '\n': *dlen += sprintf(*dst + *dlen, (a) ? "
" : "\n"); break; - case '\t': *dlen += sprintf(*dst + *dlen, (a) ? "	" : "\t"); break; - case '\r': *dlen += sprintf(*dst + *dlen, "
"); break; - default: (*dst)[(*dlen)++] = *s; - } - } - return *dst; -} - -// Recursively converts each tag to xml appending it to *s. Reallocates *s if -// its length excedes max. start is the location of the previous tag in the -// parent tag's character content. Returns *s. -char *ezxml_toxml_r(ezxml_t xml, char **s, size_t *len, size_t *max, - size_t start, char ***attr) -{ - int i, j; - char *txt = (xml->parent) ? xml->parent->txt : ""; - size_t off = 0; - - // parent character content up to this tag - *s = ezxml_ampencode(txt + start, xml->off - start, s, len, max, 0); - - while (*len + strlen(xml->name) + 4 > *max) // reallocate s - *s = realloc(*s, *max += EZXML_BUFSIZE); - - *len += sprintf(*s + *len, "<%s", xml->name); // open tag - for (i = 0; xml->attr[i]; i += 2) { // tag attributes - if (ezxml_attr(xml, xml->attr[i]) != xml->attr[i + 1]) continue; - while (*len + strlen(xml->attr[i]) + 7 > *max) // reallocate s - *s = realloc(*s, *max += EZXML_BUFSIZE); - - *len += sprintf(*s + *len, " %s=\"", xml->attr[i]); - ezxml_ampencode(xml->attr[i + 1], -1, s, len, max, 1); - *len += sprintf(*s + *len, "\""); - } - - for (i = 0; attr[i] && strcmp(attr[i][0], xml->name); i++); - for (j = 1; attr[i] && attr[i][j]; j += 3) { // default attributes - if (! attr[i][j + 1] || ezxml_attr(xml, attr[i][j]) != attr[i][j + 1]) - continue; // skip duplicates and non-values - while (*len + strlen(attr[i][j]) + 7 > *max) // reallocate s - *s = realloc(*s, *max += EZXML_BUFSIZE); - - *len += sprintf(*s + *len, " %s=\"", attr[i][j]); - ezxml_ampencode(attr[i][j + 1], -1, s, len, max, 1); - *len += sprintf(*s + *len, "\""); - } - *len += sprintf(*s + *len, ">"); - - *s = (xml->child) ? ezxml_toxml_r(xml->child, s, len, max, 0, attr) //child - : ezxml_ampencode(xml->txt, -1, s, len, max, 0); //data - - while (*len + strlen(xml->name) + 4 > *max) // reallocate s - *s = realloc(*s, *max += EZXML_BUFSIZE); - - *len += sprintf(*s + *len, "</%s>", xml->name); // close tag - - while (txt[off] && off < xml->off) off++; // make sure off is within bounds - return (xml->ordered) ? ezxml_toxml_r(xml->ordered, s, len, max, off, attr) - : ezxml_ampencode(txt + off, -1, s, len, max, 0); -} - -// Converts an ezxml structure back to xml. Returns a string of xml data that -// must be freed. -char *ezxml_toxml(ezxml_t xml) -{ - ezxml_t p = (xml) ? xml->parent : NULL, o = (xml) ? xml->ordered : NULL; - ezxml_root_t root = (ezxml_root_t)xml; - size_t len = 0, max = EZXML_BUFSIZE; - char *s = strcpy(malloc(max), ""), *t, *n; - int i, j, k; - - if (! xml || ! xml->name) return realloc(s, len + 1); - while (root->xml.parent) root = (ezxml_root_t)root->xml.parent; // root tag - - for (i = 0; ! p && root->pi[i]; i++) { // pre-root processing instructions - for (k = 2; root->pi[i][k - 1]; k++); - for (j = 1; (n = root->pi[i][j]); j++) { - if (root->pi[i][k][j - 1] == '>') continue; // not pre-root - while (len + strlen(t = root->pi[i][0]) + strlen(n) + 7 > max) - s = realloc(s, max += EZXML_BUFSIZE); - len += sprintf(s + len, "<?%s%s%s?>\n", t, *n ? " " : "", n); - } - } - - xml->parent = xml->ordered = NULL; - s = ezxml_toxml_r(xml, &s, &len, &max, 0, root->attr); - xml->parent = p; - xml->ordered = o; - - for (i = 0; ! p && root->pi[i]; i++) { // post-root processing instructions - for (k = 2; root->pi[i][k - 1]; k++); - for (j = 1; (n = root->pi[i][j]); j++) { - if (root->pi[i][k][j - 1] == '<') continue; // not post-root - while (len + strlen(t = root->pi[i][0]) + strlen(n) + 7 > max) - s = realloc(s, max += EZXML_BUFSIZE); - len += sprintf(s + len, "\n<?%s%s%s?>", t, *n ? " " : "", n); - } - } - return realloc(s, len + 1); -} - -// free the memory allocated for the ezxml structure -void ezxml_free(ezxml_t xml) -{ - ezxml_root_t root = (ezxml_root_t)xml; - int i, j; - char **a, *s; - - if (! xml) return; - ezxml_free(xml->child); - ezxml_free(xml->ordered); - - if (! xml->parent) { // free root tag allocations - for (i = 10; root->ent[i]; i += 2) // 0 - 9 are default entites (<>&"') - if ((s = root->ent[i + 1]) < root->s || s > root->e) free(s); - free(root->ent); // free list of general entities - - for (i = 0; (a = root->attr[i]); i++) { - for (j = 1; a[j++]; j += 2) // free malloced attribute values - if (a[j] && (a[j] < root->s || a[j] > root->e)) free(a[j]); - free(a); - } - if (root->attr[0]) free(root->attr); // free default attribute list - - for (i = 0; root->pi[i]; i++) { - for (j = 1; root->pi[i][j]; j++); - free(root->pi[i][j + 1]); - free(root->pi[i]); - } - if (root->pi[0]) free(root->pi); // free processing instructions - - if (root->len == -1) free(root->m); // malloced xml data -#ifndef EZXML_NOMMAP - else if (root->len) munmap(root->m, root->len); // mem mapped xml data -#endif // EZXML_NOMMAP - if (root->u) free(root->u); // utf8 conversion - } - - ezxml_free_attr(xml->attr); // tag attributes - if ((xml->flags & EZXML_TXTM)) free(xml->txt); // character content - if ((xml->flags & EZXML_NAMEM)) free(xml->name); // tag name - free(xml); -} - -// return parser error message or empty string if none -const char *ezxml_error(ezxml_t xml) -{ - while (xml && xml->parent) xml = xml->parent; // find root tag - return (xml) ? ((ezxml_root_t)xml)->err : ""; -} - -// returns a new empty ezxml structure with the given root tag name -ezxml_t ezxml_new(const char *name) -{ - static char *ent[] = { "lt;", "<", "gt;", ">", "quot;", """, - "apos;", "'", "amp;", "&", NULL }; - ezxml_root_t root = (ezxml_root_t)memset(malloc(sizeof(struct ezxml_root)), - '\0', sizeof(struct ezxml_root)); - root->xml.name = (char *)name; - root->cur = &root->xml; - strcpy(root->err, root->xml.txt = ""); - root->ent = memcpy(malloc(sizeof(ent)), ent, sizeof(ent)); - root->attr = root->pi = (char ***)(root->xml.attr = EZXML_NIL); - return &root->xml; -} - -// inserts an existing tag into an ezxml structure -ezxml_t ezxml_insert(ezxml_t xml, ezxml_t dest, size_t off) -{ - ezxml_t cur, prev, head; - - xml->next = xml->sibling = xml->ordered = NULL; - xml->off = off; - xml->parent = dest; - - if ((head = dest->child)) { // already have sub tags - if (head->off <= off) { // not first subtag - for (cur = head; cur->ordered && cur->ordered->off <= off; - cur = cur->ordered); - xml->ordered = cur->ordered; - cur->ordered = xml; - } - else { // first subtag - xml->ordered = head; - dest->child = xml; - } - - for (cur = head, prev = NULL; cur && strcmp(cur->name, xml->name); - prev = cur, cur = cur->sibling); // find tag type - if (cur && cur->off <= off) { // not first of type - while (cur->next && cur->next->off <= off) cur = cur->next; - xml->next = cur->next; - cur->next = xml; - } - else { // first tag of this type - if (prev && cur) prev->sibling = cur->sibling; // remove old first - xml->next = cur; // old first tag is now next - for (cur = head, prev = NULL; cur && cur->off <= off; - prev = cur, cur = cur->sibling); // new sibling insert point - xml->sibling = cur; - if (prev) prev->sibling = xml; - } - } - else dest->child = xml; // only sub tag - - return xml; -} - -// Adds a child tag. off is the offset of the child tag relative to the start -// of the parent tag's character content. Returns the child tag. -ezxml_t ezxml_add_child(ezxml_t xml, const char *name, size_t off) -{ - ezxml_t child; - - if (! xml) return NULL; - child = (ezxml_t)memset(malloc(sizeof(struct ezxml)), '\0', - sizeof(struct ezxml)); - child->name = (char *)name; - child->attr = EZXML_NIL; - child->txt = ""; - - return ezxml_insert(child, xml, off); -} - -// sets the character content for the given tag and returns the tag -ezxml_t ezxml_set_txt(ezxml_t xml, const char *txt) -{ - if (! xml) return NULL; - if (xml->flags & EZXML_TXTM) free(xml->txt); // existing txt was malloced - xml->flags &= ~EZXML_TXTM; - xml->txt = (char *)txt; - return xml; -} - -// Sets the given tag attribute or adds a new attribute if not found. A value -// of NULL will remove the specified attribute. Returns the tag given. -ezxml_t ezxml_set_attr(ezxml_t xml, const char *name, const char *value) -{ - int l = 0, c; - - if (! xml) return NULL; - while (xml->attr[l] && strcmp(xml->attr[l], name)) l += 2; - if (! xml->attr[l]) { // not found, add as new attribute - if (! value) return xml; // nothing to do - if (xml->attr == EZXML_NIL) { // first attribute - xml->attr = malloc(4 * sizeof(char *)); - xml->attr[1] = strdup(""); // empty list of malloced names/vals - } - else xml->attr = realloc(xml->attr, (l + 4) * sizeof(char *)); - - xml->attr[l] = (char *)name; // set attribute name - xml->attr[l + 2] = NULL; // null terminate attribute list - xml->attr[l + 3] = realloc(xml->attr[l + 1], - (c = strlen(xml->attr[l + 1])) + 2); - strcpy(xml->attr[l + 3] + c, " "); // set name/value as not malloced - if (xml->flags & EZXML_DUP) xml->attr[l + 3][c] = EZXML_NAMEM; - } - else if (xml->flags & EZXML_DUP) free((char *)name); // name was strduped - - for (c = l; xml->attr[c]; c += 2); // find end of attribute list - if (xml->attr[c + 1][l / 2] & EZXML_TXTM) free(xml->attr[l + 1]); //old val - if (xml->flags & EZXML_DUP) xml->attr[c + 1][l / 2] |= EZXML_TXTM; - else xml->attr[c + 1][l / 2] &= ~EZXML_TXTM; - - if (value) xml->attr[l + 1] = (char *)value; // set attribute value - else { // remove attribute - if (xml->attr[c + 1][l / 2] & EZXML_NAMEM) free(xml->attr[l]); - memmove(xml->attr + l, xml->attr + l + 2, (c - l + 2) * sizeof(char*)); - xml->attr = realloc(xml->attr, (c + 2) * sizeof(char *)); - memmove(xml->attr[c + 1] + (l / 2), xml->attr[c + 1] + (l / 2) + 1, - (c / 2) - (l / 2)); // fix list of which name/vals are malloced - } - xml->flags &= ~EZXML_DUP; // clear strdup() flag - return xml; -} - -// sets a flag for the given tag and returns the tag -ezxml_t ezxml_set_flag(ezxml_t xml, short flag) -{ - if (xml) xml->flags |= flag; - return xml; -} - -// removes a tag along with its subtags without freeing its memory -ezxml_t ezxml_cut(ezxml_t xml) -{ - ezxml_t cur; - - if (! xml) return NULL; // nothing to do - if (xml->next) xml->next->sibling = xml->sibling; // patch sibling list - - if (xml->parent) { // not root tag - cur = xml->parent->child; // find head of subtag list - if (cur == xml) xml->parent->child = xml->ordered; // first subtag - else { // not first subtag - while (cur->ordered != xml) cur = cur->ordered; - cur->ordered = cur->ordered->ordered; // patch ordered list - - cur = xml->parent->child; // go back to head of subtag list - if (strcmp(cur->name, xml->name)) { // not in first sibling list - while (strcmp(cur->sibling->name, xml->name)) - cur = cur->sibling; - if (cur->sibling == xml) { // first of a sibling list - cur->sibling = (xml->next) ? xml->next - : cur->sibling->sibling; - } - else cur = cur->sibling; // not first of a sibling list - } - - while (cur->next && cur->next != xml) cur = cur->next; - if (cur->next) cur->next = cur->next->next; // patch next list - } - } - xml->ordered = xml->sibling = xml->next = NULL; - return xml; -} - -#ifdef EZXML_TEST // test harness -int main(int argc, char **argv) -{ - ezxml_t xml; - char *s; - int i; - - if (argc != 2) return fprintf(stderr, "usage: %s xmlfile\n", argv[0]); - - xml = ezxml_parse_file(argv[1]); - printf("%s\n", (s = ezxml_toxml(xml))); - free(s); - i = fprintf(stderr, "%s", ezxml_error(xml)); - ezxml_free(xml); - return (i) ? 1 : 0; -} -#endif // EZXML_TEST diff --git a/3rdparty/ezxml/ezxml.h b/3rdparty/ezxml/ezxml.h deleted file mode 100644 index 3e02078..0000000 --- a/3rdparty/ezxml/ezxml.h +++ /dev/null @@ -1,167 +0,0 @@ -/* ezxml.h - * - * Copyright 2004-2006 Aaron Voisine <aaron@voisine.org> - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be included - * in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -#ifndef _EZXML_H -#define _EZXML_H - -#include <stdlib.h> -#include <stdio.h> -#include <stdarg.h> -#include <fcntl.h> - -#ifdef __cplusplus -extern "C" { -#endif - -#define EZXML_BUFSIZE 1024 // size of internal memory buffers -#define EZXML_NAMEM 0x80 // name is malloced -#define EZXML_TXTM 0x40 // txt is malloced -#define EZXML_DUP 0x20 // attribute name and value are strduped - -typedef struct ezxml *ezxml_t; -struct ezxml { - char *name; // tag name - char **attr; // tag attributes { name, value, name, value, ... NULL } - char *txt; // tag character content, empty string if none - size_t off; // tag offset from start of parent tag character content - ezxml_t next; // next tag with same name in this section at this depth - ezxml_t sibling; // next tag with different name in same section and depth - ezxml_t ordered; // next tag, same section and depth, in original order - ezxml_t child; // head of sub tag list, NULL if none - ezxml_t parent; // parent tag, NULL if current tag is root tag - short flags; // additional information -}; - -// Given a string of xml data and its length, parses it and creates an ezxml -// structure. For efficiency, modifies the data by adding null terminators -// and decoding ampersand sequences. If you don't want this, copy the data and -// pass in the copy. Returns NULL on failure. -ezxml_t ezxml_parse_str(char *s, size_t len); - -// A wrapper for ezxml_parse_str() that accepts a file descriptor. First -// attempts to mem map the file. Failing that, reads the file into memory. -// Returns NULL on failure. -ezxml_t ezxml_parse_fd(int fd); - -// a wrapper for ezxml_parse_fd() that accepts a file name -ezxml_t ezxml_parse_file(const char *file); - -// Wrapper for ezxml_parse_str() that accepts a file stream. Reads the entire -// stream into memory and then parses it. For xml files, use ezxml_parse_file() -// or ezxml_parse_fd() -ezxml_t ezxml_parse_fp(FILE *fp); - -// returns the first child tag (one level deeper) with the given name or NULL -// if not found -ezxml_t ezxml_child(ezxml_t xml, const char *name); - -// returns the next tag of the same name in the same section and depth or NULL -// if not found -#define ezxml_next(xml) ((xml) ? xml->next : NULL) - -// Returns the Nth tag with the same name in the same section at the same depth -// or NULL if not found. An index of 0 returns the tag given. -ezxml_t ezxml_idx(ezxml_t xml, int idx); - -// returns the name of the given tag -#define ezxml_name(xml) ((xml) ? xml->name : NULL) - -// returns the given tag's character content or empty string if none -#define ezxml_txt(xml) ((xml) ? xml->txt : "") - -// returns the value of the requested tag attribute, or NULL if not found -const char *ezxml_attr(ezxml_t xml, const char *attr); - -// Traverses the ezxml sturcture to retrieve a specific subtag. Takes a -// variable length list of tag names and indexes. The argument list must be -// terminated by either an index of -1 or an empty string tag name. Example: -// title = ezxml_get(library, "shelf", 0, "book", 2, "title", -1); -// This retrieves the title of the 3rd book on the 1st shelf of library. -// Returns NULL if not found. -ezxml_t ezxml_get(ezxml_t xml, ...); - -// Converts an ezxml structure back to xml. Returns a string of xml data that -// must be freed. -char *ezxml_toxml(ezxml_t xml); - -// returns a NULL terminated array of processing instructions for the given -// target -const char **ezxml_pi(ezxml_t xml, const char *target); - -// frees the memory allocated for an ezxml structure -void ezxml_free(ezxml_t xml); - -// returns parser error message or empty string if none -const char *ezxml_error(ezxml_t xml); - -// returns a new empty ezxml structure with the given root tag name -ezxml_t ezxml_new(const char *name); - -// wrapper for ezxml_new() that strdup()s name -#define ezxml_new_d(name) ezxml_set_flag(ezxml_new(strdup(name)), EZXML_NAMEM) - -// Adds a child tag. off is the offset of the child tag relative to the start -// of the parent tag's character content. Returns the child tag. -ezxml_t ezxml_add_child(ezxml_t xml, const char *name, size_t off); - -// wrapper for ezxml_add_child() that strdup()s name -#define ezxml_add_child_d(xml, name, off) \ - ezxml_set_flag(ezxml_add_child(xml, strdup(name), off), EZXML_NAMEM) - -// sets the character content for the given tag and returns the tag -ezxml_t ezxml_set_txt(ezxml_t xml, const char *txt); - -// wrapper for ezxml_set_txt() that strdup()s txt -#define ezxml_set_txt_d(xml, txt) \ - ezxml_set_flag(ezxml_set_txt(xml, strdup(txt)), EZXML_TXTM) - -// Sets the given tag attribute or adds a new attribute if not found. A value -// of NULL will remove the specified attribute. Returns the tag given. -ezxml_t ezxml_set_attr(ezxml_t xml, const char *name, const char *value); - -// Wrapper for ezxml_set_attr() that strdup()s name/value. Value cannot be NULL -#define ezxml_set_attr_d(xml, name, value) \ - ezxml_set_attr(ezxml_set_flag(xml, EZXML_DUP), strdup(name), strdup(value)) - -// sets a flag for the given tag and returns the tag -ezxml_t ezxml_set_flag(ezxml_t xml, short flag); - -// removes a tag along with its subtags without freeing its memory -ezxml_t ezxml_cut(ezxml_t xml); - -// inserts an existing tag into an ezxml structure -ezxml_t ezxml_insert(ezxml_t xml, ezxml_t dest, size_t off); - -// Moves an existing tag to become a subtag of dest at the given offset from -// the start of dest's character content. Returns the moved tag. -#define ezxml_move(xml, dest, off) ezxml_insert(ezxml_cut(xml), dest, off) - -// removes a tag along with all its subtags -#define ezxml_remove(xml) ezxml_free(ezxml_cut(xml)) - -#ifdef __cplusplus -} -#endif - -#endif // _EZXML_H diff --git a/3rdparty/stb_ds.h b/3rdparty/stb_ds.h deleted file mode 100644 index e84c82d..0000000 --- a/3rdparty/stb_ds.h +++ /dev/null @@ -1,1895 +0,0 @@ -/* stb_ds.h - v0.67 - public domain data structures - Sean Barrett 2019 - - This is a single-header-file library that provides easy-to-use - dynamic arrays and hash tables for C (also works in C++). - - For a gentle introduction: - http://nothings.org/stb_ds - - To use this library, do this in *one* C or C++ file: - #define STB_DS_IMPLEMENTATION - #include "stb_ds.h" - -TABLE OF CONTENTS - - Table of Contents - Compile-time options - License - Documentation - Notes - Notes - Dynamic arrays - Notes - Hash maps - Credits - -COMPILE-TIME OPTIONS - - #define STBDS_NO_SHORT_NAMES - - This flag needs to be set globally. - - By default stb_ds exposes shorter function names that are not qualified - with the "stbds_" prefix. If these names conflict with the names in your - code, define this flag. - - #define STBDS_SIPHASH_2_4 - - This flag only needs to be set in the file containing #define STB_DS_IMPLEMENTATION. - - By default stb_ds.h hashes using a weaker variant of SipHash and a custom hash for - 4- and 8-byte keys. On 64-bit platforms, you can define the above flag to force - stb_ds.h to use specification-compliant SipHash-2-4 for all keys. Doing so makes - hash table insertion about 20% slower on 4- and 8-byte keys, 5% slower on - 64-byte keys, and 10% slower on 256-byte keys on my test computer. - - #define STBDS_REALLOC(context,ptr,size) better_realloc - #define STBDS_FREE(context,ptr) better_free - - These defines only need to be set in the file containing #define STB_DS_IMPLEMENTATION. - - By default stb_ds uses stdlib realloc() and free() for memory management. You can - substitute your own functions instead by defining these symbols. You must either - define both, or neither. Note that at the moment, 'context' will always be NULL. - @TODO add an array/hash initialization function that takes a memory context pointer. - - #define STBDS_UNIT_TESTS - - Defines a function stbds_unit_tests() that checks the functioning of the data structures. - - Note that on older versions of gcc (e.g. 5.x.x) you may need to build with '-std=c++0x' - (or equivalentally '-std=c++11') when using anonymous structures as seen on the web - page or in STBDS_UNIT_TESTS. - -LICENSE - - Placed in the public domain and also MIT licensed. - See end of file for detailed license information. - -DOCUMENTATION - - Dynamic Arrays - - Non-function interface: - - Declare an empty dynamic array of type T - T* foo = NULL; - - Access the i'th item of a dynamic array 'foo' of type T, T* foo: - foo[i] - - Functions (actually macros) - - arrfree: - void arrfree(T*); - Frees the array. - - arrlen: - ptrdiff_t arrlen(T*); - Returns the number of elements in the array. - - arrlenu: - size_t arrlenu(T*); - Returns the number of elements in the array as an unsigned type. - - arrpop: - T arrpop(T* a) - Removes the final element of the array and returns it. - - arrput: - T arrput(T* a, T b); - Appends the item b to the end of array a. Returns b. - - arrins: - T arrins(T* a, int p, T b); - Inserts the item b into the middle of array a, into a[p], - moving the rest of the array over. Returns b. - - arrinsn: - void arrinsn(T* a, int p, int n); - Inserts n uninitialized items into array a starting at a[p], - moving the rest of the array over. - - arraddnptr: - T* arraddnptr(T* a, int n) - Appends n uninitialized items onto array at the end. - Returns a pointer to the first uninitialized item added. - - arraddnindex: - size_t arraddnindex(T* a, int n) - Appends n uninitialized items onto array at the end. - Returns the index of the first uninitialized item added. - - arrdel: - void arrdel(T* a, int p); - Deletes the element at a[p], moving the rest of the array over. - - arrdeln: - void arrdeln(T* a, int p, int n); - Deletes n elements starting at a[p], moving the rest of the array over. - - arrdelswap: - void arrdelswap(T* a, int p); - Deletes the element at a[p], replacing it with the element from - the end of the array. O(1) performance. - - arrsetlen: - void arrsetlen(T* a, int n); - Changes the length of the array to n. Allocates uninitialized - slots at the end if necessary. - - arrsetcap: - size_t arrsetcap(T* a, int n); - Sets the length of allocated storage to at least n. It will not - change the length of the array. - - arrcap: - size_t arrcap(T* a); - Returns the number of total elements the array can contain without - needing to be reallocated. - - Hash maps & String hash maps - - Given T is a structure type: struct { TK key; TV value; }. Note that some - functions do not require TV value and can have other fields. For string - hash maps, TK must be 'char *'. - - Special interface: - - stbds_rand_seed: - void stbds_rand_seed(size_t seed); - For security against adversarially chosen data, you should seed the - library with a strong random number. Or at least seed it with time(). - - stbds_hash_string: - size_t stbds_hash_string(char *str, size_t seed); - Returns a hash value for a string. - - stbds_hash_bytes: - size_t stbds_hash_bytes(void *p, size_t len, size_t seed); - These functions hash an arbitrary number of bytes. The function - uses a custom hash for 4- and 8-byte data, and a weakened version - of SipHash for everything else. On 64-bit platforms you can get - specification-compliant SipHash-2-4 on all data by defining - STBDS_SIPHASH_2_4, at a significant cost in speed. - - Non-function interface: - - Declare an empty hash map of type T - T* foo = NULL; - - Access the i'th entry in a hash table T* foo: - foo[i] - - Function interface (actually macros): - - hmfree - shfree - void hmfree(T*); - void shfree(T*); - Frees the hashmap and sets the pointer to NULL. - - hmlen - shlen - ptrdiff_t hmlen(T*) - ptrdiff_t shlen(T*) - Returns the number of elements in the hashmap. - - hmlenu - shlenu - size_t hmlenu(T*) - size_t shlenu(T*) - Returns the number of elements in the hashmap. - - hmgeti - shgeti - hmgeti_ts - ptrdiff_t hmgeti(T*, TK key) - ptrdiff_t shgeti(T*, char* key) - ptrdiff_t hmgeti_ts(T*, TK key, ptrdiff_t tempvar) - Returns the index in the hashmap which has the key 'key', or -1 - if the key is not present. - - hmget - hmget_ts - shget - TV hmget(T*, TK key) - TV shget(T*, char* key) - TV hmget_ts(T*, TK key, ptrdiff_t tempvar) - Returns the value corresponding to 'key' in the hashmap. - The structure must have a 'value' field - - hmgets - shgets - T hmgets(T*, TK key) - T shgets(T*, char* key) - Returns the structure corresponding to 'key' in the hashmap. - - hmgetp - shgetp - hmgetp_ts - hmgetp_null - shgetp_null - T* hmgetp(T*, TK key) - T* shgetp(T*, char* key) - T* hmgetp_ts(T*, TK key, ptrdiff_t tempvar) - T* hmgetp_null(T*, TK key) - T* shgetp_null(T*, char *key) - Returns a pointer to the structure corresponding to 'key' in - the hashmap. Functions ending in "_null" return NULL if the key - is not present in the hashmap; the others return a pointer to a - structure holding the default value (but not the searched-for key). - - hmdefault - shdefault - TV hmdefault(T*, TV value) - TV shdefault(T*, TV value) - Sets the default value for the hashmap, the value which will be - returned by hmget/shget if the key is not present. - - hmdefaults - shdefaults - TV hmdefaults(T*, T item) - TV shdefaults(T*, T item) - Sets the default struct for the hashmap, the contents which will be - returned by hmgets/shgets if the key is not present. - - hmput - shput - TV hmput(T*, TK key, TV value) - TV shput(T*, char* key, TV value) - Inserts a <key,value> pair into the hashmap. If the key is already - present in the hashmap, updates its value. - - hmputs - shputs - T hmputs(T*, T item) - T shputs(T*, T item) - Inserts a struct with T.key into the hashmap. If the struct is already - present in the hashmap, updates it. - - hmdel - shdel - int hmdel(T*, TK key) - int shdel(T*, char* key) - If 'key' is in the hashmap, deletes its entry and returns 1. - Otherwise returns 0. - - Function interface (actually macros) for strings only: - - sh_new_strdup - void sh_new_strdup(T*); - Overwrites the existing pointer with a newly allocated - string hashmap which will automatically allocate and free - each string key using realloc/free - - sh_new_arena - void sh_new_arena(T*); - Overwrites the existing pointer with a newly allocated - string hashmap which will automatically allocate each string - key to a string arena. Every string key ever used by this - hash table remains in the arena until the arena is freed. - Additionally, any key which is deleted and reinserted will - be allocated multiple times in the string arena. - -NOTES - - * These data structures are realloc'd when they grow, and the macro - "functions" write to the provided pointer. This means: (a) the pointer - must be an lvalue, and (b) the pointer to the data structure is not - stable, and you must maintain it the same as you would a realloc'd - pointer. For example, if you pass a pointer to a dynamic array to a - function which updates it, the function must return back the new - pointer to the caller. This is the price of trying to do this in C. - - * The following are the only functions that are thread-safe on a single data - structure, i.e. can be run in multiple threads simultaneously on the same - data structure - hmlen shlen - hmlenu shlenu - hmget_ts shget_ts - hmgeti_ts shgeti_ts - hmgets_ts shgets_ts - - * You iterate over the contents of a dynamic array and a hashmap in exactly - the same way, using arrlen/hmlen/shlen: - - for (i=0; i < arrlen(foo); ++i) - ... foo[i] ... - - * All operations except arrins/arrdel are O(1) amortized, but individual - operations can be slow, so these data structures may not be suitable - for real time use. Dynamic arrays double in capacity as needed, so - elements are copied an average of once. Hash tables double/halve - their size as needed, with appropriate hysteresis to maintain O(1) - performance. - -NOTES - DYNAMIC ARRAY - - * If you know how long a dynamic array is going to be in advance, you can avoid - extra memory allocations by using arrsetlen to allocate it to that length in - advance and use foo[n] while filling it out, or arrsetcap to allocate the memory - for that length and use arrput/arrpush as normal. - - * Unlike some other versions of the dynamic array, this version should - be safe to use with strict-aliasing optimizations. - -NOTES - HASH MAP - - * For compilers other than GCC and clang (e.g. Visual Studio), for hmput/hmget/hmdel - and variants, the key must be an lvalue (so the macro can take the address of it). - Extensions are used that eliminate this requirement if you're using C99 and later - in GCC or clang, or if you're using C++ in GCC. But note that this can make your - code less portable. - - * To test for presence of a key in a hashmap, just do 'hmgeti(foo,key) >= 0'. - - * The iteration order of your data in the hashmap is determined solely by the - order of insertions and deletions. In particular, if you never delete, new - keys are always added at the end of the array. This will be consistent - across all platforms and versions of the library. However, you should not - attempt to serialize the internal hash table, as the hash is not consistent - between different platforms, and may change with future versions of the library. - - * Use sh_new_arena() for string hashmaps that you never delete from. Initialize - with NULL if you're managing the memory for your strings, or your strings are - never freed (at least until the hashmap is freed). Otherwise, use sh_new_strdup(). - @TODO: make an arena variant that garbage collects the strings with a trivial - copy collector into a new arena whenever the table shrinks / rebuilds. Since - current arena recommendation is to only use arena if it never deletes, then - this can just replace current arena implementation. - - * If adversarial input is a serious concern and you're on a 64-bit platform, - enable STBDS_SIPHASH_2_4 (see the 'Compile-time options' section), and pass - a strong random number to stbds_rand_seed. - - * The default value for the hash table is stored in foo[-1], so if you - use code like 'hmget(T,k)->value = 5' you can accidentally overwrite - the value stored by hmdefault if 'k' is not present. - -CREDITS - - Sean Barrett -- library, idea for dynamic array API/implementation - Per Vognsen -- idea for hash table API/implementation - Rafael Sachetto -- arrpop() - github:HeroicKatora -- arraddn() reworking - - Bugfixes: - Andy Durdin - Shane Liesegang - Vinh Truong - Andreas Molzer - github:hashitaku - github:srdjanstipic - Macoy Madson - Andreas Vennstrom - Tobias Mansfield-Williams -*/ - -#ifdef STBDS_UNIT_TESTS -#define _CRT_SECURE_NO_WARNINGS -#endif - -#ifndef INCLUDE_STB_DS_H -#define INCLUDE_STB_DS_H - -#include <stddef.h> -#include <string.h> - -#ifndef STBDS_NO_SHORT_NAMES -#define arrlen stbds_arrlen -#define arrlenu stbds_arrlenu -#define arrput stbds_arrput -#define arrpush stbds_arrput -#define arrpop stbds_arrpop -#define arrfree stbds_arrfree -#define arraddn stbds_arraddn // deprecated, use one of the following instead: -#define arraddnptr stbds_arraddnptr -#define arraddnindex stbds_arraddnindex -#define arrsetlen stbds_arrsetlen -#define arrlast stbds_arrlast -#define arrins stbds_arrins -#define arrinsn stbds_arrinsn -#define arrdel stbds_arrdel -#define arrdeln stbds_arrdeln -#define arrdelswap stbds_arrdelswap -#define arrcap stbds_arrcap -#define arrsetcap stbds_arrsetcap - -#define hmput stbds_hmput -#define hmputs stbds_hmputs -#define hmget stbds_hmget -#define hmget_ts stbds_hmget_ts -#define hmgets stbds_hmgets -#define hmgetp stbds_hmgetp -#define hmgetp_ts stbds_hmgetp_ts -#define hmgetp_null stbds_hmgetp_null -#define hmgeti stbds_hmgeti -#define hmgeti_ts stbds_hmgeti_ts -#define hmdel stbds_hmdel -#define hmlen stbds_hmlen -#define hmlenu stbds_hmlenu -#define hmfree stbds_hmfree -#define hmdefault stbds_hmdefault -#define hmdefaults stbds_hmdefaults - -#define shput stbds_shput -#define shputi stbds_shputi -#define shputs stbds_shputs -#define shget stbds_shget -#define shgeti stbds_shgeti -#define shgets stbds_shgets -#define shgetp stbds_shgetp -#define shgetp_null stbds_shgetp_null -#define shdel stbds_shdel -#define shlen stbds_shlen -#define shlenu stbds_shlenu -#define shfree stbds_shfree -#define shdefault stbds_shdefault -#define shdefaults stbds_shdefaults -#define sh_new_arena stbds_sh_new_arena -#define sh_new_strdup stbds_sh_new_strdup - -#define stralloc stbds_stralloc -#define strreset stbds_strreset -#endif - -#if defined(STBDS_REALLOC) && !defined(STBDS_FREE) || !defined(STBDS_REALLOC) && defined(STBDS_FREE) -#error "You must define both STBDS_REALLOC and STBDS_FREE, or neither." -#endif -#if !defined(STBDS_REALLOC) && !defined(STBDS_FREE) -#include <stdlib.h> -#define STBDS_REALLOC(c,p,s) realloc(p,s) -#define STBDS_FREE(c,p) free(p) -#endif - -#ifdef _MSC_VER -#define STBDS_NOTUSED(v) (void)(v) -#else -#define STBDS_NOTUSED(v) (void)sizeof(v) -#endif - -#ifdef __cplusplus -extern "C" { -#endif - -// for security against attackers, seed the library with a random number, at least time() but stronger is better -extern void stbds_rand_seed(size_t seed); - -// these are the hash functions used internally if you want to test them or use them for other purposes -extern size_t stbds_hash_bytes(void *p, size_t len, size_t seed); -extern size_t stbds_hash_string(char *str, size_t seed); - -// this is a simple string arena allocator, initialize with e.g. 'stbds_string_arena my_arena={0}'. -typedef struct stbds_string_arena stbds_string_arena; -extern char * stbds_stralloc(stbds_string_arena *a, char *str); -extern void stbds_strreset(stbds_string_arena *a); - -// have to #define STBDS_UNIT_TESTS to call this -extern void stbds_unit_tests(void); - -/////////////// -// -// Everything below here is implementation details -// - -extern void * stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap); -extern void stbds_arrfreef(void *a); -extern void stbds_hmfree_func(void *p, size_t elemsize); -extern void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode); -extern void * stbds_hmget_key_ts(void *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode); -extern void * stbds_hmput_default(void *a, size_t elemsize); -extern void * stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode); -extern void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode); -extern void * stbds_shmode_func(size_t elemsize, int mode); - -#ifdef __cplusplus -} -#endif - -#if defined(__GNUC__) || defined(__clang__) -#define STBDS_HAS_TYPEOF -#ifdef __cplusplus -//#define STBDS_HAS_LITERAL_ARRAY // this is currently broken for clang -#endif -#endif - -#if !defined(__cplusplus) -#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L -#define STBDS_HAS_LITERAL_ARRAY -#endif -#endif - -// this macro takes the address of the argument, but on gcc/clang can accept rvalues -#if defined(STBDS_HAS_LITERAL_ARRAY) && defined(STBDS_HAS_TYPEOF) - #if __clang__ - #define STBDS_ADDRESSOF(typevar, value) ((__typeof__(typevar)[1]){value}) // literal array decays to pointer to value - #else - #define STBDS_ADDRESSOF(typevar, value) ((typeof(typevar)[1]){value}) // literal array decays to pointer to value - #endif -#else -#define STBDS_ADDRESSOF(typevar, value) &(value) -#endif - -#define STBDS_OFFSETOF(var,field) ((char *) &(var)->field - (char *) (var)) - -#define stbds_header(t) ((stbds_array_header *) (t) - 1) -#define stbds_temp(t) stbds_header(t)->temp -#define stbds_temp_key(t) (*(char **) stbds_header(t)->hash_table) - -#define stbds_arrsetcap(a,n) (stbds_arrgrow(a,0,n)) -#define stbds_arrsetlen(a,n) ((stbds_arrcap(a) < (size_t) (n) ? stbds_arrsetcap((a),(size_t)(n)),0 : 0), (a) ? stbds_header(a)->length = (size_t) (n) : 0) -#define stbds_arrcap(a) ((a) ? stbds_header(a)->capacity : 0) -#define stbds_arrlen(a) ((a) ? (ptrdiff_t) stbds_header(a)->length : 0) -#define stbds_arrlenu(a) ((a) ? stbds_header(a)->length : 0) -#define stbds_arrput(a,v) (stbds_arrmaybegrow(a,1), (a)[stbds_header(a)->length++] = (v)) -#define stbds_arrpush stbds_arrput // synonym -#define stbds_arrpop(a) (stbds_header(a)->length--, (a)[stbds_header(a)->length]) -#define stbds_arraddn(a,n) ((void)(stbds_arraddnindex(a, n))) // deprecated, use one of the following instead: -#define stbds_arraddnptr(a,n) (stbds_arrmaybegrow(a,n), (n) ? (stbds_header(a)->length += (n), &(a)[stbds_header(a)->length-(n)]) : (a)) -#define stbds_arraddnindex(a,n)(stbds_arrmaybegrow(a,n), (n) ? (stbds_header(a)->length += (n), stbds_header(a)->length-(n)) : stbds_arrlen(a)) -#define stbds_arraddnoff stbds_arraddnindex -#define stbds_arrlast(a) ((a)[stbds_header(a)->length-1]) -#define stbds_arrfree(a) ((void) ((a) ? STBDS_FREE(NULL,stbds_header(a)) : (void)0), (a)=NULL) -#define stbds_arrdel(a,i) stbds_arrdeln(a,i,1) -#define stbds_arrdeln(a,i,n) (memmove(&(a)[i], &(a)[(i)+(n)], sizeof *(a) * (stbds_header(a)->length-(n)-(i))), stbds_header(a)->length -= (n)) -#define stbds_arrdelswap(a,i) ((a)[i] = stbds_arrlast(a), stbds_header(a)->length -= 1) -#define stbds_arrinsn(a,i,n) (stbds_arraddn((a),(n)), memmove(&(a)[(i)+(n)], &(a)[i], sizeof *(a) * (stbds_header(a)->length-(n)-(i)))) -#define stbds_arrins(a,i,v) (stbds_arrinsn((a),(i),1), (a)[i]=(v)) - -#define stbds_arrmaybegrow(a,n) ((!(a) || stbds_header(a)->length + (n) > stbds_header(a)->capacity) \ - ? (stbds_arrgrow(a,n,0),0) : 0) - -#define stbds_arrgrow(a,b,c) ((a) = stbds_arrgrowf_wrapper((a), sizeof *(a), (b), (c))) - -#define stbds_hmput(t, k, v) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, 0), \ - (t)[stbds_temp((t)-1)].key = (k), \ - (t)[stbds_temp((t)-1)].value = (v)) - -#define stbds_hmputs(t, s) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), &(s).key, sizeof (s).key, STBDS_HM_BINARY), \ - (t)[stbds_temp((t)-1)] = (s)) - -#define stbds_hmgeti(t,k) \ - ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_HM_BINARY), \ - stbds_temp((t)-1)) - -#define stbds_hmgeti_ts(t,k,temp) \ - ((t) = stbds_hmget_key_ts_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, &(temp), STBDS_HM_BINARY), \ - (temp)) - -#define stbds_hmgetp(t, k) \ - ((void) stbds_hmgeti(t,k), &(t)[stbds_temp((t)-1)]) - -#define stbds_hmgetp_ts(t, k, temp) \ - ((void) stbds_hmgeti_ts(t,k,temp), &(t)[temp]) - -#define stbds_hmdel(t,k) \ - (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_BINARY)),(t)?stbds_temp((t)-1):0) - -#define stbds_hmdefault(t, v) \ - ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1].value = (v)) - -#define stbds_hmdefaults(t, s) \ - ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1] = (s)) - -#define stbds_hmfree(p) \ - ((void) ((p) != NULL ? stbds_hmfree_func((p)-1,sizeof*(p)),0 : 0),(p)=NULL) - -#define stbds_hmgets(t, k) (*stbds_hmgetp(t,k)) -#define stbds_hmget(t, k) (stbds_hmgetp(t,k)->value) -#define stbds_hmget_ts(t, k, temp) (stbds_hmgetp_ts(t,k,temp)->value) -#define stbds_hmlen(t) ((t) ? (ptrdiff_t) stbds_header((t)-1)->length-1 : 0) -#define stbds_hmlenu(t) ((t) ? stbds_header((t)-1)->length-1 : 0) -#define stbds_hmgetp_null(t,k) (stbds_hmgeti(t,k) == -1 ? NULL : &(t)[stbds_temp((t)-1)]) - -#define stbds_shput(t, k, v) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ - (t)[stbds_temp((t)-1)].value = (v)) - -#define stbds_shputi(t, k, v) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ - (t)[stbds_temp((t)-1)].value = (v), stbds_temp((t)-1)) - -#define stbds_shputs(t, s) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (s).key, sizeof (s).key, STBDS_HM_STRING), \ - (t)[stbds_temp((t)-1)] = (s), \ - (t)[stbds_temp((t)-1)].key = stbds_temp_key((t)-1)) // above line overwrites whole structure, so must rewrite key here if it was allocated internally - -#define stbds_pshput(t, p) \ - ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (p)->key, sizeof (p)->key, STBDS_HM_PTR_TO_STRING), \ - (t)[stbds_temp((t)-1)] = (p)) - -#define stbds_shgeti(t,k) \ - ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ - stbds_temp((t)-1)) - -#define stbds_pshgeti(t,k) \ - ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (*(t))->key, STBDS_HM_PTR_TO_STRING), \ - stbds_temp((t)-1)) - -#define stbds_shgetp(t, k) \ - ((void) stbds_shgeti(t,k), &(t)[stbds_temp((t)-1)]) - -#define stbds_pshget(t, k) \ - ((void) stbds_pshgeti(t,k), (t)[stbds_temp((t)-1)]) - -#define stbds_shdel(t,k) \ - (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_STRING)),(t)?stbds_temp((t)-1):0) -#define stbds_pshdel(t,k) \ - (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) (k), sizeof (*(t))->key, STBDS_OFFSETOF(*(t),key), STBDS_HM_PTR_TO_STRING)),(t)?stbds_temp((t)-1):0) - -#define stbds_sh_new_arena(t) \ - ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_ARENA)) -#define stbds_sh_new_strdup(t) \ - ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_STRDUP)) - -#define stbds_shdefault(t, v) stbds_hmdefault(t,v) -#define stbds_shdefaults(t, s) stbds_hmdefaults(t,s) - -#define stbds_shfree stbds_hmfree -#define stbds_shlenu stbds_hmlenu - -#define stbds_shgets(t, k) (*stbds_shgetp(t,k)) -#define stbds_shget(t, k) (stbds_shgetp(t,k)->value) -#define stbds_shgetp_null(t,k) (stbds_shgeti(t,k) == -1 ? NULL : &(t)[stbds_temp((t)-1)]) -#define stbds_shlen stbds_hmlen - -typedef struct -{ - size_t length; - size_t capacity; - void * hash_table; - ptrdiff_t temp; -} stbds_array_header; - -typedef struct stbds_string_block -{ - struct stbds_string_block *next; - char storage[8]; -} stbds_string_block; - -struct stbds_string_arena -{ - stbds_string_block *storage; - size_t remaining; - unsigned char block; - unsigned char mode; // this isn't used by the string arena itself -}; - -#define STBDS_HM_BINARY 0 -#define STBDS_HM_STRING 1 - -enum -{ - STBDS_SH_NONE, - STBDS_SH_DEFAULT, - STBDS_SH_STRDUP, - STBDS_SH_ARENA -}; - -#ifdef __cplusplus -// in C we use implicit assignment from these void*-returning functions to T*. -// in C++ these templates make the same code work -template<class T> static T * stbds_arrgrowf_wrapper(T *a, size_t elemsize, size_t addlen, size_t min_cap) { - return (T*)stbds_arrgrowf((void *)a, elemsize, addlen, min_cap); -} -template<class T> static T * stbds_hmget_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) { - return (T*)stbds_hmget_key((void*)a, elemsize, key, keysize, mode); -} -template<class T> static T * stbds_hmget_key_ts_wrapper(T *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode) { - return (T*)stbds_hmget_key_ts((void*)a, elemsize, key, keysize, temp, mode); -} -template<class T> static T * stbds_hmput_default_wrapper(T *a, size_t elemsize) { - return (T*)stbds_hmput_default((void *)a, elemsize); -} -template<class T> static T * stbds_hmput_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) { - return (T*)stbds_hmput_key((void*)a, elemsize, key, keysize, mode); -} -template<class T> static T * stbds_hmdel_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode){ - return (T*)stbds_hmdel_key((void*)a, elemsize, key, keysize, keyoffset, mode); -} -template<class T> static T * stbds_shmode_func_wrapper(T *, size_t elemsize, int mode) { - return (T*)stbds_shmode_func(elemsize, mode); -} -#else -#define stbds_arrgrowf_wrapper stbds_arrgrowf -#define stbds_hmget_key_wrapper stbds_hmget_key -#define stbds_hmget_key_ts_wrapper stbds_hmget_key_ts -#define stbds_hmput_default_wrapper stbds_hmput_default -#define stbds_hmput_key_wrapper stbds_hmput_key -#define stbds_hmdel_key_wrapper stbds_hmdel_key -#define stbds_shmode_func_wrapper(t,e,m) stbds_shmode_func(e,m) -#endif - -#endif // INCLUDE_STB_DS_H - - -////////////////////////////////////////////////////////////////////////////// -// -// IMPLEMENTATION -// - -#ifdef STB_DS_IMPLEMENTATION -#include <assert.h> -#include <string.h> - -#ifndef STBDS_ASSERT -#define STBDS_ASSERT_WAS_UNDEFINED -#define STBDS_ASSERT(x) ((void) 0) -#endif - -#ifdef STBDS_STATISTICS -#define STBDS_STATS(x) x -size_t stbds_array_grow; -size_t stbds_hash_grow; -size_t stbds_hash_shrink; -size_t stbds_hash_rebuild; -size_t stbds_hash_probes; -size_t stbds_hash_alloc; -size_t stbds_rehash_probes; -size_t stbds_rehash_items; -#else -#define STBDS_STATS(x) -#endif - -// -// stbds_arr implementation -// - -//int *prev_allocs[65536]; -//int num_prev; - -void *stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap) -{ - stbds_array_header temp={0}; // force debugging - void *b; - size_t min_len = stbds_arrlen(a) + addlen; - (void) sizeof(temp); - - // compute the minimum capacity needed - if (min_len > min_cap) - min_cap = min_len; - - if (min_cap <= stbds_arrcap(a)) - return a; - - // increase needed capacity to guarantee O(1) amortized - if (min_cap < 2 * stbds_arrcap(a)) - min_cap = 2 * stbds_arrcap(a); - else if (min_cap < 4) - min_cap = 4; - - //if (num_prev < 65536) if (a) prev_allocs[num_prev++] = (int *) ((char *) a+1); - //if (num_prev == 2201) - // num_prev = num_prev; - b = STBDS_REALLOC(NULL, (a) ? stbds_header(a) : 0, elemsize * min_cap + sizeof(stbds_array_header)); - //if (num_prev < 65536) prev_allocs[num_prev++] = (int *) (char *) b; - b = (char *) b + sizeof(stbds_array_header); - if (a == NULL) { - stbds_header(b)->length = 0; - stbds_header(b)->hash_table = 0; - stbds_header(b)->temp = 0; - } else { - STBDS_STATS(++stbds_array_grow); - } - stbds_header(b)->capacity = min_cap; - - return b; -} - -void stbds_arrfreef(void *a) -{ - STBDS_FREE(NULL, stbds_header(a)); -} - -// -// stbds_hm hash table implementation -// - -#ifdef STBDS_INTERNAL_SMALL_BUCKET -#define STBDS_BUCKET_LENGTH 4 -#else -#define STBDS_BUCKET_LENGTH 8 -#endif - -#define STBDS_BUCKET_SHIFT (STBDS_BUCKET_LENGTH == 8 ? 3 : 2) -#define STBDS_BUCKET_MASK (STBDS_BUCKET_LENGTH-1) -#define STBDS_CACHE_LINE_SIZE 64 - -#define STBDS_ALIGN_FWD(n,a) (((n) + (a) - 1) & ~((a)-1)) - -typedef struct -{ - size_t hash [STBDS_BUCKET_LENGTH]; - ptrdiff_t index[STBDS_BUCKET_LENGTH]; -} stbds_hash_bucket; // in 32-bit, this is one 64-byte cache line; in 64-bit, each array is one 64-byte cache line - -typedef struct -{ - char * temp_key; // this MUST be the first field of the hash table - size_t slot_count; - size_t used_count; - size_t used_count_threshold; - size_t used_count_shrink_threshold; - size_t tombstone_count; - size_t tombstone_count_threshold; - size_t seed; - size_t slot_count_log2; - stbds_string_arena string; - stbds_hash_bucket *storage; // not a separate allocation, just 64-byte aligned storage after this struct -} stbds_hash_index; - -#define STBDS_INDEX_EMPTY -1 -#define STBDS_INDEX_DELETED -2 -#define STBDS_INDEX_IN_USE(x) ((x) >= 0) - -#define STBDS_HASH_EMPTY 0 -#define STBDS_HASH_DELETED 1 - -static size_t stbds_hash_seed=0x31415926; - -void stbds_rand_seed(size_t seed) -{ - stbds_hash_seed = seed; -} - -#define stbds_load_32_or_64(var, temp, v32, v64_hi, v64_lo) \ - temp = v64_lo ^ v32, temp <<= 16, temp <<= 16, temp >>= 16, temp >>= 16, /* discard if 32-bit */ \ - var = v64_hi, var <<= 16, var <<= 16, /* discard if 32-bit */ \ - var ^= temp ^ v32 - -#define STBDS_SIZE_T_BITS ((sizeof (size_t)) * 8) - -static size_t stbds_probe_position(size_t hash, size_t slot_count, size_t slot_log2) -{ - size_t pos; - STBDS_NOTUSED(slot_log2); - pos = hash & (slot_count-1); - #ifdef STBDS_INTERNAL_BUCKET_START - pos &= ~STBDS_BUCKET_MASK; - #endif - return pos; -} - -static size_t stbds_log2(size_t slot_count) -{ - size_t n=0; - while (slot_count > 1) { - slot_count >>= 1; - ++n; - } - return n; -} - -static stbds_hash_index *stbds_make_hash_index(size_t slot_count, stbds_hash_index *ot) -{ - stbds_hash_index *t; - t = (stbds_hash_index *) STBDS_REALLOC(NULL,0,(slot_count >> STBDS_BUCKET_SHIFT) * sizeof(stbds_hash_bucket) + sizeof(stbds_hash_index) + STBDS_CACHE_LINE_SIZE-1); - t->storage = (stbds_hash_bucket *) STBDS_ALIGN_FWD((size_t) (t+1), STBDS_CACHE_LINE_SIZE); - t->slot_count = slot_count; - t->slot_count_log2 = stbds_log2(slot_count); - t->tombstone_count = 0; - t->used_count = 0; - - #if 0 // A1 - t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow - t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild - t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink - #elif 1 // A2 - //t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow - //t->tombstone_count_threshold = slot_count* 3/16; // if tombstones are 3/16th of table, rebuild - //t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink - - // compute without overflowing - t->used_count_threshold = slot_count - (slot_count>>2); - t->tombstone_count_threshold = (slot_count>>3) + (slot_count>>4); - t->used_count_shrink_threshold = slot_count >> 2; - - #elif 0 // B1 - t->used_count_threshold = slot_count*13/16; // if 13/16th of table is occupied, grow - t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild - t->used_count_shrink_threshold = slot_count* 5/16; // if table is only 5/16th full, shrink - #else // C1 - t->used_count_threshold = slot_count*14/16; // if 14/16th of table is occupied, grow - t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild - t->used_count_shrink_threshold = slot_count* 6/16; // if table is only 6/16th full, shrink - #endif - // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2 - // Note that the larger tables have high variance as they were run fewer times - // A1 A2 B1 C1 - // 0.10ms : 0.10ms : 0.10ms : 0.11ms : 2,000 inserts creating 2K table - // 0.96ms : 0.95ms : 0.97ms : 1.04ms : 20,000 inserts creating 20K table - // 14.48ms : 14.46ms : 10.63ms : 11.00ms : 200,000 inserts creating 200K table - // 195.74ms : 196.35ms : 203.69ms : 214.92ms : 2,000,000 inserts creating 2M table - // 2193.88ms : 2209.22ms : 2285.54ms : 2437.17ms : 20,000,000 inserts creating 20M table - // 65.27ms : 53.77ms : 65.33ms : 65.47ms : 500,000 inserts & deletes in 2K table - // 72.78ms : 62.45ms : 71.95ms : 72.85ms : 500,000 inserts & deletes in 20K table - // 89.47ms : 77.72ms : 96.49ms : 96.75ms : 500,000 inserts & deletes in 200K table - // 97.58ms : 98.14ms : 97.18ms : 97.53ms : 500,000 inserts & deletes in 2M table - // 118.61ms : 119.62ms : 120.16ms : 118.86ms : 500,000 inserts & deletes in 20M table - // 192.11ms : 194.39ms : 196.38ms : 195.73ms : 500,000 inserts & deletes in 200M table - - if (slot_count <= STBDS_BUCKET_LENGTH) - t->used_count_shrink_threshold = 0; - // to avoid infinite loop, we need to guarantee that at least one slot is empty and will terminate probes - STBDS_ASSERT(t->used_count_threshold + t->tombstone_count_threshold < t->slot_count); - STBDS_STATS(++stbds_hash_alloc); - if (ot) { - t->string = ot->string; - // reuse old seed so we can reuse old hashes so below "copy out old data" doesn't do any hashing - t->seed = ot->seed; - } else { - size_t a,b,temp; - memset(&t->string, 0, sizeof(t->string)); - t->seed = stbds_hash_seed; - // LCG - // in 32-bit, a = 2147001325 b = 715136305 - // in 64-bit, a = 2862933555777941757 b = 3037000493 - stbds_load_32_or_64(a,temp, 2147001325, 0x27bb2ee6, 0x87b0b0fd); - stbds_load_32_or_64(b,temp, 715136305, 0, 0xb504f32d); - stbds_hash_seed = stbds_hash_seed * a + b; - } - - { - size_t i,j; - for (i=0; i < slot_count >> STBDS_BUCKET_SHIFT; ++i) { - stbds_hash_bucket *b = &t->storage[i]; - for (j=0; j < STBDS_BUCKET_LENGTH; ++j) - b->hash[j] = STBDS_HASH_EMPTY; - for (j=0; j < STBDS_BUCKET_LENGTH; ++j) - b->index[j] = STBDS_INDEX_EMPTY; - } - } - - // copy out the old data, if any - if (ot) { - size_t i,j; - t->used_count = ot->used_count; - for (i=0; i < ot->slot_count >> STBDS_BUCKET_SHIFT; ++i) { - stbds_hash_bucket *ob = &ot->storage[i]; - for (j=0; j < STBDS_BUCKET_LENGTH; ++j) { - if (STBDS_INDEX_IN_USE(ob->index[j])) { - size_t hash = ob->hash[j]; - size_t pos = stbds_probe_position(hash, t->slot_count, t->slot_count_log2); - size_t step = STBDS_BUCKET_LENGTH; - STBDS_STATS(++stbds_rehash_items); - for (;;) { - size_t limit,z; - stbds_hash_bucket *bucket; - bucket = &t->storage[pos >> STBDS_BUCKET_SHIFT]; - STBDS_STATS(++stbds_rehash_probes); - - for (z=pos & STBDS_BUCKET_MASK; z < STBDS_BUCKET_LENGTH; ++z) { - if (bucket->hash[z] == 0) { - bucket->hash[z] = hash; - bucket->index[z] = ob->index[j]; - goto done; - } - } - - limit = pos & STBDS_BUCKET_MASK; - for (z = 0; z < limit; ++z) { - if (bucket->hash[z] == 0) { - bucket->hash[z] = hash; - bucket->index[z] = ob->index[j]; - goto done; - } - } - - pos += step; // quadratic probing - step += STBDS_BUCKET_LENGTH; - pos &= (t->slot_count-1); - } - } - done: - ; - } - } - } - - return t; -} - -#define STBDS_ROTATE_LEFT(val, n) (((val) << (n)) | ((val) >> (STBDS_SIZE_T_BITS - (n)))) -#define STBDS_ROTATE_RIGHT(val, n) (((val) >> (n)) | ((val) << (STBDS_SIZE_T_BITS - (n)))) - -size_t stbds_hash_string(char *str, size_t seed) -{ - size_t hash = seed; - while (*str) - hash = STBDS_ROTATE_LEFT(hash, 9) + (unsigned char) *str++; - - // Thomas Wang 64-to-32 bit mix function, hopefully also works in 32 bits - hash ^= seed; - hash = (~hash) + (hash << 18); - hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,31); - hash = hash * 21; - hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,11); - hash += (hash << 6); - hash ^= STBDS_ROTATE_RIGHT(hash,22); - return hash+seed; -} - -#ifdef STBDS_SIPHASH_2_4 -#define STBDS_SIPHASH_C_ROUNDS 2 -#define STBDS_SIPHASH_D_ROUNDS 4 -typedef int STBDS_SIPHASH_2_4_can_only_be_used_in_64_bit_builds[sizeof(size_t) == 8 ? 1 : -1]; -#endif - -#ifndef STBDS_SIPHASH_C_ROUNDS -#define STBDS_SIPHASH_C_ROUNDS 1 -#endif -#ifndef STBDS_SIPHASH_D_ROUNDS -#define STBDS_SIPHASH_D_ROUNDS 1 -#endif - -#ifdef _MSC_VER -#pragma warning(push) -#pragma warning(disable:4127) // conditional expression is constant, for do..while(0) and sizeof()== -#endif - -static size_t stbds_siphash_bytes(void *p, size_t len, size_t seed) -{ - unsigned char *d = (unsigned char *) p; - size_t i,j; - size_t v0,v1,v2,v3, data; - - // hash that works on 32- or 64-bit registers without knowing which we have - // (computes different results on 32-bit and 64-bit platform) - // derived from siphash, but on 32-bit platforms very different as it uses 4 32-bit state not 4 64-bit - v0 = ((((size_t) 0x736f6d65 << 16) << 16) + 0x70736575) ^ seed; - v1 = ((((size_t) 0x646f7261 << 16) << 16) + 0x6e646f6d) ^ ~seed; - v2 = ((((size_t) 0x6c796765 << 16) << 16) + 0x6e657261) ^ seed; - v3 = ((((size_t) 0x74656462 << 16) << 16) + 0x79746573) ^ ~seed; - - #ifdef STBDS_TEST_SIPHASH_2_4 - // hardcoded with key material in the siphash test vectors - v0 ^= 0x0706050403020100ull ^ seed; - v1 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed; - v2 ^= 0x0706050403020100ull ^ seed; - v3 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed; - #endif - - #define STBDS_SIPROUND() \ - do { \ - v0 += v1; v1 = STBDS_ROTATE_LEFT(v1, 13); v1 ^= v0; v0 = STBDS_ROTATE_LEFT(v0,STBDS_SIZE_T_BITS/2); \ - v2 += v3; v3 = STBDS_ROTATE_LEFT(v3, 16); v3 ^= v2; \ - v2 += v1; v1 = STBDS_ROTATE_LEFT(v1, 17); v1 ^= v2; v2 = STBDS_ROTATE_LEFT(v2,STBDS_SIZE_T_BITS/2); \ - v0 += v3; v3 = STBDS_ROTATE_LEFT(v3, 21); v3 ^= v0; \ - } while (0) - - for (i=0; i+sizeof(size_t) <= len; i += sizeof(size_t), d += sizeof(size_t)) { - data = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); - data |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // discarded if size_t == 4 - - v3 ^= data; - for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j) - STBDS_SIPROUND(); - v0 ^= data; - } - data = len << (STBDS_SIZE_T_BITS-8); - switch (len - i) { - case 7: data |= ((size_t) d[6] << 24) << 24; // fall through - case 6: data |= ((size_t) d[5] << 20) << 20; // fall through - case 5: data |= ((size_t) d[4] << 16) << 16; // fall through - case 4: data |= (d[3] << 24); // fall through - case 3: data |= (d[2] << 16); // fall through - case 2: data |= (d[1] << 8); // fall through - case 1: data |= d[0]; // fall through - case 0: break; - } - v3 ^= data; - for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j) - STBDS_SIPROUND(); - v0 ^= data; - v2 ^= 0xff; - for (j=0; j < STBDS_SIPHASH_D_ROUNDS; ++j) - STBDS_SIPROUND(); - -#ifdef STBDS_SIPHASH_2_4 - return v0^v1^v2^v3; -#else - return v1^v2^v3; // slightly stronger since v0^v3 in above cancels out final round operation? I tweeted at the authors of SipHash about this but they didn't reply -#endif -} - -size_t stbds_hash_bytes(void *p, size_t len, size_t seed) -{ -#ifdef STBDS_SIPHASH_2_4 - return stbds_siphash_bytes(p,len,seed); -#else - unsigned char *d = (unsigned char *) p; - - if (len == 4) { - unsigned int hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); - #if 0 - // HASH32-A Bob Jenkin's hash function w/o large constants - hash ^= seed; - hash -= (hash<<6); - hash ^= (hash>>17); - hash -= (hash<<9); - hash ^= seed; - hash ^= (hash<<4); - hash -= (hash<<3); - hash ^= (hash<<10); - hash ^= (hash>>15); - #elif 1 - // HASH32-BB Bob Jenkin's presumably-accidental version of Thomas Wang hash with rotates turned into shifts. - // Note that converting these back to rotates makes it run a lot slower, presumably due to collisions, so I'm - // not really sure what's going on. - hash ^= seed; - hash = (hash ^ 61) ^ (hash >> 16); - hash = hash + (hash << 3); - hash = hash ^ (hash >> 4); - hash = hash * 0x27d4eb2d; - hash ^= seed; - hash = hash ^ (hash >> 15); - #else // HASH32-C - Murmur3 - hash ^= seed; - hash *= 0xcc9e2d51; - hash = (hash << 17) | (hash >> 15); - hash *= 0x1b873593; - hash ^= seed; - hash = (hash << 19) | (hash >> 13); - hash = hash*5 + 0xe6546b64; - hash ^= hash >> 16; - hash *= 0x85ebca6b; - hash ^= seed; - hash ^= hash >> 13; - hash *= 0xc2b2ae35; - hash ^= hash >> 16; - #endif - // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2 - // Note that the larger tables have high variance as they were run fewer times - // HASH32-A // HASH32-BB // HASH32-C - // 0.10ms // 0.10ms // 0.10ms : 2,000 inserts creating 2K table - // 0.96ms // 0.95ms // 0.99ms : 20,000 inserts creating 20K table - // 14.69ms // 14.43ms // 14.97ms : 200,000 inserts creating 200K table - // 199.99ms // 195.36ms // 202.05ms : 2,000,000 inserts creating 2M table - // 2234.84ms // 2187.74ms // 2240.38ms : 20,000,000 inserts creating 20M table - // 55.68ms // 53.72ms // 57.31ms : 500,000 inserts & deletes in 2K table - // 63.43ms // 61.99ms // 65.73ms : 500,000 inserts & deletes in 20K table - // 80.04ms // 77.96ms // 81.83ms : 500,000 inserts & deletes in 200K table - // 100.42ms // 97.40ms // 102.39ms : 500,000 inserts & deletes in 2M table - // 119.71ms // 120.59ms // 121.63ms : 500,000 inserts & deletes in 20M table - // 185.28ms // 195.15ms // 187.74ms : 500,000 inserts & deletes in 200M table - // 15.58ms // 14.79ms // 15.52ms : 200,000 inserts creating 200K table with varying key spacing - - return (((size_t) hash << 16 << 16) | hash) ^ seed; - } else if (len == 8 && sizeof(size_t) == 8) { - size_t hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); - hash |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // avoid warning if size_t == 4 - hash ^= seed; - hash = (~hash) + (hash << 21); - hash ^= STBDS_ROTATE_RIGHT(hash,24); - hash *= 265; - hash ^= STBDS_ROTATE_RIGHT(hash,14); - hash ^= seed; - hash *= 21; - hash ^= STBDS_ROTATE_RIGHT(hash,28); - hash += (hash << 31); - hash = (~hash) + (hash << 18); - return hash; - } else { - return stbds_siphash_bytes(p,len,seed); - } -#endif -} -#ifdef _MSC_VER -#pragma warning(pop) -#endif - - -static int stbds_is_key_equal(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode, size_t i) -{ - if (mode >= STBDS_HM_STRING) - return 0==strcmp((char *) key, * (char **) ((char *) a + elemsize*i + keyoffset)); - else - return 0==memcmp(key, (char *) a + elemsize*i + keyoffset, keysize); -} - -#define STBDS_HASH_TO_ARR(x,elemsize) ((char*) (x) - (elemsize)) -#define STBDS_ARR_TO_HASH(x,elemsize) ((char*) (x) + (elemsize)) - -#define stbds_hash_table(a) ((stbds_hash_index *) stbds_header(a)->hash_table) - -void stbds_hmfree_func(void *a, size_t elemsize) -{ - if (a == NULL) return; - if (stbds_hash_table(a) != NULL) { - if (stbds_hash_table(a)->string.mode == STBDS_SH_STRDUP) { - size_t i; - // skip 0th element, which is default - for (i=1; i < stbds_header(a)->length; ++i) - STBDS_FREE(NULL, *(char**) ((char *) a + elemsize*i)); - } - stbds_strreset(&stbds_hash_table(a)->string); - } - STBDS_FREE(NULL, stbds_header(a)->hash_table); - STBDS_FREE(NULL, stbds_header(a)); -} - -static ptrdiff_t stbds_hm_find_slot(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode) -{ - void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); - stbds_hash_index *table = stbds_hash_table(raw_a); - size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed); - size_t step = STBDS_BUCKET_LENGTH; - size_t limit,i; - size_t pos; - stbds_hash_bucket *bucket; - - if (hash < 2) hash += 2; // stored hash values are forbidden from being 0, so we can detect empty slots - - pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2); - - for (;;) { - STBDS_STATS(++stbds_hash_probes); - bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; - - // start searching from pos to end of bucket, this should help performance on small hash tables that fit in cache - for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) { - if (bucket->hash[i] == hash) { - if (stbds_is_key_equal(a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { - return (pos & ~STBDS_BUCKET_MASK)+i; - } - } else if (bucket->hash[i] == STBDS_HASH_EMPTY) { - return -1; - } - } - - // search from beginning of bucket to pos - limit = pos & STBDS_BUCKET_MASK; - for (i = 0; i < limit; ++i) { - if (bucket->hash[i] == hash) { - if (stbds_is_key_equal(a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { - return (pos & ~STBDS_BUCKET_MASK)+i; - } - } else if (bucket->hash[i] == STBDS_HASH_EMPTY) { - return -1; - } - } - - // quadratic probing - pos += step; - step += STBDS_BUCKET_LENGTH; - pos &= (table->slot_count-1); - } - /* NOTREACHED */ -} - -void * stbds_hmget_key_ts(void *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode) -{ - size_t keyoffset = 0; - if (a == NULL) { - // make it non-empty so we can return a temp - a = stbds_arrgrowf(0, elemsize, 0, 1); - stbds_header(a)->length += 1; - memset(a, 0, elemsize); - *temp = STBDS_INDEX_EMPTY; - // adjust a to point after the default element - return STBDS_ARR_TO_HASH(a,elemsize); - } else { - stbds_hash_index *table; - void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); - // adjust a to point to the default element - table = (stbds_hash_index *) stbds_header(raw_a)->hash_table; - if (table == 0) { - *temp = -1; - } else { - ptrdiff_t slot = stbds_hm_find_slot(a, elemsize, key, keysize, keyoffset, mode); - if (slot < 0) { - *temp = STBDS_INDEX_EMPTY; - } else { - stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; - *temp = b->index[slot & STBDS_BUCKET_MASK]; - } - } - return a; - } -} - -void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode) -{ - ptrdiff_t temp; - void *p = stbds_hmget_key_ts(a, elemsize, key, keysize, &temp, mode); - stbds_temp(STBDS_HASH_TO_ARR(p,elemsize)) = temp; - return p; -} - -void * stbds_hmput_default(void *a, size_t elemsize) -{ - // three cases: - // a is NULL <- allocate - // a has a hash table but no entries, because of shmode <- grow - // a has entries <- do nothing - if (a == NULL || stbds_header(STBDS_HASH_TO_ARR(a,elemsize))->length == 0) { - a = stbds_arrgrowf(a ? STBDS_HASH_TO_ARR(a,elemsize) : NULL, elemsize, 0, 1); - stbds_header(a)->length += 1; - memset(a, 0, elemsize); - a=STBDS_ARR_TO_HASH(a,elemsize); - } - return a; -} - -static char *stbds_strdup(char *str); - -void *stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode) -{ - size_t keyoffset=0; - void *raw_a; - stbds_hash_index *table; - - if (a == NULL) { - a = stbds_arrgrowf(0, elemsize, 0, 1); - memset(a, 0, elemsize); - stbds_header(a)->length += 1; - // adjust a to point AFTER the default element - a = STBDS_ARR_TO_HASH(a,elemsize); - } - - // adjust a to point to the default element - raw_a = a; - a = STBDS_HASH_TO_ARR(a,elemsize); - - table = (stbds_hash_index *) stbds_header(a)->hash_table; - - if (table == NULL || table->used_count >= table->used_count_threshold) { - stbds_hash_index *nt; - size_t slot_count; - - slot_count = (table == NULL) ? STBDS_BUCKET_LENGTH : table->slot_count*2; - nt = stbds_make_hash_index(slot_count, table); - if (table) - STBDS_FREE(NULL, table); - else - nt->string.mode = mode >= STBDS_HM_STRING ? STBDS_SH_DEFAULT : 0; - stbds_header(a)->hash_table = table = nt; - STBDS_STATS(++stbds_hash_grow); - } - - // we iterate hash table explicitly because we want to track if we saw a tombstone - { - size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed); - size_t step = STBDS_BUCKET_LENGTH; - size_t pos; - ptrdiff_t tombstone = -1; - stbds_hash_bucket *bucket; - - // stored hash values are forbidden from being 0, so we can detect empty slots to early out quickly - if (hash < 2) hash += 2; - - pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2); - - for (;;) { - size_t limit, i; - STBDS_STATS(++stbds_hash_probes); - bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; - - // start searching from pos to end of bucket - for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) { - if (bucket->hash[i] == hash) { - if (stbds_is_key_equal(raw_a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { - stbds_temp(a) = bucket->index[i]; - if (mode >= STBDS_HM_STRING) - stbds_temp_key(a) = * (char **) ((char *) raw_a + elemsize*bucket->index[i] + keyoffset); - return STBDS_ARR_TO_HASH(a,elemsize); - } - } else if (bucket->hash[i] == 0) { - pos = (pos & ~STBDS_BUCKET_MASK) + i; - goto found_empty_slot; - } else if (tombstone < 0) { - if (bucket->index[i] == STBDS_INDEX_DELETED) - tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i); - } - } - - // search from beginning of bucket to pos - limit = pos & STBDS_BUCKET_MASK; - for (i = 0; i < limit; ++i) { - if (bucket->hash[i] == hash) { - if (stbds_is_key_equal(raw_a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { - stbds_temp(a) = bucket->index[i]; - return STBDS_ARR_TO_HASH(a,elemsize); - } - } else if (bucket->hash[i] == 0) { - pos = (pos & ~STBDS_BUCKET_MASK) + i; - goto found_empty_slot; - } else if (tombstone < 0) { - if (bucket->index[i] == STBDS_INDEX_DELETED) - tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i); - } - } - - // quadratic probing - pos += step; - step += STBDS_BUCKET_LENGTH; - pos &= (table->slot_count-1); - } - found_empty_slot: - if (tombstone >= 0) { - pos = tombstone; - --table->tombstone_count; - } - ++table->used_count; - - { - ptrdiff_t i = (ptrdiff_t) stbds_arrlen(a); - // we want to do stbds_arraddn(1), but we can't use the macros since we don't have something of the right type - if ((size_t) i+1 > stbds_arrcap(a)) - *(void **) &a = stbds_arrgrowf(a, elemsize, 1, 0); - raw_a = STBDS_ARR_TO_HASH(a,elemsize); - - STBDS_ASSERT((size_t) i+1 <= stbds_arrcap(a)); - stbds_header(a)->length = i+1; - bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; - bucket->hash[pos & STBDS_BUCKET_MASK] = hash; - bucket->index[pos & STBDS_BUCKET_MASK] = i-1; - stbds_temp(a) = i-1; - - switch (table->string.mode) { - case STBDS_SH_STRDUP: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = stbds_strdup((char*) key); break; - case STBDS_SH_ARENA: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = stbds_stralloc(&table->string, (char*)key); break; - case STBDS_SH_DEFAULT: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = (char *) key; break; - default: memcpy((char *) a + elemsize*i, key, keysize); break; - } - } - return STBDS_ARR_TO_HASH(a,elemsize); - } -} - -void * stbds_shmode_func(size_t elemsize, int mode) -{ - void *a = stbds_arrgrowf(0, elemsize, 0, 1); - stbds_hash_index *h; - memset(a, 0, elemsize); - stbds_header(a)->length = 1; - stbds_header(a)->hash_table = h = (stbds_hash_index *) stbds_make_hash_index(STBDS_BUCKET_LENGTH, NULL); - h->string.mode = (unsigned char) mode; - return STBDS_ARR_TO_HASH(a,elemsize); -} - -void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode) -{ - if (a == NULL) { - return 0; - } else { - stbds_hash_index *table; - void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); - table = (stbds_hash_index *) stbds_header(raw_a)->hash_table; - stbds_temp(raw_a) = 0; - if (table == 0) { - return a; - } else { - ptrdiff_t slot; - slot = stbds_hm_find_slot(a, elemsize, key, keysize, keyoffset, mode); - if (slot < 0) - return a; - else { - stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; - int i = slot & STBDS_BUCKET_MASK; - ptrdiff_t old_index = b->index[i]; - ptrdiff_t final_index = (ptrdiff_t) stbds_arrlen(raw_a)-1-1; // minus one for the raw_a vs a, and minus one for 'last' - STBDS_ASSERT(slot < (ptrdiff_t) table->slot_count); - --table->used_count; - ++table->tombstone_count; - stbds_temp(raw_a) = 1; - STBDS_ASSERT(table->used_count >= 0); - //STBDS_ASSERT(table->tombstone_count < table->slot_count/4); - b->hash[i] = STBDS_HASH_DELETED; - b->index[i] = STBDS_INDEX_DELETED; - - if (mode == STBDS_HM_STRING && table->string.mode == STBDS_SH_STRDUP) - STBDS_FREE(NULL, *(char**) ((char *) a+elemsize*old_index)); - - // if indices are the same, memcpy is a no-op, but back-pointer-fixup will fail, so skip - if (old_index != final_index) { - // swap delete - memmove((char*) a + elemsize*old_index, (char*) a + elemsize*final_index, elemsize); - - // now find the slot for the last element - if (mode == STBDS_HM_STRING) - slot = stbds_hm_find_slot(a, elemsize, *(char**) ((char *) a+elemsize*old_index + keyoffset), keysize, keyoffset, mode); - else - slot = stbds_hm_find_slot(a, elemsize, (char* ) a+elemsize*old_index + keyoffset, keysize, keyoffset, mode); - STBDS_ASSERT(slot >= 0); - b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; - i = slot & STBDS_BUCKET_MASK; - STBDS_ASSERT(b->index[i] == final_index); - b->index[i] = old_index; - } - stbds_header(raw_a)->length -= 1; - - if (table->used_count < table->used_count_shrink_threshold && table->slot_count > STBDS_BUCKET_LENGTH) { - stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count>>1, table); - STBDS_FREE(NULL, table); - STBDS_STATS(++stbds_hash_shrink); - } else if (table->tombstone_count > table->tombstone_count_threshold) { - stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count , table); - STBDS_FREE(NULL, table); - STBDS_STATS(++stbds_hash_rebuild); - } - - return a; - } - } - } - /* NOTREACHED */ -} - -static char *stbds_strdup(char *str) -{ - // to keep replaceable allocator simple, we don't want to use strdup. - // rolling our own also avoids problem of strdup vs _strdup - size_t len = strlen(str)+1; - char *p = (char*) STBDS_REALLOC(NULL, 0, len); - memmove(p, str, len); - return p; -} - -#ifndef STBDS_STRING_ARENA_BLOCKSIZE_MIN -#define STBDS_STRING_ARENA_BLOCKSIZE_MIN 512u -#endif -#ifndef STBDS_STRING_ARENA_BLOCKSIZE_MAX -#define STBDS_STRING_ARENA_BLOCKSIZE_MAX (1u<<20) -#endif - -char *stbds_stralloc(stbds_string_arena *a, char *str) -{ - char *p; - size_t len = strlen(str)+1; - if (len > a->remaining) { - // compute the next blocksize - size_t blocksize = a->block; - - // size is 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, etc., so that - // there are log(SIZE) allocations to free when we destroy the table - blocksize = (size_t) (STBDS_STRING_ARENA_BLOCKSIZE_MIN) << (blocksize>>1); - - // if size is under 1M, advance to next blocktype - if (blocksize < (size_t)(STBDS_STRING_ARENA_BLOCKSIZE_MAX)) - ++a->block; - - if (len > blocksize) { - // if string is larger than blocksize, then just allocate the full size. - // note that we still advance string_block so block size will continue - // increasing, so e.g. if somebody only calls this with 1000-long strings, - // eventually the arena will start doubling and handling those as well - stbds_string_block *sb = (stbds_string_block *) STBDS_REALLOC(NULL, 0, sizeof(*sb)-8 + len); - memmove(sb->storage, str, len); - if (a->storage) { - // insert it after the first element, so that we don't waste the space there - sb->next = a->storage->next; - a->storage->next = sb; - } else { - sb->next = 0; - a->storage = sb; - a->remaining = 0; // this is redundant, but good for clarity - } - return sb->storage; - } else { - stbds_string_block *sb = (stbds_string_block *) STBDS_REALLOC(NULL, 0, sizeof(*sb)-8 + blocksize); - sb->next = a->storage; - a->storage = sb; - a->remaining = blocksize; - } - } - - STBDS_ASSERT(len <= a->remaining); - p = a->storage->storage + a->remaining - len; - a->remaining -= len; - memmove(p, str, len); - return p; -} - -void stbds_strreset(stbds_string_arena *a) -{ - stbds_string_block *x,*y; - x = a->storage; - while (x) { - y = x->next; - STBDS_FREE(NULL, x); - x = y; - } - memset(a, 0, sizeof(*a)); -} - -#endif - -////////////////////////////////////////////////////////////////////////////// -// -// UNIT TESTS -// - -#ifdef STBDS_UNIT_TESTS -#include <stdio.h> -#ifdef STBDS_ASSERT_WAS_UNDEFINED -#undef STBDS_ASSERT -#endif -#ifndef STBDS_ASSERT -#define STBDS_ASSERT assert -#include <assert.h> -#endif - -typedef struct { int key,b,c,d; } stbds_struct; -typedef struct { int key[2],b,c,d; } stbds_struct2; - -static char buffer[256]; -char *strkey(int n) -{ -#if defined(_WIN32) && defined(__STDC_WANT_SECURE_LIB__) - sprintf_s(buffer, sizeof(buffer), "test_%d", n); -#else - sprintf(buffer, "test_%d", n); -#endif - return buffer; -} - -void stbds_unit_tests(void) -{ -#if defined(_MSC_VER) && _MSC_VER <= 1200 && defined(__cplusplus) - // VC6 C++ doesn't like the template<> trick on unnamed structures, so do nothing! - STBDS_ASSERT(0); -#else - const int testsize = 100000; - const int testsize2 = testsize/20; - int *arr=NULL; - struct { int key; int value; } *intmap = NULL; - struct { char *key; int value; } *strmap = NULL, s; - struct { stbds_struct key; int value; } *map = NULL; - stbds_struct *map2 = NULL; - stbds_struct2 *map3 = NULL; - stbds_string_arena sa = { 0 }; - int key3[2] = { 1,2 }; - ptrdiff_t temp; - - int i,j; - - STBDS_ASSERT(arrlen(arr)==0); - for (i=0; i < 20000; i += 50) { - for (j=0; j < i; ++j) - arrpush(arr,j); - arrfree(arr); - } - - for (i=0; i < 4; ++i) { - arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); - arrdel(arr,i); - arrfree(arr); - arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); - arrdelswap(arr,i); - arrfree(arr); - } - - for (i=0; i < 5; ++i) { - arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); - stbds_arrins(arr,i,5); - STBDS_ASSERT(arr[i] == 5); - if (i < 4) - STBDS_ASSERT(arr[4] == 4); - arrfree(arr); - } - - i = 1; - STBDS_ASSERT(hmgeti(intmap,i) == -1); - hmdefault(intmap, -2); - STBDS_ASSERT(hmgeti(intmap, i) == -1); - STBDS_ASSERT(hmget (intmap, i) == -2); - for (i=0; i < testsize; i+=2) - hmput(intmap, i, i*5); - for (i=0; i < testsize; i+=1) { - if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -2 ); - else STBDS_ASSERT(hmget(intmap, i) == i*5); - if (i & 1) STBDS_ASSERT(hmget_ts(intmap, i, temp) == -2 ); - else STBDS_ASSERT(hmget_ts(intmap, i, temp) == i*5); - } - for (i=0; i < testsize; i+=2) - hmput(intmap, i, i*3); - for (i=0; i < testsize; i+=1) - if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -2 ); - else STBDS_ASSERT(hmget(intmap, i) == i*3); - for (i=2; i < testsize; i+=4) - hmdel(intmap, i); // delete half the entries - for (i=0; i < testsize; i+=1) - if (i & 3) STBDS_ASSERT(hmget(intmap, i) == -2 ); - else STBDS_ASSERT(hmget(intmap, i) == i*3); - for (i=0; i < testsize; i+=1) - hmdel(intmap, i); // delete the rest of the entries - for (i=0; i < testsize; i+=1) - STBDS_ASSERT(hmget(intmap, i) == -2 ); - hmfree(intmap); - for (i=0; i < testsize; i+=2) - hmput(intmap, i, i*3); - hmfree(intmap); - - #if defined(__clang__) || defined(__GNUC__) - #ifndef __cplusplus - intmap = NULL; - hmput(intmap, 15, 7); - hmput(intmap, 11, 3); - hmput(intmap, 9, 5); - STBDS_ASSERT(hmget(intmap, 9) == 5); - STBDS_ASSERT(hmget(intmap, 11) == 3); - STBDS_ASSERT(hmget(intmap, 15) == 7); - #endif - #endif - - for (i=0; i < testsize; ++i) - stralloc(&sa, strkey(i)); - strreset(&sa); - - { - s.key = "a", s.value = 1; - shputs(strmap, s); - STBDS_ASSERT(*strmap[0].key == 'a'); - STBDS_ASSERT(strmap[0].key == s.key); - STBDS_ASSERT(strmap[0].value == s.value); - shfree(strmap); - } - - { - s.key = "a", s.value = 1; - sh_new_strdup(strmap); - shputs(strmap, s); - STBDS_ASSERT(*strmap[0].key == 'a'); - STBDS_ASSERT(strmap[0].key != s.key); - STBDS_ASSERT(strmap[0].value == s.value); - shfree(strmap); - } - - { - s.key = "a", s.value = 1; - sh_new_arena(strmap); - shputs(strmap, s); - STBDS_ASSERT(*strmap[0].key == 'a'); - STBDS_ASSERT(strmap[0].key != s.key); - STBDS_ASSERT(strmap[0].value == s.value); - shfree(strmap); - } - - for (j=0; j < 2; ++j) { - STBDS_ASSERT(shgeti(strmap,"foo") == -1); - if (j == 0) - sh_new_strdup(strmap); - else - sh_new_arena(strmap); - STBDS_ASSERT(shgeti(strmap,"foo") == -1); - shdefault(strmap, -2); - STBDS_ASSERT(shgeti(strmap,"foo") == -1); - for (i=0; i < testsize; i+=2) - shput(strmap, strkey(i), i*3); - for (i=0; i < testsize; i+=1) - if (i & 1) STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); - else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3); - for (i=2; i < testsize; i+=4) - shdel(strmap, strkey(i)); // delete half the entries - for (i=0; i < testsize; i+=1) - if (i & 3) STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); - else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3); - for (i=0; i < testsize; i+=1) - shdel(strmap, strkey(i)); // delete the rest of the entries - for (i=0; i < testsize; i+=1) - STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); - shfree(strmap); - } - - { - struct { char *key; char value; } *hash = NULL; - char name[4] = "jen"; - shput(hash, "bob" , 'h'); - shput(hash, "sally" , 'e'); - shput(hash, "fred" , 'l'); - shput(hash, "jen" , 'x'); - shput(hash, "doug" , 'o'); - - shput(hash, name , 'l'); - shfree(hash); - } - - for (i=0; i < testsize; i += 2) { - stbds_struct s = { i,i*2,i*3,i*4 }; - hmput(map, s, i*5); - } - - for (i=0; i < testsize; i += 1) { - stbds_struct s = { i,i*2,i*3 ,i*4 }; - stbds_struct t = { i,i*2,i*3+1,i*4 }; - if (i & 1) STBDS_ASSERT(hmget(map, s) == 0); - else STBDS_ASSERT(hmget(map, s) == i*5); - if (i & 1) STBDS_ASSERT(hmget_ts(map, s, temp) == 0); - else STBDS_ASSERT(hmget_ts(map, s, temp) == i*5); - //STBDS_ASSERT(hmget(map, t.key) == 0); - } - - for (i=0; i < testsize; i += 2) { - stbds_struct s = { i,i*2,i*3,i*4 }; - hmputs(map2, s); - } - hmfree(map); - - for (i=0; i < testsize; i += 1) { - stbds_struct s = { i,i*2,i*3,i*4 }; - stbds_struct t = { i,i*2,i*3+1,i*4 }; - if (i & 1) STBDS_ASSERT(hmgets(map2, s.key).d == 0); - else STBDS_ASSERT(hmgets(map2, s.key).d == i*4); - //STBDS_ASSERT(hmgetp(map2, t.key) == 0); - } - hmfree(map2); - - for (i=0; i < testsize; i += 2) { - stbds_struct2 s = { { i,i*2 }, i*3,i*4, i*5 }; - hmputs(map3, s); - } - for (i=0; i < testsize; i += 1) { - stbds_struct2 s = { { i,i*2}, i*3, i*4, i*5 }; - stbds_struct2 t = { { i,i*2}, i*3+1, i*4, i*5 }; - if (i & 1) STBDS_ASSERT(hmgets(map3, s.key).d == 0); - else STBDS_ASSERT(hmgets(map3, s.key).d == i*5); - //STBDS_ASSERT(hmgetp(map3, t.key) == 0); - } -#endif -} -#endif - - -/* ------------------------------------------------------------------------------- -This software is available under 2 licenses -- choose whichever you prefer. ------------------------------------------------------------------------------- -ALTERNATIVE A - MIT License -Copyright (c) 2019 Sean Barrett -Permission is hereby granted, free of charge, to any person obtaining a copy of -this software and associated documentation files (the "Software"), to deal in -the Software without restriction, including without limitation the rights to -use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies -of the Software, and to permit persons to whom the Software is furnished to do -so, subject to the following conditions: -The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. ------------------------------------------------------------------------------- -ALTERNATIVE B - Public Domain (www.unlicense.org) -This is free and unencumbered software released into the public domain. -Anyone is free to copy, modify, publish, use, compile, sell, or distribute this -software, either in source code form or as a compiled binary, for any purpose, -commercial or non-commercial, and by any means. -In jurisdictions that recognize copyright laws, the author or authors of this -software dedicate any and all copyright interest in the software to the public -domain. We make this dedication for the benefit of the public at large and to -the detriment of our heirs and successors. We intend this dedication to be an -overt act of relinquishment in perpetuity of all present and future rights to -this software under copyright law. -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN -ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION -WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ------------------------------------------------------------------------------- -*/ |