gnu/dist/gettext/gettext-tools/lib/3level.h

   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., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  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