2 /* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004, 2006
3 Free Software Foundation, Inc.
4 Written by James Clark (jjc@jclark.com)
6 This file is part of groff.
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
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
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. */
25 // name2(a,b) concatenates two C identifiers.
26 #ifdef TRADITIONAL_CPP
27 # define name2(a,b) a/**/b
28 #else /* not TRADITIONAL_CPP */
29 # define name2(a,b) name2x(a,b)
30 # define name2x(a,b) a ## b
31 #endif /* not TRADITIONAL_CPP */
33 // `class PTABLE(T)' is the type of a hash table mapping a string
34 // (const char *) to an object of type T.
36 // `struct PASSOC(T)' is the type of a association (pair) between a
37 // string (const char *) and an object of type T.
39 // `class PTABLE_ITERATOR(T)' is the type of an iterator iterating through a
42 // Nowadays one would use templates for this; this code predates the addition
43 // of templates to C++.
44 #define PTABLE(T) name2(T,_ptable)
45 #define PASSOC(T) name2(T,_passoc)
46 #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
48 // itable.h declares this too
49 #ifndef NEXT_PTABLE_SIZE_DEFINED
50 # define NEXT_PTABLE_SIZE_DEFINED
51 extern unsigned next_ptable_size(unsigned); // Return the first suitable
52 // hash table size greater than the given
56 extern unsigned long hash_string(const char *); // Return a hash code of the
57 // given string. The hash function is
58 // platform dependent. */
60 // Declare the types `class PTABLE(T)', `struct PASSOC(T)', and `class
61 // PTABLE_ITERATOR(T)' for the type `T'.
62 #define declare_ptable(T) \
72 class PTABLE_ITERATOR(T) { \
76 PTABLE_ITERATOR(T)(PTABLE(T) *); /* Initialize an iterator running \
77 through the given table. */ \
78 int next(const char **, T **); /* Fetch the next pair, store the key \
79 and value in arg1 and arg2, \
80 respectively, and return 1. If \
81 there is no more pair in the \
95 PTABLE(T)(); /* Create an empty table. */ \
96 ~PTABLE(T)(); /* Delete a table, including its \
98 const char *define(const char *, T *);/* Define the value (arg2) for a key \
99 (arg1). Return the copy in the \
100 table of the key (arg1), or \
101 possibly NULL if the value (arg2) \
103 T *lookup(const char *); /* Return a pointer to the value of \
104 the given key, if found in the \
105 table, or NULL otherwise. */ \
106 T *lookupassoc(const char **); /* Return a pointer to the value of \
107 the given key, passed by reference,\
108 and replace the key argument with \
109 the copy found in the table, if \
110 the key is found in the table. \
111 Return NULL otherwise. */ \
112 friend class PTABLE_ITERATOR(T); \
116 // Keys (which are strings) are allocated and freed by PTABLE.
117 // Values must be allocated by the caller (always using new[], not new)
118 // and are freed by PTABLE.
120 // Define the implementations of the members of the types `class PTABLE(T)',
121 // `struct PASSOC(T)', `class PTABLE_ITERATOR(T)' for the type `T'.
122 #define implement_ptable(T) \
124 PASSOC(T)::PASSOC(T)() \
129 PTABLE(T)::PTABLE(T)() \
131 v = new PASSOC(T)[size = INITIAL_SIZE]; \
135 PTABLE(T)::~PTABLE(T)() \
137 for (unsigned i = 0; i < size; i++) { \
144 const char *PTABLE(T)::define(const char *key, T *val) \
147 unsigned long h = hash_string(key); \
149 for (n = unsigned(h % size); \
151 n = (n == 0 ? size - 1 : n - 1)) \
152 if (strcmp(v[n].key, key) == 0) { \
159 if (used*FULL_DEN >= size*FULL_NUM) { \
160 PASSOC(T) *oldv = v; \
161 unsigned old_size = size; \
162 size = next_ptable_size(size); \
163 v = new PASSOC(T)[size]; \
164 for (unsigned i = 0; i < old_size; i++) \
165 if (oldv[i].key != 0) { \
166 if (oldv[i].val == 0) \
167 a_delete oldv[i].key; \
170 for (j = unsigned(hash_string(oldv[i].key) % size); \
172 j = (j == 0 ? size - 1 : j - 1)) \
174 v[j].key = oldv[i].key; \
175 v[j].val = oldv[i].val; \
178 for (n = unsigned(h % size); \
180 n = (n == 0 ? size - 1 : n - 1)) \
184 char *temp = new char[strlen(key)+1]; \
192 T *PTABLE(T)::lookup(const char *key) \
195 for (unsigned n = unsigned(hash_string(key) % size); \
197 n = (n == 0 ? size - 1 : n - 1)) \
198 if (strcmp(v[n].key, key) == 0) \
203 T *PTABLE(T)::lookupassoc(const char **keyptr) \
205 const char *key = *keyptr; \
207 for (unsigned n = unsigned(hash_string(key) % size); \
209 n = (n == 0 ? size - 1 : n - 1)) \
210 if (strcmp(v[n].key, key) == 0) { \
211 *keyptr = v[n].key; \
217 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \
222 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp) \
224 unsigned size = p->size; \
225 PASSOC(T) *v = p->v; \
226 for (; i < size; i++) \
227 if (v[i].key != 0) { \