dynamicArray

general purpose dynamic array for one element type
git clone https://noulin.net/git/dynamicArray.git
Log | Files | Refs | README | LICENSE

libdarray.h (2382B)


      1 #pragma once
      2 
      3 #include <stdint.h>
      4 #include <stdbool.h>
      5 #include <stdlib.h>
      6 
      7 // user parameters
      8 // the dynamic arrays hold an absolute max of 2^dArrayAddrSpace elements
      9 #define dArrayAddrSpace 24
     10 // number of elements in the smallest buffer 2^dArrayBaseBits
     11 #define dArrayBaseBits 4
     12 // user parameters end
     13 
     14 
     15 #define dArrayBaseSz (1<<dArrayBaseBits)
     16 #define dArrayAddrBits dArrayAddrSpace-dArrayBaseBits
     17 
     18 
     19 #define dArrayT(typeName, elementType)\
     20   typedef struct {\
     21     intmax_t last;\
     22     intmax_t maxCount;\
     23     void*    buffers[dArrayAddrBits+1];\
     24     elementType element;\
     25   } typeName
     26 
     27 typedef struct {
     28     uint64_t offset;
     29     intmax_t ix;
     30     bool     error;
     31 } dArrayIxt;
     32 
     33 
     34 #define dArrayInit(a) do{\
     35     (a)->last = 0;\
     36     (a)->buffers[0]       = malloc(dArrayBaseSz * sizeof((a)->element));\
     37     (a)->maxCount         = dArrayBaseSz;\
     38 }while(0)
     39 
     40 
     41 #define dArrayInitCount(a, count) do{\
     42     (a)->last = 0;\
     43     (a)->buffers[0]       = malloc(dArrayBaseSz * sizeof((a)->element));\
     44     (a)->maxCount         = dArrayBaseSz;\
     45     if (count > dArrayBaseSz) {\
     46       dArrayIxt da = dArrayIndex(count);\
     47       if (!da.error) {\
     48         (a)->maxCount <<= da.ix;\
     49         for(int i=0 ; i<da.ix ; i++) {\
     50           (a)->buffers[i+1] = malloc((dArrayBaseSz<<(i)) * sizeof((a)->element));\
     51         }\
     52       }\
     53     }\
     54 }while(0)
     55 
     56 
     57 #define dArrayFree(a) do{\
     58     for(int i = 0 ; i < dArrayIndex((a)->maxCount-1).ix+1 ; i++) {\
     59         free((a)->buffers[i]);\
     60     }\
     61 }while(0)
     62 
     63 
     64 #define dArrayAlloc(a) do{\
     65     if ((a)->last == (a)->maxCount) {\
     66         dArrayIxt da = dArrayIndex((a)->maxCount);\
     67         if (!da.error) {\
     68             (a)->maxCount   <<= 1;\
     69             (a)->buffers[da.ix] = malloc((dArrayBaseSz<<(da.ix-1)) * sizeof((a)->element));\
     70         }\
     71     }\
     72 }while(0)
     73 
     74 
     75 #define dArrayPush(a, v) do{\
     76     dArrayAlloc(a);\
     77     if ((a)->last < (a)->maxCount) {\
     78         dArrayIxt da   = dArrayIndex((a)->last);\
     79         typeof((a)->element) *dArrayB    = (a)->buffers[da.ix];\
     80         *(dArrayB+da.offset) = v;\
     81         (a)->last++;\
     82     }\
     83 }while(0)
     84 
     85 
     86 #define dArrayPop(a) (*((typeof((a)->element)*)((a)->buffers[dArrayIndex(--(a)->last).ix])+dArrayIndex((a)->last).offset))
     87 
     88 #define dArrayAt(a, index) (*((typeof((a)->element)*)((a)->buffers[dArrayIndex(index).ix])+dArrayIndex(index).offset))
     89 
     90 
     91 bool dArrayIsValidIndex(intmax_t index);
     92 dArrayIxt dArrayIndex(intmax_t index);
     93