[thirdparty/glibc.git] / locale / programs / 3level.h

/* Copyright (C) 2000 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with the GNU C Library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

/* Construction of sparse 3-level tables.
   See wchar-lookup.h or coll-lookup.h for their structure and the
   meaning of p and q.

   Before including this file, set
     TABLE        to the name of the structure to be defined
     ELEMENT      to the type of every entry
     DEFAULT      to the default value for empty entries
     ITERATE      if you want the TABLE_iterate function to be defined
     NO_FINALIZE  if you don't want the TABLE_finalize function to be defined

   This will define

     struct TABLE;
     void TABLE_init (struct TABLE *t);
     ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
     void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
     void TABLE_iterate (struct TABLE *t,
			 void (*fn) (uint32_t wc, ELEMENT value));
     void TABLE_finalize (struct TABLE *t);
*/

#define CONCAT(a,b) CONCAT1(a,b)
#define CONCAT1(a,b) a##b

struct TABLE
{
  /* Parameters.  */
  unsigned int p;
  unsigned int q;
  /* Working representation.  */
  size_t level1_alloc;
  size_t level1_size;
  uint32_t *level1;
  size_t level2_alloc;
  size_t level2_size;
  uint32_t *level2;
  size_t level3_alloc;
  size_t level3_size;
  ELEMENT *level3;
  /* Compressed representation.  */
  size_t result_size;
  char *result;
};

/* Initialize.  Assumes t->p and t->q have already been set.  */
static inline void
CONCAT(TABLE,_init) (struct TABLE *t)
{
  t->level1_alloc = t->level1_size = 0;
  t->level2_alloc = t->level2_size = 0;
  t->level3_alloc = t->level3_size = 0;
}

/* Retrieve an entry.  */
static inline ELEMENT
CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
{
  uint32_t index1 = wc >> (t->q + t->p);
  if (index1 < t->level1_size)
    {
      uint32_t lookup1 = t->level1[index1];
      if (lookup1 != ~((uint32_t) 0))
	{
	  uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
			    + (lookup1 << t->q);
	  uint32_t lookup2 = t->level2[index2];
	  if (lookup2 != ~((uint32_t) 0))
	    {
	      uint32_t index3 = (wc & ((1 << t->p) - 1))
				+ (lookup2 << t->p);
	      ELEMENT lookup3 = t->level3[index3];

	      return lookup3;
	    }
	}
    }
  return DEFAULT;
}

/* Add one entry.  */
static void
CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
{
  uint32_t index1 = wc >> (t->q + t->p);
  uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
  uint32_t index3 = wc & ((1 << t->p) - 1);
  size_t i, i1, i2;

  if (value == CONCAT(TABLE,_get) (t, wc))
    return;

  if (index1 >= t->level1_size)
    {
      if (index1 >= t->level1_alloc)
	{
	  size_t alloc = 2 * t->level1_alloc;
	  if (alloc <= index1)
	    alloc = index1 + 1;
	  t->level1 = (t->level1_alloc > 0
		       ? (uint32_t *) xrealloc ((char *) t->level1,
						alloc * sizeof (uint32_t))
		       : (uint32_t *) xmalloc (alloc * sizeof (uint32_t)));
	  t->level1_alloc = alloc;
	}
      while (index1 >= t->level1_size)
	t->level1[t->level1_size++] = ~((uint32_t) 0);
    }

  if (t->level1[index1] == ~((uint32_t) 0))
    {
      if (t->level2_size == t->level2_alloc)
	{
	  size_t alloc = 2 * t->level2_alloc + 1;
	  t->level2 = (t->level2_alloc > 0
		       ? (uint32_t *) xrealloc ((char *) t->level2,
						(alloc << t->q) * sizeof (uint32_t))
		       : (uint32_t *) xmalloc ((alloc << t->q) * sizeof (uint32_t)));
	  t->level2_alloc = alloc;
	}
      i1 = t->level2_size << t->q;
      i2 = (t->level2_size + 1) << t->q;
      for (i = i1; i < i2; i++)
	t->level2[i] = ~((uint32_t) 0);
      t->level1[index1] = t->level2_size++;
    }

  index2 += t->level1[index1] << t->q;

  if (t->level2[index2] == ~((uint32_t) 0))
    {
      if (t->level3_size == t->level3_alloc)
	{
	  size_t alloc = 2 * t->level3_alloc + 1;
	  t->level3 = (t->level3_alloc > 0
		       ? (ELEMENT *) xrealloc ((char *) t->level3,
					       (alloc << t->p) * sizeof (ELEMENT))
		       : (ELEMENT *) xmalloc ((alloc << t->p) * sizeof (ELEMENT)));
	  t->level3_alloc = alloc;
	}
      i1 = t->level3_size << t->p;
      i2 = (t->level3_size + 1) << t->p;
      for (i = i1; i < i2; i++)
	t->level3[i] = DEFAULT;
      t->level2[index2] = t->level3_size++;
    }

  index3 += t->level2[index2] << t->p;

  t->level3[index3] = value;
}

#ifdef ITERATE
/* Apply a function to all entries in the table.  */
static void
CONCAT(TABLE,_iterate) (struct TABLE *t,
			void (*fn) (uint32_t wc, ELEMENT value))
{
  uint32_t index1;
  for (index1 = 0; index1 < t->level1_size; index1++)
    {
      uint32_t lookup1 = t->level1[index1];
      if (lookup1 != ~((uint32_t) 0))
	{
	  uint32_t lookup1_shifted = lookup1 << t->q;
	  uint32_t index2;
	  for (index2 = 0; index2 < (1 << t->q); index2++)
	    {
	      uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
	      if (lookup2 != ~((uint32_t) 0))
		{
		  uint32_t lookup2_shifted = lookup2 << t->p;
		  uint32_t index3;
		  for (index3 = 0; index3 < (1 << t->p); index3++)
		    {
		      ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
		      if (lookup3 != DEFAULT)
			fn ((((index1 << t->q) + index2) << t->p) + index3,
			    lookup3);
		    }
		}
	    }
	}
    }
}
#endif

#ifndef NO_FINALIZE
/* Finalize and shrink.  */
static void
CONCAT(TABLE,_finalize) (struct TABLE *t)
{
  size_t i, j, k;
  uint32_t reorder3[t->level3_size];
  uint32_t reorder2[t->level2_size];
  uint32_t level1_offset, level2_offset, level3_offset, last_offset;

  /* Uniquify level3 blocks.  */
  k = 0;
  for (j = 0; j < t->level3_size; j++)
    {
      for (i = 0; i < k; i++)
	if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
		    (1 << t->p) * sizeof (ELEMENT)) == 0)
	  break;
      /* Relocate block j to block i.  */
      reorder3[j] = i;
      if (i == k)
	{
	  if (i != j)
	    memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
		    (1 << t->p) * sizeof (ELEMENT));
	  k++;
	}
    }
  t->level3_size = k;

  for (i = 0; i < (t->level2_size << t->q); i++)
    if (t->level2[i] != ~((uint32_t) 0))
      t->level2[i] = reorder3[t->level2[i]];

  /* Uniquify level2 blocks.  */
  k = 0;
  for (j = 0; j < t->level2_size; j++)
    {
      for (i = 0; i < k; i++)
	if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
		    (1 << t->q) * sizeof (uint32_t)) == 0)
	  break;
      /* Relocate block j to block i.  */
      reorder2[j] = i;
      if (i == k)
	{
	  if (i != j)
	    memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
		    (1 << t->q) * sizeof (uint32_t));
	  k++;
	}
    }
  t->level2_size = k;

  for (i = 0; i < t->level1_size; i++)
    if (t->level1[i] != ~((uint32_t) 0))
      t->level1[i] = reorder2[t->level1[i]];

  /* Create and fill the resulting compressed representation.  */
  last_offset =
    5 * sizeof (uint32_t)
    + t->level1_size * sizeof (uint32_t)
    + (t->level2_size << t->q) * sizeof (uint32_t)
    + (t->level3_size << t->p) * sizeof (ELEMENT);
  t->result_size = (last_offset + 3) & ~3ul;
  t->result = (char *) xmalloc (t->result_size);

  level1_offset =
    5 * sizeof (uint32_t);
  level2_offset =
    5 * sizeof (uint32_t)
    + t->level1_size * sizeof (uint32_t);
  level3_offset =
    5 * sizeof (uint32_t)
    + t->level1_size * sizeof (uint32_t)
    + (t->level2_size << t->q) * sizeof (uint32_t);

  ((uint32_t *) t->result)[0] = t->q + t->p;
  ((uint32_t *) t->result)[1] = t->level1_size;
  ((uint32_t *) t->result)[2] = t->p;
  ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
  ((uint32_t *) t->result)[4] = (1 << t->p) - 1;

  for (i = 0; i < t->level1_size; i++)
    ((uint32_t *) (t->result + level1_offset))[i] =
      (t->level1[i] == ~((uint32_t) 0)
       ? 0
       : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);

  for (i = 0; i < (t->level2_size << t->q); i++)
    ((uint32_t *) (t->result + level2_offset))[i] =
      (t->level2[i] == ~((uint32_t) 0)
       ? 0
       : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);

  for (i = 0; i < (t->level3_size << t->p); i++)
    ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i];

  if (last_offset < t->result_size)
    memset (t->result + last_offset, 0, t->result_size - last_offset);

  if (t->level1_alloc > 0)
    free (t->level1);
  if (t->level2_alloc > 0)
    free (t->level2);
  if (t->level3_alloc > 0)
    free (t->level3);
}
#endif

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