gnu/usr.bin/groff/libgroff/ptable.h

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989, 1990 Free Software Foundation, Inc.
   3      Written by James Clark (jjc@jclark.uucp)
   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 1, 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 LICENSE.  If not, write to the Free Software
  19 Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20
  21 #include <assert.h>
  22 #include <generic.h>
  23 #include <string.h>
  24
  25 #define PTABLE(T) name2(T,_ptable)
  26 #define PASSOC(T) name2(T,_passoc)
  27 #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  28
  29 extern int next_ptable_size(int);
  30 extern unsigned hash_string(const char *);
  31
  32 #define declare_ptable(T)                                                     \
  33                                                                               \
  34 struct PASSOC(T) {                                                            \
  35   char *key;                                                                  \
  36   T *val;                                                                     \
  37   PASSOC(T)();                                                                \
  38 };                                                                            \
  39                                                                               \
  40 struct PTABLE(T);                                                             \
  41                                                                               \
  42 class PTABLE_ITERATOR(T) {                                                    \
  43   PTABLE(T) *p;                                                               \
  44   int i;                                                                      \
  45 public:                                                                       \
  46   PTABLE_ITERATOR(T)(PTABLE(T) *);                                            \
  47   int next(const char **, T **);                                              \
  48 };                                                                            \
  49                                                                               \
  50 class PTABLE(T) {                                                             \
  51   PASSOC(T) *v;                                                               \
  52   int size;                                                                   \
  53   int used;                                                                   \
  54   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };                     \
  55 public:                                                                       \
  56   PTABLE(T)();                                                                \
  57   ~PTABLE(T)();                                                               \
  58   void define(const char *, T *);                                             \
  59   T *lookup(const char *);                                                    \
  60   friend class PTABLE_ITERATOR(T);                                            \
  61 };
  62
  63
  64 #define implement_ptable(T)                                                   \
  65                                                                               \
  66 PASSOC(T)::PASSOC(T)()                                                        \
  67 : key(0), val(0)                                                              \
  68 {                                                                             \
  69 }                                                                             \
  70                                                                               \
  71 PTABLE(T)::PTABLE(T)()                                                        \
  72 {                                                                             \
  73   v = new PASSOC(T)[size = INITIAL_SIZE];                                     \
  74   used = 0;                                                                   \
  75 }                                                                             \
  76                                                                               \
  77 PTABLE(T)::~PTABLE(T)()                                                       \
  78 {                                                                             \
  79   for (int i = 0; i < size; i++) {                                            \
  80     delete v[i].key;                                                          \
  81     delete v[i].val;                                                          \
  82   }                                                                           \
  83 }                                                                             \
  84                                                                               \
  85 void PTABLE(T)::define(const char *key, T *val)                               \
  86 {                                                                             \
  87   assert(key != 0);                                                           \
  88   int h = hash_string(key);                                                   \
  89   for (int n = h % size;                                                      \
  90        v[n].key != 0;                                                         \
  91        n = (n == 0 ? size - 1 : n - 1))                                       \
  92     if (strcmp(v[n].key, key) == 0) {                                         \
  93       delete v[n].val;                                                        \
  94       v[n].val = val;                                                         \
  95       return;                                                                 \
  96     }                                                                         \
  97   if (val == 0)                                                               \
  98     return;                                                                   \
  99   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 100     PASSOC(T) *oldv = v;                                                      \
 101     int old_size = size;                                                      \
 102     size = next_ptable_size(size);                                            \
 103     v = new PASSOC(T)[size];                                                  \
 104     for (int i = 0; i < old_size; i++)                                        \
 105       if (oldv[i].key != 0) {                                                 \
 106         if (oldv[i].val == 0)                                                 \
 107           delete oldv[i].key;                                                 \
 108         else {                                                                \
 109           for (int j = hash_string(oldv[i].key) % size;                       \
 110                v[j].key != 0;                                                 \
 111                j = (j == 0 ? size - 1 : j - 1))                               \
 112                  ;                                                            \
 113           v[j].key = oldv[i].key;                                             \
 114           v[j].val = oldv[i].val;                                             \
 115         }                                                                     \
 116       }                                                                       \
 117     for (n = h % size;                                                        \
 118          v[n].key != 0;                                                       \
 119          n = (n == 0 ? size - 1 : n - 1))                                     \
 120       ;                                                                       \
 121     delete oldv;                                                              \
 122   }                                                                           \
 123   char *temp = new char[strlen(key)+1];                                       \
 124   strcpy(temp, key);                                                          \
 125   v[n].key = temp;                                                            \
 126   v[n].val = val;                                                             \
 127   used++;                                                                     \
 128 }                                                                             \
 129                                                                               \
 130 T *PTABLE(T)::lookup(const char *key)                                         \
 131 {                                                                             \
 132   assert(key != 0);                                                           \
 133   for (int n = hash_string(key) % size;                                       \
 134        v[n].key != 0;                                                         \
 135        n = (n == 0 ? size - 1 : n - 1))                                       \
 136     if (strcmp(v[n].key, key) == 0)                                           \
 137       return v[n].val;                                                        \
 138   return 0;                                                                   \
 139 }                                                                             \
 140                                                                               \
 141 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                          \
 142 : p(t), i(0)                                                                  \
 143 {                                                                             \
 144 }                                                                             \
 145                                                                               \
 146 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)                     \
 147 {                                                                             \
 148   int size = p->size;                                                         \
 149   PASSOC(T) *v = p->v;                                                        \
 150   for (; i < size; i++)                                                       \
 151     if (v[i].key != 0) {                                                      \
 152       *keyp = v[i].key;                                                       \
 153       *valp = v[i].val;                                                       \
 154       i++;                                                                    \
 155       return 1;                                                               \
 156     }                                                                         \
 157   return 0;                                                                   \
 158 }
 159