hash.c

   1 /* $Id: hash.c,v 1.7 2009/03/08 11:41:22 kristaps Exp $ */
   2 /*
   3  * Copyright (c) 2008 Kristaps Dzonsons <kristaps@kth.se>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the
   7  * above copyright notice and this permission notice appear in all
   8  * copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
  11  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
  12  * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
  13  * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
  14  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  15  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  16  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  17  * PERFORMANCE OF THIS SOFTWARE.
  18  */
  19 #include <assert.h>
  20 #include <ctype.h>
  21 #include <err.h>
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <string.h>
  25
  26 #include "private.h"
  27
  28 /*
  29  * Routines for the perfect-hash hashtable used by the parser to look up
  30  * tokens by their string-ified names (`.Fl' -> MDOC_Fl).  The
  31  * allocation penalty for this is 27 * 26 * sizeof(ptr).
  32  */
  33
  34 void
  35 mdoc_tokhash_free(void *htab)
  36 {
  37
  38         free(htab);
  39 }
  40
  41
  42 void *
  43 mdoc_tokhash_alloc(void)
  44 {
  45         int               i, major, minor, ind;
  46         const void      **htab;
  47
  48         htab = calloc(27 * 26, sizeof(struct mdoc_macro *));
  49         if (NULL == htab)
  50                 err(1, "calloc");
  51
  52         for (i = 1; i < MDOC_MAX; i++) {
  53                 major = mdoc_macronames[i][0];
  54                 assert((major >= 65 && major <= 90) ||
  55                                 major == 37);
  56
  57                 if (major == 37)
  58                         major = 0;
  59                 else
  60                         major -= 64;
  61
  62                 minor = mdoc_macronames[i][1];
  63                 assert((minor >= 65 && minor <= 90) ||
  64                                 (minor == 49) ||
  65                                 (minor >= 97 && minor <= 122));
  66
  67                 if (minor == 49)
  68                         minor = 0;
  69                 else if (minor <= 90)
  70                         minor -= 65;
  71                 else
  72                         minor -= 97;
  73
  74                 assert(major >= 0 && major < 27);
  75                 assert(minor >= 0 && minor < 26);
  76
  77                 ind = (major * 27) + minor;
  78
  79                 assert(NULL == htab[ind]);
  80                 htab[ind] = &mdoc_macros[i];
  81         }
  82
  83         return((void *)htab);
  84 }
  85
  86
  87 int
  88 mdoc_tokhash_find(const void *arg, const char *tmp)
  89 {
  90         int               major, minor, ind, slot;
  91         const void      **htab;
  92
  93         htab = /* LINTED */
  94                 (const void **)arg;
  95
  96         if (0 == tmp[0] || 0 == tmp[1])
  97                 return(MDOC_MAX);
  98
  99         if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
 100                 return(MDOC_MAX);
 101
 102         if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
 103                                 (tmp[1] == 49) ||
 104                                 (tmp[1] >= 97 && tmp[1] <= 122)))
 105                 return(MDOC_MAX);
 106
 107         if (tmp[0] == 37)
 108                 major = 0;
 109         else
 110                 major = tmp[0] - 64;
 111
 112         if (tmp[1] == 49)
 113                 minor = 0;
 114         else if (tmp[1] <= 90)
 115                 minor = tmp[1] - 65;
 116         else
 117                 minor = tmp[1] - 97;
 118
 119         ind = (major * 27) + minor;
 120         if (ind < 0 || ind >= (27 * 26))
 121                 return(MDOC_MAX);
 122
 123         if (NULL == htab[ind])
 124                 return(MDOC_MAX);
 125
 126         slot = htab[ind] - /* LINTED */
 127                 (void *)mdoc_macros;
 128         assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
 129         slot /= sizeof(struct mdoc_macro);
 130
 131         /*
 132          * FIXME: is this necessary, or do we only need to check the
 133          * remaining characters (2+)?
 134          */
 135
 136         if (0 != strcmp(mdoc_macronames[slot], tmp))
 137                 return(MDOC_MAX);
 138         return(slot);
 139 }
 140