quickjs-tart

ares_slist.c (11239B)

---

 /* MIT License
  *
  * Copyright (c) 2023 Brad House
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
  * in the Software without restriction, including without limitation the rights
  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  * copies of the Software, and to permit persons to whom the Software is
  * furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice (including the next
  * paragraph) shall be included in all copies or substantial portions of the
  * Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  *
  * SPDX-License-Identifier: MIT
  */
 #include "ares_private.h"
 #include "ares_slist.h"
 
 /* SkipList implementation */
 
 #define ARES__SLIST_START_LEVELS 4
 
 struct ares_slist {
   ares_rand_state        *rand_state;
   unsigned char           rand_data[8];
   size_t                  rand_bits;
 
   ares_slist_node_t     **head;
   size_t                  levels;
   ares_slist_node_t      *tail;
 
   ares_slist_cmp_t        cmp;
   ares_slist_destructor_t destruct;
   size_t                  cnt;
 };
 
 struct ares_slist_node {
   void               *data;
   ares_slist_node_t **prev;
   ares_slist_node_t **next;
   size_t              levels;
   ares_slist_t       *parent;
 };
 
 ares_slist_t *ares_slist_create(ares_rand_state        *rand_state,
                                 ares_slist_cmp_t        cmp,
                                 ares_slist_destructor_t destruct)
 {
   ares_slist_t *list;
 
   if (rand_state == NULL || cmp == NULL) {
     return NULL;
   }
 
   list = ares_malloc_zero(sizeof(*list));
 
   if (list == NULL) {
     return NULL;
   }
 
   list->rand_state = rand_state;
   list->cmp        = cmp;
   list->destruct   = destruct;
 
   list->levels = ARES__SLIST_START_LEVELS;
   list->head   = ares_malloc_zero(sizeof(*list->head) * list->levels);
   if (list->head == NULL) {
     ares_free(list);
     return NULL;
   }
 
   return list;
 }
 
 static ares_bool_t ares_slist_coin_flip(ares_slist_t *list)
 {
   size_t total_bits = sizeof(list->rand_data) * 8;
   size_t bit;
 
   /* Refill random data used for coin flips.  We pull this in 8 byte chunks.
    * ares_rand_bytes() has some built-in caching of its own so we don't need
    * to be excessive in caching ourselves.  Prefer to require less memory per
    * skiplist */
   if (list->rand_bits == 0) {
     ares_rand_bytes(list->rand_state, list->rand_data, sizeof(list->rand_data));
     list->rand_bits = total_bits;
   }
 
   bit = total_bits - list->rand_bits;
   list->rand_bits--;
 
   return (list->rand_data[bit / 8] & (1 << (bit % 8))) ? ARES_TRUE : ARES_FALSE;
 }
 
 void ares_slist_replace_destructor(ares_slist_t           *list,
                                    ares_slist_destructor_t destruct)
 {
   if (list == NULL) {
     return;
   }
 
   list->destruct = destruct;
 }
 
 static size_t ares_slist_max_level(const ares_slist_t *list)
 {
   size_t max_level = 0;
 
   if (list->cnt + 1 <= (1 << ARES__SLIST_START_LEVELS)) {
     max_level = ARES__SLIST_START_LEVELS;
   } else {
     max_level = ares_log2(ares_round_up_pow2(list->cnt + 1));
   }
 
   if (list->levels > max_level) {
     max_level = list->levels;
   }
 
   return max_level;
 }
 
 static size_t ares_slist_calc_level(ares_slist_t *list)
 {
   size_t max_level = ares_slist_max_level(list);
   size_t level;
 
   for (level = 1; ares_slist_coin_flip(list) && level < max_level; level++)
     ;
 
   return level;
 }
 
 static void ares_slist_node_push(ares_slist_t *list, ares_slist_node_t *node)
 {
   size_t             i;
   ares_slist_node_t *left = NULL;
 
   /* Scan from highest level in the slist, even if we're not using that number
    * of levels for this entry as this is what makes it O(log n) */
   for (i = list->levels; i-- > 0;) {
     /* set left if left is NULL and the current node value is greater than the
      * head at this level */
     if (left == NULL && list->head[i] != NULL &&
         list->cmp(node->data, list->head[i]->data) > 0) {
       left = list->head[i];
     }
 
     if (left != NULL) {
       /* scan forward to find our insertion point */
       while (left->next[i] != NULL &&
              list->cmp(node->data, left->next[i]->data) > 0) {
         left = left->next[i];
       }
     }
 
     /* search only as we didn't randomly select this number of levels */
     if (i >= node->levels) {
       continue;
     }
 
     if (left == NULL) {
       /* head insertion */
       node->next[i] = list->head[i];
       node->prev[i] = NULL;
       list->head[i] = node;
     } else {
       /* Chain */
       node->next[i] = left->next[i];
       node->prev[i] = left;
       left->next[i] = node;
     }
 
     if (node->next[i] != NULL) {
       /* chain prev */
       node->next[i]->prev[i] = node;
     } else {
       if (i == 0) {
         /* update tail */
         list->tail = node;
       }
     }
   }
 }
 
 ares_slist_node_t *ares_slist_insert(ares_slist_t *list, void *val)
 {
   ares_slist_node_t *node = NULL;
 
   if (list == NULL || val == NULL) {
     return NULL;
   }
 
   node = ares_malloc_zero(sizeof(*node));
 
   if (node == NULL) {
     goto fail; /* LCOV_EXCL_LINE: OutOfMemory */
   }
 
   node->data   = val;
   node->parent = list;
 
   /* Randomly determine the number of levels we want to use */
   node->levels = ares_slist_calc_level(list);
 
   /* Allocate array of next and prev nodes for linking each level */
   node->next = ares_malloc_zero(sizeof(*node->next) * node->levels);
   if (node->next == NULL) {
     goto fail; /* LCOV_EXCL_LINE: OutOfMemory */
   }
 
   node->prev = ares_malloc_zero(sizeof(*node->prev) * node->levels);
   if (node->prev == NULL) {
     goto fail; /* LCOV_EXCL_LINE: OutOfMemory */
   }
 
   /* If the number of levels is greater than we currently support in the slist,
    * increase the count */
   if (list->levels < node->levels) {
     void *ptr =
       ares_realloc_zero(list->head, sizeof(*list->head) * list->levels,
                         sizeof(*list->head) * node->levels);
     if (ptr == NULL) {
       goto fail; /* LCOV_EXCL_LINE: OutOfMemory */
     }
 
     list->head   = ptr;
     list->levels = node->levels;
   }
 
   ares_slist_node_push(list, node);
 
   list->cnt++;
 
   return node;
 
 /* LCOV_EXCL_START: OutOfMemory */
 fail:
   if (node) {
     ares_free(node->prev);
     ares_free(node->next);
     ares_free(node);
   }
   return NULL;
   /* LCOV_EXCL_STOP */
 }
 
 static void ares_slist_node_pop(ares_slist_node_t *node)
 {
   ares_slist_t *list = node->parent;
   size_t        i;
 
   /* relink each node at each level */
   for (i = node->levels; i-- > 0;) {
     if (node->next[i] == NULL) {
       if (i == 0) {
         list->tail = node->prev[0];
       }
     } else {
       node->next[i]->prev[i] = node->prev[i];
     }
 
     if (node->prev[i] == NULL) {
       list->head[i] = node->next[i];
     } else {
       node->prev[i]->next[i] = node->next[i];
     }
   }
 
   memset(node->next, 0, sizeof(*node->next) * node->levels);
   memset(node->prev, 0, sizeof(*node->prev) * node->levels);
 }
 
 void *ares_slist_node_claim(ares_slist_node_t *node)
 {
   ares_slist_t *list;
   void         *val;
 
   if (node == NULL) {
     return NULL;
   }
 
   list = node->parent;
   val  = node->data;
 
   ares_slist_node_pop(node);
 
   ares_free(node->next);
   ares_free(node->prev);
   ares_free(node);
 
   list->cnt--;
 
   return val;
 }
 
 void ares_slist_node_reinsert(ares_slist_node_t *node)
 {
   ares_slist_t *list;
 
   if (node == NULL) {
     return;
   }
 
   list = node->parent;
 
   ares_slist_node_pop(node);
   ares_slist_node_push(list, node);
 }
 
 ares_slist_node_t *ares_slist_node_find(const ares_slist_t *list,
                                         const void         *val)
 {
   size_t             i;
   ares_slist_node_t *node = NULL;
   int                rv   = -1;
 
   if (list == NULL || val == NULL) {
     return NULL;
   }
 
   /* Scan nodes starting at the highest level. For each level scan forward
    * until the value is between the prior and next node, or if equal quit
    * as we found a match */
   for (i = list->levels; i-- > 0;) {
     if (node == NULL) {
       node = list->head[i];
     }
 
     if (node == NULL) {
       continue;
     }
 
     do {
       rv = list->cmp(val, node->data);
 
       if (rv < 0) {
         /* back off, our value is greater than current node reference */
         node = node->prev[i];
       } else if (rv > 0) {
         /* move forward and try again. if it goes past, it will loop again and
          * go to previous entry */
         node = node->next[i];
       }
 
       /* rv == 0 will terminate loop */
 
     } while (node != NULL && rv > 0);
 
     /* Found a match, no need to continue */
     if (rv == 0) {
       break;
     }
   }
 
   /* no match */
   if (rv != 0) {
     return NULL;
   }
 
   /* The list may have multiple entries that match.  They're guaranteed to be
    * in order, but we're not guaranteed to have selected the _first_ matching
    * node.  Lets scan backwards to find the first match */
   while (node->prev[0] != NULL && list->cmp(node->prev[0]->data, val) == 0) {
     node = node->prev[0];
   }
 
   return node;
 }
 
 ares_slist_node_t *ares_slist_node_first(const ares_slist_t *list)
 {
   if (list == NULL) {
     return NULL;
   }
 
   return list->head[0];
 }
 
 ares_slist_node_t *ares_slist_node_last(const ares_slist_t *list)
 {
   if (list == NULL) {
     return NULL;
   }
   return list->tail;
 }
 
 ares_slist_node_t *ares_slist_node_next(const ares_slist_node_t *node)
 {
   if (node == NULL) {
     return NULL;
   }
   return node->next[0];
 }
 
 ares_slist_node_t *ares_slist_node_prev(const ares_slist_node_t *node)
 {
   if (node == NULL) {
     return NULL;
   }
   return node->prev[0];
 }
 
 void *ares_slist_node_val(ares_slist_node_t *node)
 {
   if (node == NULL) {
     return NULL;
   }
 
   return node->data;
 }
 
 size_t ares_slist_len(const ares_slist_t *list)
 {
   if (list == NULL) {
     return 0;
   }
   return list->cnt;
 }
 
 ares_slist_t *ares_slist_node_parent(ares_slist_node_t *node)
 {
   if (node == NULL) {
     return NULL;
   }
   return node->parent;
 }
 
 void *ares_slist_first_val(const ares_slist_t *list)
 {
   return ares_slist_node_val(ares_slist_node_first(list));
 }
 
 void *ares_slist_last_val(const ares_slist_t *list)
 {
   return ares_slist_node_val(ares_slist_node_last(list));
 }
 
 void ares_slist_node_destroy(ares_slist_node_t *node)
 {
   ares_slist_destructor_t destruct;
   void                   *val;
 
   if (node == NULL) {
     return;
   }
 
   destruct = node->parent->destruct;
   val      = ares_slist_node_claim(node);
 
   if (val != NULL && destruct != NULL) {
     destruct(val);
   }
 }
 
 void ares_slist_destroy(ares_slist_t *list)
 {
   ares_slist_node_t *node;
 
   if (list == NULL) {
     return;
   }
 
   while ((node = ares_slist_node_first(list)) != NULL) {
     ares_slist_node_destroy(node);
   }
 
   ares_free(list->head);
   ares_free(list);
 }