Array
-----
- +-----------+--------------------+---------------------------------------+
- | Operation | Average complexity | Notes |
- +-----------+--------------------+-------------------------------------- +
- | Lookup | O(1) | |
- | Append | O(1) | unpredictable if capacity is exceeded |
- | Insert | O(n) | unpredictable if capacity is exceeded |
- | Sort | O(n log n) | |
- | Find | O(log n) | |
- +-----------+--------------------+---------------------------------------+
-
- An array is a data structure where all elements (members) have the same size and are
+ Data structure where all elements (members) have the same size and are
located consecutively in memory.
- Each array has a size which holds the number of current elements of the array.
- It also has a capacity, which is the number of elements that currently fit into
- the array, which may be bigger than size.
-
- The lookup complexity is O(1), which makes arrays well suited for fast lookups.
-
- The complexity for appending an element at the end of the array is O(1).
-
- The complexity for inserting an element at an arbitrary index of the array is O(n),
- where n is the length of the array. This is because memory may need to be moved.
-
- However, the insert/append complexity becomes unpredictable and largely depends on
- the implementation of the C library if the capacity is exceeded. If the capacity
- needs to be extended, the memory is reallocated. The mentioned complexity rules
- only apply as long as (cap > siz + 1). *Usually*, realloc will have a complexity
- of either O(1), if the memory block happens to be already big enough, or
- O(n) + X, if a new, bigger block needs to be allocated and the memory copied.
-
- Note that when the capacity is extended, it is possible to allocated more space space
- than needed, to prevent frequent calls to append/insert from having to reallocate
- the memory every time. If, and if yes how much additional space is allocated is
- determined by the extra space field. Extra space for ext elements is allocated
- whenever a growth reallocation happens.
-
- The array can be sorted. In this case, the array is expected to have a comparator cmp
- that is not NULL.
-
- The comparison function must return an integer less than, equal to, or greater than
- zero if the first argument is considered to be respectively less than, equal to,
- or greater than the second. If two members compare as equal, their order in the
- sorted array is undefined. [Copied from the Linux man-pages]
-
- The sorting function uses the quicksort algorithm from the C library, which has an
- average complexity of O(n log n).
-
- To maintain the order of a sorted array, add and put should not be used.
*/
#ifndef _DRAGONSTD_ARRAY_H_ // include guard
#include <stddef.h> // for size_t
#include <sys/types.h> // for ssize_t
-
-typedef int (*ArrayComparator)(const void *va, const void *vb);
+#include "bits/callback.h"
typedef struct {
/* public */
- void *ptr; // memory
- size_t ext; // extra space
- ArrayComparator cmp; // comparator
+ void *ptr; // memory
+ size_t ext; // extra space
/* private */
- size_t mbs; // member size
- size_t siz; // used space
- size_t cap; // available space
+ size_t mbs; // member size
+ size_t siz; // used space
+ size_t cap; // available space
} Array;
-void array_ini(Array *array, size_t mmb, size_t ext, ArrayComparator cmp);
+void array_ini(Array *array, size_t mmb, size_t ext);
/*
Initializes the array.
The array will have the member size of mmb and the extra space set to ext.
mmb should be bigger than 0 and may not be changed after the initialization.
ext can be 0 or bigger and may be changed any time.
- The comparator of the array is set to cmp and may be nil.
This function should be called before calling any other functions on the
array.
This function should not be called on an array that has been initialized before,
- unless the array either has a capacity of 0 or it has been deleted using
- array_del. Otherwise a memory leak will occur.
+ unless the array has a capacity of 0. Otherwise a memory leak will occur.
*/
void array_rlc(Array *array);
/*
Clones the array src to the array dst.
- dst is initialized to have the same configuration (member size, extra space,
- comparator) as src.
+ dst is initialized to have the same configuration (member size, extra space) as src.
After the operation, the contents of the array dst are be the same as those of src.
The size of dst and src are the same, the capacity of dst however is the same as
The array's memory is not free'd and the array can be reused.
*/
-void array_del(Array *array);
+void array_clr(Array *array);
/*
- Deletes the array.
+ Clears the array.
This function frees the arrays memory. If this is not called when the array's
reference is dropped, a memory leak occurs, unless the array is empty (capacity
of 0), in which case the function does not need to be called. The function works
fine on empty arrays however.
- After this, the array should no longer be used until reinitialized.
+ After this, the array is empty and can be reused.
*/
-void array_srt(Array *array);
+void array_srt(Array *array, Comparator cmp);
/*
Sorts the array using the quicksort algorithm.
- The array is assumed to have a non-NULL comparator.
+ Comparator must not be NULL.
Wraps the qsort C-library routine. Please refer to it's documentation.
*/
-ssize_t array_fnd(Array *array, const void *ptr, size_t *idx);
+ssize_t array_fnd(Array *array, const void *ptr, size_t *idx, Comparator cmp);
/*
Searches the sorted array for the element ptr.
Returns the index of the element, or -1 if it wasn't found.
points to. This is the index ptr would need to be inserted at to keep the order.
It is assumed that the array has been sorted by array_srt before (or was empty),
- and the order has been kept and the comparator has not been changed since.
+ and the order has been kept and the same comparator is used.
*/
-size_t array_ins(Array *array, const void *ptr);
+size_t array_ins(Array *array, const void *ptr, Comparator cmp);
/*
Inserts an element into a sorted array, keeping the order.
Returns the index the element has been inserted at.
Calls array_fnd and array_put.
It is assumed that the array has been sorted by array_srt before (or was empty),
- and the order has been kept and the comparator has not been changed since.
+ and the order has been kept and the same comparator is used.
*/
#endif // _DRAGONSTD_ARRAY_H_
projects / dragonstd.git / blobdiff