xref: /netbsd-src/external/gpl2/groff/dist/src/include/ptable.h (revision 89a07cf815a29524268025a1139fac4c5190f765)
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@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