dynamicArray

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

commit a2249885b2174f5ef3d0e5a0238378f2150128f1
parent 695fa3d8bb45755c9eaaa8e256293567060dd7c1
Author: Remy Noulin <loader2x@gmail.com>
Date:   Sat,  3 Feb 2018 10:45:01 +0100

implement dynamic array

README.md   | 48 +++++++++++++++++++++++++++++++
clean.sh    |  3 ++
libdarray.c | 40 ++++++++++++++++++++++++++
libdarray.h | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
main.c      | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
make.sh     |  4 +++
6 files changed, 275 insertions(+)

Diffstat:
AREADME.md | 48++++++++++++++++++++++++++++++++++++++++++++++++
Aclean.sh | 3+++
Alibdarray.c | 40++++++++++++++++++++++++++++++++++++++++
Alibdarray.h | 93+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Amain.c | 87+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Amake.sh | 4++++
6 files changed, 275 insertions(+), 0 deletions(-)

diff --git a/README.md b/README.md @@ -0,0 +1,48 @@ +# Dynamic array + +- prefix: __dArray__ +- direct access to array elements like regular C arrays with __dArrayAt__ +- the size is increased by pushing elements with __dArrayPush__ +- compile with gcc on linux + +# Usage + +Create a dynamic array type to define the element type: +``` +dArrayT(myDynt, type); +``` + +Declare a variable dynamic array: +``` +myDynt darray; +``` + +Initialize the array: +``` +dArrayInit(&darray); +or +dArrayInitCount(&darray, 17); +``` + +Push elements, it increases the size of the array when needed: +``` +dArrayPush(&darray, value); +``` + +Get and set values with __dArrayAt__: +``` +// get +int a = dArrayAt(&darray, 0); + +// set +dArrayAt(&darray, 1) = 3; +``` + +Free the dynamic array with: +``` +dArrayFree(&darray); +``` + +# Example + +See __main.c__. diff --git a/clean.sh b/clean.sh @@ -0,0 +1,3 @@ +rm -f darray +rm -f main.o +rm -f libdarray.o diff --git a/libdarray.c b/libdarray.c @@ -0,0 +1,40 @@ + +#include "libdarray.h" + +bool dArrayIsValidIndex(intmax_t index) { + if (index >= ((intmax_t)1)<<dArrayAddrSpace) { + return false; + } + return true; +} + +dArrayIxt dArrayIndex(intmax_t index) { + dArrayIxt r; + if (index >= ((intmax_t)1)<<dArrayAddrSpace) { + r.error = true; + return r; + } + r.error = false; + + intmax_t bufx = index >> dArrayBaseBits; + if (!bufx) { + r.ix = 0; + r.offset = index; + } + else { + //int pos = 0; + /* for (int i = (bufx >> 1); i != 0; pos++) { */ + /* i >>= 1; */ + /* } */ + /* find position of MSB */ +#if __LP64__ + asm ("bsrq %1, %0" : "=r" (r.ix) : "r" (bufx)); +#else + asm ("bsrl %1, %0" : "=r" (r.ix) : "r" (bufx)); +#endif + intmax_t mask = ~(0xFFFFFFFFFFFFFFFF << (dArrayBaseBits+r.ix)); + r.ix++; + r.offset = index & mask; + } + return r; +} diff --git a/libdarray.h b/libdarray.h @@ -0,0 +1,93 @@ +#pragma once + +#include <stdint.h> +#include <stdbool.h> +#include <stdlib.h> + +// user parameters +// the dynamic arrays hold an absolute max of 2^dArrayAddrSpace elements +#define dArrayAddrSpace 24 +// number of elements in the smallest buffer 2^dArrayBaseBits +#define dArrayBaseBits 4 +// user parameters end + + +#define dArrayBaseSz (1<<dArrayBaseBits) +#define dArrayAddrBits dArrayAddrSpace-dArrayBaseBits + + +#define dArrayT(typeName, elementType)\ + typedef struct {\ + intmax_t last;\ + intmax_t maxCount;\ + void* buffers[dArrayAddrBits+1];\ + elementType element;\ + } typeName + +typedef struct { + uint64_t offset; + intmax_t ix; + bool error; +} dArrayIxt; + + +#define dArrayInit(a) do{\ + (a)->last = 0;\ + (a)->buffers[0] = malloc(dArrayBaseSz * sizeof((a)->element));\ + (a)->maxCount = dArrayBaseSz;\ +}while(0) + + +#define dArrayInitCount(a, count) do{\ + (a)->last = 0;\ + (a)->buffers[0] = malloc(dArrayBaseSz * sizeof((a)->element));\ + (a)->maxCount = dArrayBaseSz;\ + if (count > dArrayBaseSz) {\ + dArrayIxt da = dArrayIndex(count);\ + if (!da.error) {\ + (a)->maxCount <<= da.ix;\ + for(int i=0 ; i<da.ix ; i++) {\ + (a)->buffers[i+1] = malloc((dArrayBaseSz<<(i)) * sizeof((a)->element));\ + }\ + }\ + }\ +}while(0) + + +#define dArrayFree(a) do{\ + for(int i = 0 ; i < dArrayIndex((a)->maxCount-1).ix+1 ; i++) {\ + free((a)->buffers[i]);\ + }\ +}while(0) + + +#define dArrayAlloc(a) do{\ + if ((a)->last == (a)->maxCount) {\ + dArrayIxt da = dArrayIndex((a)->maxCount);\ + if (!da.error) {\ + (a)->maxCount <<= 1;\ + (a)->buffers[da.ix] = malloc((dArrayBaseSz<<(da.ix-1)) * sizeof((a)->element));\ + }\ + }\ +}while(0) + + +#define dArrayPush(a, v) do{\ + dArrayAlloc(a);\ + if ((a)->last < (a)->maxCount) {\ + dArrayIxt da = dArrayIndex((a)->last);\ + typeof((a)->element) *dArrayB = (a)->buffers[da.ix];\ + *(dArrayB+da.offset) = v;\ + (a)->last++;\ + }\ +}while(0) + + +#define dArrayPop(a) (*((typeof((a)->element)*)((a)->buffers[dArrayIndex(--(a)->last).ix])+dArrayIndex((a)->last).offset)) + +#define dArrayAt(a, index) (*((typeof((a)->element)*)((a)->buffers[dArrayIndex(index).ix])+dArrayIndex(index).offset)) + + +bool dArrayIsValidIndex(intmax_t index); +dArrayIxt dArrayIndex(intmax_t index); + diff --git a/main.c b/main.c @@ -0,0 +1,87 @@ +#include "libdarray.h" +#include <stdio.h> +#include <inttypes.h> + +typedef struct { + uint32_t a,b; +} elementt; + + +// dynamic array of int elements +dArrayT(intDynt, int); + +// dynamic array of elementt elements +dArrayT(myDynt, elementt); + + +int main(int ARGC, char** ARGV) { + + // EXAMPLE 1 + + // dynamic array of int elements + intDynt a; + + // the size of the dynamic array depends on dArrayAddrSpace and dArrayBaseBits in libdarray.h + printf("sizeof intDyn: %d\n", sizeof a); + + // initialize a (malloc first buffer) + dArrayInit(&a); + + // current maxCount for a + printf("max %"PRIiMAX"\n", a.maxCount); + + // add elements + dArrayPush(&a, 1); + dArrayPush(&a, 2); + + // set value + dArrayAt(&a, 1) = 3; + + // get value + printf("get %"PRIi32"\n", dArrayAt(&a, 0)); + + // pop an element + printf("pop %"PRIi32"\n", dArrayPop(&a)); + + + // free the internal buffers in a + dArrayFree(&a); + + + // EXAMPLE 2 + + // dynamic array of elementt elements + myDynt b; + + // the size of the dynamic array depends on dArrayAddrSpace and dArrayBaseBits in libdarray.h + printf("\n\nsizeof myDyn: %d\n", sizeof b); + + // initialize b of size at least 17 + dArrayInitCount(&b, 17); + + // current maxCount for a + printf("max %"PRIiMAX"\n\n", b.maxCount); + + // local elements + typeof(b.element) dta; + + dta.a = 123; + dta.b = 2018; + + for(int i = 0; i < 1+(1<<2); i++) { + dta.a += i; + dArrayPush(&b, dta); + printf("index %"PRIi32"\n", i); + printf("maxcount %"PRIiMAX"\n", a.maxCount); + printf("get e.a %"PRIi32"\n", dArrayAt(&b, i).a); + dArrayAt(&b, i).a -= i-1; + printf("modified e.a %"PRIi32"\n", dArrayAt(&b, i).a); + printf("get e.b %"PRIi32"\n", dArrayAt(&b, i).b); + } + + // get first element + printf("\nget e(0).a %"PRIi32"\n", dArrayAt(&b, 0).a); + + // free the internal buffers in b + dArrayFree(&b); +} diff --git a/make.sh b/make.sh @@ -0,0 +1,4 @@ +gcc -ggdb -std=gnu11 -o main.o -c main.c +gcc -ggdb -std=gnu11 -c -o libdarray.o libdarray.c +gcc -o darray main.o libdarray.o +echo Built: darray