mdoc_hash.c

   1 /*      $Id: mdoc_hash.c,v 1.5 2009/06/16 19:55:28 kristaps Exp $ */
   2 /*
   3  * Copyright (c) 2008, 2009 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 above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17 #include <assert.h>
  18 #include <ctype.h>
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <string.h>
  22
  23 #include "libmdoc.h"
  24
  25 /*
  26  * Routines for the perfect-hash hashtable used by the parser to look up
  27  * tokens by their string-ified names (`.Fl' -> MDOC_Fl).  The
  28  * allocation penalty for this is 27 * 26 * sizeof(ptr).
  29  */
  30
  31 void
  32 mdoc_hash_free(void *htab)
  33 {
  34
  35         free(htab);
  36 }
  37
  38
  39 void *
  40 mdoc_hash_alloc(void)
  41 {
  42         int               i, major, minor, ind;
  43         const void      **htab;
  44
  45         htab = calloc(27 * 26 * 3, sizeof(struct mdoc_macro *));
  46         if (NULL == htab)
  47                 return(NULL);
  48
  49         for (i = 0; i < MDOC_MAX; i++) {
  50                 major = mdoc_macronames[i][0];
  51                 assert((major >= 65 && major <= 90) ||
  52                                 major == 37);
  53
  54                 if (major == 37)
  55                         major = 0;
  56                 else
  57                         major -= 64;
  58
  59                 minor = mdoc_macronames[i][1];
  60                 assert((minor >= 65 && minor <= 90) ||
  61                                 (minor == 49) ||
  62                                 (minor >= 97 && minor <= 122));
  63
  64                 if (minor == 49)
  65                         minor = 0;
  66                 else if (minor <= 90)
  67                         minor -= 65;
  68                 else
  69                         minor -= 97;
  70
  71                 assert(major >= 0 && major < 27);
  72                 assert(minor >= 0 && minor < 26);
  73
  74                 ind = (major * 27 * 3) + (minor * 3);
  75
  76                 if (NULL == htab[ind]) {
  77                         htab[ind] = &mdoc_macros[i];
  78                         continue;
  79                 }
  80
  81                 if (NULL == htab[++ind]) {
  82                         htab[ind] = &mdoc_macros[i];
  83                         continue;
  84                 }
  85
  86                 assert(NULL == htab[++ind]);
  87                 htab[ind] = &mdoc_macros[i];
  88         }
  89
  90         return((void *)htab);
  91 }
  92
  93
  94 int
  95 mdoc_hash_find(const void *arg, const char *tmp)
  96 {
  97         int               major, minor, ind, slot;
  98         const void      **htab;
  99
 100         htab = /* LINTED */
 101                 (const void **)arg;
 102
 103         if (0 == tmp[0] || 0 == tmp[1])
 104                 return(MDOC_MAX);
 105         if (tmp[2] && tmp[3])
 106                 return(MDOC_MAX);
 107
 108         if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
 109                 return(MDOC_MAX);
 110
 111         if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
 112                                 (tmp[1] == 49) ||
 113                                 (tmp[1] >= 97 && tmp[1] <= 122)))
 114                 return(MDOC_MAX);
 115
 116         if (tmp[0] == 37)
 117                 major = 0;
 118         else
 119                 major = tmp[0] - 64;
 120
 121         if (tmp[1] == 49)
 122                 minor = 0;
 123         else if (tmp[1] <= 90)
 124                 minor = tmp[1] - 65;
 125         else
 126                 minor = tmp[1] - 97;
 127
 128         ind = (major * 27 * 3) + (minor * 3);
 129         if (ind < 0 || ind >= (27 * 26 * 3))
 130                 return(MDOC_MAX);
 131
 132         if (htab[ind]) {
 133                 slot = htab[ind] - /* LINTED */
 134                         (void *)mdoc_macros;
 135                 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
 136                 slot /= sizeof(struct mdoc_macro);
 137                 if (mdoc_macronames[slot][0] == tmp[0] &&
 138                                 mdoc_macronames[slot][1] == tmp[1] &&
 139                                 (0 == tmp[2] ||
 140                                  mdoc_macronames[slot][2] == tmp[2]))
 141                         return(slot);
 142                 ind++;
 143         }
 144
 145         if (htab[ind]) {
 146                 slot = htab[ind] - /* LINTED */
 147                         (void *)mdoc_macros;
 148                 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
 149                 slot /= sizeof(struct mdoc_macro);
 150                 if (mdoc_macronames[slot][0] == tmp[0] &&
 151                                 mdoc_macronames[slot][1] == tmp[1] &&
 152                                 (0 == tmp[2] ||
 153                                  mdoc_macronames[slot][2] == tmp[2]))
 154                         return(slot);
 155                 ind++;
 156         }
 157
 158         if (NULL == htab[ind])
 159                 return(MDOC_MAX);
 160         slot = htab[ind] - /* LINTED */
 161                 (void *)mdoc_macros;
 162         assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
 163         slot /= sizeof(struct mdoc_macro);
 164         if (mdoc_macronames[slot][0] == tmp[0] &&
 165                         mdoc_macronames[slot][1] == tmp[1] &&
 166                         (0 == tmp[2] ||
 167                          mdoc_macronames[slot][2] == tmp[2]))
 168                 return(slot);
 169
 170         return(MDOC_MAX);
 171 }
 172