locale/programs/3level.h

   1 /* Copyright (C) 2000-2001, 2003 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 Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the 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    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    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 = NULL;
  70   t->level1_alloc = t->level1_size = 0;
  71   t->level2 = NULL;
  72   t->level2_alloc = t->level2_size = 0;
  73   t->level3 = NULL;
  74   t->level3_alloc = t->level3_size = 0;
  75 }
  76
  77 /* Marker for an empty slot.  This has the value 0xFFFFFFFF, regardless
  78    whether 'int' is 16 bit, 32 bit, or 64 bit.  */
  79 #define EMPTY ((uint32_t) ~0)
  80
  81 /* Retrieve an entry.  */
  82 static inline ELEMENT
  83 __attribute ((always_inline))
  84 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
  85 {
  86   uint32_t index1 = wc >> (t->q + t->p);
  87   if (index1 < t->level1_size)
  88     {
  89       uint32_t lookup1 = t->level1[index1];
  90       if (lookup1 != EMPTY)
  91         {
  92           uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
  93                             + (lookup1 << t->q);
  94           uint32_t lookup2 = t->level2[index2];
  95           if (lookup2 != EMPTY)
  96             {
  97               uint32_t index3 = (wc & ((1 << t->p) - 1))
  98                                 + (lookup2 << t->p);
  99               ELEMENT lookup3 = t->level3[index3];
 100
 101               return lookup3;
 102             }
 103         }
 104     }
 105   return DEFAULT;
 106 }
 107
 108 /* Add one entry.  */
 109 static void
 110 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
 111 {
 112   uint32_t index1 = wc >> (t->q + t->p);
 113   uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
 114   uint32_t index3 = wc & ((1 << t->p) - 1);
 115   size_t i, i1, i2;
 116
 117   if (value == CONCAT(TABLE,_get) (t, wc))
 118     return;
 119
 120   if (index1 >= t->level1_size)
 121     {
 122       if (index1 >= t->level1_alloc)
 123         {
 124           size_t alloc = 2 * t->level1_alloc;
 125           if (alloc <= index1)
 126             alloc = index1 + 1;
 127           t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
 128                                              alloc * sizeof (uint32_t));
 129           t->level1_alloc = alloc;
 130         }
 131       while (index1 >= t->level1_size)
 132         t->level1[t->level1_size++] = EMPTY;
 133     }
 134
 135   if (t->level1[index1] == EMPTY)
 136     {
 137       if (t->level2_size == t->level2_alloc)
 138         {
 139           size_t alloc = 2 * t->level2_alloc + 1;
 140           t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
 141                                              (alloc << t->q) * sizeof (uint32_t));
 142           t->level2_alloc = alloc;
 143         }
 144       i1 = t->level2_size << t->q;
 145       i2 = (t->level2_size + 1) << t->q;
 146       for (i = i1; i < i2; i++)
 147         t->level2[i] = EMPTY;
 148       t->level1[index1] = t->level2_size++;
 149     }
 150
 151   index2 += t->level1[index1] << t->q;
 152
 153   if (t->level2[index2] == EMPTY)
 154     {
 155       if (t->level3_size == t->level3_alloc)
 156         {
 157           size_t alloc = 2 * t->level3_alloc + 1;
 158           t->level3 = (ELEMENT *) xrealloc ((char *) t->level3,
 159                                             (alloc << t->p) * sizeof (ELEMENT));
 160           t->level3_alloc = alloc;
 161         }
 162       i1 = t->level3_size << t->p;
 163       i2 = (t->level3_size + 1) << t->p;
 164       for (i = i1; i < i2; i++)
 165         t->level3[i] = DEFAULT;
 166       t->level2[index2] = t->level3_size++;
 167     }
 168
 169   index3 += t->level2[index2] << t->p;
 170
 171   t->level3[index3] = value;
 172 }
 173
 174 #ifdef ITERATE
 175 /* Apply a function to all entries in the table.  */
 176 static void
 177 CONCAT(TABLE,_iterate) (struct TABLE *t,
 178                         void (*fn) (uint32_t wc, ELEMENT value))
 179 {
 180   uint32_t index1;
 181   for (index1 = 0; index1 < t->level1_size; index1++)
 182     {
 183       uint32_t lookup1 = t->level1[index1];
 184       if (lookup1 != EMPTY)
 185         {
 186           uint32_t lookup1_shifted = lookup1 << t->q;
 187           uint32_t index2;
 188           for (index2 = 0; index2 < (1 << t->q); index2++)
 189             {
 190               uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
 191               if (lookup2 != EMPTY)
 192                 {
 193                   uint32_t lookup2_shifted = lookup2 << t->p;
 194                   uint32_t index3;
 195                   for (index3 = 0; index3 < (1 << t->p); index3++)
 196                     {
 197                       ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
 198                       if (lookup3 != DEFAULT)
 199                         fn ((((index1 << t->q) + index2) << t->p) + index3,
 200                             lookup3);
 201                     }
 202                 }
 203             }
 204         }
 205     }
 206 }
 207 #endif
 208
 209 #ifndef NO_FINALIZE
 210 /* Finalize and shrink.  */
 211 static void
 212 CONCAT(TABLE,_finalize) (struct TABLE *t)
 213 {
 214   size_t i, j, k;
 215   uint32_t reorder3[t->level3_size];
 216   uint32_t reorder2[t->level2_size];
 217   uint32_t level1_offset, level2_offset, level3_offset, last_offset;
 218
 219   /* Uniquify level3 blocks.  */
 220   k = 0;
 221   for (j = 0; j < t->level3_size; j++)
 222     {
 223       for (i = 0; i < k; i++)
 224         if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
 225                     (1 << t->p) * sizeof (ELEMENT)) == 0)
 226           break;
 227       /* Relocate block j to block i.  */
 228       reorder3[j] = i;
 229       if (i == k)
 230         {
 231           if (i != j)
 232             memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
 233                     (1 << t->p) * sizeof (ELEMENT));
 234           k++;
 235         }
 236     }
 237   t->level3_size = k;
 238
 239   for (i = 0; i < (t->level2_size << t->q); i++)
 240     if (t->level2[i] != EMPTY)
 241       t->level2[i] = reorder3[t->level2[i]];
 242
 243   /* Uniquify level2 blocks.  */
 244   k = 0;
 245   for (j = 0; j < t->level2_size; j++)
 246     {
 247       for (i = 0; i < k; i++)
 248         if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
 249                     (1 << t->q) * sizeof (uint32_t)) == 0)
 250           break;
 251       /* Relocate block j to block i.  */
 252       reorder2[j] = i;
 253       if (i == k)
 254         {
 255           if (i != j)
 256             memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
 257                     (1 << t->q) * sizeof (uint32_t));
 258           k++;
 259         }
 260     }
 261   t->level2_size = k;
 262
 263   for (i = 0; i < t->level1_size; i++)
 264     if (t->level1[i] != EMPTY)
 265       t->level1[i] = reorder2[t->level1[i]];
 266
 267   /* Create and fill the resulting compressed representation.  */
 268   last_offset =
 269     5 * sizeof (uint32_t)
 270     + t->level1_size * sizeof (uint32_t)
 271     + (t->level2_size << t->q) * sizeof (uint32_t)
 272     + (t->level3_size << t->p) * sizeof (ELEMENT);
 273   t->result_size = (last_offset + 3) & ~3ul;
 274   t->result = (char *) xmalloc (t->result_size);
 275
 276   level1_offset =
 277     5 * sizeof (uint32_t);
 278   level2_offset =
 279     5 * sizeof (uint32_t)
 280     + t->level1_size * sizeof (uint32_t);
 281   level3_offset =
 282     5 * sizeof (uint32_t)
 283     + t->level1_size * sizeof (uint32_t)
 284     + (t->level2_size << t->q) * sizeof (uint32_t);
 285
 286   ((uint32_t *) t->result)[0] = t->q + t->p;
 287   ((uint32_t *) t->result)[1] = t->level1_size;
 288   ((uint32_t *) t->result)[2] = t->p;
 289   ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
 290   ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
 291
 292   for (i = 0; i < t->level1_size; i++)
 293     ((uint32_t *) (t->result + level1_offset))[i] =
 294       (t->level1[i] == EMPTY
 295        ? 0
 296        : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
 297
 298   for (i = 0; i < (t->level2_size << t->q); i++)
 299     ((uint32_t *) (t->result + level2_offset))[i] =
 300       (t->level2[i] == EMPTY
 301        ? 0
 302        : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
 303
 304   for (i = 0; i < (t->level3_size << t->p); i++)
 305     ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i];
 306
 307   if (last_offset < t->result_size)
 308     memset (t->result + last_offset, 0, t->result_size - last_offset);
 309
 310   if (t->level1_alloc > 0)
 311     free (t->level1);
 312   if (t->level2_alloc > 0)
 313     free (t->level2);
 314   if (t->level3_alloc > 0)
 315     free (t->level3);
 316 }
 317 #endif
 318
 319 #undef EMPTY
 320 #undef TABLE
 321 #undef ELEMENT
 322 #undef DEFAULT
 323 #undef ITERATE
 324 #undef NO_FINALIZE