gnu/dist/groff/src/include/ptable.h

   1 /*      $NetBSD$        */
   2
   3 // -*- C++ -*-
   4 /* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004
   5    Free Software Foundation, Inc.
   6      Written by James Clark (jjc@jclark.com)
   7
   8 This file is part of groff.
   9
  10 groff is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 2, or (at your option) any later
  13 version.
  14
  15 groff is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License along
  21 with groff; see the file COPYING.  If not, write to the Free Software
  22 Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */
  23
  24 #include <assert.h>
  25 #include <string.h>
  26
  27 #ifdef TRADITIONAL_CPP
  28 #define name2(a,b) a/**/b
  29 #else /* not TRADITIONAL_CPP */
  30 #define name2(a,b) name2x(a,b)
  31 #define name2x(a,b) a ## b
  32 #endif /* not TRADITIONAL_CPP */
  33
  34 #define PTABLE(T) name2(T,_ptable)
  35 #define PASSOC(T) name2(T,_passoc)
  36 #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  37
  38 extern unsigned next_ptable_size(unsigned);
  39 extern unsigned long hash_string(const char *);
  40
  41 #define declare_ptable(T)                                                     \
  42                                                                               \
  43 struct PASSOC(T) {                                                            \
  44   char *key;                                                                  \
  45   T *val;                                                                     \
  46   PASSOC(T)();                                                                \
  47 };                                                                            \
  48                                                                               \
  49 class PTABLE(T);                                                              \
  50                                                                               \
  51 class PTABLE_ITERATOR(T) {                                                    \
  52   PTABLE(T) *p;                                                               \
  53   unsigned i;                                                                 \
  54 public:                                                                       \
  55   PTABLE_ITERATOR(T)(PTABLE(T) *);                                            \
  56   int next(const char **, T **);                                              \
  57 };                                                                            \
  58                                                                               \
  59 class PTABLE(T) {                                                             \
  60   PASSOC(T) *v;                                                               \
  61   unsigned size;                                                              \
  62   unsigned used;                                                              \
  63   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };                     \
  64 public:                                                                       \
  65   PTABLE(T)();                                                                \
  66   ~PTABLE(T)();                                                               \
  67   void define(const char *, T *);                                             \
  68   T *lookup(const char *);                                                    \
  69   friend class PTABLE_ITERATOR(T);                                            \
  70 };
  71
  72
  73 // Keys (which are strings) are allocated and freed by PTABLE.
  74 // Values must be allocated by the caller (always using new[], not new)
  75 // and are freed by PTABLE.
  76
  77 #define implement_ptable(T)                                                   \
  78                                                                               \
  79 PASSOC(T)::PASSOC(T)()                                                        \
  80 : key(0), val(0)                                                              \
  81 {                                                                             \
  82 }                                                                             \
  83                                                                               \
  84 PTABLE(T)::PTABLE(T)()                                                        \
  85 {                                                                             \
  86   v = new PASSOC(T)[size = INITIAL_SIZE];                                     \
  87   used = 0;                                                                   \
  88 }                                                                             \
  89                                                                               \
  90 PTABLE(T)::~PTABLE(T)()                                                       \
  91 {                                                                             \
  92   for (unsigned i = 0; i < size; i++) {                                       \
  93     a_delete v[i].key;                                                        \
  94     a_delete v[i].val;                                                        \
  95   }                                                                           \
  96   a_delete v;                                                                 \
  97 }                                                                             \
  98                                                                               \
  99 void PTABLE(T)::define(const char *key, T *val)                               \
 100 {                                                                             \
 101   assert(key != 0);                                                           \
 102   unsigned long h = hash_string(key);                                         \
 103   unsigned n;                                                                 \
 104   for (n = unsigned(h % size);                                                \
 105        v[n].key != 0;                                                         \
 106        n = (n == 0 ? size - 1 : n - 1))                                       \
 107     if (strcmp(v[n].key, key) == 0) {                                         \
 108       a_delete v[n].val;                                                      \
 109       v[n].val = val;                                                         \
 110       return;                                                                 \
 111     }                                                                         \
 112   if (val == 0)                                                               \
 113     return;                                                                   \
 114   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 115     PASSOC(T) *oldv = v;                                                      \
 116     unsigned old_size = size;                                                 \
 117     size = next_ptable_size(size);                                            \
 118     v = new PASSOC(T)[size];                                                  \
 119     for (unsigned i = 0; i < old_size; i++)                                   \
 120       if (oldv[i].key != 0) {                                                 \
 121         if (oldv[i].val == 0)                                                 \
 122           a_delete oldv[i].key;                                               \
 123         else {                                                                \
 124           unsigned j;                                                         \
 125           for (j = unsigned(hash_string(oldv[i].key) % size);                 \
 126                v[j].key != 0;                                                 \
 127                j = (j == 0 ? size - 1 : j - 1))                               \
 128                  ;                                                            \
 129           v[j].key = oldv[i].key;                                             \
 130           v[j].val = oldv[i].val;                                             \
 131         }                                                                     \
 132       }                                                                       \
 133     for (n = unsigned(h % size);                                              \
 134          v[n].key != 0;                                                       \
 135          n = (n == 0 ? size - 1 : n - 1))                                     \
 136       ;                                                                       \
 137     a_delete oldv;                                                            \
 138   }                                                                           \
 139   char *temp = new char[strlen(key)+1];                                       \
 140   strcpy(temp, key);                                                          \
 141   v[n].key = temp;                                                            \
 142   v[n].val = val;                                                             \
 143   used++;                                                                     \
 144 }                                                                             \
 145                                                                               \
 146 T *PTABLE(T)::lookup(const char *key)                                         \
 147 {                                                                             \
 148   assert(key != 0);                                                           \
 149   for (unsigned n = unsigned(hash_string(key) % size);                        \
 150        v[n].key != 0;                                                         \
 151        n = (n == 0 ? size - 1 : n - 1))                                       \
 152     if (strcmp(v[n].key, key) == 0)                                           \
 153       return v[n].val;                                                        \
 154   return 0;                                                                   \
 155 }                                                                             \
 156                                                                               \
 157 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                          \
 158 : p(t), i(0)                                                                  \
 159 {                                                                             \
 160 }                                                                             \
 161                                                                               \
 162 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)                     \
 163 {                                                                             \
 164   unsigned size = p->size;                                                    \
 165   PASSOC(T) *v = p->v;                                                        \
 166   for (; i < size; i++)                                                       \
 167     if (v[i].key != 0) {                                                      \
 168       *keyp = v[i].key;                                                       \
 169       *valp = v[i].val;                                                       \
 170       i++;                                                                    \
 171       return 1;                                                               \
 172     }                                                                         \
 173   return 0;                                                                   \
 174 }