Cross-platform C SDK logo

Cross-platform C SDK

Arrays

❮ Back
Next ❯
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

ArrSt(type)*arrst_create (...)
ArrSt(type)*arrst_copy (...)
ArrSt(type)*arrst_read (...)
voidarrst_destroy (...)
voidarrst_destopt (...)
voidarrst_clear (...)
voidarrst_write (...)
uint32_tarrst_size (...)
type*arrst_get (...)
const type*arrst_get_const (...)
type*arrst_first (...)
const type*arrst_first_const (...)
type*arrst_last (...)
const type*arrst_last_const (...)
type*arrst_all (...)
const type*arrst_all_const (...)
voidarrst_grow (...)
type*arrst_new (...)
type*arrst_new0 (...)
type*arrst_new_n (...)
type*arrst_new_n0 (...)
type*arrst_prepend_n (...)
type*arrst_insert_n (...)
voidarrst_append (...)
voidarrst_prepend (...)
voidarrst_insert (...)
voidarrst_join (...)
voidarrst_delete (...)
voidarrst_pop (...)
voidarrst_sort (...)
voidarrst_sort_ex (...)
type*arrst_search (...)
const type*arrst_search_const (...)
type*arrst_bsearch (...)
const type*arrst_bsearch_const (...)
voidarrst_foreach (...)
voidarrst_foreach_const (...)
voidarrst_forback (...)
voidarrst_forback_const (...)
voidarrst_end (void)

Being able to work with data collections is essential when designing our model. In addition to the basic types and the struct, union or class, the C language offers us the array construction, which allows to store several elements under the same variable name (Listing 1):

Listing 1: C Arrays.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
typedef struct _product_t Product;
struct _product_t
{
    type_t type;
    String *code;
    String *description;
    Image *image64;
    real32_t price;
};

DeclSt(Product);
DeclPt(Product);

uint32_t integers[100];
real32_t reals[100];
Product products[100];

Or, dynamically (Listing 2):

Listing 2: Dynamic arrays.
1
2
3
4
uint32_t n = get_n();
uint32_t *integers = heap_new_n(n, uint32_t);
real32_t *reals = heap_new_n(n, real32_t);
Product *products = heap_new_n(n, Product);

The C arrays store elements in contiguous positions of memory and, although they are very quick to consult, they lack the functionality to insert, delete, search or sort. In many cases, the data is not available when the container is created, but they are entering or leaving dynamically during the program execution, so we cannot anticipate in advance a maximum number with which to make the memory reservation. The Array type implemented in NAppGUI is, in essence, a dynamic C array and a series of methods to manipulate it. By dynamic we understand that the structure adjusts its size to the actual amount of elements, keeping the main premise that all remain in memory together.

When an Array is created, memory is reserved for a few records (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 shifted to the right. As soon as the number of reserved records is exceeded, the internal dynamic block will be doubled to accommodate the new positions. In the same way it is possible to eliminate any element of 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.

Setting an array structure to the number of items it has stored.
Figure 1: The Array adapt their internal memory to the number of elements.

1. Registers or pointers

An object of type Product, our example structure, needs 20 bytes on 32-bit systems (Figure 2). The code, description and image64 fields are pointers that point to other memory areas, where the String and Image type fields reside, dynamically reserved.

Bytes in memory representing a dynamic object.
Figure 2: Product object.

Depending on what is stored inside the container, we can use two kinds of array (Listing 3). The array of records will keep the entire object (20 bytes) inside and the array of pointers only a reference to it (4 bytes), the actual object being located in another memory address (Figure 3). Although the internal structure management is the same, access to the elements differs slightly.

Use ArrSt can slightly improve performance, thanks to spatial consistency, which reduces cache failures, and saving calls to the memory manager Arrays vs Sets comparative. But this will not always be possible, and we cannot use them in these cases:

  • Opaque objects: If the type definition is not public, the container cannot calculate the space required for each element, so we can only work with pointers to them.
  • Shared objects: If other structures of the model keep pointers to the elements of the container, we will have Segmentation Fault problems due to the change of memory addresses when relocating the internal container block (Figure 4).
  • Segmentation fault error when relocating the memory block that stores the array.
    Figure 4: Register arrays are dangerous with external references.

2. Type check

You will have noticed in (Listing 1) that two statements appear just after the definition of the struct Product: DeclSt and DeclPt. These are two macros that enable compile-time type checking, defining a custom interface in the containers for this new type (Listing 4). All things considered, they mimic the C++ template<>. DeclSt enables record containers and DeclPt pointer ones.

1
2
3
Product *p1 = arrst_new(Product);
Product *p2 = arrst_get(arrst, 5, Product);
const Product *p3 = arrst_get_const(arrst, 5, Product);

Although it is not advisable, you can dispense with the use of these macros and use the "raw" interfaces of the containers, defined in array.h and rbtree.h. In this case your code will be much less readable and you will not have compiler support.

Headers array.h and rbtree.h are not documented.

3. Constructors

When memory is reserved for an object, either in the Stack Segment as automatic variables

1
Product product;

at Heap Segment through dynamic memory

1
Product *product = heap_new(Product);

or in a container

1
Product *product = arrst_new(array, Product);

its initial content is garbage, understood as undetermined bytes. Initializing an object is assigning valid and consistent values to each field of the object (Listing 5).

Listing 5: Initializing an object Product.
1
2
3
4
5
6
7
8
static void i_init(Product *product)
{
    product->type = ekCPU;
    product->code = str_c("");
    product->description = str_c("");
    product->image64 = image_copy(gui_image(NOIMAGE_PNG));
    product->price = 0.f;
}

For its part, a constructor is an initializer that previously reserves memory dynamically to store the object (Listing 6).

Listing 6: Constructor of object Product.
1
2
3
4
5
6
static Product *i_create(void)
{
    Product *product = heap_new(Product);
    i_init(product);
    return product;
}

When we use register arrays, we will only need to initialize the object, since the space to store it has been reserved by the container itself (Listing 7). However, in pointer arrays, the memory for the object must be explicitly reserved, since the container will only save a reference.

Listing 7: Insert correctly initialized objects.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Add an item using an automatic variable (a copy is required)
Product product;
i_init(&product);
arrst_append(array, product, Product);

// Add an item directly (avoiding copying)
Product *product = arrst_new(array, Product);
i_init(product);

// Add a pointer to a newly created object on the heap
Product *product = i_create();
arrpt_append(array, product, Product);
Use arrst_new, arrst_insert_n or arrst_prepend_n whenever possible to insert into record arrays, as they avoid having to copy the object.

4. Array loops

To iterate over all the elements of the array, we can choose between two types of syntax to implement the loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
uint32_t i, n = arrst_size(arrst, Product);
for (i = 0; i < n; ++i)
{
    const Product *product = arrst_get(arrst, i, Product);

    // Do something
    ...
}

arrst_foreach(product, arrst, Product)
    // Do something
    ...
arrst_end();

// In reverse order
arrst_foreach_rev(product, arrst, Product)
    // Do something
    ...
arrst_end();

5. Copy objects

Similar to constructors, there are two methods for copying objects (Listing 8). In the first one, we generate dynamic memory for the object's fields, but not for the object itself, either because it is an automatic variable or is stored in an array of records. In the second case, we reserve dynamic memory for both the object and its elements.

Listing 8: Copying an object Product.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
static void i_copy_data(Product *dest, const Product *src)
{
    dest->type = src->type;
    dest->code = str_copy(src->code);
    dest->description = str_copy(src->description);
    dest->image64 = image_copy(src->image64);
    dest->price = src->price;
}

static Product *i_copy(const Product *product)
{
    Product *new_product = heap_new(Product);
    i_copy_data(new_product, product);
    return new_product;
}

ArrSt(Product) *arrst = arrst_copy(arrst_src, i_copy_data, Product);
ArrPt(Product) *arrpt = arrpt_copy(arrpt_src, i_copy, Product);

6. Serialization

A special case of the constructor are the readers (de-serializers). When we create an array from the content of Streams (Listing 9), we need a method capable of creating or initializing an element from the stream itself. Depending on the type of container it will be necessary to reserve memory for each item or not.

Listing 9: Reading an array from a stream.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
static void i_read_data(Stream *stm, Product *product)
{
    product->type = stm_read_enum(stm, type_t);
    product->code = str_read(stm);
    product->description = str_read(stm);
    product->image64 = image_read(stm);
    product->price = stm_read_r32(stm);
}

static Product *i_read(Stream *stream)
{
    Product *product = heap_new(Product);
    i_read_data(stream, product);
    return product;
}

ArrSt(Product) *arrst = arrst_read(i_read_data, Product);
ArrPt(Product) *arrpt = arrpt_read(i_read, Product);

In the same way we can write (serialize) the contents of an array in a write stream (Listing 10). In this case, a single write function is sufficient for both types of containers, since each one knows how to access its elements.

Listing 10: Writing an array in a stream.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
static void i_write(Stream *stm, const Product *product)
{
    stm_write_enum(stm, product->type, type_t);
    str_write(stm, product->code);
    str_write(stm, product->description);
    image_write(stm, product->image64);
    stm_write_r32(stm, product->price);
}

arrst_write(stm, arrst, i_write, Product);
arrpt_write(stm, arrpt, i_write, Product);

7. Destructors

In programming many times we are confused by the verbs: 'delete', 'destroy', 'free', 'erase', 'remove', 'clear' since they essentially mean the same thing but with subtle differences. In NAppGUI we will use one verb or another depending on concrete actions:

  • Free: Only free dynamic memory allocated to an object (Listing 11). You need a double pointer, since the object will be invalidated (=NULL) after freeing it, avoiding references to free memory areas.
  • Listing 11: Freeing the memory of an object.
    1
    2
    3
    4
    
    Product *product = heap_new(Product);
    ...
    heap_free(&product, Product);
    // product = NULL
    
  • Remove: It destroys the fields of an object, but does not free the memory of the object itself. It is the opposite of the initializer (Listing 12).
  • Listing 12: Freeing memory from object fields.
    1
    2
    3
    4
    5
    6
    7
    8
    
    static void i_remove(Product *product)
    {
        str_destroy(&product->code);
        str_destroy(&product->description);
        image_destroy(&product->image64);
    }
    
    arrst_destroy(&arrst, i_remove, Product);
    
  • Destroy: The combination of the previous two. Destroy the fields of the object and free its memory (Listing 13). It is the opposite of the constructor. Obviously, it requires a double pointer to invalidate the reference.
  • Listing 13: Free the object's memory and all its contents.
    1
    2
    3
    4
    5
    6
    7
    
    static void i_destroy(Product **product)
    {
        i_remove(*product);
        heap_free(product, Product);
    }
    
    arrpt_destroy(&arrpt, i_destroy, Product);
    
  • Delete: Delete an element from an array or other type of container (Listing 14). It may have associated a destructor or remover, although it is not mandatory.
  • Listing 14: Delete an item from a container.
    1
    2
    3
    4
    5
    6
    7
    8
    
    // Just delete.
    arrst_delete(arrst, 4, NULL, Product);
    
    // Delete and remove (arrst).
    arrst_delete(arrst, 4, i_remove, Product);
    
    // Delete and destroy (arrpt).
    arrpt_delete(arrpt, 4, i_destroy, Product);
    
  • Clear: Delete all the elements of a container, but do not destroy it, just leave it to zero (Listing 15). Like arrst_delete, optionally can free objects memory.
  • Listing 15: Clear a container, deleting all its items.
    1
    2
    3
    4
    5
    6
    7
    8
    
    // Just delete all.
    arrst_clear(arrst, NULL, Product);
    
    // Delete and remove all (arrst).
    arrst_clear(arrst, i_remove, Product);
    
    // Delete and destroy all (arrpt).
    arrpt_clear(arrpt, i_destroy, Product);
    

8. Sort and search

The usual way to use arrays will be to add elements at the end by arrst_new or arrpt_append then iterate over all. This "natural" order will be enough in most cases, but we may need to organize the elements following another criterion for:

  • Present the information ordered by one or several fields of the structure.
  • Optimize searches. To locate a certain element, there is no choice but to travel 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 in large sets (Figure 5).
  • Illustration of a dichotomous search in a set of 1000 elements.
    Figure 5: In a maximum of 10 steps we will find an element among a thousand (20 steps for a million).
  • Use the function arrst_sort, to sort an array. We will have to pass a comparison function, which will determine the order relationship (Listing 16).
  • Listing 16: Sort arrays by product code.
    1
    2
    3
    4
    5
    6
    7
    
    static int i_compare(const Product *p1, const Product *p2)
    {
        return str_scmp(p1->code, p2->code);
    }
    
    arrst_sort(arrst, i_compare, Product);
    arrpt_sort(arrpt, i_compare, Product);
    

To search for an element within an array, we must also provide a function that compares the object with a key. This key contains the search criteria and is usually smaller than the element itself. Many times it is just a simple number or a text string (Listing 17).

  • arrst_search Slow method. It will search for elements in a linear way, one by one O(n).
  • arrst_bsearch Fast method. It will search elements in logarithmic way, O(logn). The array must be sorted according to the same criteria as the search.
  • Listing 17: Search for an item by its code.
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    
    static int i_compare_key(const Product *p1, const char_t *key)
    {
        return str_cmp(p1->code, key);
    }
    
    uint32_t pos;
    Product *pr1, *pr2;
    // Slow O(n)
    pr1 = arrst_search(arrst, i_compare_key, "G3900", &pos, Product, char_t);
    
    // Fast O(logn)
    pr2 = arrst_bsearch(arrst, i_compare_key, "G3900", &pos, Product, char_t);
    

9. Arrays of basic types

The basic types are a particular case of single-field structure, so we will use it ArrSt. In the specific case of enum we must create an alias by typedef, as ArrSt(type) does not support the keyword enum, just as does not support struct keyword. In C++ this alias is not necessary. When destroying the array we will pass NULL to the destructor parameter, since the basic types do not generate dynamic memory.

1
2
3
4
5
typedef enum _type_t type_t;
ArrSt(uint32_t) *integers = arrst_create(uint32_t);
ArrSt(type_t) *types = arrst_create(type_t);
arrst_destroy(&integers, NULL, uint32_t);
arrst_destroy(&types, NULL, type_t);

arrst_create ()

Create an empty array.

ArrSt(type)*
arrst_create(type);
type

Object type.

Return

The new array.


arrst_copy ()

Create a copy of an array.

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

The original array.

func_copy

Function that must copy the fields of each object.

type

Object type.

Return

The copy of the original array.

Remarks

The copy function must 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 may pose an integrity risk if the array elements contain String or other objects that need dynamic memory.


arrst_read ()

Create an array by reading its contents from a Streams (de-serialization).

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

A read stream.

func_read

Function to initialize an object from the data obtained from a stream. This function should not reserve memory for the object itself (the container already does). Serialization.

type

Object type.

Return

The array readed.


arrst_destroy ()

Destroy an array and all its elements.

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

The array. It will be set to NULL after destruction.

func_remove

Function that must free the memory associated with the object's fields, but not the object itself Destructors. If NULL only the array will be destroyed and not the internal content of the elements.

type

Object type.


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);
array

The array.

func_remove

See arrst_destroy.

type

Object 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);
array

The array.

func_remove

Remove function. See arrst_destroy.

type

Object type.


arrst_write ()

Write an array in a Streams (serialization).

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

A write stream.

array

The array.

func_write

Function that writes the content of an element in a stream Serialization.

type

Object type.


arrst_size ()

Get the number of elements in an array.

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

The array.

type

Object 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);
array

The array.

pos

Item position or index.

type

Object 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);
array

The array.

pos

Item position or index.

type

Object type.

Return

Item Pointer.


arrst_first ()

Gets a pointer to the first element of the array.

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

The array.

type

Object 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);
array

The array.

type

Object type.

Return

Item pointer.


arrst_last ()

Get a pointer to the last element of the array.

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

The array.

type

Object 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);
array

The array.

type

Object 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);
array

The array.

type

Object 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);
array

The array.

type

Object 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_grow ()

Add n elements, not initialized, at the end of the array.

void
arrst_grow(ArrSt(type) *array,
           const uint32_t n,
           type);
array

The array.

n

Number of items to add.

type

Object type.


arrst_new ()

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

type*
arrst_new(ArrSt(type) *array,
          type);
1
2
3
4
5
6
7
8
// arrst_append copies 'product'
Product product;
i_init_product(&product, ...);
arrst_append(array, product, Product);

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

The array.

type

Object type.

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);
array

The array.

type

Object 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);
array

The array.

n

Number of elements to add.

type

Object 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 them to 0.

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

The array.

n

Number of elements to add.

type

Object 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);
array

The array.

n

Number of elements to insert.

type

Object 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);
array

The array.

pos

Position where it will be inserted. The current element in pos and following will be shifted to the right.

n

Number of elements to insert.

type

Object type.

Return

Pointer to the first inserted element.

Remarks

Initial memory content is indeterminate.


arrst_append ()

Append an element to the end of the array.

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

The array.

value

Item to add.

type

Object type.


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);
array

The array.

value

Item to insert.

type

Object type.


arrst_insert ()

Insert an element in an arbitrary array position.

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

The array.

pos

Position where it will be inserted. The current item in pos and following will be shifted to the right.

value

Item to insert.

type

Object type.


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_data, Product);
arrst_destroy(&new_products, i_remove, Product);
...
arrst_destroy(&products, i_remove, Product);
dest

The destination array.

src

The array whose elements will be added to dest.

func_copy

Object copy function.

type

Object type.

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);
array

The array.

pos

Position of the item to be deleted. The current item in pos+1 and following will be shifted to the left.

func_remove

'Remove' function. See arrst_destroy.

type

Object type.


arrst_pop ()

Remove the last element from the array.

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

The array.

func_remove

'Remove' function. See arrst_destroy.

type

Object type.


arrst_sort ()

Sort array elements using Quicksort.

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

The array.

func_compare

Function to compare two elements. Sort and search.

type

Object type.


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);
array

The array.

func_compare

Function to compare two elements using an additional data.

type

Object type.

dtype

Type of data in the comparison function.


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);
1
2
3
uint32_t pos;
uint32_t key = 345;
Product *product = arrst_search(arrst, i_compare_key, &key, &pos, Product, uint32_t);
array

The array.

func_compare

Comparison function. The first parameter is the element, the second the search key. Sort and search.

key

Search key. Pointer to a data type that may be different from the type of array element.

pos

Position of the element in the array (if it exists), or UINT32_MAX if it does not exist. Can be NULL.

type

Object type.

ktype

Key type.

Return

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


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);
array

The array.

func_compare

Comparison function.

key

Search key.

pos

Position of the element in the array.

type

Object type.

ktype

Key type.

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);
array

The array.

func_compare

Comparison function. The first parameter is the element, the second the search key. Sort and search.

key

Search key. Pointer to a data type that may be different from the type of array element.

pos

Position of the element in the array (if it exists), or UINT32_MAX if it does not exist. Can be NULL.

type

Object type.

ktype

Key type.

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.


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);
array

The array.

func_compare

Comparison function.

key

Seach key.

pos

Element position in array.

type

Object type.

ktype

Key type.

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()
elem

Name of the 'element' variable within the loop. Adding the suffix '_i' we get the index.

array

The array.

type

Object type.


arrst_foreach_const ()

Const version of arrst_foreach.

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

Element.

array

The array.

type

Object 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()
elem

Name of the 'element' variable within the loop. Adding the suffix '_i' we get the index.

array

The array.

type

Object type.


arrst_forback_const ()

Const version of arrst_forback.

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

Element.

array

The array.

type

Object type.


arrst_end ()

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

void
arrst_end(void);
❮ Back
Next ❯