Arrays

This page has been automatically translated using the Google Translate API services. We are working on improving texts. Thank you for your understanding and patience.

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowcharts; they'll be obvious. Representation Is the Essence of Programming. Frederick P. Brooks, Jr. - The Mythical Man Month.

Functions

The Array (or Vector) is a container (or collection) of elements that are stored in contiguous memory locations. This fact provides a series of advantages that make it the most used data structure and the one we should resort to in the first instance. These can be summarized in:

• Direct access O(1) to elements using pointer arithmetic, which makes the use of iterators or algorithms to retrieve information unnecessary.
• Efficient use of cache. When an array element is read, adjacent elements are probably loaded into the cache due to spatial locality.
• Many algorithms (search, sorting, etc.) require iterating or manipulating data sequentially.
• Less memory fragmentation. By reserving contiguous space, arrays tend to cause less fragmentation compared to structures that store elements in dispersed locations.

The C language provides an elementary implementation of arrays (Listing 1) that have all the advantages that we have just described, but suffer from a major deficiency: they are static. That is, they cannot grow or contract on demand; the number of elements must be previously defined, either statically (in the Stack) or dynamically (in the Heap).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

typedef struct _product_t Product;
struct _product_t
{
    type_t type;
    String *code;
    String *desc;
    Image *image;
    real32_t price;
};

// Stack memory
Product sprods[100];

// Heap memory
Product *dprods = heap_new_n(100, Product);
...
// Heap free
heap_delete_n(&dprods, 100, Product);

The ArrSt type implemented in NAppGUI is, in essence, a dynamic C array plus a series of methods to manipulate it. By dynamic we mean that the structure adjusts its size to the actual number of elements, preserving the main premise that all remain together in memory. When an Array is created, memory is reserved for a few registers (Figure 1). Later, we can add new elements at the end (typical) or insert them in any random position in case we already have data in the container. In the latter case, the rest of the elements will be moved to the right. When the number of reserved records is exceeded, the internal dynamic block will be duplicated to accommodate the new positions. Likewise, it is possible to eliminate any element from the collection, moving the rest to the left to maintain the spatial coherence of the structure. If the number of items decreases by half, the memory block will be reduced. In this way, during the life of the container, the memory will be adjusted by multiplying or dividing by 2 the number of reserved elements.

1. Create arrays

• Use arrst_create to create an array.
• Use arrst_destroy to destroy an array and its elements.
• Use arrst_new to add a new element to the array.

In (Listing 2) we have a simple example of how to create an array of type Product (Figure 2). Adding a new element using arrst_new() will return a pointer to the memory area reserved for it. It is very important to keep in mind that the content of said memory is indeterminate, so we must initialize all the fields with consistent values. Likewise, when destroying the array, we must provide a destructor (i_remove()) to correctly free the memory that our object may have reserved. The memory occupied by the object itself is managed by the container and we do not have to worry about it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

static void i_remove(Product *prod)
{
    str_destroy(&prod->code);
    str_destroy(&prod->desc);
    image_destroy(&prod->image);
}

ArrSt(Product) *products = arrst_create(Product);
Product *prod = arrst_new(products, Product);
prod->type = ekHDD;
prod->code = str_c("GTK-1050");
prod->desc = str_c("Gigabyte GeForce GTX 1050 OC 2Gb GDDR5");
prod->image = load_image("card.png");
prod->price = 573.34;
...
arrst_destroy(&products, i_remove, Product);

2. Access to elements and iteration

• Use arrst_size to get the number of elements.
• Use arrst_get to get an element.
• Use arrst_all to get all elements.
• Use arrst_foreach to loop through the elements.

As we mentioned at the beginning, accessing an element of the array is nothing more than obtaining a pointer to its memory address, calculated from a base and an offset. This allows us to get a random element using its index or get the starting address (arrst_all) and use pointer arithmetic to loop through all elements (Listing 3). This is what the arrst_foreach macro does, iterating in a more elegant way.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

uint32_t i, n = arrst_size(products, Product);
for (i = 0; i < n; ++i)
{
    const Product *prod = arrst_get_const(products, i, Product);

    // Do something
    ...
}

const Product *prod = arrst_all_const(products, Product);
for(i = 0; i < n; ++i, ++prod)
{
    // Do something
    ...
}

arrst_foreach(prod, products, Product)
    // Do something
    ...
arrst_end()

// In reverse order
arrst_forback(prod, products, Product)
    // Do something
    ...
arrst_end()

3. Array copy

Use arrst_copy to copy an array.

In the case that we want to make an exact copy of an array, we must provide a copy method that allows all the fields of an object to be correctly initialized from another already existing (Listing 4). Making an exact copy of the memory block of the original object will not be safe in case there are dynamically hosted fields (String, Image).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

static void i_copy(Product *dest, const Product *src)
{
    dest->type = src->type;
    dest->code = str_copy(src->code);
    dest->desc = str_copy(src->desc);
    dest->image = image_copy(src->image);
    dest->price = src->price;
}

ArrSt(Product) *nproducts = arrst_copy(products, i_copy, Product);
...
arrst_destroy(&nproducts, i_remove, Product);

4. Array serialization

• Use arrst_read to read an array from a Stream.
• Use arrst_write to write an array to a Stream.

Serialize is to transform a memory object into a stream of bytes (Stream) in order to send them to a certain destination through an output channel. Deserializing is the reverse process, reading a stream of bytes from an input channel and re-creating the original object in memory. In the case of arrays, the operation is reduced to (de)serializing each of its elements, as we see in (Listing 5).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

static void i_read(Stream *stm, Product *prod)
{
    prod->type = stm_read_enum(stm, type_t);
    prod->code = str_read(stm);
    prod->desc = str_read(stm);
    prod->image = image_read(stm);
    prod->price = stm_read_r32(stm);
}

static void i_write(Stream *stm, const Product *prod)
{
    stm_write_enum(stm, prod->type, type_t);
    str_write(stm, prod->code);
    str_write(stm, prod->desc);
    image_write(stm, prod->image);
    stm_write_r32(stm, prod->price);
}

ArrSt(Product) *products = arrst_read(istream, i_read, Product);
...
arrst_write(ostream, products, i_write, Product);
arrst_destroy(&products, i_remove, Product);

5. Sort and search in arrays

• Use arrst_sort to sort an array.
• Use arrst_search to search for an element in a linear O(1) way.
• Use arrst_bsearch to search for an element in a binary O(logn) way.

The usual way of using arrays will be to add elements at the end using arrst_new and then iterate over the set. This "natural" order will be sufficient in most cases, but it is possible that we need to organize the elements according to another criterion to:

• Present the information ordered by one or more fields of the structure.
• Optimize searches. To locate a certain element, there is no choice but to traverse the entire array, with linear cost O(n). But we can solve the search in logarithmic time O(logn) if the array is sorted, dramatically increasing performance especially on large sets (Figure 3).

5.1. Comparators and keys

Sort and search are two closely related concepts where keys and comparators come into play.

• Key: Set of fields of an object, normally only one, that uniquely identify it within a container (code, id, reference + size, etc.). They should be as compact and fast to process as possible (e.g. integer better than string).
• Comparator: Function that establishes an order relationship between two elements of the same type by comparing their keys, for example i_compare() in (Listing 6). They are used to organize items in containers.
• Key comparator: Compares an element with a key, using the same order relationship as the element comparator. They are used to search, where it would only be necessary to provide the key. In (Listing 7) we have a search example where we use a text string as a key, since it is enough to identify the object.

1
2
3
4
5
6

static int i_compare(const Product *p1, const Product *p2)
{
    return str_scmp(p1->code, p2->code);
}

arrst_sort(products, i_compare, Product);

In the case of arrays, searches can be optimized using arrst_bsearch() if the array has been previously sorted. If it is not ordered, we will have no choice but to use the much slower arrst_search() sequential search.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

static int i_compare_key(const Product *p1, const char_t *key)
{
    return str_cmp(p1->code, key);
}

// Element position
uint32_t pos1, pos2;

// Slow O(n)
Product *prod1 = arrst_search(products, i_compare_key, "G3900", &pos1, Product, char_t);

// Fast O(logn)
Product *prod2 = arrst_bsearch(products, i_compare_key, "G3900", &pos2, Product, char_t);

6. Insert and delete in arrays

Use arrst_insert_n to insert elements.

Use arrst_delete to delete an element.

Use arrst_clear to remove all elements.

It is not usually common to add and/or delete elements from arbitrary positions in the array, but it is possible to do so if the case arises (Listing 8).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// New element at 6th position
Product *prod = arrst_insert_n(products, 6, 1, Product);
prod->type = ekHDD;
prod->code = str_c("GTK-1050");
prod->desc = str_c("Gigabyte GeForce GTX 1050 OC 2Gb GDDR5");
prod->image = load_image("card.png");
prod->price = 573.34;

// Remove 8th element
arrst_delete(products, 8, i_remove, Product);

// Remove all (without destroy the array)
arrst_clear(products, i_remove, Product);

7. Type declaration in arrays

• Use DeclSt to declare struct and enum types.

To work correctly with user types, it is necessary to declare the macro (DeclSt(Product), DeclSt(type_t)). This will define custom functions that will perform compile-time type checking, which will help us maintain the correctness of our code (Listing 9). In the case of basic types, it is not necessary to make this declaration, nor to provide a destructor, since these basic types do not generate dynamic memory.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

typedef enum _type_t type_t;
typedef struct _product_t Product;
DeclSt(type_t);
DeclSt(Product);

ArrSt(uint32_t) *ints = arrst_create(uint32_t);
ArrSt(type_t) *types = arrst_create(type_t);
ArrSt(Product) *products = arrst_create(Product);
...
// No destructor required
arrst_destroy(&ints, NULL, uint32_t);
arrst_destroy(&types, NULL, type_t);
// Destructor required
arrst_destroy(&products, i_remove, Product);

8. Array limitations

While it is true that ArrSt is an optimal structure in terms of performance and ease of use, there are cases in which we must take special care:

• Opaque objects: If the type definition is not public, the container cannot calculate the space needed for each element, so we can only work with pointers to them. See Pointer arrays.
• Shared objects: If other structures in the model maintain pointers to the container elements, we will have Segmentation Fault problems due to the change of memory addresses when relocating the internal block of the container (Figure 4). In these cases, we must also use pointer arrays.
• Many insertions and deletions: Using arrays may not be optimal in cases where you are constantly adding or deleting elements at arbitrary positions. Each operation involves moving presumably large blocks of memory to maintain the spatial coherence of the container. Use Sets sets.

arrst_create ()

Create an empty array.

ArrSt(type)*
arrst_create(type);

Return

The new array.

Remarks

See Create arrays.

arrst_copy ()

Create a copy of an array.

ArrSt(type)*
arrst_copy(const ArrSt(type) *array,
           FPtr_scopy func_copy,
           type);

Return

The copy of the original array.

Remarks

The copy function should allocate memory to the fields that require it, but NOT to the object itself. If we pass NULL, a byte-by-byte copy of the original object will be made, which can pose an integrity risk if the elements of the array contain String or other objects that need dynamic memory. See Array copy.

arrst_read ()

Create an array by reading its contents from a Streams.

ArrSt(type)*
arrst_read(Stream *stream,
           FPtr_read_init func_read,
           type);

Return

The array readed.

Remarks

See Array serialization.

arrst_destroy ()

Destroy an array and all its elements.

void
arrst_destroy(ArrSt(type) **array,
              FPtr_remove func_remove,
              type);

Remarks

See Create arrays.

arrst_destopt ()

Destroy an array and all its elements, as long as the array object is not NULL.

void
arrst_destopt(ArrSt(type) **array,
              FPtr_remove func_remove,
              type);

arrst_clear ()

Delete the contents of the array, without destroying the container that will be left with zero elements.

void
arrst_clear(ArrSt(type) *array,
            FPtr_remove func_remove,
            type);

arrst_write ()

Write an array in a Streams (serialization).

void
arrst_write(Stream *stream,
            const ArrSt(type) *array,
            FPtr_write func_write,
            type);

Remarks

See Array serialization.

arrst_size ()

Get the number of elements in an array.

uint32_t
arrst_size(const ArrSt(type) *array,
           type);

Return

Number of elements.

arrst_get ()

Get a pointer to the item in pos position.

type*
arrst_get(ArrSt(type) *array,
          const uint32_t pos,
          type);

Return

Item Pointer.

arrst_get_const ()

Get a const pointer to the item in pos position.

const type*
arrst_get_const(const ArrSt(type) *array,
                const uint32_t pos,
                type);

Return

Item Pointer.

arrst_first ()

Gets a pointer to the first element of the array.

type*
arrst_first(ArrSt(type) *array,
            type);

Return

Item pointer.

arrst_first_const ()

Gets a const pointer to the first element of the array.

const type*
arrst_first_const(const ArrSt(type) *array,
                  type);

Return

Item pointer.

arrst_last ()

Get a pointer to the last element of the array.

type*
arrst_last(ArrSt(type) *array,
           type);

Return

Item Pointer.

arrst_last_const ()

Get a const pointer to the last element of the array.

const type*
arrst_last_const(const ArrSt(type) *array,
                 type);

Return

Item Pointer.

arrst_all ()

Get a pointer to the internal memory of the array, which gives direct access to all the elements.

type*
arrst_all(ArrSt(type) *array,
          type);

Return

Base pointer. Increasing it one by one we will iterate over the elements.

Remarks

Use arrst_foreach to iterate over all elements in a more secure and elegant way.

arrst_all_const ()

Get a const pointer to the internal memory of the array, which gives direct access to all the elements.

const type*
arrst_all_const(const ArrSt(type) *array,
                type);

Return

Base pointer. Increasing it one by one we will iterate over the elements.

Remarks

Use arrst_foreach_const to iterate over all elements in a more secure and elegant way.

arrst_new ()

Reserve space for an element at the end of the array.

type*
arrst_new(ArrSt(type) *array,
          type);

1
2
3

// arrst_new avoids the copy
Product *product = arrst_new(array, Product);
i_init_product(product, ...);

Return

Pointer to added element.

Remarks

It is slightly faster than arrst_append, especially in large structures, since it avoids copying the contents of the object. Initial memory content is indeterminate.

arrst_new0 ()

Reserve space for an element at the end of the array and initialize it to 0.

type*
arrst_new0(ArrSt(type) *array,
           type);

Return

Pointer to added element.

Remarks

Same as arrst_new but initializing all memory to 0.

arrst_new_n ()

Reserve space for multiple elements at the end of the array.

type*
arrst_new_n(ArrSt(type) *array,
            const uint32_t n,
            type);

Return

Pointer to the first element added.

Remarks

Same as arrst_new but reserving multiple elements in the same call. Initial memory content is indeterminate.

arrst_new_n0 ()

Reserve space for several elements at the end of the array, and initialize the memory to 0.

type*
arrst_new_n0(ArrSt(type) *array,
             const uint32_t n,
             type);

Return

Pointer to the first element added.

Remarks

Same as arrst_new_n but initializing all memory to 0.

arrst_prepend_n ()

Reserve space for several elements at the beginning of the array. The rest of the elements will be shifted to the right.

type*
arrst_prepend_n(ArrSt(type) *array,
                const uint32_t n,
                type);

Return

Pointer to the first inserted element.

Remarks

Initial memory content is indeterminate.

arrst_insert_n ()

Reserve space for several elements in an arbitrary position of the array.

type*
arrst_insert_n(ArrSt(type) *array,
               const uint32_t pos,
               const uint32_t n,
               type);

Return

Pointer to the first inserted element.

Remarks

Initial memory content is indeterminate.

arrst_insert_n0 ()

Reserve space for several elements at an arbitrary position in the array, and initialize the memory to 0.

type*
arrst_insert_n0(ArrSt(type) *array,
                const uint32_t pos,
                const uint32_t n,
                type);

Return

Pointer to the first inserted element.

Remarks

Same as arrst_insert_n but initializing all memory to 0.

arrst_append ()

Append an element to the end of the array.

void
arrst_append(ArrSt(type) *array,
             type value,
             type);

Remarks

Use arrst_new if possible.

arrst_prepend ()

Insert an element at the beginning of the array. The rest of the elements will be shifted to the right.

void
arrst_prepend(ArrSt(type) *array,
              type value,
              type);

Remarks

Use arrst_prepend_n if possible.

arrst_insert ()

Insert an element in an arbitrary array position.

void
arrst_insert(ArrSt(type) *array,
             const uint32_t pos,
             type value,
             type);

Remarks

Use arrst_insert_n if possible.

arrst_join ()

Join two vectors. Add all the elements of src to the end of dest.

void
arrst_join(ArrSt(type) *dest,
           const ArrSt(type) *src,
           FPtr_scopy func_copy,
           type);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

ArrSt(Product) *products = create_products(...);
ArrSt(Product) *new_products = new_products(...);

// Join without 'copy' func. Dynamic 'Product' fields will be reused.
arrst_join(products, new_products, NULL, Product);
arrst_destroy(&new_products, NULL, Product);
...
arrst_destroy(&products, i_remove, Product);

// Join with 'copy' func. Dynamic 'Product' fields will be duplicate.
arrst_join(products, new_products, i_copy, Product);
arrst_destroy(&new_products, i_remove, Product);
...
arrst_destroy(&products, i_remove, Product);

Remarks

The copy function must create dynamic memory for the fields that require it, but NOT for the object itself. See arrst_copy. If it is NULL, a byte-by-byte copy of the element will be made.

arrst_delete ()

Remove an element from the array.

void
arrst_delete(ArrSt(type) *array,
             const uint32_t pos,
             FPtr_remove func_remove,
             type);

arrst_pop ()

Remove the last element from the array.

void
arrst_pop(ArrSt(type) *array,
          FPtr_remove func_remove,
          type);

arrst_sort ()

Sort array elements using Quicksort.

void
arrst_sort(ArrSt(type) *array,
           FPtr_compare func_compare,
           type);

Remarks

See Sort and search in arrays.

arrst_sort_ex ()

Sort array elements using Quicksort and additional data.

void
arrst_sort_ex(ArrSt(type) *array,
              FPtr_compare_ex func_compare,
              type,
              dtype);

Remarks

See Sort and search in arrays.

arrst_search ()

Search for an element in the array linearly O(n).

type*
arrst_search(ArrSt(type) *array,
             FPtr_compare func_compare,
             const ktype *key,
             uint32_t *pos,
             type,
             ktype);

Return

Pointer to the first element that matches the search criteria or NULL if none exists.

Remarks

See Sort and search in arrays.

arrst_search_const ()

Const version of arrst_search.

const type*
arrst_search_const(const ArrSt(type) *array,
                   FPtr_compare func_compare,
                   const ktype *key,
                   uint32_t *pos,
                   type,
                   ktype);

Return

Pointer to element.

arrst_bsearch ()

Search for an element in the array logarithmically O(logn).

type*
arrst_bsearch(ArrSt(type) *array,
              FPtr_compare func_compare,
              const ktype *key,
              uint32_t *pos,
              type,
              ktype);

Return

Pointer to the first element that matches the search criteria or NULL if none exists.

Remarks

The array must be sorted according to the same criteria as the search. If not, the result is unpredictable. See Sort and search in arrays.

arrst_bsearch_const ()

Const version of arrst_bsearch.

const type*
arrst_bsearch_const(const ArrSt(type) *array,
                    FPtr_compare func_compare,
                    const ktype *key,
                    uint32_t *pos,
                    type,
                    ktype);

Return

Pointer to element.

arrst_foreach ()

Iterate on all array elements. Uses arrst_end to close the loop.

void
arrst_foreach(type *elem,
              ArrSt(type) *array,
              type);

1
2
3

arrst_foreach(product, array, Product)
    bstd_printf("Index:%d, Id:%d\n", product_i, product->id);
arrst_end()

arrst_foreach_const ()

Const version of arrst_foreach.

void
arrst_foreach_const(const type *elem,
                    const ArrSt(type) *array,
                    type);

arrst_forback ()

Iterate on all array elements backward, from the last to the first. Uses arrst_end to close the loop.

void
arrst_forback(type *elem,
              ArrSt(type) *array,
              type);

1
2
3
4

// Now in reverse order
arrst_forback(product, array, Product)
    bstd_printf("Index:%d, Id:%d\n", product_i, product->id);
arrst_end()

arrst_forback_const ()

Const version of arrst_forback.

void
arrst_forback_const(const type *elem,
                    const ArrSt(type) *array,
                    type);

arrst_end ()

Close the loop opened by arrst_foreach, arrst_foreach_const, arrst_forback or arrst_forback_const.

void
arrst_end(void);