lib/gl_array_map.c

   1 /* Map data type implemented by an array.
   2    Copyright (C) 2006-2024 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_map.h"
  22
  23 #include <stdint.h>
  24 #include <stdlib.h>
  25
  26 /* Checked size_t computations.  */
  27 #include "xsize.h"
  28
  29 /* --------------------------- gl_map_t Data Type --------------------------- */
  30
  31 struct pair
  32 {
  33   const void *key;
  34   const void *value;
  35 };
  36
  37 /* Concrete gl_map_impl type, valid for this file only.  */
  38 struct gl_map_impl
  39 {
  40   struct gl_map_impl_base base;
  41   /* An array of ALLOCATED pairs, of which the first COUNT are used.
  42      0 <= COUNT <= ALLOCATED.  */
  43   struct pair *pairs;
  44   size_t count;
  45   size_t allocated;
  46 };
  47
  48 static gl_map_t
  49 gl_array_nx_create_empty (gl_map_implementation_t implementation,
  50                           gl_mapkey_equals_fn equals_fn,
  51                           gl_mapkey_hashcode_fn hashcode_fn,
  52                           gl_mapkey_dispose_fn kdispose_fn,
  53                           gl_mapvalue_dispose_fn vdispose_fn)
  54 {
  55   struct gl_map_impl *map =
  56     (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl));
  57
  58   if (map == NULL)
  59     return NULL;
  60
  61   map->base.vtable = implementation;
  62   map->base.equals_fn = equals_fn;
  63   map->base.kdispose_fn = kdispose_fn;
  64   map->base.vdispose_fn = vdispose_fn;
  65   map->pairs = NULL;
  66   map->count = 0;
  67   map->allocated = 0;
  68
  69   return map;
  70 }
  71
  72 static size_t
  73 gl_array_size (gl_map_t map)
  74 {
  75   return map->count;
  76 }
  77
  78 static size_t
  79 gl_array_indexof (gl_map_t map, const void *key)
  80 {
  81   size_t count = map->count;
  82
  83   if (count > 0)
  84     {
  85       gl_mapkey_equals_fn equals = map->base.equals_fn;
  86       if (equals != NULL)
  87         {
  88           size_t i;
  89
  90           for (i = 0; i < count; i++)
  91             if (equals (map->pairs[i].key, key))
  92               return i;
  93         }
  94       else
  95         {
  96           size_t i;
  97
  98           for (i = 0; i < count; i++)
  99             if (map->pairs[i].key == key)
 100               return i;
 101         }
 102     }
 103   return (size_t)(-1);
 104 }
 105
 106 static bool
 107 gl_array_search (gl_map_t map, const void *key, const void **valuep)
 108 {
 109   size_t index = gl_array_indexof (map, key);
 110   if (index != (size_t)(-1))
 111     {
 112       *valuep = map->pairs[index].value;
 113       return true;
 114     }
 115   else
 116     return false;
 117 }
 118
 119 /* Ensure that map->allocated > map->count.
 120    Return 0 upon success, -1 upon out-of-memory.  */
 121 static int
 122 grow (gl_map_t map)
 123 {
 124   size_t new_allocated;
 125   size_t memory_size;
 126   struct pair *memory;
 127
 128   new_allocated = xtimes (map->allocated, 2);
 129   new_allocated = xsum (new_allocated, 1);
 130   memory_size = xtimes (new_allocated, sizeof (struct pair));
 131   if (size_overflow_p (memory_size))
 132     /* Overflow, would lead to out of memory.  */
 133     return -1;
 134   memory = (struct pair *) realloc (map->pairs, memory_size);
 135   if (memory == NULL)
 136     /* Out of memory.  */
 137     return -1;
 138   map->pairs = memory;
 139   map->allocated = new_allocated;
 140   return 0;
 141 }
 142
 143 static int
 144 gl_array_nx_getput (gl_map_t map, const void *key, const void *value,
 145                     const void **oldvaluep)
 146 {
 147   size_t index = gl_array_indexof (map, key);
 148   if (index != (size_t)(-1))
 149     {
 150       *oldvaluep = map->pairs[index].value;
 151       map->pairs[index].value = value;
 152       return 0;
 153     }
 154   else
 155     {
 156       size_t count = map->count;
 157       struct pair *pairs;
 158
 159       if (count == map->allocated)
 160         if (grow (map) < 0)
 161           return -1;
 162       pairs = map->pairs;
 163       pairs[count].key = key;
 164       pairs[count].value = value;
 165       map->count = count + 1;
 166       return 1;
 167     }
 168 }
 169
 170 /* Remove the pair at the given position,
 171    0 <= position < gl_map_size (map).  */
 172 static void
 173 gl_array_remove_at (gl_map_t map, size_t position)
 174 {
 175   size_t count = map->count;
 176   struct pair *pairs;
 177   size_t i;
 178
 179   pairs = map->pairs;
 180   if (map->base.kdispose_fn != NULL)
 181     map->base.kdispose_fn (pairs[position].key);
 182   for (i = position + 1; i < count; i++)
 183     pairs[i - 1] = pairs[i];
 184   map->count = count - 1;
 185 }
 186
 187 static bool
 188 gl_array_getremove (gl_map_t map, const void *key, const void **oldvaluep)
 189 {
 190   size_t index = gl_array_indexof (map, key);
 191   if (index != (size_t)(-1))
 192     {
 193       *oldvaluep = map->pairs[index].value;
 194       gl_array_remove_at (map, index);
 195       return true;
 196     }
 197   else
 198     return false;
 199 }
 200
 201 static void
 202 gl_array_free (gl_map_t map)
 203 {
 204   if (map->pairs != NULL)
 205     {
 206       if (map->base.kdispose_fn != NULL || map->base.vdispose_fn != NULL)
 207         {
 208           size_t count = map->count;
 209
 210           if (count > 0)
 211             {
 212               gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
 213               gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
 214               struct pair *pairs = map->pairs;
 215
 216               do
 217                 {
 218                   if (vdispose)
 219                     vdispose (pairs->value);
 220                   if (kdispose)
 221                     kdispose (pairs->key);
 222                   pairs++;
 223                 }
 224               while (--count > 0);
 225             }
 226         }
 227       free (map->pairs);
 228     }
 229   free (map);
 230 }
 231
 232 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
 233
 234 static gl_map_iterator_t
 235 gl_array_iterator (gl_map_t map)
 236 {
 237   gl_map_iterator_t result;
 238
 239   result.vtable = map->base.vtable;
 240   result.map = map;
 241   result.count = map->count;
 242   result.p = map->pairs + 0;
 243   result.q = map->pairs + map->count;
 244 #if defined GCC_LINT || defined lint
 245   result.i = 0;
 246   result.j = 0;
 247 #endif
 248
 249   return result;
 250 }
 251
 252 static bool
 253 gl_array_iterator_next (gl_map_iterator_t *iterator,
 254                         const void **keyp, const void **valuep)
 255 {
 256   gl_map_t map = iterator->map;
 257   if (iterator->count != map->count)
 258     {
 259       if (iterator->count != map->count + 1)
 260         /* Concurrent modifications were done on the map.  */
 261         abort ();
 262       /* The last returned pair was removed.  */
 263       iterator->count--;
 264       iterator->p = (struct pair *) iterator->p - 1;
 265       iterator->q = (struct pair *) iterator->q - 1;
 266     }
 267   if (iterator->p < iterator->q)
 268     {
 269       struct pair *p = (struct pair *) iterator->p;
 270       *keyp = p->key;
 271       *valuep = p->value;
 272       iterator->p = p + 1;
 273       return true;
 274     }
 275   else
 276     return false;
 277 }
 278
 279 static void
 280 gl_array_iterator_free (gl_map_iterator_t *iterator)
 281 {
 282 }
 283
 284
 285 const struct gl_map_implementation gl_array_map_implementation =
 286   {
 287     gl_array_nx_create_empty,
 288     gl_array_size,
 289     gl_array_search,
 290     gl_array_nx_getput,
 291     gl_array_getremove,
 292     gl_array_free,
 293     gl_array_iterator,
 294     gl_array_iterator_next,
 295     gl_array_iterator_free
 296   };