NeoMutt  2024-02-01-25-ga71e95
Teaching an old dog new tricks
DOXYGEN
Loading...
Searching...
No Matches
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.
 
#define ARRAY_HEAD(name, type)
 Define a named struct for arrays of elements of a certain type.
 
#define ARRAY_HEAD_INITIALIZER    { 0, 0, NULL }
 Static initializer for arrays.
 
#define ARRAY_INIT(head)    memset((head), 0, sizeof(*(head)))
 Initialize an array.
 
#define ARRAY_EMPTY(head)    ((head)->size == 0)
 Check if an array is empty.
 
#define ARRAY_SIZE(head)    ((head)->size)
 The number of elements stored.
 
#define ARRAY_CAPACITY(head)    ((head)->capacity)
 The number of elements the array can store without reallocation.
 
#define ARRAY_GET(head, idx)    ((head)->size > (idx) ? &(head)->entries[(idx)] : NULL)
 Return the element at index.
 
#define ARRAY_SET(head, idx, elem)
 Set an element in the array.
 
#define ARRAY_FIRST(head)    ARRAY_GET((head), 0)
 Convenience method to get the first element.
 
#define ARRAY_LAST(head)
 Convenience method to get the last element.
 
#define ARRAY_ADD(head, elem)
 Add an element at the end of the array.
 
#define ARRAY_SHRINK(head, num)    ((head)->size -= MIN((num), (head)->size))
 Mark a number of slots at the end of the array as unused.
 
#define ARRAY_ELEM_SIZE(head)    (sizeof(*(head)->entries))
 Number of bytes occupied by an element of this array.
 
#define ARRAY_RESERVE(head, num)
 Reserve memory for the array.
 
#define ARRAY_FREE(head)    (FREE(&(head)->entries), (head)->size = (head)->capacity = 0)
 Release all memory.
 
#define ARRAY_FOREACH(elem, head)    ARRAY_FOREACH_FROM_TO((elem), (head), 0, (head)->size)
 Iterate over all elements of the array.
 
#define ARRAY_FOREACH_FROM(elem, head, from)    ARRAY_FOREACH_FROM_TO((elem), (head), (from), (head)->size)
 Iterate from an index to the end.
 
#define ARRAY_FOREACH_TO(elem, head, to)    ARRAY_FOREACH_FROM_TO((elem), (head), 0, (to))
 Iterate from the beginning to an index.
 
#define ARRAY_FOREACH_FROM_TO(elem, head, from, to)
 Iterate between two indexes.
 
#define ARRAY_IDX(head, elem)    (elem - (head)->entries)
 Return the index of an element of the array.
 
#define ARRAY_REMOVE(head, elem)
 Remove an entry from the array, shifting down the subsequent entries.
 
#define ARRAY_SORT(head, fn, sdata)
 Sort an array.
 
#define ARRAY_SET_NORESERVE(head, idx, elem)
 
#define __coverity_escape__(x)   0
 
#define ARRAY_ADD_NORESERVE(head, elem)
 

Detailed Description

Linear Array data structure.

Authors
  • Pietro Cerutti
  • Richard Russon

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 40 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 47 of file array.h.

◆ ARRAY_HEAD_INITIALIZER

#define ARRAY_HEAD_INITIALIZER    { 0, 0, NULL }

Static initializer for arrays.

Definition at line 58 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 65 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 74 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 87 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 95 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 109 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:189
#define ARRAY_SET_NORESERVE(head, idx, elem)
Definition: array.h:286

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 123 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 135 of file array.h.

◆ ARRAY_LAST

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

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 144 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_ADD_NORESERVE(head, elem)
Definition: array.h:296

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 156 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 172 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 180 of file array.h.

◆ ARRAY_RESERVE

#define ARRAY_RESERVE (   head,
  num 
)
Value:
(((head)->capacity > (num)) ? \
(head)->capacity : \
&(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_ELEM_SIZE(head)
Number of bytes occupied by an element of this array.
Definition: array.h:180
#define ARRAY_HEADROOM
Additional number of elements to reserve, to prevent frequent reallocations.
Definition: array.h:40
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 189 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
0Always

Definition at line 204 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 212 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 223 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 234 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++)

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 247 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 259 of file array.h.

◆ ARRAY_REMOVE

#define ARRAY_REMOVE (   head,
  elem 
)
Value:
(memmove((elem), (elem) + 1, \
ARRAY_ELEM_SIZE((head)) * \
MAX(0, (ARRAY_SIZE((head)) - ARRAY_IDX((head), (elem)) - 1))), \
ARRAY_SHRINK((head), 1))
#define ARRAY_IDX(head, elem)
Return the index of an element of the array.
Definition: array.h:259
#define MAX(a, b)
Definition: memory.h:31

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 267 of file array.h.

◆ ARRAY_SORT

#define ARRAY_SORT (   head,
  fn,
  sdata 
)
Value:
((head)->entries && \
(mutt_qsort_r((head)->entries, ARRAY_SIZE(head), ARRAY_ELEM_SIZE(head), (fn), (sdata)), true))
void mutt_qsort_r(void *base, size_t nmemb, size_t size, sort_t compar, void *sdata)
Sort an array, where the comparator has access to opaque data rather than requiring global variables.
Definition: qsort_r.c:67

Sort an array.

Parameters
headPointer to a struct defined using ARRAY_HEAD()
fnSort function, see sort_t
sdataOpaque argument to pass to sort function

Definition at line 279 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)

Definition at line 286 of file array.h.

◆ __coverity_escape__

#define __coverity_escape__ (   x)    0

Definition at line 294 of file array.h.

◆ ARRAY_ADD_NORESERVE

#define ARRAY_ADD_NORESERVE (   head,
  elem 
)
Value:
((head)->capacity > (head)->size \
? (((head)->entries[(head)->size++] = (elem)), \
((void)__coverity_escape__(elem), true)) \
: ((void)__coverity_escape__(elem), false))
#define __coverity_escape__(x)
Definition: array.h:294

Definition at line 296 of file array.h.