Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0-or-later
       2             : /*
       3             :  * June 23 2023, Christian Hopps <chopps@labn.net>
       4             :  *
       5             :  * Copyright (c) 2023, LabN Consulting, L.L.C.
       6             :  *
       7             :  */
       8             : #include <zebra.h>
       9             : #include "darr.h"
      10             : #include "memory.h"
      11             : 
      12          12 : DEFINE_MTYPE(LIB, DARR, "Dynamic Array");
      13             : 
      14             : static uint _msb(uint count)
      15             : {
      16             :         uint bit = 0;
      17             :         int msb = 0;
      18             : 
      19           0 :         while (count) {
      20           0 :                 if (count & 1)
      21           0 :                         msb = bit;
      22           0 :                 count >>= 1;
      23           0 :                 bit += 1;
      24             :         }
      25           0 :         return msb;
      26             : }
      27             : 
      28           0 : static uint darr_next_count(uint count, size_t esize)
      29             : {
      30           0 :         uint ncount;
      31             : 
      32           0 :         if (esize > sizeof(long long) && count == 1)
      33             :                 /* treat like a pointer */
      34             :                 ncount = 1;
      35             :         else {
      36           0 :                 uint msb = _msb(count);
      37             : 
      38           0 :                 ncount = 1ull << msb;
      39             :                 /* if the users count wasn't a pow2 make it the next pow2. */
      40           0 :                 if (ncount != count) {
      41           0 :                         assert(ncount < count);
      42           0 :                         ncount <<= 1;
      43           0 :                         if (esize < sizeof(long long) && ncount < 8)
      44           0 :                                 ncount = 8;
      45             :                 }
      46             :         }
      47           0 :         return ncount;
      48             : }
      49             : 
      50           0 : static size_t darr_size(uint count, size_t esize)
      51             : {
      52           0 :         return count * esize + sizeof(struct darr_metadata);
      53             : }
      54             : 
      55           0 : void *__darr_resize(void *a, uint count, size_t esize)
      56             : {
      57           0 :         uint ncount = darr_next_count(count, esize);
      58           0 :         size_t osz = (a == NULL) ? 0 : darr_size(darr_cap(a), esize);
      59           0 :         size_t sz = darr_size(ncount, esize);
      60           0 :         struct darr_metadata *dm = XREALLOC(MTYPE_DARR,
      61             :                                             a ? _darr_meta(a) : NULL, sz);
      62             : 
      63           0 :         if (sz > osz)
      64           0 :                 memset((char *)dm + osz, 0, sz - osz);
      65           0 :         dm->cap = ncount;
      66           0 :         return (void *)(dm + 1);
      67             : }
      68             : 
      69             : 
      70           0 : void *__darr_insert_n(void *a, uint at, uint count, size_t esize, bool zero)
      71             : {
      72             : 
      73           0 :         struct darr_metadata *dm;
      74           0 :         uint olen, nlen;
      75             : 
      76           0 :         if (!a)
      77           0 :                 a = __darr_resize(NULL, at + count, esize);
      78           0 :         dm = (struct darr_metadata *)a - 1;
      79           0 :         olen = dm->len;
      80             : 
      81             :         // at == 1
      82             :         // count == 100
      83             :         // olen == 2
      84             : 
      85             :         /* see if the user is expanding first using `at` */
      86           0 :         if (at >= olen)
      87           0 :                 nlen = at + count;
      88             :         else
      89           0 :                 nlen = olen + count;
      90             : 
      91           0 :         if (nlen > dm->cap) {
      92           0 :                 a = __darr_resize(a, nlen, esize);
      93           0 :                 dm = (struct darr_metadata *)a - 1;
      94             :         }
      95             : 
      96             : #define _a_at(i) ((char *)a + ((i)*esize))
      97           0 :         if (at < olen)
      98           0 :                 memmove(_a_at(at + count), _a_at(at), esize * (olen - at));
      99             : 
     100           0 :         dm->len = nlen;
     101             : 
     102           0 :         if (zero) {
     103           0 :                 if (at >= olen) {
     104           0 :                         at -= olen;
     105           0 :                         count += olen;
     106             :                 }
     107           0 :                 memset(_a_at(at), 0, esize * count);
     108             :         }
     109             : 
     110           0 :         return a;
     111             : #undef _a_at
     112             : }