Back to index

glibc  2.9
3level.h
Go to the documentation of this file.
00001 /* Copyright (C) 2000-2001, 2003, 2005 Free Software Foundation, Inc.
00002    This file is part of the GNU C Library.
00003    Contributed by Bruno Haible <haible@clisp.cons.org>, 2000.
00004 
00005    This program is free software; you can redistribute it and/or modify
00006    it under the terms of the GNU General Public License as published
00007    by the Free Software Foundation; version 2 of the License, or
00008    (at your option) any later version.
00009 
00010    This program is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013    GNU General Public License for more details.
00014 
00015    You should have received a copy of the GNU General Public License
00016    along with this program; if not, write to the Free Software Foundation,
00017    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00018 
00019 /* Construction of sparse 3-level tables.
00020    See wchar-lookup.h or coll-lookup.h for their structure and the
00021    meaning of p and q.
00022 
00023    Before including this file, set
00024      TABLE        to the name of the structure to be defined
00025      ELEMENT      to the type of every entry
00026      DEFAULT      to the default value for empty entries
00027      ITERATE      if you want the TABLE_iterate function to be defined
00028      NO_FINALIZE  if you don't want the TABLE_finalize function to be defined
00029 
00030    This will define
00031 
00032      struct TABLE;
00033      void TABLE_init (struct TABLE *t);
00034      ELEMENT TABLE_get (struct TABLE *t, uint32_t wc);
00035      void TABLE_add (struct TABLE *t, uint32_t wc, ELEMENT value);
00036      void TABLE_iterate (struct TABLE *t,
00037                       void (*fn) (uint32_t wc, ELEMENT value));
00038      void TABLE_finalize (struct TABLE *t);
00039 */
00040 
00041 #define CONCAT(a,b) CONCAT1(a,b)
00042 #define CONCAT1(a,b) a##b
00043 
00044 struct TABLE
00045 {
00046   /* Parameters.  */
00047   unsigned int p;
00048   unsigned int q;
00049   /* Working representation.  */
00050   size_t level1_alloc;
00051   size_t level1_size;
00052   uint32_t *level1;
00053   size_t level2_alloc;
00054   size_t level2_size;
00055   uint32_t *level2;
00056   size_t level3_alloc;
00057   size_t level3_size;
00058   ELEMENT *level3;
00059   /* Compressed representation.  */
00060   size_t result_size;
00061   char *result;
00062 };
00063 
00064 /* Initialize.  Assumes t->p and t->q have already been set.  */
00065 static inline void
00066 CONCAT(TABLE,_init) (struct TABLE *t)
00067 {
00068   t->level1 = NULL;
00069   t->level1_alloc = t->level1_size = 0;
00070   t->level2 = NULL;
00071   t->level2_alloc = t->level2_size = 0;
00072   t->level3 = NULL;
00073   t->level3_alloc = t->level3_size = 0;
00074 }
00075 
00076 /* Marker for an empty slot.  This has the value 0xFFFFFFFF, regardless
00077    whether 'int' is 16 bit, 32 bit, or 64 bit.  */
00078 #define EMPTY ((uint32_t) ~0)
00079 
00080 /* Retrieve an entry.  */
00081 static inline ELEMENT
00082 __attribute ((always_inline))
00083 CONCAT(TABLE,_get) (struct TABLE *t, uint32_t wc)
00084 {
00085   uint32_t index1 = wc >> (t->q + t->p);
00086   if (index1 < t->level1_size)
00087     {
00088       uint32_t lookup1 = t->level1[index1];
00089       if (lookup1 != EMPTY)
00090        {
00091          uint32_t index2 = ((wc >> t->p) & ((1 << t->q) - 1))
00092                          + (lookup1 << t->q);
00093          uint32_t lookup2 = t->level2[index2];
00094          if (lookup2 != EMPTY)
00095            {
00096              uint32_t index3 = (wc & ((1 << t->p) - 1))
00097                             + (lookup2 << t->p);
00098              ELEMENT lookup3 = t->level3[index3];
00099 
00100              return lookup3;
00101            }
00102        }
00103     }
00104   return DEFAULT;
00105 }
00106 
00107 /* Add one entry.  */
00108 static void
00109 CONCAT(TABLE,_add) (struct TABLE *t, uint32_t wc, ELEMENT value)
00110 {
00111   uint32_t index1 = wc >> (t->q + t->p);
00112   uint32_t index2 = (wc >> t->p) & ((1 << t->q) - 1);
00113   uint32_t index3 = wc & ((1 << t->p) - 1);
00114   size_t i, i1, i2;
00115 
00116   if (value == CONCAT(TABLE,_get) (t, wc))
00117     return;
00118 
00119   if (index1 >= t->level1_size)
00120     {
00121       if (index1 >= t->level1_alloc)
00122        {
00123          size_t alloc = 2 * t->level1_alloc;
00124          if (alloc <= index1)
00125            alloc = index1 + 1;
00126          t->level1 = (uint32_t *) xrealloc ((char *) t->level1,
00127                                         alloc * sizeof (uint32_t));
00128          t->level1_alloc = alloc;
00129        }
00130       while (index1 >= t->level1_size)
00131        t->level1[t->level1_size++] = EMPTY;
00132     }
00133 
00134   if (t->level1[index1] == EMPTY)
00135     {
00136       if (t->level2_size == t->level2_alloc)
00137        {
00138          size_t alloc = 2 * t->level2_alloc + 1;
00139          t->level2 = (uint32_t *) xrealloc ((char *) t->level2,
00140                                         (alloc << t->q) * sizeof (uint32_t));
00141          t->level2_alloc = alloc;
00142        }
00143       i1 = t->level2_size << t->q;
00144       i2 = (t->level2_size + 1) << t->q;
00145       for (i = i1; i < i2; i++)
00146        t->level2[i] = EMPTY;
00147       t->level1[index1] = t->level2_size++;
00148     }
00149 
00150   index2 += t->level1[index1] << t->q;
00151 
00152   if (t->level2[index2] == EMPTY)
00153     {
00154       if (t->level3_size == t->level3_alloc)
00155        {
00156          size_t alloc = 2 * t->level3_alloc + 1;
00157          t->level3 = (ELEMENT *) xrealloc ((char *) t->level3,
00158                                        (alloc << t->p) * sizeof (ELEMENT));
00159          t->level3_alloc = alloc;
00160        }
00161       i1 = t->level3_size << t->p;
00162       i2 = (t->level3_size + 1) << t->p;
00163       for (i = i1; i < i2; i++)
00164        t->level3[i] = DEFAULT;
00165       t->level2[index2] = t->level3_size++;
00166     }
00167 
00168   index3 += t->level2[index2] << t->p;
00169 
00170   t->level3[index3] = value;
00171 }
00172 
00173 #ifdef ITERATE
00174 /* Apply a function to all entries in the table.  */
00175 static void
00176 CONCAT(TABLE,_iterate) (struct TABLE *t,
00177                      void (*fn) (uint32_t wc, ELEMENT value))
00178 {
00179   uint32_t index1;
00180   for (index1 = 0; index1 < t->level1_size; index1++)
00181     {
00182       uint32_t lookup1 = t->level1[index1];
00183       if (lookup1 != EMPTY)
00184        {
00185          uint32_t lookup1_shifted = lookup1 << t->q;
00186          uint32_t index2;
00187          for (index2 = 0; index2 < (1 << t->q); index2++)
00188            {
00189              uint32_t lookup2 = t->level2[index2 + lookup1_shifted];
00190              if (lookup2 != EMPTY)
00191               {
00192                 uint32_t lookup2_shifted = lookup2 << t->p;
00193                 uint32_t index3;
00194                 for (index3 = 0; index3 < (1 << t->p); index3++)
00195                   {
00196                     ELEMENT lookup3 = t->level3[index3 + lookup2_shifted];
00197                     if (lookup3 != DEFAULT)
00198                      fn ((((index1 << t->q) + index2) << t->p) + index3,
00199                          lookup3);
00200                   }
00201               }
00202            }
00203        }
00204     }
00205 }
00206 #endif
00207 
00208 #ifndef NO_FINALIZE
00209 /* Finalize and shrink.  */
00210 static void
00211 CONCAT(TABLE,_finalize) (struct TABLE *t)
00212 {
00213   size_t i, j, k;
00214   uint32_t reorder3[t->level3_size];
00215   uint32_t reorder2[t->level2_size];
00216   uint32_t level1_offset, level2_offset, level3_offset, last_offset;
00217 
00218   /* Uniquify level3 blocks.  */
00219   k = 0;
00220   for (j = 0; j < t->level3_size; j++)
00221     {
00222       for (i = 0; i < k; i++)
00223        if (memcmp (&t->level3[i << t->p], &t->level3[j << t->p],
00224                   (1 << t->p) * sizeof (ELEMENT)) == 0)
00225          break;
00226       /* Relocate block j to block i.  */
00227       reorder3[j] = i;
00228       if (i == k)
00229        {
00230          if (i != j)
00231            memcpy (&t->level3[i << t->p], &t->level3[j << t->p],
00232                   (1 << t->p) * sizeof (ELEMENT));
00233          k++;
00234        }
00235     }
00236   t->level3_size = k;
00237 
00238   for (i = 0; i < (t->level2_size << t->q); i++)
00239     if (t->level2[i] != EMPTY)
00240       t->level2[i] = reorder3[t->level2[i]];
00241 
00242   /* Uniquify level2 blocks.  */
00243   k = 0;
00244   for (j = 0; j < t->level2_size; j++)
00245     {
00246       for (i = 0; i < k; i++)
00247        if (memcmp (&t->level2[i << t->q], &t->level2[j << t->q],
00248                   (1 << t->q) * sizeof (uint32_t)) == 0)
00249          break;
00250       /* Relocate block j to block i.  */
00251       reorder2[j] = i;
00252       if (i == k)
00253        {
00254          if (i != j)
00255            memcpy (&t->level2[i << t->q], &t->level2[j << t->q],
00256                   (1 << t->q) * sizeof (uint32_t));
00257          k++;
00258        }
00259     }
00260   t->level2_size = k;
00261 
00262   for (i = 0; i < t->level1_size; i++)
00263     if (t->level1[i] != EMPTY)
00264       t->level1[i] = reorder2[t->level1[i]];
00265 
00266   /* Create and fill the resulting compressed representation.  */
00267   last_offset =
00268     5 * sizeof (uint32_t)
00269     + t->level1_size * sizeof (uint32_t)
00270     + (t->level2_size << t->q) * sizeof (uint32_t)
00271     + (t->level3_size << t->p) * sizeof (ELEMENT);
00272   t->result_size = (last_offset + 3) & ~3ul;
00273   t->result = (char *) xmalloc (t->result_size);
00274 
00275   level1_offset =
00276     5 * sizeof (uint32_t);
00277   level2_offset =
00278     5 * sizeof (uint32_t)
00279     + t->level1_size * sizeof (uint32_t);
00280   level3_offset =
00281     5 * sizeof (uint32_t)
00282     + t->level1_size * sizeof (uint32_t)
00283     + (t->level2_size << t->q) * sizeof (uint32_t);
00284 
00285   ((uint32_t *) t->result)[0] = t->q + t->p;
00286   ((uint32_t *) t->result)[1] = t->level1_size;
00287   ((uint32_t *) t->result)[2] = t->p;
00288   ((uint32_t *) t->result)[3] = (1 << t->q) - 1;
00289   ((uint32_t *) t->result)[4] = (1 << t->p) - 1;
00290 
00291   for (i = 0; i < t->level1_size; i++)
00292     ((uint32_t *) (t->result + level1_offset))[i] =
00293       (t->level1[i] == EMPTY
00294        ? 0
00295        : (t->level1[i] << t->q) * sizeof (uint32_t) + level2_offset);
00296 
00297   for (i = 0; i < (t->level2_size << t->q); i++)
00298     ((uint32_t *) (t->result + level2_offset))[i] =
00299       (t->level2[i] == EMPTY
00300        ? 0
00301        : (t->level2[i] << t->p) * sizeof (ELEMENT) + level3_offset);
00302 
00303   for (i = 0; i < (t->level3_size << t->p); i++)
00304     ((ELEMENT *) (t->result + level3_offset))[i] = t->level3[i];
00305 
00306   if (last_offset < t->result_size)
00307     memset (t->result + last_offset, 0, t->result_size - last_offset);
00308 
00309   if (t->level1_alloc > 0)
00310     free (t->level1);
00311   if (t->level2_alloc > 0)
00312     free (t->level2);
00313   if (t->level3_alloc > 0)
00314     free (t->level3);
00315 }
00316 #endif
00317 
00318 #undef EMPTY
00319 #undef TABLE
00320 #undef ELEMENT
00321 #undef DEFAULT
00322 #undef ITERATE
00323 #undef NO_FINALIZE