NeoMutt  2020-11-20
Teaching an old dog new tricks
DOXYGEN
array.h File Reference

Linear Array data structure. More...

#include <stdbool.h>
#include <string.h>
#include "memory.h"
+ Include dependency graph for array.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define ARRAY_HEADROOM   25
 Additional number of elements to reserve, to prevent frequent reallocations. More...
 
#define ARRAY_HEAD(name, type)
 Define a named struct for arrays of elements of a certain type. More...
 
#define ARRAY_HEAD_INITIALIZER   { 0, 0, NULL }
 Static initializer for arrays. More...
 
#define ARRAY_INIT(head)   memset((head), 0, sizeof(*(head)))
 Initialize an array. More...
 
#define ARRAY_EMPTY(head)   ((head)->size == 0)
 Check if an array is empty. More...
 
#define ARRAY_SIZE(head)   ((head)->size)
 The number of elements stored. More...
 
#define ARRAY_CAPACITY(head)   ((head)->capacity)
 The number of elements the array can store without reallocation. More...
 
#define ARRAY_GET(head, idx)   ((head)->size > (idx) ? &(head)->entries[(idx)] : NULL)
 Return the element at index. More...
 
#define ARRAY_SET(head, idx, elem)
 Set an element in the array. More...
 
#define ARRAY_FIRST(head)   ARRAY_GET((head), 0)
 Convenience method to get the first element. More...
 
#define ARRAY_LAST(head)
 Convenience method to get the last element. More...
 
#define ARRAY_ADD(head, elem)
 Add an element at the end of the array. More...
 
#define ARRAY_SHRINK(head, num)   ((head)->size -= MIN((num), (head)->size))
 Mark a number of slots at the end of the array as unused. More...
 
#define ARRAY_ELEM_SIZE(head)   (sizeof(*(head)->entries))
 Number of bytes occupied by an element of this array. More...
 
#define ARRAY_RESERVE(head, num)
 Reserve memory for the array. More...
 
#define ARRAY_FREE(head)   (FREE(&(head)->entries), (head)->size = (head)->capacity = 0)
 Release all memory. More...
 
#define ARRAY_FOREACH(elem, head)   ARRAY_FOREACH_FROM_TO((elem), (head), 0, (head)->size)
 Iterate over all elements of the array. More...
 
#define ARRAY_FOREACH_FROM(elem, head, from)   ARRAY_FOREACH_FROM_TO((elem), (head), (from), (head)->size)
 Iterate from an index to the end. More...
 
#define ARRAY_FOREACH_TO(elem, head, to)   ARRAY_FOREACH_FROM_TO((elem), (head), 0, (to))
 Iterate from the beginning to an index. More...
 
#define ARRAY_FOREACH_FROM_TO(elem, head, from, to)
 Iterate between two indexes. More...
 
#define ARRAY_IDX(head, elem)   (elem - (head)->entries)
 Return the index of an element of the array. More...
 
#define ARRAY_REMOVE(head, elem)
 Remove an entry from the array, shifting down the subsequent entries. More...
 
#define ARRAY_SORT(head, fn)   qsort((head)->entries, ARRAY_SIZE(head), ARRAY_ELEM_SIZE(head), (fn))
 Sort an array. More...
 
#define ARRAY_SET_NORESERVE(head, idx, elem)
 
#define ARRAY_ADD_NORESERVE(head, elem)
 

Detailed Description

Linear Array data structure.

Authors
  • Pietro Cerutti

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file array.h.

Macro Definition Documentation

◆ ARRAY_HEADROOM

#define ARRAY_HEADROOM   25

Additional number of elements to reserve, to prevent frequent reallocations.

Definition at line 36 of file array.h.

◆ ARRAY_HEAD

#define ARRAY_HEAD (   name,
  type 
)
Value:
struct name \
{ \
size_t size; \
size_t capacity; \
type *entries; \
}

Define a named struct for arrays of elements of a certain type.

Parameters
nameName of the resulting struct
typeType of the elements stored in the array

Definition at line 43 of file array.h.

◆ ARRAY_HEAD_INITIALIZER

#define ARRAY_HEAD_INITIALIZER   { 0, 0, NULL }

Static initializer for arrays.

Definition at line 54 of file array.h.

◆ ARRAY_INIT

#define ARRAY_INIT (   head)    memset((head), 0, sizeof(*(head)))

Initialize an array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()

Definition at line 61 of file array.h.

◆ ARRAY_EMPTY

#define ARRAY_EMPTY (   head)    ((head)->size == 0)

Check if an array is empty.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
trueThe array is empty
falseThe array is not empty

Definition at line 70 of file array.h.

◆ ARRAY_SIZE

#define ARRAY_SIZE (   head)    ((head)->size)

The number of elements stored.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
numNumber of elements stored
Note
Because it is possible to add elements in the middle of the array, see ARRAY_SET(), the number returned by ARRAY_SIZE() can be larger than the number of elements actually stored. Holes are filled with zero at ARRAY_RESERVE() time and are left untouched by ARRAY_SHRINK().

Definition at line 83 of file array.h.

◆ ARRAY_CAPACITY

#define ARRAY_CAPACITY (   head)    ((head)->capacity)

The number of elements the array can store without reallocation.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
numThe capacity of the array

Definition at line 91 of file array.h.

◆ ARRAY_GET

#define ARRAY_GET (   head,
  idx 
)    ((head)->size > (idx) ? &(head)->entries[(idx)] : NULL)

Return the element at index.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
idxIndex, between 0 and ARRAY_SIZE()-1
Return values
ptrPointer to the element at the given index
NULLIndex was out of bounds
Note
Because it is possible to add elements in the middle of the array, it is also possible to retrieve elements that weren't previously explicitly set. In that case, the memory returned is all zeroes.

Definition at line 105 of file array.h.

◆ ARRAY_SET

#define ARRAY_SET (   head,
  idx,
  elem 
)
Value:
(((head)->capacity > (idx) \
? true \
: ARRAY_RESERVE((head), (idx) + 1)), \
ARRAY_SET_NORESERVE((head), (idx), (elem)))
#define ARRAY_RESERVE(head, num)
Reserve memory for the array.
Definition: array.h:185
#define ARRAY_SET_NORESERVE(head, idx, elem)
Definition: array.h:277

Set an element in the array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
idxIndex, between 0 and ARRAY_SIZE()-1
elemElement to copy
Return values
trueElement was inserted
falseElement was not inserted, array was full
Note
This method has the side effect of changing the array size, if the insertion happens after the last element.

Definition at line 119 of file array.h.

◆ ARRAY_FIRST

#define ARRAY_FIRST (   head)    ARRAY_GET((head), 0)

Convenience method to get the first element.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
ptrPointer to the first element
NULLArray is empty

Definition at line 131 of file array.h.

◆ ARRAY_LAST

#define ARRAY_LAST (   head)
Value:
(ARRAY_EMPTY((head)) \
? NULL \
: ARRAY_GET((head), ARRAY_SIZE((head)) - 1))
#define ARRAY_GET(head, idx)
Return the element at index.
Definition: array.h:105
#define ARRAY_EMPTY(head)
Check if an array is empty.
Definition: array.h:70
#define ARRAY_SIZE(head)
The number of elements stored.
Definition: array.h:83

Convenience method to get the last element.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
ptrPointer to the last element
NULLArray is empty

Definition at line 140 of file array.h.

◆ ARRAY_ADD

#define ARRAY_ADD (   head,
  elem 
)
Value:
(((head)->capacity > (head)->size \
? true \
: ARRAY_RESERVE((head), (head)->size + 1)), \
ARRAY_ADD_NORESERVE((head), (elem)))
#define ARRAY_RESERVE(head, num)
Reserve memory for the array.
Definition: array.h:185
#define ARRAY_ADD_NORESERVE(head, elem)
Definition: array.h:284

Add an element at the end of the array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
elemElement to copy
Return values
trueElement was added
falseElement was not added, array was full

Definition at line 152 of file array.h.

◆ ARRAY_SHRINK

#define ARRAY_SHRINK (   head,
  num 
)    ((head)->size -= MIN((num), (head)->size))

Mark a number of slots at the end of the array as unused.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
numNumber of slots to mark as unused
Return values
numNew size of the array
Note
This method does not do any memory management and has no effect on the capacity nor the contents of the array. It is just a resize which only works downwards.

Definition at line 168 of file array.h.

◆ ARRAY_ELEM_SIZE

#define ARRAY_ELEM_SIZE (   head)    (sizeof(*(head)->entries))

Number of bytes occupied by an element of this array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
numNumber of bytes per element

Definition at line 176 of file array.h.

◆ ARRAY_RESERVE

#define ARRAY_RESERVE (   head,
  num 
)
Value:
(((head)->capacity > (num)) ? \
(head)->capacity : \
((mutt_mem_realloc(&(head)->entries, ((num) + ARRAY_HEADROOM) * ARRAY_ELEM_SIZE(head))), \
(memset((head)->entries + (head)->capacity, 0, \
((num) + ARRAY_HEADROOM - (head)->capacity) * ARRAY_ELEM_SIZE(head))), \
((head)->capacity = (num) + ARRAY_HEADROOM)))
#define ARRAY_HEADROOM
Additional number of elements to reserve, to prevent frequent reallocations.
Definition: array.h:36
#define ARRAY_ELEM_SIZE(head)
Number of bytes occupied by an element of this array.
Definition: array.h:176
void mutt_mem_realloc(void *ptr, size_t size)
Resize a block of memory on the heap.
Definition: memory.c:114

Reserve memory for the array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
numNumber of elements to make room for
Return values
numNew capacity of the array

Definition at line 185 of file array.h.

◆ ARRAY_FREE

#define ARRAY_FREE (   head)    (FREE(&(head)->entries), (head)->size = (head)->capacity = 0)

Release all memory.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
Return values
0

Definition at line 198 of file array.h.

◆ ARRAY_FOREACH

#define ARRAY_FOREACH (   elem,
  head 
)    ARRAY_FOREACH_FROM_TO((elem), (head), 0, (head)->size)

Iterate over all elements of the array.

Parameters
elemVariable to be used as pointer to the element at each iteration
headPointer to a struct defined using ARRAY_HEAD()

Definition at line 206 of file array.h.

◆ ARRAY_FOREACH_FROM

#define ARRAY_FOREACH_FROM (   elem,
  head,
  from 
)    ARRAY_FOREACH_FROM_TO((elem), (head), (from), (head)->size)

Iterate from an index to the end.

Parameters
elemVariable to be used as pointer to the element at each iteration
headPointer to a struct defined using ARRAY_HEAD()
fromStarting index (inclusive)
Note
The from index must be between 0 and ARRAY_SIZE(head)

Definition at line 217 of file array.h.

◆ ARRAY_FOREACH_TO

#define ARRAY_FOREACH_TO (   elem,
  head,
  to 
)    ARRAY_FOREACH_FROM_TO((elem), (head), 0, (to))

Iterate from the beginning to an index.

Parameters
elemVariable to be used as pointer to the element at each iteration
headPointer to a struct defined using ARRAY_HEAD()
toTerminating index (exclusive)
Note
The to index must be between 0 and ARRAY_SIZE(head)

Definition at line 228 of file array.h.

◆ ARRAY_FOREACH_FROM_TO

#define ARRAY_FOREACH_FROM_TO (   elem,
  head,
  from,
  to 
)
Value:
for (size_t ARRAY_FOREACH_IDX = (from); \
(ARRAY_FOREACH_IDX < (to)) && \
((elem) = ARRAY_GET((head), ARRAY_FOREACH_IDX)); \
ARRAY_FOREACH_IDX++)
#define ARRAY_GET(head, idx)
Return the element at index.
Definition: array.h:105

Iterate between two indexes.

Parameters
elemVariable to be used as pointer to the element at each iteration
headPointer to a struct defined using ARRAY_HEAD()
fromStarting index (inclusive)
toTerminating index (exclusive)
Note
The from and to indexes must be between 0 and ARRAY_SIZE(head); the from index must not be bigger than to index.

Definition at line 241 of file array.h.

◆ ARRAY_IDX

#define ARRAY_IDX (   head,
  elem 
)    (elem - (head)->entries)

Return the index of an element of the array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
elemPointer to an element of the array
Return values
numThe index of element in the array

Definition at line 253 of file array.h.

◆ ARRAY_REMOVE

#define ARRAY_REMOVE (   head,
  elem 
)
Value:
(memmove((elem), (elem) + 1, \
ARRAY_ELEM_SIZE((head)) * (ARRAY_SIZE((head)) - ARRAY_IDX((head), (elem)))), \
ARRAY_SHRINK((head), 1))
#define ARRAY_IDX(head, elem)
Return the index of an element of the array.
Definition: array.h:253
#define ARRAY_ELEM_SIZE(head)
Number of bytes occupied by an element of this array.
Definition: array.h:176
#define ARRAY_SIZE(head)
The number of elements stored.
Definition: array.h:83

Remove an entry from the array, shifting down the subsequent entries.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
elemPointer to the element of the array to remove

Definition at line 261 of file array.h.

◆ ARRAY_SORT

#define ARRAY_SORT (   head,
  fn 
)    qsort((head)->entries, ARRAY_SIZE(head), ARRAY_ELEM_SIZE(head), (fn))

Sort an array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
fnSort function, see sort_t

Definition at line 271 of file array.h.

◆ ARRAY_SET_NORESERVE

#define ARRAY_SET_NORESERVE (   head,
  idx,
  elem 
)
Value:
((head)->capacity > (idx) \
? (((head)->size = MAX((head)->size, ((idx) + 1))), \
((head)->entries[(idx)] = (elem)), \
true) \
: false)
#define MAX(a, b)
Definition: memory.h:30

Definition at line 277 of file array.h.

◆ ARRAY_ADD_NORESERVE

#define ARRAY_ADD_NORESERVE (   head,
  elem 
)
Value:
((head)->capacity > (head)->size \
? (((head)->entries[(head)->size++] = (elem)), \
true) \
: false)

Definition at line 284 of file array.h.