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:

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

Copyright: This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

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

name	Name of the resulting struct
type	Type 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

head	Pointer 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

true	The array is empty
false	The 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

num	Number 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

num	The 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

head	Pointer to a struct defined using ARRAY_HEAD()
idx	Index, between 0 and ARRAY_SIZE()-1

Return values

ptr	Pointer to the element at the given index
NULL	Index 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)))

Set an element in the array.

Parameters

head	Pointer to a struct defined using ARRAY_HEAD()
idx	Index, between 0 and ARRAY_SIZE()-1
elem	Element to copy

Return values

true	Element was inserted
false	Element 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

ptr	Pointer to the first element
NULL	Array 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))

Convenience method to get the last element.

Parameters

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

ptr	Pointer to the last element
NULL	Array 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)))

Add an element at the end of the array.

Parameters

head	Pointer to a struct defined using ARRAY_HEAD()
elem	Element to copy

Return values

true	Element was added
false	Element 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

head	Pointer to a struct defined using ARRAY_HEAD()
num	Number of slots to mark as unused

Return values

num	New 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

num	Number 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 :                                                      \
       ((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)))

Reserve memory for the array.

Parameters

head	Pointer to a struct defined using ARRAY_HEAD()
num	Number of elements to make room for

Return values

num	New 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

head	Pointer to a struct defined using ARRAY_HEAD()

Return values

0 Always

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

elem	Variable to be used as pointer to the element at each iteration
head	Pointer 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

elem	Variable to be used as pointer to the element at each iteration
head	Pointer to a struct defined using ARRAY_HEAD()
from	Starting 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

elem	Variable to be used as pointer to the element at each iteration
head	Pointer to a struct defined using ARRAY_HEAD()
to	Terminating 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

elem	Variable to be used as pointer to the element at each iteration
head	Pointer to a struct defined using ARRAY_HEAD()
from	Starting index (inclusive)
to	Terminating 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

head	Pointer to a struct defined using ARRAY_HEAD()
elem	Pointer to an element of the array

Return values

num	The 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))

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

Parameters

head	Pointer to a struct defined using ARRAY_HEAD()
elem	Pointer 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))

mutt_qsort_r

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

head	Pointer to a struct defined using ARRAY_HEAD()
fn	Sort function, see sort_t
sdata	Opaque 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))

Definition at line 296 of file array.h.

Macros

Detailed Description

Macro Definition Documentation

◆ ARRAY_HEADROOM

◆ ARRAY_HEAD

◆ ARRAY_HEAD_INITIALIZER

◆ ARRAY_INIT

◆ ARRAY_EMPTY

◆ ARRAY_SIZE

◆ ARRAY_CAPACITY

◆ ARRAY_GET

◆ ARRAY_SET

◆ ARRAY_FIRST

◆ ARRAY_LAST

◆ ARRAY_ADD

◆ ARRAY_SHRINK

◆ ARRAY_ELEM_SIZE

◆ ARRAY_RESERVE

◆ ARRAY_FREE

◆ ARRAY_FOREACH

◆ ARRAY_FOREACH_FROM

◆ ARRAY_FOREACH_TO

◆ ARRAY_FOREACH_FROM_TO

◆ ARRAY_IDX

◆ ARRAY_REMOVE

◆ ARRAY_SORT

◆ ARRAY_SET_NORESERVE

◆ __coverity_escape__

◆ ARRAY_ADD_NORESERVE