text: /* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
  /*
   * lsquic_set.c -- A set implementation.
   *
   * Deleting from a set is not supported.  Implemented as a sorted array.
   * Optimized for reading.  Insertion may trigger realloc, memmove, or
   * both.
   */
  
  #include <assert.h>
  #include <errno.h>
  #include <limits.h>
  #include <stdlib.h>
  #include <string.h>
  
  #include "lsquic_set.h"
  
  
  struct lsquic_set32_elem
  {
      uint32_t   low, high;
  };
  
  
  void
  lsquic_set32_init (struct lsquic_set32 *set)
  {
      memset(set, 0, sizeof(*set));
  }
  
  
  void
  lsquic_set32_cleanup (struct lsquic_set32 *set)
  {
      free(set->elems);
  }
  
  
  static int
  lsquic_set32_insert_set_elem (struct lsquic_set32 *set, int i, uint32_t value)
  {
      struct lsquic_set32_elem *elems;
  
      if (set->n_elems == INT_MAX)
      {
          errno = EOVERFLOW;
          return -1;
      }
  
      if (set->n_alloc == set->n_elems)
      {
          if (set->n_alloc)
              set->n_alloc *= 2;
          else
              set->n_alloc = 4;
          elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
          if (!elems)
              return -1;
          set->elems = elems;
      }
      if (i < set->n_elems)
          memmove(&set->elems[i + 1], &set->elems[i],
                                      (set->n_elems - i) * sizeof(set->elems[i]));
      set->elems[i].low = set->elems[i].high = value;
      ++set->n_elems;
      return 0;
  }
  
  
  static void
  lsquic_set32_merge_set_elems (struct lsquic_set32 *set, int i)
  {
      assert(i >= 0);
      assert(i < set->n_elems - 1);
      assert(set->elems[i].high + 1 == set->elems[i + 1].low);
      set->elems[i].high = set->elems[i + 1].high;
      if (i < set->n_elems - 2)
          memmove(&set->elems[i + 1], &set->elems[i + 2],
                                  (set->n_elems - i - 2) * sizeof(set->elems[i]));
      --set->n_elems;
  }
  
  
  #ifndef NDEBUG
  static void
  lsquic_set32_check_elems_sorted (const struct lsquic_set32 *set)
  {
      int i;
      for (i = 0; i < set->n_elems; ++i)
      {
          assert(set->elems[i].low <= set->elems[i].high);
          if (i > 0)
              assert(set->elems[i - 1].high + 1 < set->elems[i].low);
      }
  }
  #endif
  
  
  int
  lsquic_set32_add (struct lsquic_set32 *set, uint32_t value)
  {
      if (value < 64)
      {
          set->lowset |= 1ULL << value;
          return 0;
      }
  
      int low, high, i;
  
      if (set->n_elems > 0)
      {
          low = 0, high = set->n_elems - 1;
          do
          {
              i = low + (high - low) / 2;
              if (set->elems[i].low <= value && set->elems[i].high >= value)
                  return 0;
              else if (set->elems[i].high < value)
                  low = i + 1;
              else
                  high = i - 1;
          }
          while (low <= high);
  
          if (value < set->elems[i].low)
          {
              if (set->elems[i].low - 1 == value)
              {
                  set->elems[i].low = value;
                  if (i > 0 && set->elems[i - 1].high + 1 == value)
                      lsquic_set32_merge_set_elems(set, i - 1);
              }
              else if (i > 0 && set->elems[i - 1].high + 1 == value)
                  set->elems[i - 1].high = value;
              else if (0 != lsquic_set32_insert_set_elem(set, i, value))
                  return -1;
          }
          else
          {
              assert(value > set->elems[i].high);
              if (set->elems[i].high + 1 == value)
              {
                  set->elems[i].high = value;
                  if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
                      lsquic_set32_merge_set_elems(set, i);
              }
              else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
                  set->elems[i + 1].low = value;
              else if (0 != lsquic_set32_insert_set_elem(set, i + 1, value))
                  return 0;
          }
      }
      else
      {
          assert(NULL == set->elems);
          if (0 != lsquic_set32_insert_set_elem(set, 0, value))
              return -1;
      }
  #ifndef NDEBUG
      lsquic_set32_check_elems_sorted(set);
  #endif
      return 0;
  }
  
  
  int
  lsquic_set32_has (const struct lsquic_set32 *set, uint32_t value)
  {
      if (value < 64)
      {
          return !!(set->lowset & (1ULL << value));
      }
  
      int low, high, i;
  
      low = 0, high = set->n_elems - 1;
      while (low <= high)
      {
          i = low + (high - low) / 2;
          if (set->elems[i].low <= value && set->elems[i].high >= value)
              return 1;
          else if (set->elems[i].high < value)
              low = i + 1;
          else
              high = i - 1;
      }
  
      return 0;
  }
  
  
  /* ******* ******* ******** *******
   *
   * The following code is a set of two replacements:
   *
   * :.,$s/lsquic_set32/lsquic_set64/g
   * :.,$s/uint32_t/uint64_t/g
   */
  struct lsquic_set64_elem
  {
      uint64_t   low, high;
  };
  
  
  void
  lsquic_set64_init (struct lsquic_set64 *set)
  {
      memset(set, 0, sizeof(*set));
  }
  
  
  void
  lsquic_set64_cleanup (struct lsquic_set64 *set)
  {
      free(set->elems);
  }
  
  
  static int
  lsquic_set64_insert_set_elem (struct lsquic_set64 *set, int i, uint64_t value)
  {
      struct lsquic_set64_elem *elems;
  
      if (set->n_elems == INT_MAX)
      {
          errno = EOVERFLOW;
          return -1;
      }
  
      if (set->n_alloc == set->n_elems)
      {
          if (set->n_alloc)
              set->n_alloc *= 2;
          else
              set->n_alloc = 4;
          elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
          if (!elems)
              return -1;
          set->elems = elems;
      }
      if (i < set->n_elems)
          memmove(&set->elems[i + 1], &set->elems[i],
                                      (set->n_elems - i) * sizeof(set->elems[i]));
      set->elems[i].low = set->elems[i].high = value;
      ++set->n_elems;
      return 0;
  }
  
  
  static void
  lsquic_set64_merge_set_elems (struct lsquic_set64 *set, int i)
  {
      assert(i >= 0);
      assert(i < set->n_elems - 1);
      assert(set->elems[i].high + 1 == set->elems[i + 1].low);
      set->elems[i].high = set->elems[i + 1].high;
      if (i < set->n_elems - 2)
          memmove(&set->elems[i + 1], &set->elems[i + 2],
                                  (set->n_elems - i - 2) * sizeof(set->elems[i]));
      --set->n_elems;
  }
  
  
  #ifndef NDEBUG
  static void
  lsquic_set64_check_elems_sorted (const struct lsquic_set64 *set)
  {
      int i;
      for (i = 0; i < set->n_elems; ++i)
      {
          assert(set->elems[i].low <= set->elems[i].high);
          if (i > 0)
              assert(set->elems[i - 1].high + 1 < set->elems[i].low);
      }
  }
  #endif
  
  
  int
  lsquic_set64_add (struct lsquic_set64 *set, uint64_t value)
  {
      if (value < 64)
      {
          set->lowset |= 1ULL << value;
          return 0;
      }
  
      int low, high, i;
  
      if (set->n_elems > 0)
      {
          low = 0, high = set->n_elems - 1;
          do
          {
              i = low + (high - low) / 2;
              if (set->elems[i].low <= value && set->elems[i].high >= value)
                  return 0;
              else if (set->elems[i].high < value)
                  low = i + 1;
              else
                  high = i - 1;
          }
          while (low <= high);
  
          if (value < set->elems[i].low)
          {
              if (set->elems[i].low - 1 == value)
              {
                  set->elems[i].low = value;
                  if (i > 0 && set->elems[i - 1].high + 1 == value)
                      lsquic_set64_merge_set_elems(set, i - 1);
              }
              else if (i > 0 && set->elems[i - 1].high + 1 == value)
                  set->elems[i - 1].high = value;
              else if (0 != lsquic_set64_insert_set_elem(set, i, value))
                  return -1;
          }
          else
          {
              assert(value > set->elems[i].high);
              if (set->elems[i].high + 1 == value)
              {
                  set->elems[i].high = value;
                  if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
                      lsquic_set64_merge_set_elems(set, i);
              }
              else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
                  set->elems[i + 1].low = value;
              else if (0 != lsquic_set64_insert_set_elem(set, i + 1, value))
                  return 0;
          }
      }
      else
      {
          assert(NULL == set->elems);
          if (0 != lsquic_set64_insert_set_elem(set, 0, value))
              return -1;
      }
  #ifndef NDEBUG
      lsquic_set64_check_elems_sorted(set);
  #endif
      return 0;
  }
  
  
  int
  lsquic_set64_has (const struct lsquic_set64 *set, uint64_t value)
  {
      if (value < 64)
      {
          return !!(set->lowset & (1ULL << value));
      }
  
      int low, high, i;
  
      low = 0, high = set->n_elems - 1;
      while (low <= high)
      {
          i = low + (high - low) / 2;
          if (set->elems[i].low <= value && set->elems[i].high >= value)
              return 1;
          else if (set->elems[i].high < value)
              low = i + 1;
          else
              high = i - 1;
      }
  
      return 0;
  }
  
  
  