locale/programs/3level.h

   1 /* Copyright (C) 2000-2017 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, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <stdint.h>
  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_ADD_LOCALE  if you don't want the add_locale_TABLE function
  30                     to be defined
  31
  32    This will define
  33
  34      struct TABLE;
  35      void TABLE_init (struct TABLE *t);
  36      ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
  37      void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
  38      void TABLE_iterate (struct TABLE *t,
  39                          void (*fn) (uint32_t wc, ELEMENT value));
  40      void add_locale_TABLE (struct locale_file *file, struct TABLE *t);
  41 */
  42
  43 #define CONCAT(a,b) CONCAT1(a,b)
  44 #define CONCAT1(a,b) a##b
  45
  46 struct TABLE
  47 {
  48   /* Parameters.  */
  49   unsigned int p;
  50   unsigned int q;
  51   /* Working representation.  */
  52   size_t level1_alloc;
  53   size_t level1_size;
  54   uint32_t *level1;
  55   size_t level2_alloc;
  56   size_t level2_size;
  57   uint32_t *level2;
  58   size_t level3_alloc;
  59   size_t level3_size;
  60   ELEMENT *level3;
  61   /* Size of compressed representation.  */
  62   size_t result_size;
  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_ADD_LOCALE
 210 /* Finalize and shrink.  */
 211 static void
 212 CONCAT(add_locale_,TABLE) (struct locale_file *file, 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 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 = LOCFILE_ALIGN_UP (last_offset);
 274
 275   level2_offset =
 276     5 * sizeof (uint32_t)
 277     + t->level1_size * sizeof (uint32_t);
 278   level3_offset =
 279     5 * sizeof (uint32_t)
 280     + t->level1_size * sizeof (uint32_t)
 281     + (t->level2_size << t->q) * sizeof (uint32_t);
 282
 283   start_locale_structure (file);
 284   add_locale_uint32 (file, t->q + t->p);
 285   add_locale_uint32 (file, t->level1_size);
 286   add_locale_uint32 (file, t->p);
 287   add_locale_uint32 (file, (1 << t->q) - 1);
 288   add_locale_uint32 (file, (1 << t->p) - 1);
 289
 290   for (i = 0; i < t->level1_size; i++)
 291     add_locale_uint32
 292       (file,
 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     add_locale_uint32
 299       (file,
 300        t->level2[i] == EMPTY
 301        ? 0
 302        : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
 303
 304   if (sizeof (ELEMENT) == 1)
 305     add_locale_raw_data (file, t->level3, t->level3_size << t->p);
 306   else if (sizeof (ELEMENT) == sizeof (uint32_t))
 307     add_locale_uint32_array (file, (uint32_t *) t->level3,
 308                              t->level3_size << t->p);
 309   else
 310     abort ();
 311   align_locale_data (file, LOCFILE_ALIGN);
 312   end_locale_structure (file);
 313
 314   if (t->level1_alloc > 0)
 315     free (t->level1);
 316   if (t->level2_alloc > 0)
 317     free (t->level2);
 318   if (t->level3_alloc > 0)
 319     free (t->level3);
 320 }
 321 #endif
 322
 323 #undef EMPTY
 324 #undef TABLE
 325 #undef ELEMENT
 326 #undef DEFAULT
 327 #undef ITERATE
 328 #undef NO_ADD_LOCALE