lib/gl_array_oset.c

   1 /* Ordered set data type implemented by an array.
   2    Copyright (C) 2006-2007, 2009-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9
  10    This file 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 Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser 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_oset.h"
  22
  23 #include <stdlib.h>
  24
  25 /* Checked size_t computations.  */
  26 #include "xsize.h"
  27
  28 /* -------------------------- gl_oset_t Data Type -------------------------- */
  29
  30 /* Concrete gl_oset_impl type, valid for this file only.  */
  31 struct gl_oset_impl
  32 {
  33   struct gl_oset_impl_base base;
  34   /* An array of ALLOCATED elements, of which the first COUNT are used.
  35      0 <= COUNT <= ALLOCATED.  */
  36   const void **elements;
  37   size_t count;
  38   size_t allocated;
  39 };
  40
  41 static gl_oset_t
  42 gl_array_nx_create_empty (gl_oset_implementation_t implementation,
  43                           gl_setelement_compar_fn compar_fn,
  44                           gl_setelement_dispose_fn dispose_fn)
  45 {
  46   struct gl_oset_impl *set =
  47     (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
  48
  49   if (set == NULL)
  50     return NULL;
  51
  52   set->base.vtable = implementation;
  53   set->base.compar_fn = compar_fn;
  54   set->base.dispose_fn = dispose_fn;
  55   set->elements = NULL;
  56   set->count = 0;
  57   set->allocated = 0;
  58
  59   return set;
  60 }
  61
  62 static size_t _GL_ATTRIBUTE_PURE
  63 gl_array_size (gl_oset_t set)
  64 {
  65   return set->count;
  66 }
  67
  68 static size_t _GL_ATTRIBUTE_PURE
  69 gl_array_indexof (gl_oset_t set, const void *elt)
  70 {
  71   size_t count = set->count;
  72
  73   if (count > 0)
  74     {
  75       gl_setelement_compar_fn compar = set->base.compar_fn;
  76       size_t low = 0;
  77       size_t high = count;
  78
  79       /* At each loop iteration, low < high; for indices < low the values
  80          are smaller than ELT; for indices >= high the values are greater
  81          than ELT.  So, if the element occurs in the list, it is at
  82          low <= position < high.  */
  83       do
  84         {
  85           size_t mid = low + (high - low) / 2; /* low <= mid < high */
  86           int cmp = (compar != NULL
  87                      ? compar (set->elements[mid], elt)
  88                      : (set->elements[mid] > elt ? 1 :
  89                         set->elements[mid] < elt ? -1 : 0));
  90
  91           if (cmp < 0)
  92             low = mid + 1;
  93           else if (cmp > 0)
  94             high = mid;
  95           else /* cmp == 0 */
  96             /* We have an element equal to ELT at index MID.  */
  97             return mid;
  98         }
  99       while (low < high);
 100     }
 101   return (size_t)(-1);
 102 }
 103
 104 static bool _GL_ATTRIBUTE_PURE
 105 gl_array_search (gl_oset_t set, const void *elt)
 106 {
 107   return gl_array_indexof (set, elt) != (size_t)(-1);
 108 }
 109
 110 /* Searches the least element in the ordered set that compares greater or equal
 111    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 112    by the THRESHOLD_FN.
 113    Returns the position at which it was found, or gl_list_size (SET) if not
 114    found.  */
 115 static size_t _GL_ATTRIBUTE_PURE
 116 gl_array_indexof_atleast (gl_oset_t set,
 117                           gl_setelement_threshold_fn threshold_fn,
 118                           const void *threshold)
 119 {
 120   size_t count = set->count;
 121
 122   if (count > 0)
 123     {
 124       size_t low = 0;
 125       size_t high = count;
 126
 127       /* At each loop iteration, low < high; for indices < low the values are
 128          smaller than THRESHOLD; for indices >= high the values are nonexistent.
 129          So, if an element >= THRESHOLD occurs in the list, it is at
 130          low <= position < high.  */
 131       do
 132         {
 133           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 134
 135           if (! threshold_fn (set->elements[mid], threshold))
 136             low = mid + 1;
 137           else
 138             {
 139               /* We have an element >= THRESHOLD at index MID.  But we need the
 140                  minimal such index.  */
 141               high = mid;
 142               /* At each loop iteration, low <= high and
 143                    compar (set->elements[high], threshold) >= 0,
 144                  and we know that the first occurrence of the element is at
 145                  low <= position <= high.  */
 146               while (low < high)
 147                 {
 148                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 149
 150                   if (! threshold_fn (set->elements[mid2], threshold))
 151                     low = mid2 + 1;
 152                   else
 153                     high = mid2;
 154                 }
 155               return low;
 156             }
 157         }
 158       while (low < high);
 159     }
 160   return count;
 161 }
 162
 163 static bool _GL_ATTRIBUTE_PURE
 164 gl_array_search_atleast (gl_oset_t set,
 165                          gl_setelement_threshold_fn threshold_fn,
 166                          const void *threshold,
 167                          const void **eltp)
 168 {
 169   size_t index = gl_array_indexof_atleast (set, threshold_fn, threshold);
 170
 171   if (index == set->count)
 172     return false;
 173   else
 174     {
 175       *eltp = set->elements[index];
 176       return true;
 177     }
 178 }
 179
 180 /* Ensure that set->allocated > set->count.
 181    Return 0 upon success, -1 upon out-of-memory.  */
 182 static int
 183 grow (gl_oset_t set)
 184 {
 185   size_t new_allocated;
 186   size_t memory_size;
 187   const void **memory;
 188
 189   new_allocated = xtimes (set->allocated, 2);
 190   new_allocated = xsum (new_allocated, 1);
 191   memory_size = xtimes (new_allocated, sizeof (const void *));
 192   if (size_overflow_p (memory_size))
 193     /* Overflow, would lead to out of memory.  */
 194     return -1;
 195   memory = (const void **) realloc (set->elements, memory_size);
 196   if (memory == NULL)
 197     /* Out of memory.  */
 198     return -1;
 199   set->elements = memory;
 200   set->allocated = new_allocated;
 201   return 0;
 202 }
 203
 204 /* Add the given element ELT at the given position,
 205    0 <= position <= gl_oset_size (set).
 206    Return 1 upon success, -1 upon out-of-memory.  */
 207 static int
 208 gl_array_nx_add_at (gl_oset_t set, size_t position, const void *elt)
 209 {
 210   size_t count = set->count;
 211   const void **elements;
 212   size_t i;
 213
 214   if (count == set->allocated)
 215     if (grow (set) < 0)
 216       return -1;
 217   elements = set->elements;
 218   for (i = count; i > position; i--)
 219     elements[i] = elements[i - 1];
 220   elements[position] = elt;
 221   set->count = count + 1;
 222   return 1;
 223 }
 224
 225 /* Remove the element at the given position,
 226    0 <= position < gl_oset_size (set).  */
 227 static void
 228 gl_array_remove_at (gl_oset_t set, size_t position)
 229 {
 230   size_t count = set->count;
 231   const void **elements;
 232   size_t i;
 233
 234   elements = set->elements;
 235   if (set->base.dispose_fn != NULL)
 236     set->base.dispose_fn (elements[position]);
 237   for (i = position + 1; i < count; i++)
 238     elements[i - 1] = elements[i];
 239   set->count = count - 1;
 240 }
 241
 242 static int
 243 gl_array_nx_add (gl_oset_t set, const void *elt)
 244 {
 245   size_t count = set->count;
 246   size_t low = 0;
 247
 248   if (count > 0)
 249     {
 250       gl_setelement_compar_fn compar = set->base.compar_fn;
 251       size_t high = count;
 252
 253       /* At each loop iteration, low < high; for indices < low the values
 254          are smaller than ELT; for indices >= high the values are greater
 255          than ELT.  So, if the element occurs in the list, it is at
 256          low <= position < high.  */
 257       do
 258         {
 259           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 260           int cmp = (compar != NULL
 261                      ? compar (set->elements[mid], elt)
 262                      : (set->elements[mid] > elt ? 1 :
 263                         set->elements[mid] < elt ? -1 : 0));
 264
 265           if (cmp < 0)
 266             low = mid + 1;
 267           else if (cmp > 0)
 268             high = mid;
 269           else /* cmp == 0 */
 270             return false;
 271         }
 272       while (low < high);
 273     }
 274   return gl_array_nx_add_at (set, low, elt);
 275 }
 276
 277 static bool
 278 gl_array_remove (gl_oset_t set, const void *elt)
 279 {
 280   size_t index = gl_array_indexof (set, elt);
 281   if (index != (size_t)(-1))
 282     {
 283       gl_array_remove_at (set, index);
 284       return true;
 285     }
 286   else
 287     return false;
 288 }
 289
 290 static int
 291 gl_array_update (gl_oset_t set, const void *elt,
 292                  void (*action) (const void * /*elt*/, void * /*action_data*/),
 293                  void *action_data)
 294 {
 295   /* Like gl_array_remove, action (...), gl_array_nx_add, except that we don't
 296      actually remove ELT.  */
 297   /* Remember the old position.  */
 298   size_t old_index = gl_array_indexof (set, elt);
 299   /* Invoke ACTION.  */
 300   action (elt, action_data);
 301   /* Determine the new position.  */
 302   if (old_index != (size_t)(-1))
 303     {
 304       size_t count = set->count;
 305
 306       if (count > 1)
 307         {
 308           gl_setelement_compar_fn compar = set->base.compar_fn;
 309           size_t low;
 310           size_t high;
 311
 312           if (old_index > 0)
 313             {
 314               size_t mid = old_index - 1;
 315               int cmp = (compar != NULL
 316                          ? compar (set->elements[mid], elt)
 317                          : (set->elements[mid] > elt ? 1 :
 318                             set->elements[mid] < elt ? -1 : 0));
 319               if (cmp < 0)
 320                 {
 321                   low = old_index + 1;
 322                   high = count;
 323                 }
 324               else if (cmp > 0)
 325                 {
 326                   low = 0;
 327                   high = mid;
 328                 }
 329               else /* cmp == 0 */
 330                 {
 331                   /* Two adjacent elements are the same.  */
 332                   gl_array_remove_at (set, old_index);
 333                   return -1;
 334                 }
 335             }
 336           else
 337             {
 338               low = old_index + 1;
 339               high = count;
 340             }
 341
 342           /* At each loop iteration, low <= high; for indices < low the values
 343              are smaller than ELT; for indices >= high the values are greater
 344              than ELT.  So, if the element occurs in the list, it is at
 345              low <= position < high.  */
 346           while (low < high)
 347             {
 348               size_t mid = low + (high - low) / 2; /* low <= mid < high */
 349               int cmp = (compar != NULL
 350                          ? compar (set->elements[mid], elt)
 351                          : (set->elements[mid] > elt ? 1 :
 352                             set->elements[mid] < elt ? -1 : 0));
 353
 354               if (cmp < 0)
 355                 low = mid + 1;
 356               else if (cmp > 0)
 357                 high = mid;
 358               else /* cmp == 0 */
 359                 {
 360                   /* Two elements are the same.  */
 361                   gl_array_remove_at (set, old_index);
 362                   return -1;
 363                 }
 364             }
 365
 366           if (low < old_index)
 367             {
 368               /* Move the element from old_index to low.  */
 369               size_t new_index = low;
 370               const void **elements = set->elements;
 371               size_t i;
 372
 373               for (i = old_index; i > new_index; i--)
 374                 elements[i] = elements[i - 1];
 375               elements[new_index] = elt;
 376               return true;
 377             }
 378           else
 379             {
 380               /* low > old_index.  */
 381               /* Move the element from old_index to low - 1.  */
 382               size_t new_index = low - 1;
 383
 384               if (new_index > old_index)
 385                 {
 386                   const void **elements = set->elements;
 387                   size_t i;
 388
 389                   for (i = old_index; i < new_index; i++)
 390                     elements[i] = elements[i + 1];
 391                   elements[new_index] = elt;
 392                   return true;
 393                 }
 394             }
 395         }
 396     }
 397   return false;
 398 }
 399
 400 static void
 401 gl_array_free (gl_oset_t set)
 402 {
 403   if (set->elements != NULL)
 404     {
 405       if (set->base.dispose_fn != NULL)
 406         {
 407           size_t count = set->count;
 408
 409           if (count > 0)
 410             {
 411               gl_setelement_dispose_fn dispose = set->base.dispose_fn;
 412               const void **elements = set->elements;
 413
 414               do
 415                 dispose (*elements++);
 416               while (--count > 0);
 417             }
 418         }
 419       free (set->elements);
 420     }
 421   free (set);
 422 }
 423
 424 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 425
 426 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
 427 gl_array_iterator (gl_oset_t set)
 428 {
 429   gl_oset_iterator_t result;
 430
 431   result.vtable = set->base.vtable;
 432   result.set = set;
 433   result.count = set->count;
 434   result.p = set->elements + 0;
 435   result.q = set->elements + set->count;
 436 #if defined GCC_LINT || defined lint
 437   result.i = 0;
 438   result.j = 0;
 439 #endif
 440
 441   return result;
 442 }
 443
 444 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
 445 gl_array_iterator_atleast (gl_oset_t set,
 446                            gl_setelement_threshold_fn threshold_fn,
 447                            const void *threshold)
 448 {
 449   size_t index = gl_array_indexof_atleast (set, threshold_fn, threshold);
 450   gl_oset_iterator_t result;
 451
 452   result.vtable = set->base.vtable;
 453   result.set = set;
 454   result.count = set->count;
 455   result.p = set->elements + index;
 456   result.q = set->elements + set->count;
 457 #if defined GCC_LINT || defined lint
 458   result.i = 0;
 459   result.j = 0;
 460 #endif
 461
 462   return result;
 463 }
 464
 465 static bool
 466 gl_array_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 467 {
 468   gl_oset_t set = iterator->set;
 469   if (iterator->count != set->count)
 470     {
 471       if (iterator->count != set->count + 1)
 472         /* Concurrent modifications were done on the set.  */
 473         abort ();
 474       /* The last returned element was removed.  */
 475       iterator->count--;
 476       iterator->p = (const void **) iterator->p - 1;
 477       iterator->q = (const void **) iterator->q - 1;
 478     }
 479   if (iterator->p < iterator->q)
 480     {
 481       const void **p = (const void **) iterator->p;
 482       *eltp = *p;
 483       iterator->p = p + 1;
 484       return true;
 485     }
 486   else
 487     return false;
 488 }
 489
 490 static void
 491 gl_array_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_oset_iterator_t *iterator)
 492 {
 493 }
 494
 495
 496 const struct gl_oset_implementation gl_array_oset_implementation =
 497   {
 498     gl_array_nx_create_empty,
 499     gl_array_size,
 500     gl_array_search,
 501     gl_array_search_atleast,
 502     gl_array_nx_add,
 503     gl_array_remove,
 504     gl_array_update,
 505     gl_array_free,
 506     gl_array_iterator,
 507     gl_array_iterator_atleast,
 508     gl_array_iterator_next,
 509     gl_array_iterator_free
 510   };