Baillehache Pascal's personal website

LibCapy - list

Generic list class.

Macros:

#define CAPY_LIST_H

#define CapyDecListIterator(name, type_)                         \
typedef struct name name;                                        \
typedef struct name ## Iterator {                                \
  size_t idx;                                                    \
  name ## Elem* curElem;                                         \
  name* list;                                                    \
  type_ datatype;                                                \
  CapyPad(type_, 0);                                             \
  CapyListIteratorType type;                                     \
  CapyPad(CapyListIteratorType, 1);                              \
  void (*destruct)(void);                                        \
  type_* (*reset)(void);                                         \
  type_* (*prev)(void);                                          \
  type_* (*next)(void);                                          \
  bool (*isActive)(void);                                        \
  type_* (*get)(void);                                           \
  void (*setType)(CapyListIteratorType type);                    \
  bool (*isFirst)(void);                                         \
  bool (*isLast)(void);                                          \
  void (*toLast)(void);                                          \
} name ## Iterator;                                              \
name ## Iterator name ## Iterator ## Create(                     \
  name* const arr, CapyListIteratorType const type);             \
name ## Iterator* name ## Iterator ## Alloc(                     \
  name* const arr, CapyListIteratorType const type);             \
void name ## Iterator ## Destruct(void);                         \
void name ## Iterator ## Free(name ## Iterator** const that);    \
type_* name ## Iterator ## Reset(void);                          \
type_* name ## Iterator ## Prev(void);                           \
type_* name ## Iterator ## Next(void);                           \
bool name ## Iterator ## IsActive(void);                         \
type_* name ## Iterator ## Get(void);                            \
bool name ## Iterator ## IsFirst(void);                          \
bool name ## Iterator ## IsLast(void);                           \
void name ## Iterator ## ToLast(void);                           \
void name ## Iterator ## SetType(CapyListIteratorType type);

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

#define CapyDefListIteratorCreate(name, type_) \
name ## Iterator name ## Iterator ## Create(   \
  name* const list,                            \
  CapyListIteratorType const type) {           \
  name ## Iterator that = {                    \
    .idx = 0,                                  \
    .curElem = NULL,                           \
    .list = list,                              \
    .type = type,                              \
    .destruct = name ## Iterator ## Destruct,  \
    .reset = name ## Iterator ## Reset,        \
    .prev = name ## Iterator ## Prev,          \
    .next = name ## Iterator ## Next,          \
    .isActive = name ## Iterator ## IsActive,  \
    .get = name ## Iterator ## Get,            \
    .setType = name ## Iterator ## SetType,    \
    .isFirst = name ## Iterator ## IsFirst,    \
    .isLast = name ## Iterator ## IsLast,      \
    .toLast = name ## Iterator ## ToLast,      \
  };                                           \
  $(&that, reset)();                           \
  return that;                                 \
}

Create an iterator on a generic list

Input argument(s):

list: the generic list on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefListIteratorAlloc(name, type_)     \
name ## Iterator* name ## Iterator ## Alloc(      \
  name* const list,                               \
  CapyListIteratorType const type) {              \
  name ## Iterator* that = NULL;                  \
  safeMalloc(that, 1);                            \
  if(!that) return NULL;                          \
  *that = name ## Iterator ## Create(list, type); \
  return that;                                    \
}

Allocate memory and create an iterator on a generic list

Input argument(s):

list: the generic list on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefListIteratorDestruct(name, type) \
void name ## Iterator ## Destruct(void) {       \
  return;                                       \
}

Free the memory used by an iterator.

Input argument(s):

that: the iterator to free

#define CapyDefListIteratorFree(name, type)                    \
void name ## Iterator ## Free(name ## Iterator** const that) { \
  if(*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 CapyDefListIteratorReset(name, type_)           \
type_* name ## Iterator ## Reset(void) {                \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  assert(that->list && "List iterator uninitialised");  \
  that->idx = 0;                                        \
  switch(that->type) {                                  \
    case capyListIteratorType_forward:                  \
      that->curElem = that->list->head;                 \
      break;                                            \
    case capyListIteratorType_backward:                 \
      that->curElem = that->list->tail;                 \
      break;                                            \
  }                                                     \
  if(name ## Iterator ## IsActive())                    \
    return name ## Iterator ## Get();                   \
  else                                                  \
    return NULL;                                        \
}

Reset the iterator

Output and side effect(s):

Return the first element of the iteration

#define CapyDefListIteratorPrev(name, type_)            \
type_* name ## Iterator ## Prev(void) {                 \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  --(that->idx);                                        \
  switch(that->type) {                                  \
    case capyListIteratorType_forward:                  \
      if(name ## Iterator ## IsActive())                \
        that->curElem = that->curElem->prev;            \
      break;                                            \
    case capyListIteratorType_backward:                 \
      if(name ## Iterator ## IsActive())                \
        that->curElem = that->curElem->next;            \
      break;                                            \
  }                                                     \
  if(name ## Iterator ## IsActive())                    \
    return name ## Iterator ## Get();                   \
  else                                                  \
    return NULL;                                        \
}

Move the iterator to the previous element

Output and side effect(s):

Return the previous element of the iteration

#define CapyDefListIteratorNext(name, type_)            \
type_* name ## Iterator ## Next(void) {                 \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  ++(that->idx);                                        \
  switch(that->type) {                                  \
    case capyListIteratorType_forward:                  \
      if(name ## Iterator ## IsActive())                \
        that->curElem = that->curElem->next;            \
      break;                                            \
    case capyListIteratorType_backward:                 \
      if(name ## Iterator ## IsActive())                \
        that->curElem = that->curElem->prev;            \
      break;                                            \
  }                                                     \
  if(name ## Iterator ## IsActive())                    \
    return name ## Iterator ## Get();                   \
  else                                                  \
    return NULL;                                        \
}

Move the iterator to the next element

Output and side effect(s):

Return the next element of the iteration

#define CapyDefListIteratorIsActive(name, type)         \
bool name ## Iterator ## IsActive(void) {               \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  return (that->curElem != NULL);                       \
}

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 CapyDefListIteratorGet(name, type_)                    \
type_* name ## Iterator ## Get(void) {                         \
  name ## Iterator* that = (name ## Iterator*)capyThat;        \
  return &(that->curElem->data);                               \
}

Get the current element of the iteration

Output and side effect(s):

Return a pointer to the current element

#define CapyDefListIteratorSetType(name, type_)               \
void name ## Iterator ## SetType(CapyListIteratorType type) { \
  name ## Iterator* that = (name ## Iterator*)capyThat;       \
  that->type = type;                                          \
  name ## Iterator ## Reset();                                \
}

Set the type of the iterator and reset it

Input argument(s):

type: the new type of the iterator

#define CapyDefListIteratorIsFirst(name, type_)                     \
bool name ## Iterator ## IsFirst(void) {                            \
  name ## Iterator* that = (name ## Iterator*)capyThat;             \
  bool ret = false;                                                 \
  switch(that->type) {                                              \
    case capyListIteratorType_forward:                              \
      ret = (that->curElem != NULL && that->curElem->prev == NULL); \
      break;                                                        \
    case capyListIteratorType_backward:                             \
      ret = (that->curElem != NULL && that->curElem->next == NULL); \
      break;                                                        \
  }                                                                 \
  return ret;                                                       \
}

Return true if the iterator is on the first element of the iteration

Output and side effect(s):

Return true or false

#define CapyDefListIteratorIsLast(name, type_)                      \
bool name ## Iterator ## IsLast(void) {                             \
  name ## Iterator* that = (name ## Iterator*)capyThat;             \
  bool ret = false;                                                 \
  switch(that->type) {                                              \
    case capyListIteratorType_forward:                              \
      ret = (that->curElem != NULL && that->curElem->next == NULL); \
      break;                                                        \
    case capyListIteratorType_backward:                             \
      ret = (that->curElem != NULL && that->curElem->prev == NULL); \
      break;                                                        \
  }                                                                 \
  return ret;                                                       \
}

Return true if the iterator is on the last element of the iteration

Output and side effect(s):

Return true or false

#define CapyDefListIteratorToLast(name, type_)                      \
void name ## Iterator ## ToLast(void) {                             \
  name ## Iterator* that = (name ## Iterator*)capyThat;             \
  switch(that->type) {                                              \
    case capyListIteratorType_forward:                              \
      that->curElem = that->list->tail;                             \
      break;                                                        \
    case capyListIteratorType_backward:                             \
      that->curElem = that->list->head;                             \
      break;                                                        \
  }                                                                 \
}

Move the iterator to the last element of the iteration

#define CapyDefListIterator(name, type)   \
  CapyDefListIteratorCreate(name, type)   \
  CapyDefListIteratorAlloc(name, type)    \
  CapyDefListIteratorDestruct(name, type) \
  CapyDefListIteratorFree(name, type)     \
  CapyDefListIteratorReset(name, type)    \
  CapyDefListIteratorPrev(name, type)     \
  CapyDefListIteratorNext(name, type)     \
  CapyDefListIteratorIsActive(name, type) \
  CapyDefListIteratorGet(name, type)      \
  CapyDefListIteratorIsFirst(name, type)  \
  CapyDefListIteratorIsLast(name, type)   \
  CapyDefListIteratorToLast(name, type)   \
  CapyDefListIteratorSetType(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 CapyDecList(name, type)                    \
typedef struct name ## Elem name ## Elem;          \
typedef struct name ## Elem {                      \
  name ## Elem* prev;                              \
  name ## Elem* next;                              \
  type data;                                       \
  CapyPad(type, 0);                                \
} name ## Elem;                                    \
CapyDecListIterator(name, type)                    \
typedef struct name {                              \
  name ## Elem* head;                              \
  name ## Elem* tail;                              \
  name ## Iterator iter;                           \
  void (*destruct)(void);                          \
  size_t (*getSize)(void);                         \
  void (*push)(type const val);                    \
  void (*add)(type const val);                     \
  type (*pop)(void);                               \
  type (*drop)(void);                              \
  type (*get)(size_t const idx);                   \
  type* (*getPtr)(size_t const idx);               \
  void (*flush)(void);                             \
  type (*getHead)(void);                           \
  type (*getTail)(void);                           \
  type* (*getPtrHead)(void);                       \
  type* (*getPtrTail)(void);                       \
  bool (*isEmpty)(void);                           \
  void (*initIterator)(void);                      \
  void (*remove)(                                  \
      CapyComparator* cmp,                         \
    type const* const elem);                       \
  type* (*find)(                                   \
      CapyComparator* cmp,                         \
    type const* const elem);                       \
} 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 ## Push(type const val);                 \
void name ## Add(type const val);                  \
type name ## Pop(void);                            \
type name ## Drop(void);                           \
type name ## Get(size_t const idx);                \
type* name ## GetPtr(size_t const idx);            \
void name ## Flush(void);                          \
type name ## GetHead(void);                        \
type name ## GetTail(void);                        \
type* name ## GetPtrHead(void);                    \
type* name ## GetPtrTail(void);                    \
bool name ## IsEmpty(void);                        \
void name ## Remove(                               \
      CapyComparator* cmp,                         \
    type const* const elem);                       \
type* name ## Find(                                \
      CapyComparator* cmp,                         \
    type const* const elem);                       \
void name ## InitIterator(void);

Generic double linked list structure. Declaration macro for a list structure named 'name', containing elements of type 'type'

#define CapyDefListCreate(name, type)     \
name name ## Create(void) {               \
  return (name){                          \
    .head = NULL,                         \
    .tail = NULL,                         \
    .destruct = name ## Destruct,         \
    .getSize = name ## GetSize,           \
    .push = name ## Push,                 \
    .add = name ## Add,                   \
    .pop = name ## Pop,                   \
    .drop = name ## Drop,                 \
    .get = name ## Get,                   \
    .getPtr = name ## GetPtr,             \
    .flush = name ## Flush,               \
    .getHead = name ## GetHead,           \
    .getTail = name ## GetTail,           \
    .getPtrHead = name ## GetPtrHead,     \
    .getPtrTail = name ## GetPtrTail,     \
    .initIterator = name ## InitIterator, \
    .isEmpty = name ## IsEmpty,           \
    .remove = name ## Remove,             \
    .find = name ## Find,                 \
  };                                      \
}

Definition macro and submacros for a list named 'name', containing elements of type 'type' Create a list containing elements of type 'type'

Output and side effect(s):

Return a list

#define CapyDefListAlloc(name, type)     \
name* name ## Alloc(void) {              \
  name* that = NULL;                     \
  safeMalloc(that, 1);                   \
  if(!that) return NULL;                 \
  *that = name ## Create();              \
  that->iter = name ## IteratorCreate(   \
    that, capyListIteratorType_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 CapyDefListDestruct(name, type)   \
void name ## Destruct(void) {             \
  name* that = (name*)capyThat;           \
  $(that, flush)();                       \
}

Free the memory used by a list.

Input argument(s):

that: the list to free

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

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

Input argument(s):

that: a pointer to the list to free

#define CapyDefListGetSize(name, type) \
size_t name ## GetSize(void) {         \
  name* that = (name*)capyThat;        \
  name ## Elem* elem = that->head;     \
  size_t size = 0;                     \
  while(elem != NULL) {                \
    ++size;                            \
    elem = elem->next;                 \
  }                                    \
  return size;                         \
}

Get the size of a list Output Return the size of the list

#define CapyDefListPush(name, type)       \
void name ## Push(type val) {             \
  name* that = (name*)capyThat;           \
  name ## Elem* elem = NULL;              \
  safeMalloc(elem, 1);                    \
  if(!elem) return;                       \
  elem->next = that->head;                \
  elem->prev = NULL;                      \
  elem->data = val;                       \
  if(that->head != NULL)                  \
    that->head->prev = elem;              \
  that->head = elem;                      \
  if(that->tail == NULL)                  \
    that->tail = elem;                    \
}

Push an element to the head of a list

Input argument(s):

val: the element's value

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefListAdd(name, type)        \
void name ## Add(type val) {              \
  name* that = (name*)capyThat;           \
  name ## Elem* elem = NULL;              \
  safeMalloc(elem, 1);                    \
  if(!elem) return;                       \
  elem->prev = that->tail;                \
  elem->next = NULL;                      \
  elem->data = val;                       \
  if(that->tail != NULL)                  \
    that->tail->next = elem;              \
  that->tail = elem;                      \
  if(that->head == NULL)                  \
    that->head = elem;                    \
}

Add an element to the tail of a list

Input argument(s):

val: the element's value

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefListPop(name, type) \
type name ## Pop(void) {           \
  name* that = (name*)capyThat;    \
  name ## Elem* elem = that->head; \
  that->head = elem->next;         \
  if(elem->next != NULL)           \
    elem->next->prev = NULL;       \
  if(that->tail == elem)           \
    that->tail = NULL;             \
  type val = elem->data;           \
  free(elem);                      \
  return val;                      \
}

Remove an element from the head of a list

Output and side effect(s):

Return the removed element's value

#define CapyDefListDrop(name, type) \
type name ## Drop(void) {           \
  name* that = (name*)capyThat;     \
  name ## Elem* elem = that->tail;  \
  that->tail = elem->prev;          \
  if(elem->prev != NULL)            \
    elem->prev->next = NULL;        \
  if(that->head == elem)            \
    that->head = NULL;              \
  type val = elem->data;            \
  free(elem);                       \
  return val;                       \
}

Remove an element from the tail of a list

Output and side effect(s):

Return the removed element's value

#define CapyDefListGet(name, type)                    \
type name ## Get(size_t const idx) {                  \
  name* that = (name*)capyThat;                       \
  name ## Elem* elem = that->head;                    \
  for(size_t i = 0; i < idx && elem != NULL; ++i)     \
    elem = elem->next;                                \
  if(elem == NULL) raiseExc(CapyExc_InvalidElemIdx);  \
  return elem->data;                                  \
}

Get the value of the element in the list at the given position

Output and side effect(s):

Return the element's value

#define CapyDefListGetPtr(name, type)                 \
type* name ## GetPtr(size_t const idx) {              \
  name* that = (name*)capyThat;                       \
  name ## Elem* elem = that->head;                    \
  for(size_t i = 0; i < idx && elem != NULL; ++i)     \
    elem = elem->next;                                \
  if(elem == NULL) raiseExc(CapyExc_InvalidElemIdx);  \
  return &(elem->data);                               \
}

Get a pointer to the value of the element in the list at the given position

Output and side effect(s):

Return the pointer to the element's value

#define CapyDefListFlush(name, type)         \
void name ## Flush(void) {                   \
  name* that = (name*)capyThat;              \
  while(that->head != NULL) $(that, pop)();  \
}

Empty the list by removing all its elements

#define CapyDefListGetHead(name, type) \
type name ## GetHead(void) {           \
  name* that = (name*)capyThat;        \
  return that->head->data;             \
}

Get the value of the element at the head of the list

Output and side effect(s):

Return the element's value

#define CapyDefListGetTail(name, type) \
type name ## GetTail(void) {           \
  name* that = (name*)capyThat;        \
  return that->tail->data;             \
}

Get the value of the element at the tail of the list

Output and side effect(s):

Return the element's value

#define CapyDefListGetPtrHead(name, type) \
type* name ## GetPtrHead(void) {          \
  name* that = (name*)capyThat;           \
  return &(that->head->data);             \
}

Get a pointer to the value of the element at the head of the list

Output and side effect(s):

Return the pointer to the element's value

#define CapyDefListGetPtrTail(name, type) \
type* name ## GetPtrTail(void) {          \
  name* that = (name*)capyThat;           \
  return &(that->tail->data);             \
}

Get a pointer to the value of the element at the tail of the list

Output and side effect(s):

Return the pointer to the element's value

#define CapyDefListIsEmpty(name, type)      \
bool name ## IsEmpty(void) {                \
  return (((name*)capyThat)->head == NULL); \
}

Check if a list is empty

Output and side effect(s):

Return true if the list is empty, else false

#define CapyDefListRemove(name, type)                    \
void name ## Remove(                                     \
    CapyComparator* cmp,                                 \
  type const* const elem) {                              \
  name* that = (name*)capyThat;                          \
  name ## Elem* ptr = that->head;                        \
  while(ptr != NULL) {                                   \
    int resCmp = $(cmp, eval)(&(ptr->data), elem);       \
    if(resCmp == 0) {                                    \
      name ## Elem* next = ptr->next;                    \
      if(ptr->prev != NULL) ptr->prev->next = ptr->next; \
      if(ptr->next != NULL) ptr->next->prev = ptr->prev; \
      if(that->head == ptr) that->head = ptr->next;      \
      if(that->tail == ptr) that->tail = ptr->prev;      \
      free(ptr);                                         \
      ptr = next;                                        \
    } else ptr = ptr->next;                              \
  }                                                      \
  $(&(that->iter), reset)();                             \
}

Remove elements from the list

Input argument(s):

cmp: comparator to find the element
elem: the element to be removed

Output and side effect(s):

All the elements in the list equal (according to the given comparator) to the given element are removed. The iterator is reset.

#define CapyDefListFind(name, type)                      \
type* name ## Find(                                      \
    CapyComparator* cmp,                                 \
  type const* const elem) {                              \
  name* that = (name*)capyThat;                          \
  name ## Elem* ptr = that->head;                        \
  while(ptr != NULL) {                                   \
    int resCmp = $(cmp, eval)(&(ptr->data), elem);       \
    if(resCmp == 0) return &(ptr->data);                 \
    ptr = ptr->next;                                     \
  }                                                      \
  return NULL;                                           \
}

Find an element in the list

Input argument(s):

cmp: comparator to find the element
elem: the element to be found

Output and side effect(s):

The first element in the list equal (according to the given comparator) to the given element is returned. If none could be found, return NULL.

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

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

#define CapyDefList(name, type)       \
  CapyDefListCreate(name, type)       \
  CapyDefListAlloc(name, type)        \
  CapyDefListDestruct(name, type)     \
  CapyDefListFree(name, type)         \
  CapyDefListGetSize(name, type)      \
  CapyDefListPush(name, type)         \
  CapyDefListAdd(name, type)          \
  CapyDefListPop(name, type)          \
  CapyDefListDrop(name, type)         \
  CapyDefListGet(name, type)          \
  CapyDefListGetPtr(name, type)       \
  CapyDefListFlush(name, type)        \
  CapyDefListGetHead(name, type)      \
  CapyDefListGetTail(name, type)      \
  CapyDefListGetPtrHead(name, type)   \
  CapyDefListGetPtrTail(name, type)   \
  CapyDefListIsEmpty(name, type)      \
  CapyDefListRemove(name, type)       \
  CapyDefListFind(name, type)         \
  CapyDefListInitIterator(name, type) \
  CapyDefListIterator(name, type)

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

Enumerations:

typedef enum CapyListIteratorType {
  capyListIteratorType_forward,
  capyListIteratorType_backward,
} CapyListIteratorType;

Enumeration for the types of iterator on generic list

Typedefs:

None.

Functions:

None.

2021-11-08
in LibCapy,
74 views