quickjs-tart

quickjs-based runtime for wallet-core logic
Log | Files | Refs | README | LICENSE

ares_llist.c (8329B)

      1 /* MIT License
      2  *
      3  * Copyright (c) 2023 Brad House
      4  *
      5  * Permission is hereby granted, free of charge, to any person obtaining a copy
      6  * of this software and associated documentation files (the "Software"), to deal
      7  * in the Software without restriction, including without limitation the rights
      8  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      9  * copies of the Software, and to permit persons to whom the Software is
     10  * furnished to do so, subject to the following conditions:
     11  *
     12  * The above copyright notice and this permission notice (including the next
     13  * paragraph) shall be included in all copies or substantial portions of the
     14  * Software.
     15  *
     16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     22  * SOFTWARE.
     23  *
     24  * SPDX-License-Identifier: MIT
     25  */
     26 #include "ares_private.h"
     27 #include "ares_llist.h"
     28 
     29 struct ares_llist {
     30   ares_llist_node_t      *head;
     31   ares_llist_node_t      *tail;
     32   ares_llist_destructor_t destruct;
     33   size_t                  cnt;
     34 };
     35 
     36 struct ares_llist_node {
     37   void              *data;
     38   ares_llist_node_t *prev;
     39   ares_llist_node_t *next;
     40   ares_llist_t      *parent;
     41 };
     42 
     43 ares_llist_t *ares_llist_create(ares_llist_destructor_t destruct)
     44 {
     45   ares_llist_t *list = ares_malloc_zero(sizeof(*list));
     46 
     47   if (list == NULL) {
     48     return NULL;
     49   }
     50 
     51   list->destruct = destruct;
     52 
     53   return list;
     54 }
     55 
     56 void ares_llist_replace_destructor(ares_llist_t           *list,
     57                                    ares_llist_destructor_t destruct)
     58 {
     59   if (list == NULL) {
     60     return;
     61   }
     62 
     63   list->destruct = destruct;
     64 }
     65 
     66 typedef enum {
     67   ARES__LLIST_INSERT_HEAD,
     68   ARES__LLIST_INSERT_TAIL,
     69   ARES__LLIST_INSERT_BEFORE
     70 } ares_llist_insert_type_t;
     71 
     72 static void ares_llist_attach_at(ares_llist_t            *list,
     73                                  ares_llist_insert_type_t type,
     74                                  ares_llist_node_t *at, ares_llist_node_t *node)
     75 {
     76   if (list == NULL || node == NULL) {
     77     return; /* LCOV_EXCL_LINE: DefensiveCoding */
     78   }
     79 
     80   node->parent = list;
     81 
     82   if (type == ARES__LLIST_INSERT_BEFORE && (at == list->head || at == NULL)) {
     83     type = ARES__LLIST_INSERT_HEAD;
     84   }
     85 
     86   switch (type) {
     87     case ARES__LLIST_INSERT_HEAD:
     88       node->next = list->head;
     89       node->prev = NULL;
     90       if (list->head) {
     91         list->head->prev = node;
     92       }
     93       list->head = node;
     94       break;
     95     case ARES__LLIST_INSERT_TAIL:
     96       node->next = NULL;
     97       node->prev = list->tail;
     98       if (list->tail) {
     99         list->tail->next = node;
    100       }
    101       list->tail = node;
    102       break;
    103     case ARES__LLIST_INSERT_BEFORE:
    104       node->next = at;
    105       node->prev = at->prev;
    106       at->prev   = node;
    107       break;
    108   }
    109   if (list->tail == NULL) {
    110     list->tail = node;
    111   }
    112   if (list->head == NULL) {
    113     list->head = node;
    114   }
    115 
    116   list->cnt++;
    117 }
    118 
    119 static ares_llist_node_t *ares_llist_insert_at(ares_llist_t            *list,
    120                                                ares_llist_insert_type_t type,
    121                                                ares_llist_node_t *at, void *val)
    122 {
    123   ares_llist_node_t *node = NULL;
    124 
    125   if (list == NULL || val == NULL) {
    126     return NULL; /* LCOV_EXCL_LINE: DefensiveCoding */
    127   }
    128 
    129   node = ares_malloc_zero(sizeof(*node));
    130 
    131   if (node == NULL) {
    132     return NULL;
    133   }
    134 
    135   node->data = val;
    136   ares_llist_attach_at(list, type, at, node);
    137 
    138   return node;
    139 }
    140 
    141 ares_llist_node_t *ares_llist_insert_first(ares_llist_t *list, void *val)
    142 {
    143   return ares_llist_insert_at(list, ARES__LLIST_INSERT_HEAD, NULL, val);
    144 }
    145 
    146 ares_llist_node_t *ares_llist_insert_last(ares_llist_t *list, void *val)
    147 {
    148   return ares_llist_insert_at(list, ARES__LLIST_INSERT_TAIL, NULL, val);
    149 }
    150 
    151 ares_llist_node_t *ares_llist_insert_before(ares_llist_node_t *node, void *val)
    152 {
    153   if (node == NULL) {
    154     return NULL;
    155   }
    156 
    157   return ares_llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, node,
    158                               val);
    159 }
    160 
    161 ares_llist_node_t *ares_llist_insert_after(ares_llist_node_t *node, void *val)
    162 {
    163   if (node == NULL) {
    164     return NULL;
    165   }
    166 
    167   if (node->next == NULL) {
    168     return ares_llist_insert_last(node->parent, val);
    169   }
    170 
    171   return ares_llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE,
    172                               node->next, val);
    173 }
    174 
    175 ares_llist_node_t *ares_llist_node_first(ares_llist_t *list)
    176 {
    177   if (list == NULL) {
    178     return NULL;
    179   }
    180   return list->head;
    181 }
    182 
    183 ares_llist_node_t *ares_llist_node_idx(ares_llist_t *list, size_t idx)
    184 {
    185   ares_llist_node_t *node;
    186   size_t             cnt;
    187 
    188   if (list == NULL) {
    189     return NULL;
    190   }
    191   if (idx >= list->cnt) {
    192     return NULL;
    193   }
    194 
    195   node = list->head;
    196   for (cnt = 0; node != NULL && cnt < idx; cnt++) {
    197     node = node->next;
    198   }
    199 
    200   return node;
    201 }
    202 
    203 ares_llist_node_t *ares_llist_node_last(ares_llist_t *list)
    204 {
    205   if (list == NULL) {
    206     return NULL;
    207   }
    208   return list->tail;
    209 }
    210 
    211 ares_llist_node_t *ares_llist_node_next(ares_llist_node_t *node)
    212 {
    213   if (node == NULL) {
    214     return NULL;
    215   }
    216   return node->next;
    217 }
    218 
    219 ares_llist_node_t *ares_llist_node_prev(ares_llist_node_t *node)
    220 {
    221   if (node == NULL) {
    222     return NULL;
    223   }
    224   return node->prev;
    225 }
    226 
    227 void *ares_llist_node_val(ares_llist_node_t *node)
    228 {
    229   if (node == NULL) {
    230     return NULL;
    231   }
    232 
    233   return node->data;
    234 }
    235 
    236 size_t ares_llist_len(const ares_llist_t *list)
    237 {
    238   if (list == NULL) {
    239     return 0;
    240   }
    241   return list->cnt;
    242 }
    243 
    244 ares_llist_t *ares_llist_node_parent(ares_llist_node_t *node)
    245 {
    246   if (node == NULL) {
    247     return NULL;
    248   }
    249   return node->parent;
    250 }
    251 
    252 void *ares_llist_first_val(ares_llist_t *list)
    253 {
    254   return ares_llist_node_val(ares_llist_node_first(list));
    255 }
    256 
    257 void *ares_llist_last_val(ares_llist_t *list)
    258 {
    259   return ares_llist_node_val(ares_llist_node_last(list));
    260 }
    261 
    262 static void ares_llist_node_detach(ares_llist_node_t *node)
    263 {
    264   ares_llist_t *list;
    265 
    266   if (node == NULL) {
    267     return; /* LCOV_EXCL_LINE: DefensiveCoding */
    268   }
    269 
    270   list = node->parent;
    271 
    272   if (node->prev) {
    273     node->prev->next = node->next;
    274   }
    275 
    276   if (node->next) {
    277     node->next->prev = node->prev;
    278   }
    279 
    280   if (node == list->head) {
    281     list->head = node->next;
    282   }
    283 
    284   if (node == list->tail) {
    285     list->tail = node->prev;
    286   }
    287 
    288   node->parent = NULL;
    289   list->cnt--;
    290 }
    291 
    292 void *ares_llist_node_claim(ares_llist_node_t *node)
    293 {
    294   void *val;
    295 
    296   if (node == NULL) {
    297     return NULL;
    298   }
    299 
    300   val = node->data;
    301   ares_llist_node_detach(node);
    302   ares_free(node);
    303 
    304   return val;
    305 }
    306 
    307 void ares_llist_node_destroy(ares_llist_node_t *node)
    308 {
    309   ares_llist_destructor_t destruct;
    310   void                   *val;
    311 
    312   if (node == NULL) {
    313     return;
    314   }
    315 
    316   destruct = node->parent->destruct;
    317 
    318   val = ares_llist_node_claim(node);
    319   if (val != NULL && destruct != NULL) {
    320     destruct(val);
    321   }
    322 }
    323 
    324 void ares_llist_node_replace(ares_llist_node_t *node, void *val)
    325 {
    326   ares_llist_destructor_t destruct;
    327 
    328   if (node == NULL) {
    329     return;
    330   }
    331 
    332   destruct = node->parent->destruct;
    333   if (destruct != NULL) {
    334     destruct(node->data);
    335   }
    336 
    337   node->data = val;
    338 }
    339 
    340 void ares_llist_clear(ares_llist_t *list)
    341 {
    342   ares_llist_node_t *node;
    343 
    344   if (list == NULL) {
    345     return;
    346   }
    347 
    348   while ((node = ares_llist_node_first(list)) != NULL) {
    349     ares_llist_node_destroy(node);
    350   }
    351 }
    352 
    353 void ares_llist_destroy(ares_llist_t *list)
    354 {
    355   if (list == NULL) {
    356     return;
    357   }
    358   ares_llist_clear(list);
    359   ares_free(list);
    360 }
    361 
    362 void ares_llist_node_mvparent_last(ares_llist_node_t *node,
    363                                    ares_llist_t      *new_parent)
    364 {
    365   if (node == NULL || new_parent == NULL) {
    366     return; /* LCOV_EXCL_LINE: DefensiveCoding */
    367   }
    368 
    369   ares_llist_node_detach(node);
    370   ares_llist_attach_at(new_parent, ARES__LLIST_INSERT_TAIL, NULL, node);
    371 }
    372 
    373 void ares_llist_node_mvparent_first(ares_llist_node_t *node,
    374                                     ares_llist_t      *new_parent)
    375 {
    376   if (node == NULL || new_parent == NULL) {
    377     return; /* LCOV_EXCL_LINE: DefensiveCoding */
    378   }
    379 
    380   ares_llist_node_detach(node);
    381   ares_llist_attach_at(new_parent, ARES__LLIST_INSERT_HEAD, NULL, node);
    382 }