lib/gen_tables.h

   1 /* gen_tables.h -- Declarations used for lookup tables.
   2  * Copyright 2008 Red Hat Inc., Durham, North Carolina.
   3  * All Rights Reserved.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  * Authors:
  20  *      Miloslav Trmač <mitr@redhat.com>
  21  */
  22 #ifndef GEN_TABLES_H__
  23 #define GEN_TABLES_H__
  24
  25 #include <stddef.h>
  26 #include <stdint.h>
  27
  28 /* Assumes ASCII; verified in gen_tables.c. */
  29 #define GT_ISUPPER(X) ((X) >= 'A' && (X) <= 'Z')
  30 #define GT_ISLOWER(X) ((X) >= 'a' && (X) <= 'z')
  31
  32 inline static int s2i__(const char *strings, const unsigned *s_table,
  33                         const int *i_table, size_t n, const char *s, int *value)
  34 {
  35         ssize_t left, right;
  36
  37         left = 0;
  38         right = n - 1;
  39         while (left <= right) { /* invariant: left <= x <= right */
  40                 size_t mid;
  41                 int r;
  42
  43                 mid = (left + right) / 2;
  44                 /* FIXME? avoid recomparing a common prefix */
  45                 r = strcmp(s, strings + s_table[mid]);
  46                 if (r == 0) {
  47                         *value = i_table[mid];
  48                         return 1;
  49                 }
  50                 if (r < 0)
  51                         right = mid - 1;
  52                 else
  53                         left = mid + 1;
  54         }
  55         return 0;
  56 }
  57
  58 inline static const char *i2s_direct__(const char *strings,
  59                                        const unsigned *table, int min, int max,
  60                                        int v)
  61 {
  62         unsigned off;
  63
  64         if (v < min || v > max)
  65                 return NULL;
  66         off = table[v - min];
  67         if (off != -1u)
  68                 return strings + off;
  69         return NULL;
  70 }
  71
  72 inline static const char *i2s_bsearch__(const char *strings,
  73                                         const int *i_table,
  74                                         const unsigned *s_table, size_t n,
  75                                         int v)
  76 {
  77         ssize_t left, right;
  78
  79         left = 0;
  80         right = n - 1;
  81         while (left <= right) { /* invariant: left <= x <= right */
  82                 size_t mid;
  83                 int mid_val;
  84
  85                 mid = (left + right) / 2;
  86                 mid_val = i_table[mid];
  87                 if (v == mid_val)
  88                         return strings + s_table[mid];
  89                 if (v < mid_val)
  90                         right = mid - 1;
  91                 else
  92                         left = mid + 1;
  93         }
  94         return NULL;
  95 }
  96
  97 struct transtab {
  98         int value;
  99         unsigned offset;
 100 };
 101
 102 #endif