src/include/itable.h

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989-2014  Free Software Foundation, Inc.
   3      Written by James Clark (jjc@jclark.com)
   4
   5 This file is part of groff.
   6
   7 groff is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation, either version 3 of the License, or
  10 (at your option) any later version.
  11
  12 groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
  19
  20 #include <assert.h>
  21
  22 // name2(a,b) concatenates two C identifiers.
  23 #ifdef TRADITIONAL_CPP
  24 # define name2(a,b) a/**/b
  25 #else /* not TRADITIONAL_CPP */
  26 # define name2(a,b) name2x(a,b)
  27 # define name2x(a,b) a ## b
  28 #endif /* not TRADITIONAL_CPP */
  29
  30 // `class ITABLE(T)' is the type of a hash table mapping an integer (int >= 0)
  31 // to an object of type T.
  32 //
  33 // `struct IASSOC(T)' is the type of a association (pair) between an integer
  34 // (int >= 0) and an object of type T.
  35 //
  36 // `class ITABLE_ITERATOR(T)' is the type of an iterator iterating through a
  37 // `class ITABLE(T)'.
  38 //
  39 // Nowadays one would use templates for this; this code predates the addition
  40 // of templates to C++.
  41 #define ITABLE(T) name2(T,_itable)
  42 #define IASSOC(T) name2(T,_iassoc)
  43 #define ITABLE_ITERATOR(T) name2(T,_itable_iterator)
  44
  45 // ptable.h declares this too
  46 #ifndef NEXT_PTABLE_SIZE_DEFINED
  47 # define NEXT_PTABLE_SIZE_DEFINED
  48 extern unsigned next_ptable_size(unsigned);     // Return the first suitable
  49                                 // hash table size greater than the given
  50                                 // value.
  51 #endif
  52
  53 // Declare the types `class ITABLE(T)', `struct IASSOC(T)', and `class
  54 // ITABLE_ITERATOR(T)' for the type `T'.
  55 #define declare_itable(T)                                                     \
  56                                                                               \
  57 struct IASSOC(T) {                                                            \
  58   int key;                                                                    \
  59   T *val;                                                                     \
  60   IASSOC(T)();                                                                \
  61 };                                                                            \
  62                                                                               \
  63 class ITABLE(T);                                                              \
  64                                                                               \
  65 class ITABLE_ITERATOR(T) {                                                    \
  66   ITABLE(T) *p;                                                               \
  67   unsigned i;                                                                 \
  68 public:                                                                       \
  69   ITABLE_ITERATOR(T)(ITABLE(T) *);      /* Initialize an iterator running     \
  70                                            through the given table.  */       \
  71   int next(int *, T **);                /* Fetch the next pair, store the key \
  72                                            and value in arg1 and arg2,        \
  73                                            respectively, and return 1.  If    \
  74                                            there is no more pair in the       \
  75                                            table, return 0.  */               \
  76 };                                                                            \
  77                                                                               \
  78 class ITABLE(T) {                                                             \
  79   IASSOC(T) *v;                                                               \
  80   unsigned size;                                                              \
  81   unsigned used;                                                              \
  82   enum {                                                                      \
  83     FULL_NUM = 2,                                                             \
  84     FULL_DEN = 3,                                                             \
  85     INITIAL_SIZE = 17                                                         \
  86   };                                                                          \
  87 public:                                                                       \
  88   ITABLE(T)();                          /* Create an empty table.  */         \
  89   ~ITABLE(T)();                         /* Delete a table, including its      \
  90                                            values.  */                        \
  91   void define(int, T *);                /* Define the value (arg2) for a key  \
  92                                            (arg1).  */                        \
  93   T *lookup(int);                       /* Return a pointer to the value of   \
  94                                            the given key, if found in the     \
  95                                            table, or NULL otherwise.  */      \
  96   friend class ITABLE_ITERATOR(T);                                            \
  97 };
  98
  99
 100 // Values must be allocated by the caller (always using new[], not new)
 101 // and are freed by ITABLE.
 102
 103 // Define the implementations of the members of the types `class ITABLE(T)',
 104 // `struct IASSOC(T)', `class ITABLE_ITERATOR(T)' for the type `T'.
 105 #define implement_itable(T)                                                   \
 106                                                                               \
 107 IASSOC(T)::IASSOC(T)()                                                        \
 108 : key(-1), val(0)                                                             \
 109 {                                                                             \
 110 }                                                                             \
 111                                                                               \
 112 ITABLE(T)::ITABLE(T)()                                                        \
 113 {                                                                             \
 114   v = new IASSOC(T)[size = INITIAL_SIZE];                                     \
 115   used = 0;                                                                   \
 116 }                                                                             \
 117                                                                               \
 118 ITABLE(T)::~ITABLE(T)()                                                       \
 119 {                                                                             \
 120   for (unsigned i = 0; i < size; i++)                                         \
 121     a_delete v[i].val;                                                        \
 122   a_delete v;                                                                 \
 123 }                                                                             \
 124                                                                               \
 125 void ITABLE(T)::define(int key, T *val)                                       \
 126 {                                                                             \
 127   assert(key >= 0);                                                           \
 128   unsigned int h = (unsigned int)(key);                                       \
 129   unsigned n;                                                                 \
 130   for (n = unsigned(h % size);                                                \
 131        v[n].key >= 0;                                                         \
 132        n = (n == 0 ? size - 1 : n - 1))                                       \
 133     if (v[n].key == key) {                                                    \
 134       a_delete v[n].val;                                                      \
 135       v[n].val = val;                                                         \
 136       return;                                                                 \
 137     }                                                                         \
 138   if (val == 0)                                                               \
 139     return;                                                                   \
 140   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 141     IASSOC(T) *oldv = v;                                                      \
 142     unsigned old_size = size;                                                 \
 143     size = next_ptable_size(size);                                            \
 144     v = new IASSOC(T)[size];                                                  \
 145     for (unsigned i = 0; i < old_size; i++)                                   \
 146       if (oldv[i].key >= 0) {                                                 \
 147         if (oldv[i].val != 0) {                                               \
 148           unsigned j;                                                         \
 149           for (j = (unsigned int)(oldv[i].key) % size;                        \
 150                v[j].key >= 0;                                                 \
 151                j = (j == 0 ? size - 1 : j - 1))                               \
 152                  ;                                                            \
 153           v[j].key = oldv[i].key;                                             \
 154           v[j].val = oldv[i].val;                                             \
 155         }                                                                     \
 156       }                                                                       \
 157     for (n = unsigned(h % size);                                              \
 158          v[n].key >= 0;                                                       \
 159          n = (n == 0 ? size - 1 : n - 1))                                     \
 160       ;                                                                       \
 161     a_delete oldv;                                                            \
 162   }                                                                           \
 163   v[n].key = key;                                                             \
 164   v[n].val = val;                                                             \
 165   used++;                                                                     \
 166 }                                                                             \
 167                                                                               \
 168 T *ITABLE(T)::lookup(int key)                                                 \
 169 {                                                                             \
 170   assert(key >= 0);                                                           \
 171   for (unsigned n = (unsigned int)key % size;                                 \
 172        v[n].key >= 0;                                                         \
 173        n = (n == 0 ? size - 1 : n - 1))                                       \
 174     if (v[n].key == key)                                                      \
 175       return v[n].val;                                                        \
 176   return 0;                                                                   \
 177 }                                                                             \
 178                                                                               \
 179 ITABLE_ITERATOR(T)::ITABLE_ITERATOR(T)(ITABLE(T) *t)                          \
 180 : p(t), i(0)                                                                  \
 181 {                                                                             \
 182 }                                                                             \
 183                                                                               \
 184 int ITABLE_ITERATOR(T)::next(int *keyp, T **valp)                             \
 185 {                                                                             \
 186   unsigned size = p->size;                                                    \
 187   IASSOC(T) *v = p->v;                                                        \
 188   for (; i < size; i++)                                                       \
 189     if (v[i].key >= 0) {                                                      \
 190       *keyp = v[i].key;                                                       \
 191       *valp = v[i].val;                                                       \
 192       i++;                                                                    \
 193       return 1;                                                               \
 194     }                                                                         \
 195   return 0;                                                                   \
 196 }
 197
 198 // end of itable.h