Return to hash.c CVS log

Up to [cvsweb.bsd.lv] / mandoc

Annotation of mandoc/hash.c, Revision 1.5

1.5     ! kristaps    1: /* $Id: hash.c,v 1.4 2009/01/05 17:57:07 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
        !            31:  * allocation penalty for this is 27 * 26 * sizeof(ptr).
        !            32:  */
        !            33:
1.1       kristaps   34:
                     35: void
1.3       kristaps   36: mdoc_tokhash_free(void *htab)
1.1       kristaps   37: {
                     38:
                     39:        free(htab);
                     40: }
                     41:
                     42:
                     43: void *
1.3       kristaps   44: mdoc_tokhash_alloc(void)
1.1       kristaps   45: {
1.2       kristaps   46:        int               i, major, minor, ind;
1.1       kristaps   47:        const void      **htab;
                     48:
                     49:        htab = calloc(27 * 26, sizeof(struct mdoc_macro *));
                     50:        if (NULL == htab)
                     51:                err(1, "calloc");
                     52:
                     53:        for (i = 1; i < MDOC_MAX; i++) {
                     54:                major = mdoc_macronames[i][0];
                     55:                assert((major >= 65 && major <= 90) ||
                     56:                                major == 37);
                     57:
                     58:                if (major == 37)
                     59:                        major = 0;
                     60:                else
                     61:                        major -= 64;
                     62:
                     63:                minor = mdoc_macronames[i][1];
                     64:                assert((minor >= 65 && minor <= 90) ||
                     65:                                (minor == 49) ||
                     66:                                (minor >= 97 && minor <= 122));
                     67:
                     68:                if (minor == 49)
                     69:                        minor = 0;
                     70:                else if (minor <= 90)
                     71:                        minor -= 65;
                     72:                else
                     73:                        minor -= 97;
                     74:
                     75:                assert(major >= 0 && major < 27);
                     76:                assert(minor >= 0 && minor < 26);
                     77:
1.2       kristaps   78:                ind = (major * 27) + minor;
1.1       kristaps   79:
1.2       kristaps   80:                assert(NULL == htab[ind]);
                     81:                htab[ind] = &mdoc_macros[i];
1.1       kristaps   82:        }
                     83:
                     84:        return((void *)htab);
                     85: }
                     86:
                     87:
                     88: int
1.3       kristaps   89: mdoc_tokhash_find(const void *arg, const char *tmp)
1.1       kristaps   90: {
1.2       kristaps   91:        int               major, minor, ind, slot;
1.1       kristaps   92:        const void      **htab;
                     93:
1.2       kristaps   94:        htab = /* LINTED */
                     95:                (const void **)arg;
1.1       kristaps   96:
                     97:        if (0 == tmp[0] || 0 == tmp[1])
                     98:                return(MDOC_MAX);
                     99:
                    100:        if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
                    101:                return(MDOC_MAX);
                    102:
                    103:        if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
                    104:                                (tmp[1] == 49) ||
                    105:                                (tmp[1] >= 97 && tmp[1] <= 122)))
                    106:                return(MDOC_MAX);
                    107:
                    108:        if (tmp[0] == 37)
                    109:                major = 0;
                    110:        else
                    111:                major = tmp[0] - 64;
                    112:
                    113:        if (tmp[1] == 49)
                    114:                minor = 0;
                    115:        else if (tmp[1] <= 90)
                    116:                minor = tmp[1] - 65;
                    117:        else
                    118:                minor = tmp[1] - 97;
                    119:
1.2       kristaps  120:        ind = (major * 27) + minor;
1.4       kristaps  121:        if (ind < 0 || ind >= (27 * 26))
                    122:                return(MDOC_MAX);
1.1       kristaps  123:
1.2       kristaps  124:        if (NULL == htab[ind])
1.1       kristaps  125:                return(MDOC_MAX);
                    126:
1.2       kristaps  127:        slot = htab[ind] - /* LINTED */
                    128:                (void *)mdoc_macros;
                    129:        assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
1.1       kristaps  130:        slot /= sizeof(struct mdoc_macro);
                    131:
                    132:        if (0 != strcmp(mdoc_macronames[slot], tmp))
                    133:                return(MDOC_MAX);
                    134:        return(slot);
                    135: }
                    136: