src/include/ptable.h

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989, 1990, 1991, 1992, 2003 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 2, or (at your option) any later
  10 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 along
  18 with groff; see the file COPYING.  If not, write to the Free Software
  19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  20
  21 #include <assert.h>
  22 #include <string.h>
  23
  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 #define PTABLE(T) name2(T,_ptable)
  32 #define PASSOC(T) name2(T,_passoc)
  33 #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  34
  35 extern unsigned next_ptable_size(unsigned);
  36 extern unsigned long hash_string(const char *);
  37
  38 #define declare_ptable(T)                                                     \
  39                                                                               \
  40 struct PASSOC(T) {                                                            \
  41   char *key;                                                                  \
  42   T *val;                                                                     \
  43   PASSOC(T)();                                                                \
  44 };                                                                            \
  45                                                                               \
  46 struct PTABLE(T);                                                             \
  47                                                                               \
  48 class PTABLE_ITERATOR(T) {                                                    \
  49   PTABLE(T) *p;                                                               \
  50   unsigned i;                                                                 \
  51 public:                                                                       \
  52   PTABLE_ITERATOR(T)(PTABLE(T) *);                                            \
  53   int next(const char **, T **);                                              \
  54 };                                                                            \
  55                                                                               \
  56 class PTABLE(T) {                                                             \
  57   PASSOC(T) *v;                                                               \
  58   unsigned size;                                                              \
  59   unsigned used;                                                              \
  60   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };                     \
  61 public:                                                                       \
  62   PTABLE(T)();                                                                \
  63   ~PTABLE(T)();                                                               \
  64   void define(const char *, T *);                                             \
  65   T *lookup(const char *);                                                    \
  66   friend class PTABLE_ITERATOR(T);                                            \
  67 };
  68
  69
  70 // Keys (which are strings) are allocated and freed by PTABLE.
  71 // Values must be allocated by the caller (always using new[], not new)
  72 // and are freed by PTABLE.
  73
  74 #define implement_ptable(T)                                                   \
  75                                                                               \
  76 PASSOC(T)::PASSOC(T)()                                                        \
  77 : key(0), val(0)                                                              \
  78 {                                                                             \
  79 }                                                                             \
  80                                                                               \
  81 PTABLE(T)::PTABLE(T)()                                                        \
  82 {                                                                             \
  83   v = new PASSOC(T)[size = INITIAL_SIZE];                                     \
  84   used = 0;                                                                   \
  85 }                                                                             \
  86                                                                               \
  87 PTABLE(T)::~PTABLE(T)()                                                       \
  88 {                                                                             \
  89   for (unsigned i = 0; i < size; i++) {                                       \
  90     a_delete v[i].key;                                                        \
  91     a_delete v[i].val;                                                        \
  92   }                                                                           \
  93   a_delete v;                                                                 \
  94 }                                                                             \
  95                                                                               \
  96 void PTABLE(T)::define(const char *key, T *val)                               \
  97 {                                                                             \
  98   assert(key != 0);                                                           \
  99   unsigned long h = hash_string(key);                                         \
 100   unsigned n;                                                                 \
 101   for (n = unsigned(h % size);                                                \
 102        v[n].key != 0;                                                         \
 103        n = (n == 0 ? size - 1 : n - 1))                                       \
 104     if (strcmp(v[n].key, key) == 0) {                                         \
 105       a_delete v[n].val;                                                      \
 106       v[n].val = val;                                                         \
 107       return;                                                                 \
 108     }                                                                         \
 109   if (val == 0)                                                               \
 110     return;                                                                   \
 111   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 112     PASSOC(T) *oldv = v;                                                      \
 113     unsigned old_size = size;                                                 \
 114     size = next_ptable_size(size);                                            \
 115     v = new PASSOC(T)[size];                                                  \
 116     for (unsigned i = 0; i < old_size; i++)                                   \
 117       if (oldv[i].key != 0) {                                                 \
 118         if (oldv[i].val == 0)                                                 \
 119           a_delete oldv[i].key;                                               \
 120         else {                                                                \
 121           unsigned j;                                                         \
 122           for (j = unsigned(hash_string(oldv[i].key) % size);                 \
 123                v[j].key != 0;                                                 \
 124                j = (j == 0 ? size - 1 : j - 1))                               \
 125                  ;                                                            \
 126           v[j].key = oldv[i].key;                                             \
 127           v[j].val = oldv[i].val;                                             \
 128         }                                                                     \
 129       }                                                                       \
 130     for (n = unsigned(h % size);                                              \
 131          v[n].key != 0;                                                       \
 132          n = (n == 0 ? size - 1 : n - 1))                                     \
 133       ;                                                                       \
 134     a_delete oldv;                                                            \
 135   }                                                                           \
 136   char *temp = new char[strlen(key)+1];                                       \
 137   strcpy(temp, key);                                                          \
 138   v[n].key = temp;                                                            \
 139   v[n].val = val;                                                             \
 140   used++;                                                                     \
 141 }                                                                             \
 142                                                                               \
 143 T *PTABLE(T)::lookup(const char *key)                                         \
 144 {                                                                             \
 145   assert(key != 0);                                                           \
 146   for (unsigned n = unsigned(hash_string(key) % size);                        \
 147        v[n].key != 0;                                                         \
 148        n = (n == 0 ? size - 1 : n - 1))                                       \
 149     if (strcmp(v[n].key, key) == 0)                                           \
 150       return v[n].val;                                                        \
 151   return 0;                                                                   \
 152 }                                                                             \
 153                                                                               \
 154 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                          \
 155 : p(t), i(0)                                                                  \
 156 {                                                                             \
 157 }                                                                             \
 158                                                                               \
 159 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)                     \
 160 {                                                                             \
 161   unsigned size = p->size;                                                    \
 162   PASSOC(T) *v = p->v;                                                        \
 163   for (; i < size; i++)                                                       \
 164     if (v[i].key != 0) {                                                      \
 165       *keyp = v[i].key;                                                       \
 166       *valp = v[i].val;                                                       \
 167       i++;                                                                    \
 168       return 1;                                                               \
 169     }                                                                         \
 170   return 0;                                                                   \
 171 }