quickjs-tart

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

ares_array.c (9741B)

      1 /* MIT License
      2  *
      3  * Copyright (c) 2024 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_array.h"
     28 
     29 #define ARES__ARRAY_MIN 4
     30 
     31 struct ares_array {
     32   ares_array_destructor_t destruct;
     33   void                   *arr;
     34   size_t                  member_size;
     35   size_t                  cnt;
     36   size_t                  offset;
     37   size_t                  alloc_cnt;
     38 };
     39 
     40 ares_array_t *ares_array_create(size_t                  member_size,
     41                                 ares_array_destructor_t destruct)
     42 {
     43   ares_array_t *arr;
     44 
     45   if (member_size == 0) {
     46     return NULL;
     47   }
     48 
     49   arr = ares_malloc_zero(sizeof(*arr));
     50   if (arr == NULL) {
     51     return NULL;
     52   }
     53 
     54   arr->member_size = member_size;
     55   arr->destruct    = destruct;
     56   return arr;
     57 }
     58 
     59 size_t ares_array_len(const ares_array_t *arr)
     60 {
     61   if (arr == NULL) {
     62     return 0;
     63   }
     64   return arr->cnt;
     65 }
     66 
     67 void *ares_array_at(ares_array_t *arr, size_t idx)
     68 {
     69   if (arr == NULL || idx >= arr->cnt) {
     70     return NULL;
     71   }
     72   return (unsigned char *)arr->arr + ((idx + arr->offset) * arr->member_size);
     73 }
     74 
     75 const void *ares_array_at_const(const ares_array_t *arr, size_t idx)
     76 {
     77   if (arr == NULL || idx >= arr->cnt) {
     78     return NULL;
     79   }
     80   return (unsigned char *)arr->arr + ((idx + arr->offset) * arr->member_size);
     81 }
     82 
     83 ares_status_t ares_array_sort(ares_array_t *arr, ares_array_cmp_t cmp)
     84 {
     85   if (arr == NULL || cmp == NULL) {
     86     return ARES_EFORMERR;
     87   }
     88 
     89   /* Nothing to sort */
     90   if (arr->cnt < 2) {
     91     return ARES_SUCCESS;
     92   }
     93 
     94   qsort((unsigned char *)arr->arr + (arr->offset * arr->member_size), arr->cnt,
     95         arr->member_size, cmp);
     96   return ARES_SUCCESS;
     97 }
     98 
     99 void ares_array_destroy(ares_array_t *arr)
    100 {
    101   size_t i;
    102 
    103   if (arr == NULL) {
    104     return;
    105   }
    106 
    107   if (arr->destruct != NULL) {
    108     for (i = 0; i < arr->cnt; i++) {
    109       arr->destruct(ares_array_at(arr, i));
    110     }
    111   }
    112 
    113   ares_free(arr->arr);
    114   ares_free(arr);
    115 }
    116 
    117 /* NOTE: this function operates on actual indexes, NOT indexes using the
    118  *       arr->offset */
    119 static ares_status_t ares_array_move(ares_array_t *arr, size_t dest_idx,
    120                                      size_t src_idx)
    121 {
    122   void       *dest_ptr;
    123   const void *src_ptr;
    124   size_t      nmembers;
    125 
    126   if (arr == NULL || dest_idx >= arr->alloc_cnt || src_idx >= arr->alloc_cnt) {
    127     return ARES_EFORMERR;
    128   }
    129 
    130   /* Nothing to do */
    131   if (dest_idx == src_idx) {
    132     return ARES_SUCCESS;
    133   }
    134 
    135   dest_ptr = (unsigned char *)arr->arr + (dest_idx * arr->member_size);
    136   src_ptr  = (unsigned char *)arr->arr + (src_idx * arr->member_size);
    137 
    138   /* Check to make sure shifting to the right won't overflow our allocation
    139    * boundary */
    140   if (dest_idx > src_idx && arr->cnt + (dest_idx - src_idx) > arr->alloc_cnt) {
    141     return ARES_EFORMERR;
    142   }
    143 
    144   nmembers = arr->cnt - (src_idx - arr->offset);
    145   memmove(dest_ptr, src_ptr, nmembers * arr->member_size);
    146 
    147   return ARES_SUCCESS;
    148 }
    149 
    150 void *ares_array_finish(ares_array_t *arr, size_t *num_members)
    151 {
    152   void *ptr;
    153 
    154   if (arr == NULL || num_members == NULL) {
    155     return NULL;
    156   }
    157 
    158   /* Make sure we move data to beginning of allocation */
    159   if (arr->offset != 0) {
    160     if (ares_array_move(arr, 0, arr->offset) != ARES_SUCCESS) {
    161       return NULL;
    162     }
    163     arr->offset = 0;
    164   }
    165 
    166   ptr          = arr->arr;
    167   *num_members = arr->cnt;
    168   ares_free(arr);
    169   return ptr;
    170 }
    171 
    172 ares_status_t ares_array_set_size(ares_array_t *arr, size_t size)
    173 {
    174   void *temp;
    175 
    176   if (arr == NULL || size == 0 || size < arr->cnt) {
    177     return ARES_EFORMERR;
    178   }
    179 
    180   /* Always operate on powers of 2 */
    181   size = ares_round_up_pow2(size);
    182 
    183   if (size < ARES__ARRAY_MIN) {
    184     size = ARES__ARRAY_MIN;
    185   }
    186 
    187   /* If our allocation size is already large enough, skip */
    188   if (size <= arr->alloc_cnt) {
    189     return ARES_SUCCESS;
    190   }
    191 
    192   temp = ares_realloc_zero(arr->arr, arr->alloc_cnt * arr->member_size,
    193                            size * arr->member_size);
    194   if (temp == NULL) {
    195     return ARES_ENOMEM;
    196   }
    197   arr->alloc_cnt = size;
    198   arr->arr       = temp;
    199   return ARES_SUCCESS;
    200 }
    201 
    202 ares_status_t ares_array_insert_at(void **elem_ptr, ares_array_t *arr,
    203                                    size_t idx)
    204 {
    205   void         *ptr;
    206   ares_status_t status;
    207 
    208   if (arr == NULL) {
    209     return ARES_EFORMERR;
    210   }
    211 
    212   /* Not >= since we are allowed to append to the end */
    213   if (idx > arr->cnt) {
    214     return ARES_EFORMERR;
    215   }
    216 
    217   /* Allocate more if needed */
    218   status = ares_array_set_size(arr, arr->cnt + 1);
    219   if (status != ARES_SUCCESS) {
    220     return status;
    221   }
    222 
    223   /* Shift if we have memory but not enough room at the end */
    224   if (arr->cnt + 1 + arr->offset > arr->alloc_cnt) {
    225     status = ares_array_move(arr, 0, arr->offset);
    226     if (status != ARES_SUCCESS) {
    227       return status;
    228     }
    229     arr->offset = 0;
    230   }
    231 
    232   /* If we're inserting anywhere other than the end, we need to move some
    233    * elements out of the way */
    234   if (idx != arr->cnt) {
    235     status = ares_array_move(arr, idx + arr->offset + 1, idx + arr->offset);
    236     if (status != ARES_SUCCESS) {
    237       return status;
    238     }
    239   }
    240 
    241   /* Ok, we're guaranteed to have a gap where we need it, lets zero it out,
    242    * and return it */
    243   ptr = (unsigned char *)arr->arr + ((idx + arr->offset) * arr->member_size);
    244   memset(ptr, 0, arr->member_size);
    245   arr->cnt++;
    246 
    247   if (elem_ptr) {
    248     *elem_ptr = ptr;
    249   }
    250 
    251   return ARES_SUCCESS;
    252 }
    253 
    254 ares_status_t ares_array_insert_last(void **elem_ptr, ares_array_t *arr)
    255 {
    256   return ares_array_insert_at(elem_ptr, arr, ares_array_len(arr));
    257 }
    258 
    259 ares_status_t ares_array_insert_first(void **elem_ptr, ares_array_t *arr)
    260 {
    261   return ares_array_insert_at(elem_ptr, arr, 0);
    262 }
    263 
    264 ares_status_t ares_array_insertdata_at(ares_array_t *arr, size_t idx,
    265                                        const void *data_ptr)
    266 {
    267   ares_status_t status;
    268   void         *ptr = NULL;
    269 
    270   status = ares_array_insert_at(&ptr, arr, idx);
    271   if (status != ARES_SUCCESS) {
    272     return status;
    273   }
    274   memcpy(ptr, data_ptr, arr->member_size);
    275   return ARES_SUCCESS;
    276 }
    277 
    278 ares_status_t ares_array_insertdata_last(ares_array_t *arr,
    279                                          const void   *data_ptr)
    280 {
    281   ares_status_t status;
    282   void         *ptr = NULL;
    283 
    284   status = ares_array_insert_last(&ptr, arr);
    285   if (status != ARES_SUCCESS) {
    286     return status;
    287   }
    288   memcpy(ptr, data_ptr, arr->member_size);
    289   return ARES_SUCCESS;
    290 }
    291 
    292 ares_status_t ares_array_insertdata_first(ares_array_t *arr,
    293                                           const void   *data_ptr)
    294 {
    295   ares_status_t status;
    296   void         *ptr = NULL;
    297 
    298   status = ares_array_insert_last(&ptr, arr);
    299   if (status != ARES_SUCCESS) {
    300     return status;
    301   }
    302   memcpy(ptr, data_ptr, arr->member_size);
    303   return ARES_SUCCESS;
    304 }
    305 
    306 void *ares_array_first(ares_array_t *arr)
    307 {
    308   return ares_array_at(arr, 0);
    309 }
    310 
    311 void *ares_array_last(ares_array_t *arr)
    312 {
    313   size_t cnt = ares_array_len(arr);
    314   if (cnt == 0) {
    315     return NULL;
    316   }
    317   return ares_array_at(arr, cnt - 1);
    318 }
    319 
    320 const void *ares_array_first_const(const ares_array_t *arr)
    321 {
    322   return ares_array_at_const(arr, 0);
    323 }
    324 
    325 const void *ares_array_last_const(const ares_array_t *arr)
    326 {
    327   size_t cnt = ares_array_len(arr);
    328   if (cnt == 0) {
    329     return NULL;
    330   }
    331   return ares_array_at_const(arr, cnt - 1);
    332 }
    333 
    334 ares_status_t ares_array_claim_at(void *dest, size_t dest_size,
    335                                   ares_array_t *arr, size_t idx)
    336 {
    337   ares_status_t status;
    338 
    339   if (arr == NULL || idx >= arr->cnt) {
    340     return ARES_EFORMERR;
    341   }
    342 
    343   if (dest != NULL && dest_size < arr->member_size) {
    344     return ARES_EFORMERR;
    345   }
    346 
    347   if (dest) {
    348     memcpy(dest, ares_array_at(arr, idx), arr->member_size);
    349   }
    350 
    351   if (idx == 0) {
    352     /* Optimization, if first element, just increment offset, makes removing a
    353      * lot from the start quick */
    354     arr->offset++;
    355   } else if (idx != arr->cnt - 1) {
    356     /* Must shift entire array if removing an element from the middle. Does
    357      * nothing if removing last element other than decrement count. */
    358     status = ares_array_move(arr, idx + arr->offset, idx + arr->offset + 1);
    359     if (status != ARES_SUCCESS) {
    360       return status;
    361     }
    362   }
    363 
    364   arr->cnt--;
    365   return ARES_SUCCESS;
    366 }
    367 
    368 ares_status_t ares_array_remove_at(ares_array_t *arr, size_t idx)
    369 {
    370   void *ptr = ares_array_at(arr, idx);
    371   if (arr == NULL || ptr == NULL) {
    372     return ARES_EFORMERR;
    373   }
    374 
    375   if (arr->destruct != NULL) {
    376     arr->destruct(ptr);
    377   }
    378 
    379   return ares_array_claim_at(NULL, 0, arr, idx);
    380 }
    381 
    382 ares_status_t ares_array_remove_first(ares_array_t *arr)
    383 {
    384   return ares_array_remove_at(arr, 0);
    385 }
    386 
    387 ares_status_t ares_array_remove_last(ares_array_t *arr)
    388 {
    389   size_t cnt = ares_array_len(arr);
    390   if (cnt == 0) {
    391     return ARES_EFORMERR;
    392   }
    393   return ares_array_remove_at(arr, cnt - 1);
    394 }