1 // -*- C++ -*- 2 /* Copyright (C) 1989, 1990, 1991, 1992 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, 675 Mass Ave, Cambridge, MA 02139, 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 #define implement_ptable(T) \ 71 \ 72 PASSOC(T)::PASSOC(T)() \ 73 : key(0), val(0) \ 74 { \ 75 } \ 76 \ 77 PTABLE(T)::PTABLE(T)() \ 78 { \ 79 v = new PASSOC(T)[size = INITIAL_SIZE]; \ 80 used = 0; \ 81 } \ 82 \ 83 PTABLE(T)::~PTABLE(T)() \ 84 { \ 85 for (unsigned i = 0; i < size; i++) { \ 86 a_delete v[i].key; \ 87 delete v[i].val; \ 88 } \ 89 a_delete v; \ 90 } \ 91 \ 92 void PTABLE(T)::define(const char *key, T *val) \ 93 { \ 94 assert(key != 0); \ 95 unsigned long h = hash_string(key); \ 96 for (unsigned n = unsigned(h % size); \ 97 v[n].key != 0; \ 98 n = (n == 0 ? size - 1 : n - 1)) \ 99 if (strcmp(v[n].key, key) == 0) { \ 100 delete v[n].val; \ 101 v[n].val = val; \ 102 return; \ 103 } \ 104 if (val == 0) \ 105 return; \ 106 if (used*FULL_DEN >= size*FULL_NUM) { \ 107 PASSOC(T) *oldv = v; \ 108 unsigned old_size = size; \ 109 size = next_ptable_size(size); \ 110 v = new PASSOC(T)[size]; \ 111 for (unsigned i = 0; i < old_size; i++) \ 112 if (oldv[i].key != 0) { \ 113 if (oldv[i].val == 0) \ 114 a_delete oldv[i].key; \ 115 else { \ 116 for (unsigned j = unsigned(hash_string(oldv[i].key) % size); \ 117 v[j].key != 0; \ 118 j = (j == 0 ? size - 1 : j - 1)) \ 119 ; \ 120 v[j].key = oldv[i].key; \ 121 v[j].val = oldv[i].val; \ 122 } \ 123 } \ 124 for (n = unsigned(h % size); \ 125 v[n].key != 0; \ 126 n = (n == 0 ? size - 1 : n - 1)) \ 127 ; \ 128 a_delete oldv; \ 129 } \ 130 char *temp = new char[strlen(key)+1]; \ 131 strcpy(temp, key); \ 132 v[n].key = temp; \ 133 v[n].val = val; \ 134 used++; \ 135 } \ 136 \ 137 T *PTABLE(T)::lookup(const char *key) \ 138 { \ 139 assert(key != 0); \ 140 for (unsigned n = unsigned(hash_string(key) % size); \ 141 v[n].key != 0; \ 142 n = (n == 0 ? size - 1 : n - 1)) \ 143 if (strcmp(v[n].key, key) == 0) \ 144 return v[n].val; \ 145 return 0; \ 146 } \ 147 \ 148 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \ 149 : p(t), i(0) \ 150 { \ 151 } \ 152 \ 153 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp) \ 154 { \ 155 unsigned size = p->size; \ 156 PASSOC(T) *v = p->v; \ 157 for (; i < size; i++) \ 158 if (v[i].key != 0) { \ 159 *keyp = v[i].key; \ 160 *valp = v[i].val; \ 161 i++; \ 162 return 1; \ 163 } \ 164 return 0; \ 165 } 166 167