locale/programs/3level.h

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