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, see <http://www.gnu.org/licenses/>.  */
  22
  23 /* Construction of sparse 3-level tables.
  24    See wchar-lookup.h for their structure and the meaning of p and q.
  25
  26    Before including this file, set
  27      TABLE        to the name of the structure to be defined
  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      int TABLE_get (struct TABLE *t, uint32_t wc);
  36      void TABLE_add (struct TABLE *t, uint32_t wc);
  37      void TABLE_iterate (struct TABLE *t, void (*fn) (uint32_t wc));
  38      void TABLE_finalize (struct TABLE *t);
  39 */
  40
  41 #define CONCAT(a,b) CONCAT1(a,b)
  42 #define CONCAT1(a,b) a##b
  43
  44 struct TABLE
  45 {
  46   /* Parameters.  */
  47   unsigned int p;
  48   unsigned int q;
  49   /* Working representation.  */
  50   size_t level1_alloc;
  51   size_t level1_size;
  52   uint32_t *level1;
  53   size_t level2_alloc;
  54   size_t level2_size;
  55   uint32_t *level2;
  56   size_t level3_alloc;
  57   size_t level3_size;
  58   uint32_t *level3;
  59   /* Compressed representation.  */
  60   size_t result_size;
  61   char *result;
  62 };
  63
  64 /* Initialize.  Assumes t->p and t->q have already been set.  */
  65 static inline void
  66 CONCAT(TABLE,_init) (struct TABLE *t)
  67 {
  68   t->level1 = NULL;
  69   t->level1_alloc = t->level1_size = 0;
  70   t->level2 = NULL;
  71   t->level2_alloc = t->level2_size = 0;
  72   t->level3 = NULL;
  73   t->level3_alloc = t->level3_size = 0;
  74 }
  75
  76 /* Marker for an empty slot.  This has the value 0xFFFFFFFF, regardless
  77    whether 'int' is 16 bit, 32 bit, or 64 bit.  */
  78 #define EMPTY ((uint32_t) ~0)
  79
  80 /* Retrieve an entry.  */
  81 static inline int
  82 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
  83 {
  84   uint32_t index1 = wc >> (t->q + t->p + 5);
  85   if (index1 < t->level1_size)
  86     {
  87       uint32_t lookup1 = t->level1[index1];
  88       if (lookup1 != EMPTY)
  89         {
  90           uint32_t index2 = ((wc >> (t->p + 5)) & ((1 << t->q) - 1))
  91                             + (lookup1 << t->q);
  92           uint32_t lookup2 = t->level2[index2];
  93           if (lookup2 != EMPTY)
  94             {
  95               uint32_t index3 = ((wc >> 5) & ((1 << t->p) - 1))
  96                                 + (lookup2 << t->p);
  97               uint32_t lookup3 = t->level3[index3];
  98               uint32_t index4 = wc & 0x1f;
  99
 100               return (lookup3 >> index4) & 1;
 101             }
 102         }
 103     }
 104   return 0;
 105 }
 106
 107 /* Add one entry.  */
 108 static void
 109 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc)
 110 {
 111   uint32_t index1 = wc >> (t->q + t->p + 5);
 112   uint32_t index2 = (wc >> (t->p + 5)) & ((1 << t->q) - 1);
 113   uint32_t index3 = (wc >> 5) & ((1 << t->p) - 1);
 114   uint32_t index4 = wc & 0x1f;
 115   size_t i, i1, i2;
 116
 117   if (index1 >= t->level1_size)
 118     {
 119       if (index1 >= t->level1_alloc)
 120         {
 121           size_t alloc = 2 * t->level1_alloc;
 122           if (alloc <= index1)
 123             alloc = index1 + 1;
 124           t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
 125                                              alloc * sizeof (uint32_t));
 126           t->level1_alloc = alloc;
 127         }
 128       while (index1 >= t->level1_size)
 129         t->level1[t->level1_size++] = EMPTY;
 130     }
 131
 132   if (t->level1[index1] == EMPTY)
 133     {
 134       if (t->level2_size == t->level2_alloc)
 135         {
 136           size_t alloc = 2 * t->level2_alloc + 1;
 137           t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
 138                                              (alloc << t->q) * sizeof (uint32_t));
 139           t->level2_alloc = alloc;
 140         }
 141       i1 = t->level2_size << t->q;
 142       i2 = (t->level2_size + 1) << t->q;
 143       for (i = i1; i < i2; i++)
 144         t->level2[i] = EMPTY;
 145       t->level1[index1] = t->level2_size++;
 146     }
 147
 148   index2 += t->level1[index1] << t->q;
 149
 150   if (t->level2[index2] == EMPTY)
 151     {
 152       if (t->level3_size == t->level3_alloc)
 153         {
 154           size_t alloc = 2 * t->level3_alloc + 1;
 155           t->level3 = (uint32_t *) xrealloc ((char *) t->level3,
 156                                             (alloc << t->p) * sizeof (uint32_t));
 157           t->level3_alloc = alloc;
 158         }
 159       i1 = t->level3_size << t->p;
 160       i2 = (t->level3_size + 1) << t->p;
 161       for (i = i1; i < i2; i++)
 162         t->level3[i] = 0;
 163       t->level2[index2] = t->level3_size++;
 164     }
 165
 166   index3 += t->level2[index2] << t->p;
 167
 168   t->level3[index3] |= (uint32_t)1 << index4;
 169 }
 170
 171 #ifdef ITERATE
 172 /* Apply a function to all entries in the table.  */
 173 static void
 174 CONCAT(TABLE,_iterate) (struct TABLE *t, void (*fn) (uint32_t wc))
 175 {
 176   uint32_t index1;
 177   for (index1 = 0; index1 < t->level1_size; index1++)
 178     {
 179       uint32_t lookup1 = t->level1[index1];
 180       if (lookup1 != EMPTY)
 181         {
 182           uint32_t lookup1_shifted = lookup1 << t->q;
 183           uint32_t index2;
 184           for (index2 = 0; index2 < (1 << t->q); index2++)
 185             {
 186               uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
 187               if (lookup2 != EMPTY)
 188                 {
 189                   uint32_t lookup2_shifted = lookup2 << t->p;
 190                   uint32_t index3;
 191                   for (index3 = 0; index3 < (1 << t->p); index3++)
 192                     {
 193                       uint32_t lookup3 = t->level3[index3 + lookup2_shifted];
 194                       uint32_t index4;
 195                       for (index4 = 0; index4 < 32; index4++)
 196                         if ((lookup3 >> index4) & 1)
 197                           fn ((((((index1 << t->q) + index2) << t->p) + index3) << 5) + index4);
 198                     }
 199                 }
 200             }
 201         }
 202     }
 203 }
 204 #endif
 205
 206 #ifndef NO_FINALIZE
 207 /* Finalize and shrink.  */
 208 static void
 209 CONCAT(TABLE,_finalize) (struct TABLE *t)
 210 {
 211   size_t i, j, k;
 212   uint32_t reorder3[t->level3_size];
 213   uint32_t reorder2[t->level2_size];
 214   uint32_t level1_offset, level2_offset, level3_offset;
 215
 216   /* Uniquify level3 blocks.  */
 217   k = 0;
 218   for (j = 0; j < t->level3_size; j++)
 219     {
 220       for (i = 0; i < k; i++)
 221         if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
 222                     (1 << t->p) * sizeof (uint32_t)) == 0)
 223           break;
 224       /* Relocate block j to block i.  */
 225       reorder3[j] = i;
 226       if (i == k)
 227         {
 228           if (i != j)
 229             memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
 230                     (1 << t->p) * sizeof (uint32_t));
 231           k++;
 232         }
 233     }
 234   t->level3_size = k;
 235
 236   for (i = 0; i < (t->level2_size << t->q); i++)
 237     if (t->level2[i] != EMPTY)
 238       t->level2[i] = reorder3[t->level2[i]];
 239
 240   /* Uniquify level2 blocks.  */
 241   k = 0;
 242   for (j = 0; j < t->level2_size; j++)
 243     {
 244       for (i = 0; i < k; i++)
 245         if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
 246                     (1 << t->q) * sizeof (uint32_t)) == 0)
 247           break;
 248       /* Relocate block j to block i.  */
 249       reorder2[j] = i;
 250       if (i == k)
 251         {
 252           if (i != j)
 253             memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
 254                     (1 << t->q) * sizeof (uint32_t));
 255           k++;
 256         }
 257     }
 258   t->level2_size = k;
 259
 260   for (i = 0; i < t->level1_size; i++)
 261     if (t->level1[i] != EMPTY)
 262       t->level1[i] = reorder2[t->level1[i]];
 263
 264   /* Create and fill the resulting compressed representation.  */
 265   t->result_size =
 266     5 * sizeof (uint32_t)
 267     + t->level1_size * sizeof (uint32_t)
 268     + (t->level2_size << t->q) * sizeof (uint32_t)
 269     + (t->level3_size << t->p) * sizeof (uint32_t);
 270   t->result = (char *) xmalloc (t->result_size);
 271
 272   level1_offset =
 273     5 * sizeof (uint32_t);
 274   level2_offset =
 275     5 * sizeof (uint32_t)
 276     + t->level1_size * sizeof (uint32_t);
 277   level3_offset =
 278     5 * sizeof (uint32_t)
 279     + t->level1_size * sizeof (uint32_t)
 280     + (t->level2_size << t->q) * sizeof (uint32_t);
 281
 282   ((uint32_t *) t->result)[0] = t->q + t->p + 5;
 283   ((uint32_t *) t->result)[1] = t->level1_size;
 284   ((uint32_t *) t->result)[2] = t->p + 5;
 285   ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
 286   ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
 287
 288   for (i = 0; i < t->level1_size; i++)
 289     ((uint32_t *) (t->result + level1_offset))[i] =
 290       (t->level1[i] == EMPTY
 291        ? 0
 292        : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
 293
 294   for (i = 0; i < (t->level2_size << t->q); i++)
 295     ((uint32_t *) (t->result + level2_offset))[i] =
 296       (t->level2[i] == EMPTY
 297        ? 0
 298        : (t->level2[i] << t->p) * sizeof (uint32_t) + level3_offset);
 299
 300   for (i = 0; i < (t->level3_size << t->p); i++)
 301     ((uint32_t *) (t->result + level3_offset))[i] = t->level3[i];
 302
 303   if (t->level1_alloc > 0)
 304     free (t->level1);
 305   if (t->level2_alloc > 0)
 306     free (t->level2);
 307   if (t->level3_alloc > 0)
 308     free (t->level3);
 309 }
 310 #endif
 311
 312 #undef EMPTY
 313 #undef TABLE
 314 #undef ITERATE
 315 #undef NO_FINALIZE