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