src/include/itable.h

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