locale/programs/3level.h

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