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 6This file is part of groff. 7 8groff is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13groff is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License along 19with groff; see the file COPYING. If not, write to the Free Software 20Foundation, 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 36extern unsigned next_ptable_size(unsigned); 37extern unsigned long hash_string(const char *); 38 39#define declare_ptable(T) \ 40 \ 41struct PASSOC(T) { \ 42 char *key; \ 43 T *val; \ 44 PASSOC(T)(); \ 45}; \ 46 \ 47class PTABLE(T); \ 48 \ 49class PTABLE_ITERATOR(T) { \ 50 PTABLE(T) *p; \ 51 unsigned i; \ 52public: \ 53 PTABLE_ITERATOR(T)(PTABLE(T) *); \ 54 int next(const char **, T **); \ 55}; \ 56 \ 57class PTABLE(T) { \ 58 PASSOC(T) *v; \ 59 unsigned size; \ 60 unsigned used; \ 61 enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 }; \ 62public: \ 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 \ 77PASSOC(T)::PASSOC(T)() \ 78: key(0), val(0) \ 79{ \ 80} \ 81 \ 82PTABLE(T)::PTABLE(T)() \ 83{ \ 84 v = new PASSOC(T)[size = INITIAL_SIZE]; \ 85 used = 0; \ 86} \ 87 \ 88PTABLE(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 \ 97void 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 \ 144T *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 \ 155PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \ 156: p(t), i(0) \ 157{ \ 158} \ 159 \ 160int 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