contrib/groff/src/include/ptable.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 #include <string.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 PTABLE(T)' is the type of a hash table mapping a string
  33 // (const char *) to an object of type T.
  34 //
  35 // `struct PASSOC(T)' is the type of a association (pair) between a
  36 // string (const char *) and an object of type T.
  37 //
  38 // `class PTABLE_ITERATOR(T)' is the type of an iterator iterating through a
  39 // `class PTABLE(T)'.
  40 //
  41 // Nowadays one would use templates for this; this code predates the addition
  42 // of templates to C++.
  43 #define PTABLE(T) name2(T,_ptable)
  44 #define PASSOC(T) name2(T,_passoc)
  45 #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  46
  47 // itable.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 extern unsigned long hash_string(const char *); // Return a hash code of the
  56                                 // given string.  The hash function is
  57                                 // platform dependent.  */
  58
  59 // Declare the types `class PTABLE(T)', `struct PASSOC(T)', and `class
  60 // PTABLE_ITERATOR(T)' for the type `T'.
  61 #define declare_ptable(T)                                                     \
  62                                                                               \
  63 struct PASSOC(T) {                                                            \
  64   char *key;                                                                  \
  65   T *val;                                                                     \
  66   PASSOC(T)();                                                                \
  67 };                                                                            \
  68                                                                               \
  69 class PTABLE(T);                                                              \
  70                                                                               \
  71 class PTABLE_ITERATOR(T) {                                                    \
  72   PTABLE(T) *p;                                                               \
  73   unsigned i;                                                                 \
  74 public:                                                                       \
  75   PTABLE_ITERATOR(T)(PTABLE(T) *);      /* Initialize an iterator running     \
  76                                            through the given table.  */       \
  77   int next(const char **, T **);        /* Fetch the next pair, store the key \
  78                                            and value in arg1 and arg2,        \
  79                                            respectively, and return 1.  If    \
  80                                            there is no more pair in the       \
  81                                            table, return 0.  */               \
  82 };                                                                            \
  83                                                                               \
  84 class PTABLE(T) {                                                             \
  85   PASSOC(T) *v;                                                               \
  86   unsigned size;                                                              \
  87   unsigned used;                                                              \
  88   enum {                                                                      \
  89     FULL_NUM = 2,                                                             \
  90     FULL_DEN = 3,                                                             \
  91     INITIAL_SIZE = 17                                                         \
  92   };                                                                          \
  93 public:                                                                       \
  94   PTABLE(T)();                          /* Create an empty table.  */         \
  95   ~PTABLE(T)();                         /* Delete a table, including its      \
  96                                            values.  */                        \
  97   const char *define(const char *, T *);/* Define the value (arg2) for a key  \
  98                                            (arg1).  Return the copy in the    \
  99                                            table of the key (arg1), or        \
 100                                            possibly NULL if the value (arg2)  \
 101                                            is NULL.  */                       \
 102   T *lookup(const char *);              /* Return a pointer to the value of   \
 103                                            the given key, if found in the     \
 104                                            table, or NULL otherwise.  */      \
 105   T *lookupassoc(const char **);        /* Return a pointer to the value of   \
 106                                            the given key, passed by reference,\
 107                                            and replace the key argument with  \
 108                                            the copy found in the table, if    \
 109                                            the key is found in the table.     \
 110                                            Return NULL otherwise.  */         \
 111   friend class PTABLE_ITERATOR(T);                                            \
 112 };
 113
 114
 115 // Keys (which are strings) are allocated and freed by PTABLE.
 116 // Values must be allocated by the caller (always using new[], not new)
 117 // and are freed by PTABLE.
 118
 119 // Define the implementations of the members of the types `class PTABLE(T)',
 120 // `struct PASSOC(T)', `class PTABLE_ITERATOR(T)' for the type `T'.
 121 #define implement_ptable(T)                                                   \
 122                                                                               \
 123 PASSOC(T)::PASSOC(T)()                                                        \
 124 : key(0), val(0)                                                              \
 125 {                                                                             \
 126 }                                                                             \
 127                                                                               \
 128 PTABLE(T)::PTABLE(T)()                                                        \
 129 {                                                                             \
 130   v = new PASSOC(T)[size = INITIAL_SIZE];                                     \
 131   used = 0;                                                                   \
 132 }                                                                             \
 133                                                                               \
 134 PTABLE(T)::~PTABLE(T)()                                                       \
 135 {                                                                             \
 136   for (unsigned i = 0; i < size; i++) {                                       \
 137     a_delete v[i].key;                                                        \
 138     a_delete v[i].val;                                                        \
 139   }                                                                           \
 140   a_delete v;                                                                 \
 141 }                                                                             \
 142                                                                               \
 143 const char *PTABLE(T)::define(const char *key, T *val)                        \
 144 {                                                                             \
 145   assert(key != 0);                                                           \
 146   unsigned long h = hash_string(key);                                         \
 147   unsigned n;                                                                 \
 148   for (n = unsigned(h % size);                                                \
 149        v[n].key != 0;                                                         \
 150        n = (n == 0 ? size - 1 : n - 1))                                       \
 151     if (strcmp(v[n].key, key) == 0) {                                         \
 152       a_delete v[n].val;                                                      \
 153       v[n].val = val;                                                         \
 154       return v[n].key;                                                        \
 155     }                                                                         \
 156   if (val == 0)                                                               \
 157     return 0;                                                                 \
 158   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 159     PASSOC(T) *oldv = v;                                                      \
 160     unsigned old_size = size;                                                 \
 161     size = next_ptable_size(size);                                            \
 162     v = new PASSOC(T)[size];                                                  \
 163     for (unsigned i = 0; i < old_size; i++)                                   \
 164       if (oldv[i].key != 0) {                                                 \
 165         if (oldv[i].val == 0)                                                 \
 166           a_delete oldv[i].key;                                               \
 167         else {                                                                \
 168           unsigned j;                                                         \
 169           for (j = unsigned(hash_string(oldv[i].key) % size);                 \
 170                v[j].key != 0;                                                 \
 171                j = (j == 0 ? size - 1 : j - 1))                               \
 172                  ;                                                            \
 173           v[j].key = oldv[i].key;                                             \
 174           v[j].val = oldv[i].val;                                             \
 175         }                                                                     \
 176       }                                                                       \
 177     for (n = unsigned(h % size);                                              \
 178          v[n].key != 0;                                                       \
 179          n = (n == 0 ? size - 1 : n - 1))                                     \
 180       ;                                                                       \
 181     a_delete oldv;                                                            \
 182   }                                                                           \
 183   char *temp = new char[strlen(key)+1];                                       \
 184   strcpy(temp, key);                                                          \
 185   v[n].key = temp;                                                            \
 186   v[n].val = val;                                                             \
 187   used++;                                                                     \
 188   return temp;                                                                \
 189 }                                                                             \
 190                                                                               \
 191 T *PTABLE(T)::lookup(const char *key)                                         \
 192 {                                                                             \
 193   assert(key != 0);                                                           \
 194   for (unsigned n = unsigned(hash_string(key) % size);                        \
 195        v[n].key != 0;                                                         \
 196        n = (n == 0 ? size - 1 : n - 1))                                       \
 197     if (strcmp(v[n].key, key) == 0)                                           \
 198       return v[n].val;                                                        \
 199   return 0;                                                                   \
 200 }                                                                             \
 201                                                                               \
 202 T *PTABLE(T)::lookupassoc(const char **keyptr)                                \
 203 {                                                                             \
 204   const char *key = *keyptr;                                                  \
 205   assert(key != 0);                                                           \
 206   for (unsigned n = unsigned(hash_string(key) % size);                        \
 207        v[n].key != 0;                                                         \
 208        n = (n == 0 ? size - 1 : n - 1))                                       \
 209     if (strcmp(v[n].key, key) == 0) {                                         \
 210       *keyptr = v[n].key;                                                     \
 211       return v[n].val;                                                        \
 212     }                                                                         \
 213   return 0;                                                                   \
 214 }                                                                             \
 215                                                                               \
 216 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                          \
 217 : p(t), i(0)                                                                  \
 218 {                                                                             \
 219 }                                                                             \
 220                                                                               \
 221 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)                     \
 222 {                                                                             \
 223   unsigned size = p->size;                                                    \
 224   PASSOC(T) *v = p->v;                                                        \
 225   for (; i < size; i++)                                                       \
 226     if (v[i].key != 0) {                                                      \
 227       *keyp = v[i].key;                                                       \
 228       *valp = v[i].val;                                                       \
 229       i++;                                                                    \
 230       return 1;                                                               \
 231     }                                                                         \
 232   return 0;                                                                   \
 233 }
 234
 235 // end of ptable.h