commit: 7025106aac8f8dfa8e7d5ccd7e795d59dd0ae2c6
Author: Fabian Groffen <grobian <AT> gentoo <DOT> org>
AuthorDate: Sat Jan 10 13:42:59 2026 +0000
Commit: Fabian Groffen <grobian <AT> gentoo <DOT> org>
CommitDate: Wed Jan 21 21:30:35 2026 +0000
URL: https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=7025106a
libq/array: rewrite with cleaner API
Hide internal details of the list from external consumers. Require a
flow of array_new() ... array_append() ... array_get() ... array_free()
instead of externally (stack) allocated array structures.
Ensure sorted state is administered internally, and sort as needed for
searching.
Adapt all code to use new APIs where possible.
Reflow code for 2026 codestyle, no content change
Signed-off-by: Fabian Groffen <grobian <AT> gentoo.org>
libq/array.c | 309 ++++++++++++++++++++++++++++++++++-------------------------
libq/array.h | 23 +++--
2 files changed, 194 insertions(+), 138 deletions(-)
diff --git a/libq/array.c b/libq/array.c
index 2c85eb8..69eb962 100644
--- a/libq/array.c
+++ b/libq/array.c
@@ -18,133 +18,163 @@
#define ARRAY_INC_SIZE 32
struct array_t {
- void **eles;
- size_t len;
- size_t siz;
+ void **eles;
+ size_t len;
+ size_t siz;
+ bool sorted:1;
};
/* allocates a new array */
-array *array_new(void)
+array *array_new
+(
+ void
+)
{
- return xzalloc(sizeof(array));
+ return xzalloc(sizeof(array));
}
/* frees an array without freeing any of the data stored in the array */
-void array_free(array *arr)
+void array_free
+(
+ array *arr
+)
{
- if (arr == NULL)
- return;
+ if (arr == NULL)
+ return;
- free(arr->eles);
- free(arr);
+ free(arr->eles);
+ free(arr);
}
/* frees the array and all the data pointed to by all of its elements
* if the callback free function is NULL, free() is used */
-void array_deepfree(array *arr, array_free_cb *func)
+void array_deepfree
+(
+ array *arr,
+ array_free_cb *func
+)
{
- size_t i;
+ size_t i;
- if (arr == NULL)
- return;
+ if (arr == NULL)
+ return;
- if (func == NULL)
- func = &free;
+ if (func == NULL)
+ func = &free;
- for (i = 0; i < arr->len; i++)
- func(arr->eles[i]);
+ for (i = 0; i < arr->len; i++)
+ func(arr->eles[i]);
- array_free(arr);
+ array_free(arr);
}
/* appends the given pointer to the list, no copying of data takes place
* returns the pointer */
-void *array_append(array *arr, void *data)
+void *array_append
+(
+ array *arr,
+ void *data
+)
{
- size_t n;
+ size_t n;
- if (arr == NULL)
- return NULL;
+ if (arr == NULL)
+ return NULL;
- n = arr->len++;
+ n = arr->len++;
- if (arr->len > arr->siz)
- {
- arr->siz += ARRAY_INC_SIZE;
- arr->eles = xrealloc(arr->eles, arr->siz *
sizeof(arr->eles[0]));
- }
+ if (arr->len > arr->siz)
+ {
+ arr->siz += ARRAY_INC_SIZE;
+ arr->eles = xrealloc(arr->eles, arr->siz * sizeof(arr->eles[0]));
+ }
- return arr->eles[n] = data;
+ arr->sorted = false;
+ return arr->eles[n] = data;
}
/* copies data of len bytes and appends to the array
* returns the pointer to the copied data */
-void *array_append_copy(array *arr, const void *data, size_t len)
+void *array_append_copy
+(
+ array *arr,
+ const void *data,
+ size_t len
+)
{
- void *ret = NULL;
-
- if (data != NULL &&
- len > 0)
- {
- ret = xmemdup(data, len);
- }
-
- if (array_append(arr, ret) == NULL &&
- ret != NULL)
- {
- free(ret);
- ret = NULL;
- }
-
- return ret;
+ void *ret = NULL;
+
+ if (data != NULL &&
+ len > 0)
+ ret = xmemdup(data, len);
+
+ if (array_append(arr, ret) == NULL &&
+ ret != NULL)
+ {
+ free(ret);
+ ret = NULL;
+ }
+
+ arr->sorted = false;
+ return ret;
}
/* removes the given element from the array and returns the pointer to
* the data removed from the array
* the caller should ensure the pointer is freed if necessary */
-void *array_remove(array *arr, size_t elem)
+void *array_remove
+(
+ array *arr,
+ size_t elem
+)
{
- void *ret;
-
- if (arr == NULL ||
- elem >= arr->len)
- {
- return NULL;
- }
-
- ret = arr->eles[elem];
- arr->len--;
- if (elem < arr->len)
- {
- memmove(&arr->eles[elem], &arr->eles[elem + 1],
- sizeof(arr->eles[0]) * (arr->len - elem));
- }
-
- return ret;
+ void *ret;
+
+ if (arr == NULL ||
+ elem >= arr->len)
+ return NULL;
+
+ ret = arr->eles[elem];
+ arr->len--;
+ if (elem < arr->len)
+ {
+ memmove(&arr->eles[elem], &arr->eles[elem + 1],
+ sizeof(arr->eles[0]) * (arr->len - elem));
+ }
+
+ return ret;
}
/* frees the element at offset elem and removes it from the list, if the
* callback free function is NULL, free() is used */
-void array_delete(array *arr, size_t elem, array_free_cb *func)
+void array_delete
+(
+ array *arr,
+ size_t elem,
+ array_free_cb *func
+)
{
- if (arr == NULL)
- return;
+ if (arr == NULL)
+ return;
- if (func == NULL)
- func = &free;
+ if (func == NULL)
+ func = &free;
- func(arr->eles[elem]);
+ func(arr->eles[elem]);
- (void)array_remove(arr, elem);
+ (void)array_remove(arr, elem);
}
/* returns the number of elements in use */
-size_t array_cnt(array *arr)
+size_t array_cnt
+(
+ array *arr
+)
{
- if (arr == NULL)
- return 0;
+ if (arr == NULL)
+ return 0;
- return arr->len;
+ return arr->len;
}
/* returns the element at the given offset, or NULL when no such element
@@ -152,25 +182,33 @@ size_t array_cnt(array *arr)
* note that NULL can also be returned if the element has the value of
* NULL, so if the caller wants to know the difference, it should check
* the input is sane using array_cnt() */
-void *array_get(array *arr, size_t elem)
+void *array_get
+(
+ array *arr,
+ size_t elem
+)
{
- if (arr == NULL)
- return NULL;
+ if (arr == NULL)
+ return NULL;
- if (arr->len <= elem)
- return NULL;
+ if (arr->len <= elem)
+ return NULL;
- return arr->eles[elem];
+ return arr->eles[elem];
}
/* sorts the elements in the array using the given comparator */
-void array_sort(array *arr, int (*compar)(const void *, const void *))
+void array_sort
+(
+ array *arr,
+ array_compar_cb *compar
+)
{
- if (arr != NULL &&
- arr->len > 1)
- {
- qsort(arr->eles, arr->len, sizeof(void *), compar);
- }
+ if (arr != NULL &&
+ arr->len > 1 &&
+ !arr->sorted)
+ qsort(arr->eles, arr->len, sizeof(void *), compar);
+ arr->sorted = true;
}
/* binary search over the array, returning the first element for which
@@ -182,46 +220,61 @@ void array_sort(array *arr, int (*compar)(const void *,
const void *))
* and compare the element at retoff to check if the value was found */
void *array_binsearch
(
- array *arr,
- void *needle,
- int (*compar)(const void *, const void *),
- size_t *retoff
+ array *arr,
+ void *needle,
+ array_compar_cb *compar,
+ size_t *retoff
)
{
- size_t low;
- size_t high;
- size_t elem;
- int cmp;
-
- if (arr == NULL ||
- compar == NULL)
- {
- return NULL;
- }
-
- low = 0;
- high = arr->len;
-
- while (low != high)
- {
- elem = low + ((high - low) / 2);
- cmp = compar(needle, arr->eles[elem]);
- if (cmp == 0)
- {
- if (retoff != NULL)
- *retoff = elem;
- return arr->eles[elem];
- }
- else if (cmp < 0)
- {
- high = elem;
- }
- else if (cmp > 0)
- {
- low = elem + 1;
- }
- }
-
- *retoff = 0;
- return NULL;
+ size_t low;
+ size_t high;
+ size_t elem;
+ int cmp;
+
+ if (arr == NULL ||
+ compar == NULL)
+ return NULL;
+
+ if (!arr->sorted)
+ array_sort(arr, compar);
+
+ low = 0;
+ high = arr->len;
+
+ while (low != high)
+ {
+ elem = low + ((high - low) / 2);
+ cmp = compar(&arr->eles[elem], &needle);
+ if (cmp == 0)
+ {
+ /* an array is not necessarily unique, so attempt to find the
+ * first match */
+ if (elem > low &&
+ compar(&arr->eles[elem - 1], &needle) == 0)
+ {
+ /* treat as < 0 */
+ high = elem;
+ }
+ else
+ {
+ if (retoff != NULL)
+ *retoff = elem;
+ return arr->eles[elem];
+ }
+ }
+ else if (cmp > 0)
+ {
+ high = elem;
+ }
+ else if (cmp < 0)
+ {
+ low = elem + 1;
+ }
+ }
+
+ if (retoff != NULL)
+ *retoff = 0;
+ return NULL;
}
+
+/* vim: set ts=2 sw=2 expandtab cino+=\:0 foldmethod=marker: */
diff --git a/libq/array.h b/libq/array.h
index 84f7812..6938ec7 100644
--- a/libq/array.h
+++ b/libq/array.h
@@ -14,6 +14,7 @@
typedef struct array_t array;
typedef void (array_free_cb)(void *priv);
+typedef int (array_compar_cb)(const void *l, const void *r);
array *array_new(void);
void array_free(array *arr);
@@ -24,20 +25,22 @@ void *array_remove(array *arr, size_t elem);
void array_delete(array *arr, size_t elem, array_free_cb *func);
size_t array_cnt(array *arr);
void *array_get(array *arr, size_t elem);
-void array_sort(array *arr, int (*compar)(const void *, const void *));
-void *array_binsearch(array *arr, void *needle, int (*compar)(const void *,
const void *), size_t *retoff);
+void array_sort(array *arr, array_compar_cb *func);
+void *array_binsearch(array *arr, void *needle, array_compar_cb *func, size_t
*retoff);
#define array_append_strcpy(A,S) array_append_copy(A,S,strlen(S)+1/*NUL*/)
#define array_for_each(arr, n, ele) \
- for (n = 0, ele = NULL; \
- (n < array_cnt(arr) && \
- (ele = array_get(arr, n))); \
- n++)
+ for (n = 0, ele = NULL; \
+ (n < array_cnt(arr) && \
+ (ele = array_get(arr, n))); \
+ n++)
#define array_for_each_rev(arr, n, ele) \
- for (n = array_cnt(arr), ele = NULL; \
- (n-- > 0 && \
- (ele = array_get(arr, n))); \
- /*nothing*/)
+ for (n = array_cnt(arr), ele = NULL; \
+ (n-- > 0 && \
+ (ele = array_get(arr, n))); \
+ /*nothing*/)
#endif
+
+/* vim: set ts=2 sw=2 expandtab cino+=\:0 foldmethod=marker: */
