lib/gl_array_omap.c

   1 /* Ordered map data type implemented by an array.
   2    Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2018.
   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 by
   7    the Free Software Foundation; either version 3 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 <https://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 /* Specification.  */
  21 #include "gl_array_omap.h"
  22
  23 #include <stdlib.h>
  24
  25 /* Checked size_t computations.  */
  26 #include "xsize.h"
  27
  28 /* -------------------------- gl_omap_t Data Type -------------------------- */
  29
  30 struct pair
  31 {
  32   const void *key;
  33   const void *value;
  34 };
  35
  36 /* Concrete gl_omap_impl type, valid for this file only.  */
  37 struct gl_omap_impl
  38 {
  39   struct gl_omap_impl_base base;
  40   /* An array of ALLOCATED pairs, of which the first COUNT are used.
  41      0 <= COUNT <= ALLOCATED.  */
  42   struct pair *pairs;
  43   size_t count;
  44   size_t allocated;
  45 };
  46
  47 static gl_omap_t
  48 gl_array_nx_create_empty (gl_omap_implementation_t implementation,
  49                           gl_mapkey_compar_fn compar_fn,
  50                           gl_mapkey_dispose_fn kdispose_fn,
  51                           gl_mapvalue_dispose_fn vdispose_fn)
  52 {
  53   struct gl_omap_impl *map =
  54     (struct gl_omap_impl *) malloc (sizeof (struct gl_omap_impl));
  55
  56   if (map == NULL)
  57     return NULL;
  58
  59   map->base.vtable = implementation;
  60   map->base.compar_fn = compar_fn;
  61   map->base.kdispose_fn = kdispose_fn;
  62   map->base.vdispose_fn = vdispose_fn;
  63   map->pairs = NULL;
  64   map->count = 0;
  65   map->allocated = 0;
  66
  67   return map;
  68 }
  69
  70 static size_t _GL_ATTRIBUTE_PURE
  71 gl_array_size (gl_omap_t map)
  72 {
  73   return map->count;
  74 }
  75
  76 static size_t _GL_ATTRIBUTE_PURE
  77 gl_array_indexof (gl_omap_t map, const void *key)
  78 {
  79   size_t count = map->count;
  80
  81   if (count > 0)
  82     {
  83       gl_mapkey_compar_fn compar = map->base.compar_fn;
  84       size_t low = 0;
  85       size_t high = count;
  86
  87       /* At each loop iteration, low < high; for indices < low the values
  88          are smaller than KEY; for indices >= high the values are greater
  89          than KEY.  So, if the key occurs in the map, it is at
  90          low <= position < high.  */
  91       do
  92         {
  93           size_t mid = low + (high - low) / 2; /* low <= mid < high */
  94           int cmp = (compar != NULL
  95                      ? compar (map->pairs[mid].key, key)
  96                      : (map->pairs[mid].key > key ? 1 :
  97                         map->pairs[mid].key < key ? -1 : 0));
  98
  99           if (cmp < 0)
 100             low = mid + 1;
 101           else if (cmp > 0)
 102             high = mid;
 103           else /* cmp == 0 */
 104             /* We have a key equal to KEY at index MID.  */
 105             return mid;
 106         }
 107       while (low < high);
 108     }
 109   return (size_t)(-1);
 110 }
 111
 112 static bool _GL_ATTRIBUTE_PURE
 113 gl_array_search (gl_omap_t map, const void *key, const void **valuep)
 114 {
 115   size_t index = gl_array_indexof (map, key);
 116   if (index != (size_t)(-1))
 117     {
 118       *valuep = map->pairs[index].value;
 119       return true;
 120     }
 121   else
 122     return false;
 123 }
 124
 125 static bool _GL_ATTRIBUTE_PURE
 126 gl_array_search_atleast (gl_omap_t map,
 127                          gl_mapkey_threshold_fn threshold_fn,
 128                          const void *threshold,
 129                          const void **keyp, const void **valuep)
 130 {
 131   size_t count = map->count;
 132
 133   if (count > 0)
 134     {
 135       size_t low = 0;
 136       size_t high = count;
 137
 138       /* At each loop iteration, low < high; for indices < low the values are
 139          smaller than THRESHOLD; for indices >= high the values are nonexistent.
 140          So, if a key >= THRESHOLD occurs in the map, it is at
 141          low <= position < high.  */
 142       do
 143         {
 144           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 145
 146           if (! threshold_fn (map->pairs[mid].key, threshold))
 147             low = mid + 1;
 148           else
 149             {
 150               /* We have a key >= THRESHOLD at index MID.  But we need the
 151                  minimal such index.  */
 152               high = mid;
 153               /* At each loop iteration, low <= high and
 154                    compar (map->pairs[high].key, value) >= 0,
 155                  and we know that the first occurrence of the key is at
 156                  low <= position <= high.  */
 157               while (low < high)
 158                 {
 159                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 160
 161                   if (! threshold_fn (map->pairs[mid2].key, threshold))
 162                     low = mid2 + 1;
 163                   else
 164                     high = mid2;
 165                 }
 166               *keyp = map->pairs[low].key;
 167               *valuep = map->pairs[low].value;
 168               return true;
 169             }
 170         }
 171       while (low < high);
 172     }
 173   return false;
 174 }
 175
 176 /* Ensure that map->allocated > map->count.
 177    Return 0 upon success, -1 upon out-of-memory.  */
 178 static int
 179 grow (gl_omap_t map)
 180 {
 181   size_t new_allocated;
 182   size_t memory_size;
 183   struct pair *memory;
 184
 185   new_allocated = xtimes (map->allocated, 2);
 186   new_allocated = xsum (new_allocated, 1);
 187   memory_size = xtimes (new_allocated, sizeof (struct pair));
 188   if (size_overflow_p (memory_size))
 189     /* Overflow, would lead to out of memory.  */
 190     return -1;
 191   memory = (struct pair *) realloc (map->pairs, memory_size);
 192   if (memory == NULL)
 193     /* Out of memory.  */
 194     return -1;
 195   map->pairs = memory;
 196   map->allocated = new_allocated;
 197   return 0;
 198 }
 199
 200 /* Add the given pair (KEY, VALUE) at the given position,
 201    0 <= position <= gl_omap_size (map).
 202    Return 1 upon success, -1 upon out-of-memory.  */
 203 static int
 204 gl_array_nx_add_at (gl_omap_t map, size_t position,
 205                     const void *key, const void *value)
 206 {
 207   size_t count = map->count;
 208   struct pair *pairs;
 209   size_t i;
 210
 211   if (count == map->allocated)
 212     if (grow (map) < 0)
 213       return -1;
 214   pairs = map->pairs;
 215   for (i = count; i > position; i--)
 216     pairs[i] = pairs[i - 1];
 217   pairs[position].key = key;
 218   pairs[position].value = value;
 219   map->count = count + 1;
 220   return 1;
 221 }
 222
 223 static int
 224 gl_array_nx_getput (gl_omap_t map, const void *key, const void *value,
 225                     const void **oldvaluep)
 226 {
 227   size_t count = map->count;
 228   size_t low = 0;
 229
 230   if (count > 0)
 231     {
 232       gl_mapkey_compar_fn compar = map->base.compar_fn;
 233       size_t high = count;
 234
 235       /* At each loop iteration, low < high; for indices < low the keys
 236          are smaller than KEY; for indices >= high the keys are greater
 237          than KEY.  So, if the key occurs in the map, it is at
 238          low <= position < high.  */
 239       do
 240         {
 241           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 242           int cmp = (compar != NULL
 243                      ? compar (map->pairs[mid].key, key)
 244                      : (map->pairs[mid].key > key ? 1 :
 245                         map->pairs[mid].key < key ? -1 : 0));
 246
 247           if (cmp < 0)
 248             low = mid + 1;
 249           else if (cmp > 0)
 250             high = mid;
 251           else /* cmp == 0 */
 252             {
 253               *oldvaluep = map->pairs[mid].value;
 254               map->pairs[mid].value = value;
 255               return 0;
 256             }
 257         }
 258       while (low < high);
 259     }
 260   return gl_array_nx_add_at (map, low, key, value);
 261 }
 262
 263 /* Remove the pair at the given position,
 264    0 <= position < gl_omap_size (map).  */
 265 static void
 266 gl_array_remove_at (gl_omap_t map, size_t position)
 267 {
 268   size_t count = map->count;
 269   struct pair *pairs;
 270   size_t i;
 271
 272   pairs = map->pairs;
 273   if (map->base.kdispose_fn != NULL)
 274     map->base.kdispose_fn (pairs[position].key);
 275   for (i = position + 1; i < count; i++)
 276     pairs[i - 1] = pairs[i];
 277   map->count = count - 1;
 278 }
 279
 280 static bool
 281 gl_array_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
 282 {
 283   size_t index = gl_array_indexof (map, key);
 284   if (index != (size_t)(-1))
 285     {
 286       *oldvaluep = map->pairs[index].value;
 287       gl_array_remove_at (map, index);
 288       return true;
 289     }
 290   else
 291     return false;
 292 }
 293
 294 static void
 295 gl_array_free (gl_omap_t map)
 296 {
 297   if (map->pairs != NULL)
 298     {
 299       if (map->base.kdispose_fn != NULL || map->base.vdispose_fn != NULL)
 300         {
 301           size_t count = map->count;
 302
 303           if (count > 0)
 304             {
 305               gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
 306               gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
 307               struct pair *pairs = map->pairs;
 308
 309               do
 310                 {
 311                   if (vdispose)
 312                     vdispose (pairs->value);
 313                   if (kdispose)
 314                     kdispose (pairs->key);
 315                   pairs++;
 316                 }
 317               while (--count > 0);
 318             }
 319         }
 320       free (map->pairs);
 321     }
 322   free (map);
 323 }
 324
 325 /* ---------------------- gl_omap_iterator_t Data Type ---------------------- */
 326
 327 static gl_omap_iterator_t _GL_ATTRIBUTE_PURE
 328 gl_array_iterator (gl_omap_t map)
 329 {
 330   gl_omap_iterator_t result;
 331
 332   result.vtable = map->base.vtable;
 333   result.map = map;
 334   result.count = map->count;
 335   result.p = map->pairs + 0;
 336   result.q = map->pairs + map->count;
 337 #if defined GCC_LINT || defined lint
 338   result.i = 0;
 339   result.j = 0;
 340 #endif
 341
 342   return result;
 343 }
 344
 345 static bool
 346 gl_array_iterator_next (gl_omap_iterator_t *iterator,
 347                         const void **keyp, const void **valuep)
 348 {
 349   gl_omap_t map = iterator->map;
 350   if (iterator->count != map->count)
 351     {
 352       if (iterator->count != map->count + 1)
 353         /* Concurrent modifications were done on the map.  */
 354         abort ();
 355       /* The last returned pair was removed.  */
 356       iterator->count--;
 357       iterator->p = (struct pair *) iterator->p - 1;
 358       iterator->q = (struct pair *) iterator->q - 1;
 359     }
 360   if (iterator->p < iterator->q)
 361     {
 362       struct pair *p = (struct pair *) iterator->p;
 363       *keyp = p->key;
 364       *valuep = p->value;
 365       iterator->p = p + 1;
 366       return true;
 367     }
 368   else
 369     return false;
 370 }
 371
 372 static void
 373 gl_array_iterator_free (gl_omap_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
 374 {
 375 }
 376
 377
 378 const struct gl_omap_implementation gl_array_omap_implementation =
 379   {
 380     gl_array_nx_create_empty,
 381     gl_array_size,
 382     gl_array_search,
 383     gl_array_search_atleast,
 384     gl_array_nx_getput,
 385     gl_array_getremove,
 386     gl_array_free,
 387     gl_array_iterator,
 388     gl_array_iterator_next,
 389     gl_array_iterator_free
 390   };