Return to hash.c CVS log

Up to [cvsweb.bsd.lv] / mandoc

Annotation of mandoc/hash.c, Revision 1.8

1.8     ! kristaps    1: /* $Id: hash.c,v 1.7 2009/03/08 11:41:22 kristaps Exp $ */
1.1       kristaps    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:
1.5       kristaps   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
1.6       kristaps   31:  * allocation penalty for this is 27 * 26 * sizeof(ptr).
1.5       kristaps   32:  */
                     33:
1.1       kristaps   34: void
1.3       kristaps   35: mdoc_tokhash_free(void *htab)
1.1       kristaps   36: {
                     37:
                     38:        free(htab);
                     39: }
                     40:
                     41:
                     42: void *
1.3       kristaps   43: mdoc_tokhash_alloc(void)
1.1       kristaps   44: {
1.2       kristaps   45:        int               i, major, minor, ind;
1.1       kristaps   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:
1.2       kristaps   77:                ind = (major * 27) + minor;
1.1       kristaps   78:
1.2       kristaps   79:                assert(NULL == htab[ind]);
                     80:                htab[ind] = &mdoc_macros[i];
1.1       kristaps   81:        }
                     82:
                     83:        return((void *)htab);
                     84: }
                     85:
                     86:
                     87: int
1.3       kristaps   88: mdoc_tokhash_find(const void *arg, const char *tmp)
1.1       kristaps   89: {
1.2       kristaps   90:        int               major, minor, ind, slot;
1.1       kristaps   91:        const void      **htab;
                     92:
1.2       kristaps   93:        htab = /* LINTED */
                     94:                (const void **)arg;
1.1       kristaps   95:
                     96:        if (0 == tmp[0] || 0 == tmp[1])
                     97:                return(MDOC_MAX);
1.8     ! kristaps   98:        if (tmp[2] && tmp[3])
        !            99:                return(MDOC_MAX);
1.1       kristaps  100:
                    101:        if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
                    102:                return(MDOC_MAX);
                    103:
                    104:        if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
                    105:                                (tmp[1] == 49) ||
                    106:                                (tmp[1] >= 97 && tmp[1] <= 122)))
                    107:                return(MDOC_MAX);
                    108:
                    109:        if (tmp[0] == 37)
                    110:                major = 0;
                    111:        else
                    112:                major = tmp[0] - 64;
                    113:
                    114:        if (tmp[1] == 49)
                    115:                minor = 0;
                    116:        else if (tmp[1] <= 90)
                    117:                minor = tmp[1] - 65;
                    118:        else
                    119:                minor = tmp[1] - 97;
                    120:
1.2       kristaps  121:        ind = (major * 27) + minor;
1.4       kristaps  122:        if (ind < 0 || ind >= (27 * 26))
                    123:                return(MDOC_MAX);
1.1       kristaps  124:
1.2       kristaps  125:        if (NULL == htab[ind])
1.1       kristaps  126:                return(MDOC_MAX);
                    127:
1.2       kristaps  128:        slot = htab[ind] - /* LINTED */
                    129:                (void *)mdoc_macros;
                    130:        assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
1.1       kristaps  131:        slot /= sizeof(struct mdoc_macro);
                    132:
1.8     ! kristaps  133:        if (0 == tmp[2])
        !           134:                return(slot);
1.7       kristaps  135:
1.8     ! kristaps  136:        assert(0 == tmp[3]);
        !           137:        return(tmp[2] == mdoc_macronames[slot][2] ? slot : MDOC_MAX);
1.1       kristaps  138: }
                    139: