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