xref: /netbsd-src/external/gpl2/gettext/dist/gnulib-local/lib/3level.h (revision 946379e7b37692fc43f68eb0d1c10daa0a7f3b6c)
1 /* Copyright (C) 2000-2001 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
4 
5 
6    NOTE: The canonical source of this file is maintained with the GNU C Library.
7    Bugs can be reported to bug-glibc@gnu.org.
8 
9    This program is free software; you can redistribute it and/or modify it
10    under the terms of the GNU General Public License as published by the
11    Free Software Foundation; either version 2, or (at your option) any
12    later version.
13 
14    This program is distributed in the hope that it will be useful,
15    but WITHOUT ANY WARRANTY; without even the implied warranty of
16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17    GNU General Public License for more details.
18 
19    You should have received a copy of the GNU General Public License
20    along with this program; if not, write to the Free Software
21    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22    USA.  */
23 
24 /* Construction of sparse 3-level tables.
25    See wchar-lookup.h or coll-lookup.h for their structure and the
26    meaning of p and q.
27 
28    Before including this file, set
29      TABLE        to the name of the structure to be defined
30      ELEMENT      to the type of every entry
31      DEFAULT      to the default value for empty entries
32      ITERATE      if you want the TABLE_iterate function to be defined
33      NO_FINALIZE  if you don't want the TABLE_finalize function to be defined
34 
35    This will define
36 
37      struct TABLE;
38      void TABLE_init (struct TABLE *t);
39      ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
40      void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
41      void TABLE_iterate (struct TABLE *t,
42 			 void (*fn) (uint32_t wc, ELEMENT value));
43      void TABLE_finalize (struct TABLE *t);
44 */
45 
46 #define CONCAT(a,b) CONCAT1(a,b)
47 #define CONCAT1(a,b) a##b
48 
49 struct TABLE
50 {
51   /* Parameters.  */
52   unsigned int p;
53   unsigned int q;
54   /* Working representation.  */
55   size_t level1_alloc;
56   size_t level1_size;
57   uint32_t *level1;
58   size_t level2_alloc;
59   size_t level2_size;
60   uint32_t *level2;
61   size_t level3_alloc;
62   size_t level3_size;
63   ELEMENT *level3;
64   /* Compressed representation.  */
65   size_t result_size;
66   char *result;
67 };
68 
69 /* Initialize.  Assumes t->p and t->q have already been set.  */
70 static inline void
CONCAT(TABLE,_init)71 CONCAT(TABLE,_init) (struct TABLE *t)
72 {
73   t->level1 = NULL;
74   t->level1_alloc = t->level1_size = 0;
75   t->level2 = NULL;
76   t->level2_alloc = t->level2_size = 0;
77   t->level3 = NULL;
78   t->level3_alloc = t->level3_size = 0;
79 }
80 
81 /* Marker for an empty slot.  This has the value 0xFFFFFFFF, regardless
82    whether 'int' is 16 bit, 32 bit, or 64 bit.  */
83 #define EMPTY ((uint32_t) ~0)
84 
85 /* Retrieve an entry.  */
86 static inline ELEMENT
CONCAT(TABLE,_get)87 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
88 {
89   uint32_t index1 = wc >> (t->q + t->p);
90   if (index1 < t->level1_size)
91     {
92       uint32_t lookup1 = t->level1[index1];
93       if (lookup1 != EMPTY)
94 	{
95 	  uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
96 			    + (lookup1 << t->q);
97 	  uint32_t lookup2 = t->level2[index2];
98 	  if (lookup2 != EMPTY)
99 	    {
100 	      uint32_t index3 = (wc & ((1 << t->p) - 1))
101 				+ (lookup2 << t->p);
102 	      ELEMENT lookup3 = t->level3[index3];
103 
104 	      return lookup3;
105 	    }
106 	}
107     }
108   return DEFAULT;
109 }
110 
111 /* Add one entry.  */
112 static void
CONCAT(TABLE,_add)113 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
114 {
115   uint32_t index1 = wc >> (t->q + t->p);
116   uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
117   uint32_t index3 = wc & ((1 << t->p) - 1);
118   size_t i, i1, i2;
119 
120   if (value == CONCAT(TABLE,_get) (t, wc))
121     return;
122 
123   if (index1 >= t->level1_size)
124     {
125       if (index1 >= t->level1_alloc)
126 	{
127 	  size_t alloc = 2 * t->level1_alloc;
128 	  if (alloc <= index1)
129 	    alloc = index1 + 1;
130 	  t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
131 					     alloc * sizeof (uint32_t));
132 	  t->level1_alloc = alloc;
133 	}
134       while (index1 >= t->level1_size)
135 	t->level1[t->level1_size++] = EMPTY;
136     }
137 
138   if (t->level1[index1] == EMPTY)
139     {
140       if (t->level2_size == t->level2_alloc)
141 	{
142 	  size_t alloc = 2 * t->level2_alloc + 1;
143 	  t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
144 					     (alloc << t->q) * sizeof (uint32_t));
145 	  t->level2_alloc = alloc;
146 	}
147       i1 = t->level2_size << t->q;
148       i2 = (t->level2_size + 1) << t->q;
149       for (i = i1; i < i2; i++)
150 	t->level2[i] = EMPTY;
151       t->level1[index1] = t->level2_size++;
152     }
153 
154   index2 += t->level1[index1] << t->q;
155 
156   if (t->level2[index2] == EMPTY)
157     {
158       if (t->level3_size == t->level3_alloc)
159 	{
160 	  size_t alloc = 2 * t->level3_alloc + 1;
161 	  t->level3 = (ELEMENT *) xrealloc ((char *) t->level3,
162 					    (alloc << t->p) * sizeof (ELEMENT));
163 	  t->level3_alloc = alloc;
164 	}
165       i1 = t->level3_size << t->p;
166       i2 = (t->level3_size + 1) << t->p;
167       for (i = i1; i < i2; i++)
168 	t->level3[i] = DEFAULT;
169       t->level2[index2] = t->level3_size++;
170     }
171 
172   index3 += t->level2[index2] << t->p;
173 
174   t->level3[index3] = value;
175 }
176 
177 #ifdef ITERATE
178 /* Apply a function to all entries in the table.  */
179 static void
CONCAT(TABLE,_iterate)180 CONCAT(TABLE,_iterate) (struct TABLE *t,
181 			void (*fn) (uint32_t wc, ELEMENT value))
182 {
183   uint32_t index1;
184   for (index1 = 0; index1 < t->level1_size; index1++)
185     {
186       uint32_t lookup1 = t->level1[index1];
187       if (lookup1 != EMPTY)
188 	{
189 	  uint32_t lookup1_shifted = lookup1 << t->q;
190 	  uint32_t index2;
191 	  for (index2 = 0; index2 < (1 << t->q); index2++)
192 	    {
193 	      uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
194 	      if (lookup2 != EMPTY)
195 		{
196 		  uint32_t lookup2_shifted = lookup2 << t->p;
197 		  uint32_t index3;
198 		  for (index3 = 0; index3 < (1 << t->p); index3++)
199 		    {
200 		      ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
201 		      if (lookup3 != DEFAULT)
202 			fn ((((index1 << t->q) + index2) << t->p) + index3,
203 			    lookup3);
204 		    }
205 		}
206 	    }
207 	}
208     }
209 }
210 #endif
211 
212 #ifndef NO_FINALIZE
213 /* Finalize and shrink.  */
214 static void
CONCAT(TABLE,_finalize)215 CONCAT(TABLE,_finalize) (struct TABLE *t)
216 {
217   size_t i, j, k;
218   uint32_t reorder3[t->level3_size];
219   uint32_t reorder2[t->level2_size];
220   uint32_t level1_offset, level2_offset, level3_offset, last_offset;
221 
222   /* Uniquify level3 blocks.  */
223   k = 0;
224   for (j = 0; j < t->level3_size; j++)
225     {
226       for (i = 0; i < k; i++)
227 	if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
228 		    (1 << t->p) * sizeof (ELEMENT)) == 0)
229 	  break;
230       /* Relocate block j to block i.  */
231       reorder3[j] = i;
232       if (i == k)
233 	{
234 	  if (i != j)
235 	    memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
236 		    (1 << t->p) * sizeof (ELEMENT));
237 	  k++;
238 	}
239     }
240   t->level3_size = k;
241 
242   for (i = 0; i < (t->level2_size << t->q); i++)
243     if (t->level2[i] != EMPTY)
244       t->level2[i] = reorder3[t->level2[i]];
245 
246   /* Uniquify level2 blocks.  */
247   k = 0;
248   for (j = 0; j < t->level2_size; j++)
249     {
250       for (i = 0; i < k; i++)
251 	if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
252 		    (1 << t->q) * sizeof (uint32_t)) == 0)
253 	  break;
254       /* Relocate block j to block i.  */
255       reorder2[j] = i;
256       if (i == k)
257 	{
258 	  if (i != j)
259 	    memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
260 		    (1 << t->q) * sizeof (uint32_t));
261 	  k++;
262 	}
263     }
264   t->level2_size = k;
265 
266   for (i = 0; i < t->level1_size; i++)
267     if (t->level1[i] != EMPTY)
268       t->level1[i] = reorder2[t->level1[i]];
269 
270   /* Create and fill the resulting compressed representation.  */
271   last_offset =
272     5 * sizeof (uint32_t)
273     + t->level1_size * sizeof (uint32_t)
274     + (t->level2_size << t->q) * sizeof (uint32_t)
275     + (t->level3_size << t->p) * sizeof (ELEMENT);
276   t->result_size = (last_offset + 3) & ~3ul;
277   t->result = (char *) xmalloc (t->result_size);
278 
279   level1_offset =
280     5 * sizeof (uint32_t);
281   level2_offset =
282     5 * sizeof (uint32_t)
283     + t->level1_size * sizeof (uint32_t);
284   level3_offset =
285     5 * sizeof (uint32_t)
286     + t->level1_size * sizeof (uint32_t)
287     + (t->level2_size << t->q) * sizeof (uint32_t);
288 
289   ((uint32_t *) t->result)[0] = t->q + t->p;
290   ((uint32_t *) t->result)[1] = t->level1_size;
291   ((uint32_t *) t->result)[2] = t->p;
292   ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
293   ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
294 
295   for (i = 0; i < t->level1_size; i++)
296     ((uint32_t *) (t->result + level1_offset))[i] =
297       (t->level1[i] == EMPTY
298        ? 0
299        : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
300 
301   for (i = 0; i < (t->level2_size << t->q); i++)
302     ((uint32_t *) (t->result + level2_offset))[i] =
303       (t->level2[i] == EMPTY
304        ? 0
305        : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
306 
307   for (i = 0; i < (t->level3_size << t->p); i++)
308     ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i];
309 
310   if (last_offset < t->result_size)
311     memset (t->result + last_offset, 0, t->result_size - last_offset);
312 
313   if (t->level1_alloc > 0)
314     free (t->level1);
315   if (t->level2_alloc > 0)
316     free (t->level2);
317   if (t->level3_alloc > 0)
318     free (t->level3);
319 }
320 #endif
321 
322 #undef EMPTY
323 #undef TABLE
324 #undef ELEMENT
325 #undef DEFAULT
326 #undef ITERATE
327 #undef NO_FINALIZE
328