1 /* $NetBSD: ptable.h,v 1.1.1.1 2016/01/13 18:41:48 christos Exp $ */ 2 3 // -*- C++ -*- 4 /* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004 5 Free Software Foundation, Inc. 6 Written by James Clark (jjc (at) 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 } 175
Indexes created Tue Feb 24 08:35:24 UTC 2026