contrib/groff/src/include/itable.h

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