Baillehache Pascal's personal website

LibCapy - array

Generic array class.

Macros:

#define CAPY_ARRAY_H

#define CapyDecArrayIterator(name, type_)                    \
typedef struct name name;                                    \
typedef struct name ## Iterator {                            \
  size_t idx;                                                \
  name* arr;                                                 \
  type_ datatype;                                            \
  CapyPad(type_, datatype);                                  \
  CapyArrayIteratorType type;                                \
  CapyPad(CapyArrayIteratorType, type);                      \
  void (*destruct)(void);                                    \
  type_* (*reset)(void);                                     \
  type_* (*prev)(void);                                      \
  type_* (*next)(void);                                      \
  bool (*isActive)(void);                                    \
  type_* (*get)(void);                                       \
  void (*setType)(CapyArrayIteratorType type);               \
  void (*toLast)(void);                                      \
} name ## Iterator;                                          \
name ## Iterator name ## IteratorCreate(                     \
  name* const arr, CapyArrayIteratorType const type);        \
name ## Iterator* name ## IteratorAlloc(                     \
  name* const arr, CapyArrayIteratorType const type);        \
void name ## IteratorDestruct(void);                         \
void name ## IteratorFree(name ## Iterator** const that);    \
type_* name ## IteratorReset(void);                          \
type_* name ## IteratorPrev(void);                           \
type_* name ## IteratorNext(void);                           \
bool name ## IteratorIsActive(void);                         \
void name ## IteratorToLast(void);                           \
type_* name ## IteratorGet(void);                            \
void name ## IteratorSetType(CapyArrayIteratorType type);

Iterator for generic array structure. Declaration macro for an iterator structure named 'name' ## Iterator, associated to an array named 'name' containing elements of type 'type'

#define CapyDefArrayIteratorCreate(name, type_)        \
name ## Iterator name ## IteratorCreate(               \
  name* const arr,                                     \
  CapyArrayIteratorType const type) {                  \
  name ## Iterator that = {                            \
    .idx = 0,                                          \
    .arr = arr,                                        \
    .type = type,                                      \
    .destruct = name ## IteratorDestruct,              \
    .reset = name ## IteratorReset,                    \
    .prev = name ## IteratorPrev,                      \
    .next = name ## IteratorNext,                      \
    .toLast = name ## IteratorToLast,                  \
    .isActive = name ## IteratorIsActive,              \
    .get = name ## IteratorGet,                        \
    .setType = name ## IteratorSetType,                \
  };                                                   \
  $(&that, reset)();                                   \
  return that;                                         \
}

Create an iterator on a generic array

Input argument(s):

arr: the generic array on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefArrayIteratorAlloc(name, type_)                    \
name ## Iterator* name ## IteratorAlloc(                          \
  name* const arr,                                                \
  CapyArrayIteratorType const type) {                             \
  name ## Iterator* that = NULL;                                  \
  safeMalloc(that, 1);                                            \
  if(!that) return NULL;                                          \
  name ## Iterator i = name ## IteratorCreate(arr, type);         \
  memcpy(that, &i, sizeof(name ## Iterator));                     \
  return that;                                                    \
}

Allocate memory and create an iterator on a generic array

Input argument(s):

arr: the generic array on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefArrayIteratorDestruct(name, type) \
void name ## IteratorDestruct(void) {            \
  return;                                        \
}

Free the memory used by an iterator.

Input argument(s):

that: the iterator to free

#define CapyDefArrayIteratorFree(name, type)               \
void name ## IteratorFree(name ## Iterator** const that) { \
  if(that == NULL || *that == NULL) return;                \
  $(*that, destruct)();                                    \
  free(*that);                                             \
  *that = NULL;                                            \
}

Free the memory used by a pointer to an iterator and reset '*that' to NULL

Input argument(s):

that: a pointer to the iterator to free

#define CapyDefArrayIteratorReset(name, type_)          \
type_* name ## IteratorReset(void) {                    \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  assert(that->arr && "Array iterator uninitialised");  \
  that->idx = 0;                                        \
  if(name ## IteratorIsActive())                        \
    return name ## IteratorGet();                       \
  else                                                  \
    return NULL;                                        \
}

Reset the iterator

Output and side effect(s):

Return the first element of the iteration

#define CapyDefArrayIteratorPrev(name, type_)             \
type_* name ## IteratorPrev(void) {                       \
  name ## Iterator* that = (name ## Iterator*)capyThat;   \
  --(that->idx);                                          \
  if(name ## IteratorIsActive())                          \
    return name ## IteratorGet();                         \
  else                                                    \
    return NULL;                                          \
}

Move the iterator to the previous element

Output and side effect(s):

Return the previous element of the iteration

#define CapyDefArrayIteratorNext(name, type_)             \
type_* name ## IteratorNext(void) {                       \
  name ## Iterator* that = (name ## Iterator*)capyThat;   \
  ++(that->idx);                                          \
  if(name ## IteratorIsActive())                          \
    return name ## IteratorGet();                         \
  else                                                    \
    return NULL;                                          \
}

Move the iterator to the next element

Output and side effect(s):

Return the next element of the iteration

#define CapyDefArrayIteratorToLast(name, type_)           \
void name ## IteratorToLast(void) {                       \
  name ## Iterator* that = (name ## Iterator*)capyThat;   \
  that->idx = that->arr->size - 1;                        \
}

Move the iterator to the last element

#define CapyDefArrayIteratorIsActive(name, type)        \
bool name ## IteratorIsActive(void) {                   \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  return (that->idx < that->arr->size);                 \
}

Check if the iterator is on a valid element

Output and side effect(s):

Return true if the iterator is on a valid element, else false

#define CapyDefArrayIteratorGet(name, type_)                        \
type_* name ## IteratorGet(void) {                                  \
  name ## Iterator* that = (name ## Iterator*)capyThat;             \
  if($(that, isActive)() == false) return NULL;                     \
  switch(that->type) {                                              \
    case capyArrayIteratorType_forward:                             \
      return $(that->arr, getPtr)(that->idx);                       \
    case capyArrayIteratorType_backward:                            \
      return $(that->arr, getPtr)(that->arr->size - 1 - that->idx); \
  }                                                                 \
  return NULL;                                                      \
}

Get the current element of the iteration

Output and side effect(s):

Return a pointer to the current element

#define CapyDefArrayIteratorSetType(name, type_)           \
void name ## IteratorSetType(CapyArrayIteratorType type) { \
  name ## Iterator* that = (name ## Iterator*)capyThat;    \
  that->type = type;                                       \
  name ## IteratorReset();                                 \
}

Set the type of the iterator and reset it

Input argument(s):

type: the new type of the iterator

#define CapyDefArrayIterator(name, type)   \
  CapyDefArrayIteratorCreate(name, type)   \
  CapyDefArrayIteratorAlloc(name, type)    \
  CapyDefArrayIteratorDestruct(name, type) \
  CapyDefArrayIteratorFree(name, type)     \
  CapyDefArrayIteratorReset(name, type)    \
  CapyDefArrayIteratorPrev(name, type)     \
  CapyDefArrayIteratorNext(name, type)     \
  CapyDefArrayIteratorToLast(name, type)   \
  CapyDefArrayIteratorIsActive(name, type) \
  CapyDefArrayIteratorGet(name, type)      \
  CapyDefArrayIteratorSetType(name, type)

Definition macro calling all the submacros at once for an iterator on an array structure named 'name', containing elements of type 'type'

#define CapyDecSizedArray(name, type, size_)               \
CapyDecArrayIterator(name, type)                           \
typedef struct name {                                      \
  type data[size_];                                        \
  CapyPad(type[size_], data);                              \
  size_t size;                                             \
  size_t sizeData;                                         \
  name ## Iterator iter;                                   \
  void (*destruct)(void);                                  \
  size_t (*getSize)(void);                                 \
  void (*set)(size_t idx, type const* const val);          \
  type (*get)(size_t const idx);                           \
  type* (*getPtr)(size_t const idx);                       \
  void (*initIterator)(void);                              \
  name* (*clone)(void);                                    \
  void (*shuffle)(CapyRandom* const rnd);                  \
  void (*shuffleLemire)(CapyRandom* const rnd);            \
  void (*qsort)(CapyComparator* const cmp);                \
  type* (*getMin)(CapyComparator* const cmp);              \
  type* (*getMax)(CapyComparator* const cmp);              \
  size_t (*search)(                                        \
        type const* const val,                             \
    CapyComparator* const cmp);                            \
} name;                                                    \
name name ## Create(void);                                 \
name* name ## Alloc(void);                                 \
void name ## Destruct(void);                               \
void name ## Free(name** const that);                      \
size_t name ## GetSize(void);                              \
void name ## Set(size_t const idx, type const* const val); \
type name ## Get(size_t const idx);                        \
type* name ## GetPtr(size_t const idx);                    \
void name ## InitIterator(void);                           \
void name ## Shuffle(CapyRandom* const rnd);               \
void name ## ShuffleLemire(CapyRandom* const rnd);         \
void name ## QSort(CapyComparator* const cmp);             \
type* name ## GetMin(CapyComparator* const cmp);           \
type* name ## GetMax(CapyComparator* const cmp);           \
size_t name ## Search(                                     \
  type const* const val,CapyComparator* const cmp);        \
name* name ## Clone(void);

Fixed size generic array structure. Declaration macro for an array structure named 'name', containing 'size_' elements of type 'type'

#define CapyDefSizedArrayCreate(name, type, size_) \
name name ## Create(void) {                        \
  return (name){                                   \
    .size = size_,                                 \
    .sizeData = sizeof(type),                      \
    .destruct = name ## Destruct,                  \
    .getSize = name ## GetSize,                    \
    .set = name ## Set,                            \
    .get = name ## Get,                            \
    .initIterator = name ## InitIterator,          \
    .getPtr = name ## GetPtr,                      \
    .clone = name ## Clone,                        \
    .shuffle = name ## Shuffle,                    \
    .shuffleLemire = name ## ShuffleLemire,        \
    .qsort = name ## QSort,                        \
    .getMin = name ## GetMin,                      \
    .getMax = name ## GetMax,                      \
    .search = name ## Search,                      \
    .iter = {.arr = NULL},                         \
  };                                               \
}

Fixed size generic array structure. Definition macro and submacros for an array structure named 'name', containing 'size_' elements of type 'type' Create an array

Output and side effect(s):

Return an array containing 'size_' elements of type 'type'

#define CapyDefSizedArrayAlloc(name, type, size_) \
name* name ## Alloc(void) {                       \
  name* that = NULL;                              \
  safeMalloc(that, 1);                            \
  if(!that) return NULL;                          \
  *that = name ## Create();                       \
  that->iter = name ## IteratorCreate(            \
    that, capyArrayIteratorType_forward);         \
  return that;                                    \
}

Allocate memory for a new array and create it

Output and side effect(s):

Return an array containing 'size_' elements of type 'type'

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefSizedArrayClone(name, type, size_) \
name* name ## Clone(void) {                       \
  name* that = (name*)capyThat;                   \
  name* clone = NULL;                             \
  safeMalloc(clone, 1);                           \
  if(!clone) return NULL;                         \
  *clone = *that;                                 \
  clone->iter = name ## IteratorCreate(           \
    clone, capyArrayIteratorType_forward);        \
  return clone;                                   \
}

Clone an array

Output and side effect(s):

Return a clone of the array

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefSizedArrayDestruct(name, type, size_)       \
void name ## Destruct(void) {return;}

Free the memory used by an array.

Input argument(s):

that: the array to free

#define CapyDefSizedArrayFree(name, type, size_) \
void name ## Free(name** const that) {           \
  if(that == NULL || *that == NULL) return;      \
  $(*that, destruct)();                          \
  free(*that);                                   \
  *that = NULL;                                  \
}

Free the memory used by a pointer to an array and reset '*that' to NULL

Input argument(s):

that: a pointer to the array to free

#define CapyDefSizedArrayGetSize(name, type, size_) \
size_t name ## GetSize(void) {                      \
  return size_;                                     \
}

Get the size of the array

Output and side effect(s):

Return the size

#define CapyDefSizedArraySet(name, type, size_)             \
void name ## Set(size_t const idx, type const* const val) { \
  assert (val != NULL);                                     \
  name* that = (name*)capyThat;                             \
  that->data[idx] = *val;                                   \
}

Set an element of the array

Input argument(s):

idx: the index of the element to set
val: the value to set

#define CapyDefSizedArrayGet(name, type, size_) \
type name ## Get(size_t const idx) {            \
  name* that = (name*)capyThat;                 \
  return that->data[idx];                       \
}

Get an element of the array

Input argument(s):

idx: the index of the element to get

Output and side effect(s):

Return the element value

#define CapyDefSizedArrayGetPtr(name, type, size_) \
type* name ## GetPtr(size_t const idx) {           \
  name* that = (name*)capyThat;                    \
  return &(that->data[idx]);                       \
}

Get a pointer to an element of the array

Input argument(s):

idx: the index of the element to get

Output and side effect(s):

Return the pointer to the element

#define CapyDefSizedArrayInitIterator(name, type, size_)         \
void name ## InitIterator(void) {                                \
  name* that = (name*)capyThat;                                  \
  that->iter =                                                   \
    name ## IteratorCreate(that, capyArrayIteratorType_forward); \
}

Initialise the iterator of the array, must be called after the creation of the array when it is created with Create(), Alloc() automatically initialise the iterator.

#define CapyDefSizedArrayShuffle(name, type, size_)         \
void name ## Shuffle(CapyRandom* const rnd) {               \
  name* that = (name*)capyThat;                             \
  CapyRangeSize range = {.max = size_ - 1};                 \
  for(range.min = 0; range.min < size_ - 1; ++range.min) {  \
    size_t jElem = $(rnd, getSizeRange)(&range);            \
    if(jElem != range.min) {                                \
      type tmp = that->data[range.min];                     \
      that->data[range.min] = that->data[jElem];            \
      that->data[jElem] = tmp;                              \
    }                                                       \
  }                                                         \
}

Shuffle the array given a pseudo-random number generator. Fisher-Yates algorithm.

#define CapyDefSizedArrayShuffleLemire(name, type, size_)   \
void name ## ShuffleLemire(CapyRandom* const rnd) {         \
  name* that = (name*)capyThat;                             \
  CapyRangeUInt32 range = {.max = size_ - 1};               \
  for(range.min = 0; range.min < size_ - 1; ++range.min) {  \
    size_t jElem = $(rnd, getUInt32RangeLemire)(&range);    \
    if(jElem != range.min) {                                \
      type tmp = that->data[range.min];                     \
      that->data[range.min] = that->data[jElem];            \
      that->data[jElem] = tmp;                              \
    }                                                       \
  }                                                         \
}

Shuffle the array given a pseudo-random number generator. Fisher-Yates and Lemire algorithm. The size of the array must be less than 2^32. Faster than Shuffle.

#define CapyDefSizedArrayQSort(name, type, size_)      \
void name ## QSort(CapyComparator* const cmp) {        \
  name* that = (name*)capyThat;                        \
  if(that->size < 2) return;                           \
  CapyQuickSort(that->data, sizeof(type), size_, cmp); \
}

Sort the array using the qsort function given a comparator.

#define CapyDefSizedArrayGetMin(name, type, size_)  \
type* name ## GetMin(CapyComparator* const cmp) {   \
  name* that = (name*)capyThat;                     \
  if(that->size == 0) return NULL;                  \
  type* min = $(that, getPtr)(0);                   \
  loop(i, that->size) {                             \
    type* val = $(that, getPtr)(i);                 \
    if($(cmp, eval)(min, val) > 0) min = val;       \
  }                                                 \
  return min;                                       \
}

Return the minimum element given a comparator

#define CapyDefSizedArrayGetMax(name, type, size_) \
type* name ## GetMax(CapyComparator* const cmp) {  \
  name* that = (name*)capyThat;                    \
  if(that->size == 0) return NULL;                 \
  type* max = $(that, getPtr)(0);                  \
  loop(i, that->size) {                            \
    type* val = $(that, getPtr)(i);                \
    if($(cmp, eval)(max, val) < 0) max = val;      \
  }                                                \
  return max;                                      \
}

Return the maximum element given a comparator

#define CapyDefSizedArraySearch(name, type, size_)            \
size_t name ## Search(                                        \
  type const* const val, CapyComparator* const cmp) {         \
  name* that = (name*)capyThat;                               \
  if(that->size == 0) raiseExc(CapyExc_InvalidElemIdx);       \
  CapyRangeSize range = {.min = 0, .max = that->size - 1};    \
  while(range.min < range.max) {                              \
    size_t idx = range.min + (range.max - range.min) / 2;     \
    if(idx == range.min) idx = range.max;                     \
    type const* const v = $(that, getPtr)(idx);               \
    int ret = $(cmp, eval)(v, val);                           \
    if(ret < 0) range.min = idx + 1;                          \
    else if(ret > 0) range.max = idx - 1;                     \
    else return idx;                                          \
  }                                                           \
  type const* const v = $(that, getPtr)(range.min);           \
  int ret = $(cmp, eval)(v, val);                             \
  if(ret == 0) return range.min;                              \
  raiseExc(CapyExc_InvalidElemIdx);                           \
  return 0;                                                   \
}

Return the index of the value, searched using binary search, or raise CapyExc_InvalidElemIdx if the value is not found

#define CapyDefSizedArray(name, type, size_)        \
  CapyDefSizedArrayCreate(name, type, size_)        \
  CapyDefSizedArrayAlloc(name, type, size_)         \
  CapyDefSizedArrayClone(name, type, size_)         \
  CapyDefSizedArrayDestruct(name, type, size_)      \
  CapyDefSizedArrayFree(name, type, size_)          \
  CapyDefSizedArrayGetSize(name, type, size_)       \
  CapyDefSizedArraySet(name, type, size_)           \
  CapyDefSizedArrayGet(name, type, size_)           \
  CapyDefSizedArrayGetPtr(name, type, size_)        \
  CapyDefSizedArrayInitIterator(name, type, size_)  \
  CapyDefSizedArrayShuffle(name, type, size_)       \
  CapyDefSizedArrayShuffleLemire(name, type, size_) \
  CapyDefSizedArrayQSort(name, type, size_)         \
  CapyDefSizedArrayGetMin(name, type, size_)        \
  CapyDefSizedArrayGetMax(name, type, size_)        \
  CapyDefSizedArraySearch(name, type, size_)        \
  CapyDefArrayIterator(name, type)

Definition macro calling all the submacros at once for an array structure named 'name', containing 'size_' elements of type 'type'

#define CapyDecArray(name, type)                           \
CapyDecArrayIterator(name, type)                           \
typedef struct name {                                      \
  type* data;                                              \
  size_t size;                                             \
  size_t sizeData;                                         \
  name ## Iterator iter;                                   \
  void (*destruct)(void);                                  \
  size_t (*getSize)(void);                                 \
  void (*set)(size_t idx, type const* const val);          \
  type (*get)(size_t const idx);                           \
  type* (*getPtr)(size_t const idx);                       \
  void (*resize)(size_t const size);                       \
  void (*initIterator)(void);                              \
  name* (*clone)(void);                                    \
  void (*shuffle)(CapyRandom* const rnd);                  \
  void (*shuffleLemire)(CapyRandom* const rnd);            \
  void (*qsort)(CapyComparator* const cmp);                \
  type* (*getMin)(CapyComparator* const cmp);              \
  type* (*getMax)(CapyComparator* const cmp);              \
  size_t (*search)(                                        \
        type const* const val,                             \
    CapyComparator* const cmp);                            \
} name;                                                    \
name name ## Create(size_t const size);                    \
name* name ## Alloc(size_t const size);                    \
name* name ## Clone(void);                                 \
void name ## Destruct(void);                               \
void name ## Free(name** const that);                      \
size_t name ## GetSize(void);                              \
void name ## Set(size_t const idx, type const* const val); \
type name ## Get(size_t const idx);                        \
type name ## NoGet(size_t const idx);                      \
type* name ## GetPtr(size_t const idx);                    \
void name ## Resize(size_t const size);                    \
void name ## Shuffle(CapyRandom* const rnd);               \
void name ## ShuffleLemire(CapyRandom* const rnd);         \
void name ## QSort(CapyComparator* const cmp);             \
type* name ## GetMin(CapyComparator* const cmp);           \
type* name ## GetMax(CapyComparator* const cmp);           \
size_t name ## Search(                                     \
  type const* const val,CapyComparator* const cmp);        \
void name ## InitIterator(void);

---------------------------------------------------------------------------- Resizable generic array structure. Declaration macro for an array structure named 'name', containing elements of type 'type'

#define CapyDefArrayCreate(name, type)               \
name name ## Create_(size_t size, size_t sizeData) { \
  name that = {                                      \
    .data = NULL,                                    \
    .size = size,                                    \
    .sizeData = sizeData,                            \
    .destruct = name ## Destruct,                    \
    .getSize = name ## GetSize,                      \
    .set = name ## Set,                              \
    .get = name ## Get,                              \
    .getPtr = name ## GetPtr,                        \
    .initIterator = name ## InitIterator,            \
    .resize = name ## Resize,                        \
    .clone = name ## Clone,                          \
    .shuffle = name ## Shuffle,                      \
    .shuffleLemire = name ## ShuffleLemire,          \
    .qsort = name ## QSort,                          \
    .getMin = name ## GetMin,                        \
    .getMax = name ## GetMax,                        \
    .search = name ## Search,                        \
    .iter = {.arr = NULL},                           \
  };                                                 \
  if(size > 0) {                                     \
    that.data = malloc(sizeData * size);             \
    if(that.data == NULL)                            \
      raiseExc(CapyExc_MallocFailed);                \
  }                                                  \
  if(sizeData != sizeof(type))                       \
    that.get = name ## NoGet;                        \
  return that;                                       \
}                                                    \
name name ## Create(size_t size) {                   \
  return name ## Create_(size, sizeof(type));        \
}

Resizable generic array structure. Definition macro and submacros for an array structure named 'name', containing elements of type 'type' Create an array

Input argument(s):

size: the new size of the array, may be zero

Output and side effect(s):

Return an array containing elements of type 'type'

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefArrayAlloc(name, type)                  \
name* name ## Alloc_(size_t size, size_t sizeData) {   \
  name* that = NULL;                                   \
  safeMalloc(that, 1);                                 \
  if(!that) return NULL;                               \
  name a = name ## Create_(size, sizeData);            \
  memcpy(that, &a, sizeof(name));                      \
  name ## Iterator i = name ## IteratorCreate(         \
    that, capyArrayIteratorType_forward);              \
  memcpy(&(that->iter), &i, sizeof(name ## Iterator)); \
  return that;                                         \
}                                                      \
name* name ## Alloc(size_t size) {                     \
  return name ## Alloc_(size, sizeof(type));           \
}

Allocate memory for a new array and create it

Input argument(s):

size: the new size of the array, may be zero

Output and side effect(s):

Return an array containing elements of type 'type'

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefArrayClone(name, type)                             \
name* name ## Clone(void) {                                       \
  name* that = (name*)capyThat;                                   \
  name* clone = NULL;                                             \
  safeMalloc(clone, 1);                                           \
  if(!clone) return NULL;                                         \
  name a = name ## Create_(that->size, that->sizeData);           \
  memcpy(clone, &a, sizeof(name));                                \
  name ## Iterator i = name ## IteratorCreate(                    \
    that, capyArrayIteratorType_forward);                         \
  memcpy(&(that->iter), &i, sizeof(name ## Iterator));            \
  clone->data = malloc(that->sizeData * that->size);              \
  if(clone->data == NULL)                                         \
    raiseExc(CapyExc_MallocFailed);                               \
  else                                                            \
    memcpy(clone->data, that->data, that->sizeData * that->size); \
  return clone;                                                   \
}

Clone an array

Output and side effect(s):

Return a clone of the array

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefArrayDestruct(name, type)  \
void name ## Destruct(void) {             \
  name* that = (name*)capyThat;           \
  free(that->data);                       \
  that->data = NULL;                      \
  that->size = 0;                         \
}

Free the memory used by an array.

Input argument(s):

that: the array to free

#define CapyDefArrayFree(name, type)         \
void name ## Free(name** const that) {       \
  if(that == NULL || *that == NULL) return;  \
  $(*that, destruct)();                      \
  free(*that);                               \
  *that = NULL;                              \
}

Free the memory used by a pointer to an array and reset '*that' to NULL

Input argument(s):

that: a pointer to the array to free

#define CapyDefArrayGetSize(name, type) \
size_t name ## GetSize(void) {          \
  return ((name*)capyThat)->size;       \
}

Get the size of the array

Output and side effect(s):

Return the size

#define CapyDefArraySet(name, type)                         \
void name ## Set(size_t const idx, type const* const val) { \
  assert(val != NULL);                                      \
  name* that = (name*)capyThat;                             \
  memcpy(                                                   \
    (char*)(that->data) + idx * that->sizeData,             \
    val,                                                    \
    that->sizeData);                                        \
}

Set an element of the array

Input argument(s):

idx: the index of the element to set
val: the value to set

#define CapyDefArrayGet(name, type)                  \
type name ## Get(size_t const idx) {                 \
  return *(type*)((char*)(((name*)capyThat)->data) + \
    idx * ((name*)capyThat)->sizeData);              \
}                                                    \
type name ## NoGet(size_t const idx) {               \
  assert(false &&                                    \
    "Cannot return element of type "                 \
    CAPY_MACRO_TO_STR(type)                          \
    ", use getPtr instead.");                        \
  (void)idx;                                         \
  type nothing;                                      \
  memset(¬hing, 0, sizeof(nothing));              \
  return nothing;                                    \
}

Get an element of the array

Input argument(s):

idx: the index of the element to get

Output and side effect(s):

Return the element value

#define CapyDefArrayGetPtr(name, type)                                     \
type* name ## GetPtr(size_t const idx) {                                   \
  return (type*)(                                                          \
    (char*)(((name*)capyThat)->data) + idx * ((name*)capyThat)->sizeData); \
}

Get a pointer to an element of the array

Input argument(s):

idx: the index of the element to get

Output and side effect(s):

Return the pointer to the element

#define CapyDefArrayResize(name, type)              \
void name ## Resize(size_t const size) {            \
  name* that = (name*)capyThat;                     \
  if(size == 0)                                     \
    $(that, destruct)();                            \
  else                                              \
    safeRealloc(that->data, size * that->sizeData); \
  that->size = size;                                \
}

Resize the array. If the new size of the array is bigger than the current size, new element are not initialised. If the new size of the array is smaller than the old size, elements after the new size are lost.

Input argument(s):

size: the new size of the array, may be zero, in number of element

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefArrayInitIterator(name, type)           \
void name ## InitIterator(void) {                      \
  name* that = (name*)capyThat;                        \
  name ## Iterator i = name ## IteratorCreate(         \
    that, capyArrayIteratorType_forward);              \
  memcpy(&(that->iter), &i, sizeof(name ## Iterator)); \
}

Initialise the iterator of the array, must be called after the creation of the array when it is created with Create(), Alloc() automatically initialise the iterator.

#define CapyDefArrayShuffle(name, type)                          \
void name ## Shuffle(CapyRandom* const rnd) {                    \
  name* that = (name*)capyThat;                                  \
  CapyRangeSize range = {.min = 0, .max = that->size - 1};       \
  for(range.min = 0; range.min < that->size - 1; ++range.min) {  \
    size_t jElem = $(rnd, getSizeRange)(&range);                 \
    if(range.min != jElem) {                                     \
      char tmp[that->sizeData];                                  \
      memcpy(                                                    \
        tmp,                                                     \
        (char*)(that->data) + range.min * that->sizeData,        \
        that->sizeData);                                         \
      memcpy(                                                    \
        (char*)(that->data) + range.min * that->sizeData,        \
        (char*)(that->data) + jElem * that->sizeData,            \
        that->sizeData);                                         \
      memcpy(                                                    \
        (char*)(that->data) + jElem * that->sizeData,            \
        tmp,                                                     \
        that->sizeData);                                         \
    }                                                            \
  }                                                              \
}

Shuffle the array given a pseudo-random number generator. Fisher-Yates algorithm.

#define CapyDefArrayShuffleLemire(name, type)                    \
void name ## ShuffleLemire(CapyRandom* const rnd) {              \
  name* that = (name*)capyThat;                                  \
  CapyRangeSize range = {.min = 0, .max = that->size - 1};       \
  for(range.min = 0; range.min < that->size - 1; ++range.min) {  \
    size_t jElem = $(rnd, getSizeRange)(&range);                 \
    if(range.min != jElem) {                                     \
      char tmp[that->sizeData];                                  \
      memcpy(                                                    \
        tmp,                                                     \
        (char*)(that->data) + range.min * that->sizeData,        \
        that->sizeData);                                         \
      memcpy(                                                    \
        (char*)(that->data) + range.min * that->sizeData,        \
        (char*)(that->data) + jElem * that->sizeData,            \
        that->sizeData);                                         \
      memcpy(                                                    \
        (char*)(that->data) + jElem * that->sizeData,            \
        tmp,                                                     \
        that->sizeData);                                         \
    }                                                            \
  }                                                              \
}

Shuffle the array given a pseudo-random number generator. Fisher-Yates and Lemire algorithm. The array must be less than 2^32 in size. Faster than shuffle.

#define CapyDefArrayQSort(name, type)             \
void name ## QSort(CapyComparator* const cmp) {   \
  name* that = (name*)capyThat;                   \
  if(that->size < 2) return;                      \
  CapyQuickSort(                                  \
    that->data, that->sizeData, that->size, cmp); \
}

Sort the array using the qsort function given a comparator.

#define CapyDefArrayGetMin(name, type)            \
type* name ## GetMin(CapyComparator* const cmp) { \
  name* that = (name*)capyThat;                   \
  if(that->size == 0) return NULL;                \
  type* min = $(that, getPtr)(0);                 \
  loop(i, that->size) {                           \
    type* val = $(that, getPtr)(i);               \
    if($(cmp, eval)(min, val) > 0) min = val;     \
  }                                               \
  return min;                                     \
}

Return the minimum element given a comparator

#define CapyDefArrayGetMax(name, type)            \
type* name ## GetMax(CapyComparator* const cmp) { \
  name* that = (name*)capyThat;                   \
  if(that->size == 0) return NULL;                \
  type* max = $(that, getPtr)(0);                 \
  loop(i, that->size) {                           \
    type* val = $(that, getPtr)(i);               \
    if($(cmp, eval)(max, val) < 0) max = val;     \
  }                                               \
  return max;                                     \
}

Return the maximum element given a comparator

#define CapyDefArraySearch(name, type)                        \
size_t name ## Search(                                        \
  type const* const val, CapyComparator* const cmp) {         \
  name* that = (name*)capyThat;                               \
  if(that->size == 0) raiseExc(CapyExc_InvalidElemIdx);       \
  CapyRangeSize range = {.min = 0, .max = that->size - 1};    \
  while(range.min < range.max) {                              \
    size_t idx = range.min + (range.max - range.min) / 2;     \
    if(idx == range.min) idx = range.max;                     \
    type const* const v = $(that, getPtr)(idx);               \
    int ret = $(cmp, eval)(v, val);                           \
    if(ret < 0) range.min = idx + 1;                          \
    else if(ret > 0) range.max = idx - 1;                     \
    else return idx;                                          \
  }                                                           \
  type const* const v = $(that, getPtr)(range.min);           \
  int ret = $(cmp, eval)(v, val);                             \
  if(ret == 0) return range.min;                              \
  raiseExc(CapyExc_InvalidElemIdx);                           \
  return 0;                                                   \
}

Return the index of the value, searched using binary search, or raise CapyExc_InvalidElemIdx if the value is not found

#define CapyDefArray(name, type)        \
  CapyDefArrayCreate(name, type)        \
  CapyDefArrayAlloc(name, type)         \
  CapyDefArrayClone(name, type)         \
  CapyDefArrayDestruct(name, type)      \
  CapyDefArrayFree(name, type)          \
  CapyDefArrayGetSize(name, type)       \
  CapyDefArraySet(name, type)           \
  CapyDefArrayGet(name, type)           \
  CapyDefArrayGetPtr(name, type)        \
  CapyDefArrayResize(name, type)        \
  CapyDefArrayInitIterator(name, type)  \
  CapyDefArrayShuffle(name, type)       \
  CapyDefArrayShuffleLemire(name, type) \
  CapyDefArrayQSort(name, type)         \
  CapyDefArrayGetMin(name, type)        \
  CapyDefArrayGetMax(name, type)        \
  CapyDefArraySearch(name, type)        \
  CapyDefArrayIterator(name, type)

Definition macro calling all the submacros at once for an array structure named 'name', containing elements of type 'type'

Enumerations:

typedef enum CapyArrayIteratorType {
  capyArrayIteratorType_forward,
  capyArrayIteratorType_backward,
} CapyArrayIteratorType;

Enumeration for the types of iterator on generic array

Typedefs:

typedef struct CapyRandom CapyRandom;

Predeclaration of the Random class used by the shuffle method (can't include due to loop dependency with DistributionDiscrete)

Functions:

None.

2021-11-06
in LibCapy,
86 views