lib/unictype/3levelbit.h

   1 /* Copyright (C) 2000-2002, 2009-2012 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    See glibc/locale/programs/ld-ctype.c.
   8    Bugs can be reported to bug-glibc@gnu.org.
   9
  10    This program is free software; you can redistribute it and/or modify it
  11    under the terms of the GNU General Public License as published by the
  12    Free Software Foundation; either version 2, or (at your option) any
  13    later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  23    USA.  */
  24
  25 /* Construction of sparse 3-level tables.
  26    See wchar-lookup.h for their structure and the meaning of p and q.
  27
  28    Before including this file, set
  29      TABLE        to the name of the structure to be defined
  30      ITERATE      if you want the TABLE_iterate function to be defined
  31      NO_FINALIZE  if you don't want the TABLE_finalize function to be defined
  32
  33    This will define
  34
  35      struct TABLE;
  36      void TABLE_init (struct TABLE *t);
  37      int TABLE_get (struct TABLE *t, uint32_t wc);
  38      void TABLE_add (struct TABLE *t, uint32_t wc);
  39      void TABLE_iterate (struct TABLE *t, void (*fn) (uint32_t wc));
  40      void TABLE_finalize (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   uint32_t *level3;
  61   /* Compressed representation.  */
  62   size_t result_size;
  63   char *result;
  64 };
  65
  66 /* Initialize.  Assumes t->p and t->q have already been set.  */
  67 static inline void
  68 CONCAT(TABLE,_init) (struct TABLE *t)
  69 {
  70   t->level1 = NULL;
  71   t->level1_alloc = t->level1_size = 0;
  72   t->level2 = NULL;
  73   t->level2_alloc = t->level2_size = 0;
  74   t->level3 = NULL;
  75   t->level3_alloc = t->level3_size = 0;
  76 }
  77
  78 /* Marker for an empty slot.  This has the value 0xFFFFFFFF, regardless
  79    whether 'int' is 16 bit, 32 bit, or 64 bit.  */
  80 #define EMPTY ((uint32_t) ~0)
  81
  82 /* Retrieve an entry.  */
  83 static inline int
  84 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
  85 {
  86   uint32_t index1 = wc >> (t->q + t->p + 5);
  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 + 5)) & ((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 >> 5) & ((1 << t->p) - 1))
  98                                 + (lookup2 << t->p);
  99               uint32_t lookup3 = t->level3[index3];
 100               uint32_t index4 = wc & 0x1f;
 101
 102               return (lookup3 >> index4) & 1;
 103             }
 104         }
 105     }
 106   return 0;
 107 }
 108
 109 /* Add one entry.  */
 110 static void
 111 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc)
 112 {
 113   uint32_t index1 = wc >> (t->q + t->p + 5);
 114   uint32_t index2 = (wc >> (t->p + 5)) & ((1 << t->q) - 1);
 115   uint32_t index3 = (wc >> 5) & ((1 << t->p) - 1);
 116   uint32_t index4 = wc & 0x1f;
 117   size_t i, i1, i2;
 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 = (uint32_t *) xrealloc ((char *) t->level3,
 158                                             (alloc << t->p) * sizeof (uint32_t));
 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] = 0;
 165       t->level2[index2] = t->level3_size++;
 166     }
 167
 168   index3 += t->level2[index2] << t->p;
 169
 170   t->level3[index3] |= (uint32_t)1 << index4;
 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, void (*fn) (uint32_t wc))
 177 {
 178   uint32_t index1;
 179   for (index1 = 0; index1 < t->level1_size; index1++)
 180     {
 181       uint32_t lookup1 = t->level1[index1];
 182       if (lookup1 != EMPTY)
 183         {
 184           uint32_t lookup1_shifted = lookup1 << t->q;
 185           uint32_t index2;
 186           for (index2 = 0; index2 < (1 << t->q); index2++)
 187             {
 188               uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
 189               if (lookup2 != EMPTY)
 190                 {
 191                   uint32_t lookup2_shifted = lookup2 << t->p;
 192                   uint32_t index3;
 193                   for (index3 = 0; index3 < (1 << t->p); index3++)
 194                     {
 195                       uint32_t lookup3 = t->level3[index3 + lookup2_shifted];
 196                       uint32_t index4;
 197                       for (index4 = 0; index4 < 32; index4++)
 198                         if ((lookup3 >> index4) & 1)
 199                           fn ((((((index1 << t->q) + index2) << t->p) + index3) << 5) + index4);
 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;
 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 (uint32_t)) == 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 (uint32_t));
 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   t->result_size =
 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 (uint32_t);
 272   t->result = (char *) xmalloc (t->result_size);
 273
 274   level1_offset =
 275     5 * sizeof (uint32_t);
 276   level2_offset =
 277     5 * sizeof (uint32_t)
 278     + t->level1_size * sizeof (uint32_t);
 279   level3_offset =
 280     5 * sizeof (uint32_t)
 281     + t->level1_size * sizeof (uint32_t)
 282     + (t->level2_size << t->q) * sizeof (uint32_t);
 283
 284   ((uint32_t *) t->result)[0] = t->q + t->p + 5;
 285   ((uint32_t *) t->result)[1] = t->level1_size;
 286   ((uint32_t *) t->result)[2] = t->p + 5;
 287   ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
 288   ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
 289
 290   for (i = 0; i < t->level1_size; i++)
 291     ((uint32_t *) (t->result + level1_offset))[i] =
 292       (t->level1[i] == EMPTY
 293        ? 0
 294        : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
 295
 296   for (i = 0; i < (t->level2_size << t->q); i++)
 297     ((uint32_t *) (t->result + level2_offset))[i] =
 298       (t->level2[i] == EMPTY
 299        ? 0
 300        : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
 301
 302   for (i = 0; i < (t->level3_size << t->p); i++)
 303     ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
 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 EMPTY
 315 #undef TABLE
 316 #undef ITERATE
 317 #undef NO_FINALIZE