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 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 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 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 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 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