From: Gustavo Sverzut Barbieri <barbi...@profusion.mobi>
Array with configurable member size and optimized operations such as
binary search and insert sorted.
---
.gitignore | 1 +
Makefile.am | 11 +-
ell/array.c | 758 +++++++++++++++++++++++++++++++++++++++++++++++++++++
ell/array.h | 92 +++++++
ell/ell.h | 1 +
unit/test-array.c | 262 ++++++++++++++++++
6 files changed, 1122 insertions(+), 3 deletions(-)
create mode 100644 ell/array.c
create mode 100644 ell/array.h
create mode 100644 unit/test-array.c
diff --git a/.gitignore b/.gitignore
index 3d88ef7..81c83c7 100644
--- a/.gitignore
+++ b/.gitignore
@@ -37,6 +37,7 @@ unit/test-settings
unit/test-netlink
unit/test-dbus
unit/test-dbus-message
+unit/test-array
doc/*.bak
doc/*.stamp
diff --git a/Makefile.am b/Makefile.am
index ffac42e..e822cd8 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -18,7 +18,8 @@ pkginclude_HEADERS = ell/ell.h ell/util.h \
ell/checksum.h \
ell/netlink.h \
ell/dbus.h \
- ell/idle.h
+ ell/idle.h \
+ ell/array.h
lib_LTLIBRARIES = ell/libell.la
@@ -38,7 +39,8 @@ ell_libell_la_SOURCES = $(include_HEADERS) ell/private.h \
ell/checksum.c \
ell/netlink.c \
ell/dbus.c \
- ell/idle.c
+ ell/idle.c \
+ ell/array.c
ell_libell_la_LDFLAGS = -version-info 0:0:0
@@ -58,7 +60,8 @@ noinst_PROGRAMS = unit/test-unit unit/test-queue \
unit/test-main unit/test-io \
unit/test-plugin unit/test-checksum \
unit/test-settings unit/test-netlink \
- unit/test-dbus unit/test-dbus-message
+ unit/test-dbus unit/test-dbus-message \
+ unit/test-array
unit_test_unit_LDADD = ell/libell-private.la
@@ -86,6 +89,8 @@ unit_test_dbus_LDADD = ell/libell-private.la
unit_test_dbus_message_LDADD = ell/libell-private.la
+unit_test_array_LDADD = ell/libell-private.la
+
noinst_LTLIBRARIES += unit/example-plugin.la
unit_example_plugin_la_LDFLAGS = -no-undefined -module -avoid-version \
diff --git a/ell/array.c b/ell/array.c
new file mode 100644
index 0000000..53c7517
--- /dev/null
+++ b/ell/array.c
@@ -0,0 +1,758 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2012 ProFUSION embedded systems. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation.
+ *
+ * This library 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "util.h"
+#include "array.h"
+#include "private.h"
+
+/**
+ * SECTION:array
+ * @short_description: Array support
+ *
+ * Array support
+ */
+
+static void init_array(struct l_array *array, unsigned int member_size,
unsigned int step)
+{
+ array->member_size = member_size;
+ array->len = 0;
+ array->max = 0;
+ array->step = (step > 0) ? step : 32;
+ array->members = NULL;
+}
+
+static void clear_array(struct l_array *array, l_array_destroy_func_t destroy)
+{
+ if (destroy) {
+ uint8_t *itr, *itr_end;
+
+ itr = array->members;
+ itr_end = itr + array->len * array->member_size;
+ for (; itr < itr_end; itr += array->member_size)
+ destroy(itr);
+ }
+
+ l_free(array->members);
+}
+
+static bool resize_array(struct l_array *array, unsigned int new_size)
+{
+ unsigned int new_max;
+
+ if (new_size < array->max)
+ return true;
+
+ if (new_size % array->step == 0)
+ new_max = new_size;
+ else
+ new_max = ((new_size / array->step) + 1) * array->step;
+
+ array->members = l_realloc(array->members,
+ new_max * array->member_size);
+ array->max = new_max;
+ return true;
+}
+
+static inline void __attribute__ ((always_inline)) array_swap(struct l_array
*array, void *a, void *b, void *tmp)
+{
+ if (a == b)
+ return;
+ memcpy(tmp, a, array->member_size);
+ memcpy(a, b, array->member_size);
+ memcpy(b, tmp, array->member_size);
+}
+
+static inline void *__attribute__ ((always_inline))get_member(const struct
l_array *array, unsigned int position)
+{
+ unsigned int offset = position * array->member_size;
+ return (uint8_t *)array->members + offset;
+}
+
+static int lookup(const struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data)
+{
+ const uint8_t *itr, *itr_end;
+ unsigned int sz;
+
+ sz = array->member_size;
+ itr = array->members;
+ itr_end = itr + array->len * sz;
+ for (; itr < itr_end; itr += sz) {
+ if (function(data, itr, user_data) == 0) {
+ unsigned int offset = itr - (uint8_t*)array->members;
+ return offset / sz;
+ }
+ }
+
+ return -1;
+}
+
+static unsigned int lookup_sorted_near(const struct l_array *array,
+ const void *data,
+ l_array_compare_func_t function,
+ void *user_data, int *cmp)
+{
+ unsigned int start, last, middle;
+
+ if (array->len == 0) {
+ *cmp = -1;
+ return 0;
+ } else if (array->len == 1) {
+ *cmp = function(data, array->members, user_data);
+ return 0;
+ }
+
+ start = 0;
+ last = array->len - 1; /* inclusive */
+ do {
+ void *p;
+ middle = start + (last - start) / 2; /* avoid overflow */
+ p = get_member(array, middle);
+ *cmp = function(data, p, user_data);
+ if (*cmp == 0)
+ return middle;
+ else if (*cmp > 0)
+ start = middle + 1;
+ else if (middle > 0)
+ last = middle - 1;
+ else
+ break;
+ } while (start <= last);
+ return middle;
+}
+
+/**
+ * l_array_new:
+ * @member_size: size of each member in the array.
+ * @step: when resizing the array, do this using the following extra amount.
+ *
+ * Create a new array. If the @step is 0, then a safe default is chosen.
+ *
+ * No error handling is needed since. In case of real memory allocation
+ * problems abort() will be called.
+ *
+ * Returns: a newly allocated #l_array object
+ */
+LIB_EXPORT struct l_array *l_array_new(unsigned int member_size, unsigned int
step)
+{
+ struct l_array *ret;
+
+ if (member_size == 0)
+ return NULL;
+
+ ret = l_new(struct l_array, 1);
+ init_array(ret, member_size, step);
+ return ret;
+}
+
+/**
+ * l_array_destroy:
+ * @array: array object
+ * @destroy: destroy function
+ *
+ * Free array and call @destory on all remaining members.
+ *
+ * The data given to @destory is the member memory, just free its
+ * members as the member itself is managed by the array.
+ */
+LIB_EXPORT void l_array_destroy(struct l_array *array,
+ l_array_destroy_func_t destroy)
+{
+ if (unlikely(!array))
+ return;
+
+ clear_array(array, destroy);
+ l_free(array);
+}
+
+/**
+ * l_array_init:
+ * @array: array object to initialize.
+ * @member_size: size of each member in the array.
+ * @step: when resizing the array, do this using the following extra amount.
+ *
+ * Initialize array. If the @step is 0, then a safe default is chosen.
+ *
+ * This is useful for arrays inlined into other structures or
+ * allocated at stack.
+ */
+LIB_EXPORT void l_array_init(struct l_array *array,
+ unsigned int member_size, unsigned int step)
+{
+ if (unlikely(!array))
+ return;
+ if (member_size == 0)
+ return;
+ init_array(array, member_size, step);
+}
+
+/**
+ * l_array_clear:
+ * @array: array object
+ * @destroy: destroy function
+ *
+ * Free members and call @destory on all remaining entries.
+ **/
+LIB_EXPORT void l_array_clear(struct l_array *array,
+ l_array_destroy_func_t destroy)
+{
+ if (unlikely(!array))
+ return;
+ clear_array(array, destroy);
+ array->len = 0;
+ array->max = 0;
+ array->members = NULL;
+}
+
+/**
+ * l_array_append:
+ * @array: array object
+ * @data: data to be copied at the end
+ *
+ * Copies the given pointer contents at the end of the array. The
+ * pointer is not referenced, instead it's contents is copied to the
+ * members array using the previously defined #member_size.
+ *
+ * See also l_array_insert_at().
+ *
+ * Returns: the index of the new member or -1 on errors.
+ **/
+LIB_EXPORT int l_array_append(struct l_array *array, const void *data)
+{
+ void *p;
+
+ if (unlikely(!array))
+ return -1;
+
+ if (!resize_array(array, array->len + 1))
+ return -1;
+
+ p = get_member(array, array->len);
+ memcpy(p, data, array->member_size);
+
+ array->len++;
+ return array->len - 1;
+}
+
+/**
+ * l_array_insert:
+ * @array: array object
+ * @data: data to be copied
+ * @function: compare function
+ * @user_data: user data given to compare function
+ *
+ * Copies the given pointer contents at the array position defined by
+ * given compare @function. The pointer is not referenced, instead
+ * it's contents is copied to the members array using the previously
+ * defined #member_size.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself, do no change it.
+ *
+ * If you're keeping a sorted array see l_array_insert_sorted().
+ *
+ * Returns: the index of the new member or -1 on errors.
+ **/
+LIB_EXPORT int l_array_insert(struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data)
+{
+ const uint8_t *itr, *itr_end;
+ unsigned int sz;
+
+ if (unlikely(!array))
+ return -1;
+
+ sz = array->member_size;
+ itr = array->members;
+ itr_end = itr + array->len * sz;
+ for (; itr < itr_end; itr += sz) {
+ unsigned int offset, position;
+ int cmp = function(itr, data, user_data);
+ if (cmp <= 0)
+ continue;
+
+ offset = itr - (uint8_t *)array->members;
+ position = offset / sz;
+ if (!l_array_insert_at(array, position, data))
+ return -1;
+ return position;
+ }
+ return l_array_append(array, data);
+}
+
+/**
+ * l_array_insert_sorted:
+ * @array: array object
+ * @data: data to be copied
+ * @function: compare function
+ * @user_data: user data given to compare function
+ *
+ * Copies the given pointer contents at the array position defined by
+ * given compare @function. The pointer is not referenced, instead
+ * it's contents is copied to the members array using the previously
+ * defined #member_size.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself, do no change it.
+ *
+ * This variation will optimize insertion position assuming the array
+ * is already sorted by doing binary search.
+ *
+ * Returns: the index of the new member or -1 on errors.
+ **/
+LIB_EXPORT int l_array_insert_sorted(struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data)
+{
+ unsigned int pos;
+ int cmp;
+
+ if (unlikely(!array))
+ return -1;
+
+ pos = lookup_sorted_near(array, data, function, user_data, &cmp);
+ if (cmp > 0)
+ pos++;
+
+ if (!l_array_insert_at(array, pos, data))
+ return -1;
+ return pos;
+}
+
+/**
+ * l_array_remove:
+ * @array: array object
+ * @data: data to be found and removed
+ *
+ * Find data in the array and remove it. Data may be an existing
+ * member of array (then optimized) or the contents will be matched
+ * using memcmp().
+ *
+ * See also l_array_pop() and l_array_remove_at().
+ *
+ * Returns: the index of the removed member or -1 on errors.
+ **/
+LIB_EXPORT int l_array_remove(struct l_array *array, const void *data)
+{
+ const uint8_t *itr, *itr_end;
+ unsigned int position, sz;
+
+ if (unlikely(!array))
+ return -1;
+
+ sz = array->member_size;
+ if (data >= array->members && data < get_member(array, array->len)) {
+ unsigned int offset = (uint8_t*)data - (uint8_t*)array->members;
+ position = offset / sz;
+ goto found;
+ }
+
+ itr = array->members;
+ itr_end = itr + array->len * sz;
+ for (; itr < itr_end; itr += sz) {
+ if (memcmp(data, itr, sz) == 0) {
+ unsigned int offset = itr - (uint8_t*)array->members;
+ position = offset / sz;
+ goto found;
+ }
+ }
+ return -1;
+
+found:
+ if (!l_array_remove_at(array, position))
+ return -1;
+ return position;
+}
+
+/**
+ * l_array_pop:
+ * @array: array object
+ *
+ * Removes the last member of the array.
+ *
+ * Returns: the index of the removed member or -1 on errors.
+ **/
+LIB_EXPORT int l_array_pop(struct l_array *array)
+{
+ if (unlikely(!array))
+ return -1;
+ if (array->len == 0)
+ return -1;
+ if (!resize_array(array, array->len - 1))
+ return -1;
+ array->len--;
+ return array->len + 1;
+}
+
+/**
+ * l_array_get_at:
+ * @array: array object
+ * @position: member position
+ *
+ * Gets the member given its position in the array. It is a pointer to
+ * its current memory, then it can be invalidated with functions that
+ * changes the array such as l_array_append(), l_array_insert_at() or
+ * l_array_remove_at() or variants.
+ *
+ * See also l_array_lookup() and l_array_lookup_sorted().
+ *
+ * Returns: pointer to current member memory.
+ */
+LIB_EXPORT void *l_array_get_at(const struct l_array *array, unsigned int
position)
+{
+ if (unlikely(!array))
+ return NULL;
+ if (unlikely(position >= array->len))
+ return NULL;
+ return get_member(array, position);
+}
+
+/**
+ * l_array_insert_at:
+ * @array: array object
+ * @position: where to insert the member
+ * @data: data to be copied at position
+ *
+ * Copies the given pointer contents at the given @position in the
+ * array. The pointer is not referenced, instead it's contents is
+ * copied to the members array using the previously defined
+ * #member_size.
+ *
+ * All the members from @position to the end of the array are shifted
+ * to the end.
+ *
+ * If @position is equal to the end of the array (equals to
+ * l_array_length()), then the member is appended.
+ *
+ * If @position is bigger than the array length, it will fail.
+ *
+ * Returns: the index of the new member or -1 on errors.
+ **/
+LIB_EXPORT bool l_array_insert_at(struct l_array *array,
+ unsigned int position, const void *data)
+{
+ unsigned int sz;
+ uint8_t *p;
+
+ if (unlikely(!array))
+ return false;
+ if (unlikely(position > array->len))
+ return false;
+
+ if (!resize_array(array, array->len + 1))
+ return false;
+
+ p = get_member(array, position);
+
+ sz = array->member_size;
+ if (array->len > position)
+ memmove(p + sz, p, (array->len - position) * sz);
+ memcpy(p, data, sz);
+
+ array->len++;
+ return true;
+}
+
+/**
+ * l_array_remove:
+ * @array: array object
+ * @position: position to be removed.
+ *
+ * The member is removed from array and any members after it are moved
+ * towards the array head.
+ *
+ * See also l_array_pop() and l_array_remove().
+ *
+ * Returns: #true when member has been removed and #false in case of failure.
+ **/
+LIB_EXPORT bool l_array_remove_at(struct l_array *array, unsigned int position)
+{
+ if (unlikely(!array))
+ return false;
+ if (unlikely(position >= array->len))
+ return false;
+
+ if (position + 1 < array->len) {
+ unsigned int sz = array->member_size;
+ uint8_t *p = get_member(array, position);
+ memmove(p, p + sz, (array->len - position - 1) * sz);
+ }
+
+ resize_array(array, array->len - 1);
+ array->len--;
+ return true;
+}
+
+/**
+ * l_array_reverse:
+ * @array: array object
+ *
+ * Reverse members in the array.
+ */
+LIB_EXPORT void l_array_reverse(struct l_array *array)
+{
+ size_t sz;
+ uint8_t *fwd, *rev, *fwd_end;
+ void *tmp;
+
+ if (unlikely(!array))
+ return;
+
+ if (array->len < 2)
+ return;
+
+ sz = array->member_size;
+
+ tmp = l_malloc(sz);
+
+ fwd = array->members;
+ fwd_end = fwd + (array->len / 2) * sz;
+
+ rev = fwd + (array->len - 1) * sz;
+
+ for (; fwd < fwd_end; fwd += sz, rev -= sz)
+ array_swap(array, fwd, rev, tmp);
+
+ l_free(tmp);
+}
+
+static unsigned int array_partition(struct l_array *array,
+ unsigned int start, unsigned int last,
+ unsigned int pivot,
+ l_array_compare_func_t function,
+ void *user_data,
+ void *buf)
+{
+ const unsigned sz = array->member_size;
+ uint8_t *itr, *itr_end, *p;
+ void *pivot_value = buf;
+ void *swap_tmp = (uint8_t *)buf + sz;
+
+ p = get_member(array, pivot);
+
+ memcpy(pivot_value, p, sz);
+ array_swap(array, p, get_member(array, last), swap_tmp);
+
+ p = get_member(array, start);
+ itr = get_member(array, start);
+ itr_end = itr + (last - start) * sz;
+ for (; itr < itr_end; itr += sz) {
+ if (function(itr, pivot_value, user_data) < 0) {
+ array_swap(array, itr, p, swap_tmp);
+ p += sz;
+ }
+ }
+ array_swap(array, p, get_member(array, last), swap_tmp);
+
+ return (p - (uint8_t *)array->members) / sz;
+}
+
+static void array_sort(struct l_array *array,
+ unsigned int start, unsigned int last,
+ l_array_compare_func_t function, void *user_data,
+ void *buf)
+{
+ unsigned int pivot, new_pivot;
+
+ if (last <= start)
+ return;
+
+ pivot = start + (last - start) / 2; /* avoid overflow */
+ new_pivot = array_partition(array, start, last, pivot,
+ function, user_data, buf);
+
+ if (start + 1 < new_pivot)
+ array_sort(array, start, new_pivot - 1,
+ function, user_data, buf);
+
+ if (new_pivot + 1 < last)
+ array_sort(array, new_pivot + 1, last,
+ function, user_data, buf);
+}
+
+/**
+ * l_array_sort:
+ * @array: array object
+ * @function: compare function
+ * @user_data: user data given to compare function
+ *
+ * Applies quick sort to the @array.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself, do no change it.
+ */
+LIB_EXPORT void l_array_sort(struct l_array *array,
+ l_array_compare_func_t function, void *user_data)
+{
+ unsigned int start, last;
+ void *buf;
+
+ if (unlikely(!array))
+ return;
+
+ start = 0;
+ last = array->len - 1; /* inclusive */
+
+ buf = l_malloc(array->member_size * 2);
+ array_sort(array, start, last, function, user_data, buf);
+ l_free(buf);
+}
+
+/**
+ * l_array_lookup:
+ * @array: array object
+ * @function: compare function
+ * @user_data: user data given to compare function
+ *
+ * Walks array linearly looking for given data as compared by @function.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself, do no change it.
+ *
+ * See also l_array_lookup_sorted().
+ *
+ * Returns: the member index or -1 if not found.
+ */
+LIB_EXPORT int l_array_lookup(const struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data)
+{
+ if (unlikely(!array))
+ return -1;
+ return lookup(array, data, function, user_data);
+}
+
+/**
+ * l_array_lookup_sorted:
+ * @array: array object
+ * @function: compare function
+ * @user_data: user data given to compare function
+ *
+ * Uses binary search for given data as compared by @function.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself, do no change it.
+ *
+ * Returns: the member index or -1 if not found.
+ */
+LIB_EXPORT int l_array_lookup_sorted(const struct l_array *array, const void
*data,
+ l_array_compare_func_t function, void *user_data)
+{
+ unsigned int pos;
+ int cmp;
+
+ if (unlikely(!array))
+ return -1;
+
+ pos = lookup_sorted_near(array, data, function, user_data, &cmp);
+ if (cmp == 0)
+ return pos;
+ return -1;
+}
+
+/**
+ * l_array_foreach:
+ * @array: array object
+ * @function: callback function
+ * @user_data: user data given to callback function
+ *
+ * Call @function for every given data in @array.
+ *
+ * The data given to @function are the pointer to member memory
+ * itself.
+ */
+LIB_EXPORT void l_array_foreach(const struct l_array *array,
+ l_array_foreach_func_t function, void *user_data)
+{
+ uint8_t *itr, *itr_end;
+
+ if (unlikely(!array))
+ return;
+ if (unlikely(!function))
+ return;
+
+ itr = array->members;
+ itr_end = itr + array->len * array->member_size;
+ for (; itr < itr_end; itr += array->member_size)
+ function(itr, user_data);
+}
+
+/**
+ * l_array_foreach:
+ * @array: array object
+ * @function: callback function
+ * @user_data: user data given to callback function
+ *
+ * Remove all entries in the @array where @function returns #true.
+ *
+ * Returns: number of removed entries
+ */
+LIB_EXPORT unsigned int l_array_foreach_remove(struct l_array *array,
+ l_array_remove_func_t function, void *user_data)
+{
+ unsigned int i = 0, count = 0;
+
+ if (unlikely(!array))
+ return 0;
+
+ while (i < array->len) {
+ void *p = get_member(array, i);
+ if (function(p, user_data) == false) {
+ i++;
+ continue;
+ }
+
+ l_array_remove_at(array, i);
+ count++;
+ }
+
+ return count;
+}
+
+/**
+ * l_array_length:
+ * @array: array object
+ *
+ * Returns: entries of the array
+ **/
+LIB_EXPORT unsigned int l_array_length(const struct l_array *array)
+{
+ if (unlikely(!array))
+ return 0;
+
+ return array->len;
+}
+
+/**
+ * l_array_isempty:
+ * @array: array object
+ *
+ * Returns: #true if @array is empty and #false is not
+ **/
+LIB_EXPORT bool l_array_isempty(const struct l_array *array)
+{
+ if (unlikely(!array))
+ return true;
+
+ return array->len == 0;
+}
diff --git a/ell/array.h b/ell/array.h
new file mode 100644
index 0000000..f18d9fe
--- /dev/null
+++ b/ell/array.h
@@ -0,0 +1,92 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2012 ProFUSION embedded systems. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation.
+ *
+ * This library 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifndef __ELL_ARRAY_H
+#define __ELL_ARRAY_H
+
+#include <stdbool.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef void (*l_array_foreach_func_t) (void *value, void *user_data);
+typedef void (*l_array_destroy_func_t) (void *value);
+typedef int (*l_array_compare_func_t) (const void *a, const void *b,
+ void *user_data);
+typedef bool (*l_array_remove_func_t) (void *data, void *user_data);
+
+struct l_array {
+ unsigned int member_size;
+ unsigned int len;
+ unsigned int max;
+ unsigned int step;
+ void *members;
+};
+
+struct l_array *l_array_new(unsigned int member_size, unsigned int step);
+void l_array_destroy(struct l_array *array,
+ l_array_destroy_func_t destroy);
+
+void l_array_init(struct l_array *array,
+ unsigned int member_size, unsigned int step);
+void l_array_clear(struct l_array *array,
+ l_array_destroy_func_t destroy);
+
+int l_array_append(struct l_array *array, const void *data);
+int l_array_insert(struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data);
+int l_array_insert_sorted(struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data);
+int l_array_remove(struct l_array *array, const void *data);
+int l_array_pop(struct l_array *array);
+
+void *l_array_get_at(const struct l_array *array, unsigned int position);
+bool l_array_insert_at(struct l_array *array,
+ unsigned int position, const void *data);
+bool l_array_remove_at(struct l_array *array, unsigned int position);
+
+void l_array_reverse(struct l_array *array);
+void l_array_sort(struct l_array *array,
+ l_array_compare_func_t function, void *user_data);
+int l_array_lookup(const struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data);
+int l_array_lookup_sorted(const struct l_array *array, const void *data,
+ l_array_compare_func_t function, void *user_data);
+
+void l_array_foreach(const struct l_array *array,
+ l_array_foreach_func_t function, void *user_data);
+unsigned int l_array_foreach_remove(struct l_array *array,
+ l_array_remove_func_t function, void *user_data);
+
+unsigned int l_array_length(const struct l_array *array);
+bool l_array_isempty(const struct l_array *array);
+
+#define L_ARRAY_FOREACH(array, itr) \
+ for (itr = array->members; \
+ itr < ((typeof(*itr)*)array->members) + array->len; \
+ itr++)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __ELL_ARRAY_H */
diff --git a/ell/ell.h b/ell/ell.h
index f62c554..1ac8904 100644
--- a/ell/ell.h
+++ b/ell/ell.h
@@ -22,6 +22,7 @@
#include <ell/util.h>
#include <ell/test.h>
#include <ell/queue.h>
+#include <ell/array.h>
#include <ell/hashmap.h>
#include <ell/string.h>
#include <ell/main.h>
diff --git a/unit/test-array.c b/unit/test-array.c
new file mode 100644
index 0000000..24d9e07
--- /dev/null
+++ b/unit/test-array.c
@@ -0,0 +1,262 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2012 ProFUSION embedded systems. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * 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, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdio.h>
+#include <assert.h>
+
+#include <ell/ell.h>
+
+static void test_basic(const void *test_data)
+{
+ const int test_members = 5;
+ struct l_array *array;
+ int i, pos, *member;
+ const struct spec {
+ int pos, value;
+ } *s, specs[] = {
+ {test_members, 1234},
+ {5, 0x1337},
+ {0, 0xbeef},
+ {-1, -1}
+ };
+
+ array = l_array_new(sizeof(int), 2);
+ assert(array);
+
+ for (i = 0; i < test_members; i++) {
+ pos = l_array_append(array, &i);
+ assert(pos == i);
+ }
+ assert(l_array_length(array) == (unsigned)test_members);
+
+ for (i = 0; i < test_members; i++) {
+ member = l_array_get_at(array, i);
+ assert(*member == i);
+ }
+
+ for (s = specs; s->pos >= 0; s++) {
+ assert(l_array_insert_at(array, s->pos, &s->value));
+
+ for (i = 0; i < s->pos; i++) {
+ member = l_array_get_at(array, i);
+ assert(*member == i);
+ }
+ member = l_array_get_at(array, s->pos);
+ assert(*member == s->value);
+ for (i = s->pos + 1; i < test_members + 1; i++) {
+ member = l_array_get_at(array, i);
+ assert(*member == i - 1);
+ }
+
+ assert(l_array_remove_at(array, s->pos));
+ for (i = 0; i < test_members; i++) {
+ member = l_array_get_at(array, i);
+ assert(*member == i);
+ }
+ }
+
+ l_array_destroy(array, NULL);
+}
+
+static const short rand_numbers[] = {
+ 9, 0, 2, 3, 6, 5, 4, 7, 8, 1, 10
+};
+static const int numbers_count = sizeof(rand_numbers)/sizeof(rand_numbers[0]);
+
+static void show_sort_array(const struct l_array *array)
+{
+ int i, len = l_array_length(array);
+ printf("array with %d members:\n", len);
+ for (i = 0; i < len; i++) {
+ short *member = l_array_get_at(array, i);
+ printf("\tarray[%2d]=%5hd\n", i, *member);
+ }
+}
+
+static bool check_short_sorted(const struct l_array *array)
+{
+ int i;
+ for (i = 0; i < numbers_count; i++) {
+ short *member = l_array_get_at(array, i);
+ if (*member != (short)i) {
+ show_sort_array(array);
+ fprintf(stderr, "not sorted at %d: %hd\n", i, *member);
+ return false;
+ }
+ }
+ return true;
+}
+
+static int short_cmp(const void *pa, const void *pb, void *user_data)
+{
+ const short *a = pa, *b = pb;
+ return *a - *b;
+}
+
+static void test_insert_sort(const void *test_data)
+{
+ struct l_array *array;
+ int i, pos;
+
+ array = l_array_new(sizeof(short), 1);
+ assert(array);
+
+ /* insert sorted and already sorted sequence */
+ for (i = 0; i < numbers_count; i++) {
+ short val = i;
+ pos = l_array_insert(array, &val, short_cmp, NULL);
+ assert(pos == (int)val);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = i;
+ pos = l_array_insert_sorted(array, &val, short_cmp, NULL);
+ assert(pos == (int)val);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ /* insert sorted the reverse sequence */
+ for (i = 0; i < numbers_count; i++) {
+ short val = numbers_count - i - 1;
+ pos = l_array_insert(array, &val, short_cmp, NULL);
+ assert(pos == 0);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = numbers_count - i - 1;
+ pos = l_array_insert_sorted(array, &val, short_cmp, NULL);
+ assert(pos == 0);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ /* insert sorted random numbers */
+ for (i = 0; i < numbers_count; i++) {
+ short val = rand_numbers[i];
+ l_array_insert(array, &val, short_cmp, NULL);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = rand_numbers[i];
+ l_array_insert_sorted(array, &val, short_cmp, NULL);
+ }
+ assert(check_short_sorted(array));
+ l_array_clear(array, NULL);
+
+ l_array_destroy(array, NULL);
+}
+
+static void test_sort(const void *test_data)
+{
+ struct l_array *array;
+ int i;
+
+ array = l_array_new(sizeof(short), 1);
+ assert(array);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = rand_numbers[i];
+ l_array_append(array, &val);
+ }
+ l_array_sort(array, short_cmp, NULL);
+ assert(check_short_sorted(array));
+ l_array_destroy(array, NULL);
+}
+
+static void test_reverse(const void *test_data)
+{
+ struct l_array *array;
+ int i;
+
+ array = l_array_new(sizeof(short), 1);
+ assert(array);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = i;
+ l_array_append(array, &val);
+ }
+ l_array_reverse(array);
+
+ for (i = 0; i < numbers_count; i++) {
+ short *member = l_array_get_at(array, i);
+ assert(*member == (numbers_count - i - 1));
+ }
+
+ l_array_destroy(array, NULL);
+}
+
+static void array_foreach(void *p, void *user_data)
+{
+ short *member = p;
+ int *i = user_data;
+ assert(*i == *member);
+ (*i)++;
+}
+
+static void test_itr(const void *test_data)
+{
+ struct l_array *array;
+ short *member;
+ int i;
+
+ array = l_array_new(sizeof(short), 1);
+ assert(array);
+
+ for (i = 0; i < numbers_count; i++) {
+ short val = i;
+ l_array_append(array, &val);
+ }
+ i = 0;
+ L_ARRAY_FOREACH(array, member) {
+ assert(*member == i);
+ i++;
+ }
+ assert(i == numbers_count);
+
+ i = 0;
+ l_array_foreach(array, array_foreach, &i);
+ assert(i == numbers_count);
+
+ l_array_destroy(array, NULL);
+}
+
+int main(int argc, char *argv[])
+{
+ l_test_init(&argc, &argv);
+
+ l_test_add("Basic Test", test_basic, NULL);
+ l_test_add("Insert Sorted Test", test_insert_sort, NULL);
+ l_test_add("Reverse Test", test_reverse, NULL);
+ l_test_add("Sort Test", test_sort, NULL);
+ l_test_add("Iterators", test_itr, NULL);
+ return l_test_run();
+}
--
1.7.10.2
_______________________________________________
connman mailing list
connman@connman.net
http://lists.connman.net/listinfo/connman
