-/* $Id: mdoc_hash.c,v 1.4 2009/06/10 20:18:43 kristaps Exp $ */
+/* $Id: mdoc_hash.c,v 1.21 2014/08/10 23:54:41 schwarze Exp $ */
/*
- * Copyright (c) 2008, 2009 Kristaps Dzonsons <kristaps@kth.se>
+ * Copyright (c) 2008, 2009 Kristaps Dzonsons <kristaps@bsd.lv>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include "config.h"
+
+#include <sys/types.h>
+
#include <assert.h>
#include <ctype.h>
+#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
+#include "mdoc.h"
#include "libmdoc.h"
+static unsigned char table[27 * 12];
+
+
/*
- * Routines for the perfect-hash hashtable used by the parser to look up
- * tokens by their string-ified names (`.Fl' -> MDOC_Fl). The
- * allocation penalty for this is 27 * 26 * sizeof(ptr).
+ * XXX - this hash has global scope, so if intended for use as a library
+ * with multiple callers, it will need re-invocation protection.
*/
-
void
-mdoc_hash_free(void *htab)
+mdoc_hash_init(void)
{
+ int i, j, major;
+ const char *p;
- free(htab);
-}
-
+ memset(table, UCHAR_MAX, sizeof(table));
-void *
-mdoc_hash_alloc(void)
-{
- int i, major, minor, ind;
- const void **htab;
+ for (i = 0; i < (int)MDOC_MAX; i++) {
+ p = mdoc_macronames[i];
- htab = calloc(27 * 26 * 3, sizeof(struct mdoc_macro *));
- if (NULL == htab)
- return(NULL);
-
- for (i = 1; i < MDOC_MAX; i++) {
- major = mdoc_macronames[i][0];
- assert((major >= 65 && major <= 90) ||
- major == 37);
-
- if (major == 37)
- major = 0;
+ if (isalpha((unsigned char)p[1]))
+ major = 12 * (tolower((unsigned char)p[1]) - 97);
else
- major -= 64;
-
- minor = mdoc_macronames[i][1];
- assert((minor >= 65 && minor <= 90) ||
- (minor == 49) ||
- (minor >= 97 && minor <= 122));
-
- if (minor == 49)
- minor = 0;
- else if (minor <= 90)
- minor -= 65;
- else
- minor -= 97;
-
- assert(major >= 0 && major < 27);
- assert(minor >= 0 && minor < 26);
-
- ind = (major * 27 * 3) + (minor * 3);
-
- if (NULL == htab[ind]) {
- htab[ind] = &mdoc_macros[i];
- continue;
- }
+ major = 12 * 26;
- if (NULL == htab[++ind]) {
- htab[ind] = &mdoc_macros[i];
- continue;
- }
+ for (j = 0; j < 12; j++)
+ if (UCHAR_MAX == table[major + j]) {
+ table[major + j] = (unsigned char)i;
+ break;
+ }
- assert(NULL == htab[++ind]);
- htab[ind] = &mdoc_macros[i];
+ assert(j < 12);
}
-
- return((void *)htab);
}
-
-int
-mdoc_hash_find(const void *arg, const char *tmp)
+enum mdoct
+mdoc_hash_find(const char *p)
{
- int major, minor, ind, slot;
- const void **htab;
-
- htab = /* LINTED */
- (const void **)arg;
-
- if (0 == tmp[0] || 0 == tmp[1])
- return(MDOC_MAX);
- if (tmp[2] && tmp[3])
- return(MDOC_MAX);
+ int major, i, j;
- if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
+ if (0 == p[0])
return(MDOC_MAX);
-
- if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
- (tmp[1] == 49) ||
- (tmp[1] >= 97 && tmp[1] <= 122)))
+ if ( ! isalpha((unsigned char)p[0]) && '%' != p[0])
return(MDOC_MAX);
- if (tmp[0] == 37)
- major = 0;
+ if (isalpha((unsigned char)p[1]))
+ major = 12 * (tolower((unsigned char)p[1]) - 97);
+ else if ('1' == p[1])
+ major = 12 * 26;
else
- major = tmp[0] - 64;
-
- if (tmp[1] == 49)
- minor = 0;
- else if (tmp[1] <= 90)
- minor = tmp[1] - 65;
- else
- minor = tmp[1] - 97;
-
- ind = (major * 27 * 3) + (minor * 3);
- if (ind < 0 || ind >= (27 * 26 * 3))
return(MDOC_MAX);
- if (htab[ind]) {
- slot = htab[ind] - /* LINTED */
- (void *)mdoc_macros;
- assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
- slot /= sizeof(struct mdoc_macro);
- if (mdoc_macronames[slot][0] == tmp[0] &&
- mdoc_macronames[slot][1] == tmp[1] &&
- (0 == tmp[2] ||
- mdoc_macronames[slot][2] == tmp[2]))
- return(slot);
- ind++;
- }
+ if (p[2] && p[3])
+ return(MDOC_MAX);
- if (htab[ind]) {
- slot = htab[ind] - /* LINTED */
- (void *)mdoc_macros;
- assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
- slot /= sizeof(struct mdoc_macro);
- if (mdoc_macronames[slot][0] == tmp[0] &&
- mdoc_macronames[slot][1] == tmp[1] &&
- (0 == tmp[2] ||
- mdoc_macronames[slot][2] == tmp[2]))
- return(slot);
- ind++;
+ for (j = 0; j < 12; j++) {
+ if (UCHAR_MAX == (i = table[major + j]))
+ break;
+ if (0 == strcmp(p, mdoc_macronames[i]))
+ return((enum mdoct)i);
}
- if (NULL == htab[ind])
- return(MDOC_MAX);
- slot = htab[ind] - /* LINTED */
- (void *)mdoc_macros;
- assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
- slot /= sizeof(struct mdoc_macro);
- if (mdoc_macronames[slot][0] == tmp[0] &&
- mdoc_macronames[slot][1] == tmp[1] &&
- (0 == tmp[2] ||
- mdoc_macronames[slot][2] == tmp[2]))
- return(slot);
-
return(MDOC_MAX);
}
-
git.ckatri.com / mandoc.git / blobdiff