/src/strongswan/src/libstrongswan/collections/array.c

Source
/*
 * Copyright (C) 2014 Tobias Brunner
 * Copyright (C) 2013 Martin Willi
 *
 * Copyright (C) secunet Security Networks AG
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
 *
 * 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.
 */

#define _GNU_SOURCE /* for qsort_r() */
#include <stdlib.h>

#include "array.h"

#ifndef HAVE_QSORT_R
#include <threading/thread_value.h>
#endif

/**
 * Data is an allocated block, with potentially unused head and tail:
 *
 *   "esize" each (or sizeof(void*) if esize = 0)
 *  /-\ /-\ /-\ /-\ /-\ /-\
 *
 * +---------------+-------------------------------+---------------+
 * | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |
 * +---------------+-------------------------------+---------------+
 *
 * \--------------/ \-----------------------------/ \-------------/
 *      unused                    used                   unused
 *      "head"                   "count"                 "tail"
 *
 */
struct array_t {
  /** number of elements currently in array (not counting head/tail) */
  uint32_t count;
  /** size of each element, 0 for a pointer based array */
  uint16_t esize;
  /** allocated but unused elements at array front */
  uint8_t head;
  /** allocated but unused elements at array end */
  uint8_t tail;
  /** array elements */
  void *data;
};

#ifndef HAVE_QSORT_R
  /* store data to replicate qsort_r in thread local storage */
  static thread_value_t *sort_data;
#endif

/** maximum number of unused head/tail elements before cleanup */
#define ARRAY_MAX_UNUSED 32

/**
 * Get the actual size of a number of elements
 */
static size_t get_size(array_t *array, uint32_t num)
{
  if (array->esize)
  {
    return (size_t)array->esize * num;
  }
  return sizeof(void*) * num;
}

/**
 * Increase allocated but unused tail room to at least "room"
 */
static void make_tail_room(array_t *array, uint8_t room)
{
  if (array->tail < room)
  {
    array->data = realloc(array->data,
            get_size(array, array->count + array->head + room));
    array->tail = room;
  }
}

/**
 * Increase allocated but unused head room to at least "room"
 */
static void make_head_room(array_t *array, uint8_t room)
{
  if (array->head < room)
  {
    uint8_t increase = room - array->head;

    array->data = realloc(array->data,
            get_size(array, array->count + array->tail + room));
    memmove(array->data + get_size(array, increase), array->data,
        get_size(array, array->count + array->tail + array->head));
    array->head = room;
  }
}

/**
 * Make space for an item at index using tail room
 */
static void insert_tail(array_t *array, int idx)
{
  make_tail_room(array, 1);
  /* move up all elements after idx by one */
  memmove(array->data + get_size(array, array->head + idx + 1),
      array->data + get_size(array, array->head + idx),
      get_size(array, array->count - idx));

  array->tail--;
  array->count++;
}

/**
 * Make space for an item at index using head room
 */
static void insert_head(array_t *array, int idx)
{
  make_head_room(array, 1);
  /* move down all elements before idx by one */
  memmove(array->data + get_size(array, array->head - 1),
      array->data + get_size(array, array->head),
      get_size(array, idx));

  array->head--;
  array->count++;
}

/**
 * Remove an item, increase tail
 */
static void remove_tail(array_t *array, int idx)
{
  /* move all items after idx one down */
  memmove(array->data + get_size(array, idx + array->head),
      array->data + get_size(array, idx + array->head + 1),
      get_size(array, array->count - 1 - idx));
  array->count--;
  array->tail++;
}

/**
 * Remove an item, increase head
 */
static void remove_head(array_t *array, int idx)
{
  /* move all items before idx one up */
  memmove(array->data + get_size(array, array->head + 1),
      array->data + get_size(array, array->head), get_size(array, idx));
  array->count--;
  array->head++;
}

array_t *array_create(u_int esize, uint8_t reserve)
{
  array_t *array;

  INIT(array,
    .esize = esize,
    .tail = reserve,
  );
  if (array->tail)
  {
    array->data = malloc(get_size(array, array->tail));
  }
  return array;
}

int array_count(array_t *array)
{
  if (array)
  {
    return array->count;
  }
  return 0;
}

void array_compress(array_t *array)
{
  if (array)
  {
    uint32_t tail;

    tail = array->tail;
    if (array->head)
    {
      memmove(array->data, array->data + get_size(array, array->head),
          get_size(array, array->count + array->tail));
      tail += array->head;
      array->head = 0;
    }
    if (tail)
    {
      size_t size = get_size(array, array->count);

      if (size)
      {
        array->data = realloc(array->data, size);
      }
      else
      {
        free(array->data);
        array->data = NULL;
      }
      array->tail = 0;
    }
  }
}

typedef struct {
  /** public enumerator interface */
  enumerator_t public;
  /** enumerated array */
  array_t *array;
  /** current index +1, initialized at 0 */
  int idx;
} array_enumerator_t;

METHOD(enumerator_t, enumerate, bool,
  array_enumerator_t *this, va_list args)
{
  void *pos, **out;

  VA_ARGS_VGET(args, out);

  if (this->idx >= this->array->count)
  {
    return FALSE;
  }

  pos = this->array->data +
      get_size(this->array, this->idx + this->array->head);
  if (this->array->esize)
  {
    /* for element based arrays we return a pointer to the element */
    *out = pos;
  }
  else
  {
    /* for pointer based arrays we return the pointer directly */
    *out = *(void**)pos;
  }
  this->idx++;
  return TRUE;
}

enumerator_t* array_create_enumerator(array_t *array)
{
  array_enumerator_t *enumerator;

  if (!array)
  {
    return enumerator_create_empty();
  }

  INIT(enumerator,
    .public = {
      .enumerate = enumerator_enumerate_default,
      .venumerate = _enumerate,
      .destroy = (void*)free,
    },
    .array = array,
  );
  return &enumerator->public;
}

void array_remove_at(array_t *array, enumerator_t *public)
{
  array_enumerator_t *enumerator = (array_enumerator_t*)public;

  if (enumerator->idx)
  {
    array_remove(array, --enumerator->idx, NULL);
  }
}

void array_insert_create(array_t **array, int idx, void *ptr)
{
  if (*array == NULL)
  {
    *array = array_create(0, 0);
  }
  array_insert(*array, idx, ptr);
}

void array_insert_create_value(array_t **array, u_int esize,
                 int idx, void *val)
{
  if (*array == NULL)
  {
    *array = array_create(esize, 0);
  }
  array_insert(*array, idx, val);
}

void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
{
  void *ptr;

  while (enumerator->enumerate(enumerator, &ptr))
  {
    array_insert(array, idx, ptr);
  }
  enumerator->destroy(enumerator);
}

void array_insert(array_t *array, int idx, void *data)
{
  if (idx < 0 || idx <= array_count(array))
  {
    void *pos;

    if (idx < 0)
    {
      idx = array_count(array);
    }

    if (array->head && !array->tail)
    {
      insert_head(array, idx);
    }
    else if (array->tail && !array->head)
    {
      insert_tail(array, idx);
    }
    else if (idx > array_count(array) / 2)
    {
      insert_tail(array, idx);
    }
    else
    {
      insert_head(array, idx);
    }

    pos = array->data + get_size(array, array->head + idx);
    if (array->esize)
    {
      memcpy(pos, data, get_size(array, 1));
    }
    else
    {
      /* pointer based array, copy pointer value */
      *(void**)pos = data;
    }
  }
}

bool array_get(array_t *array, int idx, void *data)
{
  if (!array)
  {
    return FALSE;
  }
  if (idx >= 0 && idx >= array_count(array))
  {
    return FALSE;
  }
  if (idx < 0)
  {
    if (array_count(array) == 0)
    {
      return FALSE;
    }
    idx = array_count(array) - 1;
  }
  if (data)
  {
    memcpy(data, array->data + get_size(array, array->head + idx),
         get_size(array, 1));
  }
  return TRUE;
}

bool array_remove(array_t *array, int idx, void *data)
{
  if (!array_get(array, idx, data))
  {
    return FALSE;
  }
  if (idx < 0)
  {
    idx = array_count(array) - 1;
  }
  if (idx > array_count(array) / 2)
  {
    remove_tail(array, idx);
  }
  else
  {
    remove_head(array, idx);
  }
  if (array->head + array->tail > ARRAY_MAX_UNUSED)
  {
    array_compress(array);
  }
  return TRUE;
}

typedef struct {
  /** the array */
  array_t *array;
  /** comparison function */
  int (*cmp)(const void*,const void*,void*);
  /** optional user arg */
  void *arg;
} sort_data_t;

#ifdef HAVE_QSORT_R_GNU
static int compare_elements(const void *a, const void *b, void *arg)
#elif defined(HAVE_QSORT_R_BSD)
static int compare_elements(void *arg, const void *a, const void *b)
#else /* !HAVE_QSORT_R */
static int compare_elements(const void *a, const void *b)
#endif
{
#ifdef HAVE_QSORT_R
  sort_data_t *data = (sort_data_t*)arg;
#else
  sort_data_t *data = sort_data->get(sort_data);
#endif

  if (data->array->esize)
  {
    return data->cmp(a, b, data->arg);
  }
  return data->cmp(*(void**)a, *(void**)b, data->arg);
}

void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
        void *user)
{
  if (array)
  {
    sort_data_t data = {
      .array = array,
      .cmp = cmp,
      .arg = user,
    };
    void *start;

    start = array->data + get_size(array, array->head);

#ifdef HAVE_QSORT_R_GNU
    qsort_r(start, array->count, get_size(array, 1), compare_elements,
        &data);
#elif defined(HAVE_QSORT_R_BSD)
    qsort_r(start, array->count, get_size(array, 1), &data,
        compare_elements);
#else /* !HAVE_QSORT_R */
    sort_data_t *recursive;

    recursive = sort_data->get(sort_data);
    sort_data->set(sort_data, &data);
    qsort(start, array->count, get_size(array, 1), compare_elements);
    sort_data->set(sort_data, recursive);
#endif
  }
}

typedef struct {
  /** the array */
  array_t *array;
  /** the key */
  const void *key;
  /** comparison function */
  int (*cmp)(const void*,const void*);
} bsearch_data_t;

static int search_elements(const void *a, const void *b)
{
  bsearch_data_t *data = (bsearch_data_t*)a;

  if (data->array->esize)
  {
    return data->cmp(data->key, b);
  }
  return data->cmp(data->key, *(void**)b);
}

int array_bsearch(array_t *array, const void *key,
          int (*cmp)(const void*,const void*), void *out)
{
  int idx = -1;

  if (array)
  {
    bsearch_data_t data = {
      .array = array,
      .key = key,
      .cmp = cmp,
    };
    void *start, *item;

    start = array->data + get_size(array, array->head);

    item = bsearch(&data, start, array->count, get_size(array, 1),
             search_elements);
    if (item)
    {
      if (out)
      {
        memcpy(out, item, get_size(array, 1));
      }
      idx = (item - start) / get_size(array, 1);
    }
  }
  return idx;
}

void array_invoke(array_t *array, array_callback_t cb, void *user)
{
  if (array)
  {
    void *obj;
    int i;

    for (i = array->head; i < array->count + array->head; i++)
    {
      obj = array->data + get_size(array, i);
      if (!array->esize)
      {
        /* dereference if we store store pointers */
        obj = *(void**)obj;
      }
      cb(obj, i - array->head, user);
    }
  }
}

void array_invoke_offset(array_t *array, size_t offset)
{
  if (array)
  {
    void (*method)(void *data);
    void *obj;
    int i;

    for (i = array->head; i < array->count + array->head; i++)
    {
      obj = array->data + get_size(array, i);
      if (!array->esize)
      {
        /* dereference if we store store pointers */
        obj = *(void**)obj;
      }
      method = *(void**)(obj + offset);
      method(obj);
    }
  }
}

void array_destroy(array_t *array)
{
  if (array)
  {
    free(array->data);
    free(array);
  }
}

void array_destroy_function(array_t *array, array_callback_t cb, void *user)
{
  array_invoke(array, cb, user);
  array_destroy(array);
}

void array_destroy_offset(array_t *array, size_t offset)
{
  array_invoke_offset(array, offset);
  array_destroy(array);
}

void arrays_init()
{
#ifndef HAVE_QSORT_R
  sort_data =  thread_value_create(NULL);
#endif
}

void arrays_deinit()
{
#ifndef HAVE_QSORT_R
  sort_data->destroy(sort_data);
#endif
}

Coverage Report

Created: 2026-04-12 07:02

Line	Count	Source
1		/*
2		* Copyright (C) 2014 Tobias Brunner
3		* Copyright (C) 2013 Martin Willi
4		*
5		* Copyright (C) secunet Security Networks AG
6		*
7		* This program is free software; you can redistribute it and/or modify it
8		* under the terms of the GNU General Public License as published by the
9		* Free Software Foundation; either version 2 of the License, or (at your
10		* option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11		*
12		* This program is distributed in the hope that it will be useful, but
13		* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14		* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15		* for more details.
16		*/
17
18		#define _GNU_SOURCE /* for qsort_r() */
19		#include <stdlib.h>
20
21		#include "array.h"
22
23		#ifndef HAVE_QSORT_R
24		#include <threading/thread_value.h>
25		#endif
26
27		/**
28		* Data is an allocated block, with potentially unused head and tail:
29		*
30		* "esize" each (or sizeof(void*) if esize = 0)
31		* /-\ /-\ /-\ /-\ /-\ /-\
32		*
33		* +---------------+-------------------------------+---------------+
34		* \| h \| e \| a \| d \| e \| l \| e \| m \| e \| n \| t \| s \| t \| a \| i \| l \|
35		* +---------------+-------------------------------+---------------+
36		*
37		* \--------------/ \-----------------------------/ \-------------/
38		* unused used unused
39		* "head" "count" "tail"
40		*
41		*/
42		struct array_t {
43		/** number of elements currently in array (not counting head/tail) */
44		uint32_t count;
45		/** size of each element, 0 for a pointer based array */
46		uint16_t esize;
47		/** allocated but unused elements at array front */
48		uint8_t head;
49		/** allocated but unused elements at array end */
50		uint8_t tail;
51		/** array elements */
52		void *data;
53		};
54
55		#ifndef HAVE_QSORT_R
56		/* store data to replicate qsort_r in thread local storage */
57		static thread_value_t *sort_data;
58		#endif
59
60		/** maximum number of unused head/tail elements before cleanup */
61	0	#define ARRAY_MAX_UNUSED 32
62
63		/**
64		* Get the actual size of a number of elements
65		*/
66		static size_t get_size(array_t *array, uint32_t num)
67	513	{
68	513	if (array->esize)
69	0	{
70	0	return (size_t)array->esize * num;
71	0	}
72	513	return sizeof(void) num;
73	513	}
74
75		/**
76		* Increase allocated but unused tail room to at least "room"
77		*/
78		static void make_tail_room(array_t *array, uint8_t room)
79	0	{
80	0	if (array->tail < room)
81	0	{
82	0	array->data = realloc(array->data,
83	0	get_size(array, array->count + array->head + room));
84	0	array->tail = room;
85	0	}
86	0	}
87
88		/**
89		* Increase allocated but unused head room to at least "room"
90		*/
91		static void make_head_room(array_t *array, uint8_t room)
92	29	{
93	29	if (array->head < room)
94	29	{
95	29	uint8_t increase = room - array->head;
96
97	29	array->data = realloc(array->data,
98	29	get_size(array, array->count + array->tail + room));
99	29	memmove(array->data + get_size(array, increase), array->data,
100	29	get_size(array, array->count + array->tail + array->head));
101	29	array->head = room;
102	29	}
103	29	}
104
105		/**
106		* Make space for an item at index using tail room
107		*/
108		static void insert_tail(array_t *array, int idx)
109	0	{
110	0	make_tail_room(array, 1);
111		/* move up all elements after idx by one */
112	0	memmove(array->data + get_size(array, array->head + idx + 1),
113	0	array->data + get_size(array, array->head + idx),
114	0	get_size(array, array->count - idx));
115
116	0	array->tail--;
117	0	array->count++;
118	0	}
119
120		/**
121		* Make space for an item at index using head room
122		*/
123		static void insert_head(array_t *array, int idx)
124	29	{
125	29	make_head_room(array, 1);
126		/* move down all elements before idx by one */
127	29	memmove(array->data + get_size(array, array->head - 1),
128	29	array->data + get_size(array, array->head),
129	29	get_size(array, idx));
130
131	29	array->head--;
132	29	array->count++;
133	29	}
134
135		/**
136		* Remove an item, increase tail
137		*/
138		static void remove_tail(array_t *array, int idx)
139	0	{
140		/* move all items after idx one down */
141	0	memmove(array->data + get_size(array, idx + array->head),
142	0	array->data + get_size(array, idx + array->head + 1),
143	0	get_size(array, array->count - 1 - idx));
144	0	array->count--;
145	0	array->tail++;
146	0	}
147
148		/**
149		* Remove an item, increase head
150		*/
151		static void remove_head(array_t *array, int idx)
152	0	{
153		/* move all items before idx one up */
154	0	memmove(array->data + get_size(array, array->head + 1),
155	0	array->data + get_size(array, array->head), get_size(array, idx));
156	0	array->count--;
157	0	array->head++;
158	0	}
159
160		array_t *array_create(u_int esize, uint8_t reserve)
161	31	{
162	31	array_t *array;
163
164	31	INIT(array,
165	31	.esize = esize,
166	31	.tail = reserve,
167	31	);
168	31	if (array->tail)
169	0	{
170	0	array->data = malloc(get_size(array, array->tail));
171	0	}
172	31	return array;
173	31	}
174
175		int array_count(array_t *array)
176	216	{
177	216	if (array)
178	177	{
179	177	return array->count;
180	177	}
181	39	return 0;
182	216	}
183
184		void array_compress(array_t *array)
185	0	{
186	0	if (array)
187	0	{
188	0	uint32_t tail;
189
190	0	tail = array->tail;
191	0	if (array->head)
192	0	{
193	0	memmove(array->data, array->data + get_size(array, array->head),
194	0	get_size(array, array->count + array->tail));
195	0	tail += array->head;
196	0	array->head = 0;
197	0	}
198	0	if (tail)
199	0	{
200	0	size_t size = get_size(array, array->count);
201
202	0	if (size)
203	0	{
204	0	array->data = realloc(array->data, size);
205	0	}
206	0	else
207	0	{
208	0	free(array->data);
209	0	array->data = NULL;
210	0	}
211	0	array->tail = 0;
212	0	}
213	0	}
214	0	}
215
216		typedef struct {
217		/** public enumerator interface */
218		enumerator_t public;
219		/** enumerated array */
220		array_t *array;
221		/** current index +1, initialized at 0 */
222		int idx;
223		} array_enumerator_t;
224
225		METHOD(enumerator_t, enumerate, bool,
226		array_enumerator_t *this, va_list args)
227	0	{
228	0	void pos, *out;
229
230	0	VA_ARGS_VGET(args, out);
231
232	0	if (this->idx >= this->array->count)
233	0	{
234	0	return FALSE;
235	0	}
236
237	0	pos = this->array->data +
238	0	get_size(this->array, this->idx + this->array->head);
239	0	if (this->array->esize)
240	0	{
241		/* for element based arrays we return a pointer to the element */
242	0	*out = pos;
243	0	}
244	0	else
245	0	{
246		/* for pointer based arrays we return the pointer directly */
247	0	out = (void**)pos;
248	0	}
249	0	this->idx++;
250	0	return TRUE;
251	0	}
252
253		enumerator_t* array_create_enumerator(array_t *array)
254	4	{
255	4	array_enumerator_t *enumerator;
256
257	4	if (!array)
258	4	{
259	4	return enumerator_create_empty();
260	4	}
261
262	4	INIT(enumerator,
263	0	.public = {
264	0	.enumerate = enumerator_enumerate_default,
265	0	.venumerate = _enumerate,
266	0	.destroy = (void*)free,
267	0	},
268	0	.array = array,
269	0	);
270	0	return &enumerator->public;
271	4	}
272
273		void array_remove_at(array_t array, enumerator_t public)
274	0	{
275	0	array_enumerator_t enumerator = (array_enumerator_t)public;
276
277	0	if (enumerator->idx)
278	0	{
279	0	array_remove(array, --enumerator->idx, NULL);
280	0	}
281	0	}
282
283		void array_insert_create(array_t *array, int idx, void ptr)
284	27	{
285	27	if (*array == NULL)
286	27	{
287	27	*array = array_create(0, 0);
288	27	}
289	27	array_insert(*array, idx, ptr);
290	27	}
291
292		void array_insert_create_value(array_t **array, u_int esize,
293		int idx, void *val)
294	0	{
295	0	if (*array == NULL)
296	0	{
297	0	*array = array_create(esize, 0);
298	0	}
299	0	array_insert(*array, idx, val);
300	0	}
301
302		void array_insert_enumerator(array_t array, int idx, enumerator_t enumerator)
303	0	{
304	0	void *ptr;
305
306	0	while (enumerator->enumerate(enumerator, &ptr))
307	0	{
308	0	array_insert(array, idx, ptr);
309	0	}
310	0	enumerator->destroy(enumerator);
311	0	}
312
313		void array_insert(array_t array, int idx, void data)
314	29	{
315	29	if (idx < 0 \|\| idx <= array_count(array))
316	29	{
317	29	void *pos;
318
319	29	if (idx < 0)
320	27	{
321	27	idx = array_count(array);
322	27	}
323
324	29	if (array->head && !array->tail)
325	0	{
326	0	insert_head(array, idx);
327	0	}
328	29	else if (array->tail && !array->head)
329	0	{
330	0	insert_tail(array, idx);
331	0	}
332	29	else if (idx > array_count(array) / 2)
333	0	{
334	0	insert_tail(array, idx);
335	0	}
336	29	else
337	29	{
338	29	insert_head(array, idx);
339	29	}
340
341	29	pos = array->data + get_size(array, array->head + idx);
342	29	if (array->esize)
343	0	{
344	0	memcpy(pos, data, get_size(array, 1));
345	0	}
346	29	else
347	29	{
348		/* pointer based array, copy pointer value */
349	29	(void*)pos = data;
350	29	}
351	29	}
352	29	}
353
354		bool array_get(array_t array, int idx, void data)
355	49	{
356	49	if (!array)
357	8	{
358	8	return FALSE;
359	8	}
360	41	if (idx >= 0 && idx >= array_count(array))
361	0	{
362	0	return FALSE;
363	0	}
364	41	if (idx < 0)
365	4	{
366	4	if (array_count(array) == 0)
367	0	{
368	0	return FALSE;
369	0	}
370	4	idx = array_count(array) - 1;
371	4	}
372	41	if (data)
373	41	{
374	41	memcpy(data, array->data + get_size(array, array->head + idx),
375	41	get_size(array, 1));
376	41	}
377	41	return TRUE;
378	41	}
379
380		bool array_remove(array_t array, int idx, void data)
381	8	{
382	8	if (!array_get(array, idx, data))
383	8	{
384	8	return FALSE;
385	8	}
386	0	if (idx < 0)
387	0	{
388	0	idx = array_count(array) - 1;
389	0	}
390	0	if (idx > array_count(array) / 2)
391	0	{
392	0	remove_tail(array, idx);
393	0	}
394	0	else
395	0	{
396	0	remove_head(array, idx);
397	0	}
398	0	if (array->head + array->tail > ARRAY_MAX_UNUSED)
399	0	{
400	0	array_compress(array);
401	0	}
402	0	return TRUE;
403	8	}
404
405		typedef struct {
406		/** the array */
407		array_t *array;
408		/** comparison function */
409		int (cmp)(const void,const void,void);
410		/** optional user arg */
411		void *arg;
412		} sort_data_t;
413
414		#ifdef HAVE_QSORT_R_GNU
415		static int compare_elements(const void a, const void b, void *arg)
416		#elif defined(HAVE_QSORT_R_BSD)
417		static int compare_elements(void arg, const void a, const void *b)
418		#else /* !HAVE_QSORT_R */
419		static int compare_elements(const void a, const void b)
420		#endif
421	0	{
422	0	#ifdef HAVE_QSORT_R
423	0	sort_data_t data = (sort_data_t)arg;
424		#else
425		sort_data_t *data = sort_data->get(sort_data);
426		#endif
427
428	0	if (data->array->esize)
429	0	{
430	0	return data->cmp(a, b, data->arg);
431	0	}
432	0	return data->cmp((void)a, (void**)b, data->arg);
433	0	}
434
435		void array_sort(array_t array, int (cmp)(const void,const void,void*),
436		void *user)
437	2	{
438	2	if (array)
439	2	{
440	2	sort_data_t data = {
441	2	.array = array,
442	2	.cmp = cmp,
443	2	.arg = user,
444	2	};
445	2	void *start;
446
447	2	start = array->data + get_size(array, array->head);
448
449	2	#ifdef HAVE_QSORT_R_GNU
450	2	qsort_r(start, array->count, get_size(array, 1), compare_elements,
451	2	&data);
452		#elif defined(HAVE_QSORT_R_BSD)
453		qsort_r(start, array->count, get_size(array, 1), &data,
454		compare_elements);
455		#else /* !HAVE_QSORT_R */
456		sort_data_t *recursive;
457
458		recursive = sort_data->get(sort_data);
459		sort_data->set(sort_data, &data);
460		qsort(start, array->count, get_size(array, 1), compare_elements);
461		sort_data->set(sort_data, recursive);
462		#endif
463	2	}
464	2	}
465
466		typedef struct {
467		/** the array */
468		array_t *array;
469		/** the key */
470		const void *key;
471		/** comparison function */
472		int (cmp)(const void,const void*);
473		} bsearch_data_t;
474
475		static int search_elements(const void a, const void b)
476	74	{
477	74	bsearch_data_t data = (bsearch_data_t)a;
478
479	74	if (data->array->esize)
480	0	{
481	0	return data->cmp(data->key, b);
482	0	}
483	74	return data->cmp(data->key, (void*)b);
484	74	}
485
486		int array_bsearch(array_t array, const void key,
487		int (cmp)(const void,const void), void out)
488	115	{
489	115	int idx = -1;
490
491	115	if (array)
492	74	{
493	74	bsearch_data_t data = {
494	74	.array = array,
495	74	.key = key,
496	74	.cmp = cmp,
497	74	};
498	74	void start, item;
499
500	74	start = array->data + get_size(array, array->head);
501
502	74	item = bsearch(&data, start, array->count, get_size(array, 1),
503	74	search_elements);
504	74	if (item)
505	37	{
506	37	if (out)
507	37	{
508	37	memcpy(out, item, get_size(array, 1));
509	37	}
510	37	idx = (item - start) / get_size(array, 1);
511	37	}
512	74	}
513	115	return idx;
514	115	}
515
516		void array_invoke(array_t array, array_callback_t cb, void user)
517	14	{
518	14	if (array)
519	2	{
520	2	void *obj;
521	2	int i;
522
523	4	for (i = array->head; i < array->count + array->head; i++)
524	2	{
525	2	obj = array->data + get_size(array, i);
526	2	if (!array->esize)
527	2	{
528		/* dereference if we store store pointers */
529	2	obj = (void*)obj;
530	2	}
531	2	cb(obj, i - array->head, user);
532	2	}
533	2	}
534	14	}
535
536		void array_invoke_offset(array_t *array, size_t offset)
537	2.86k	{
538	2.86k	if (array)
539	0	{
540	0	void (method)(void data);
541	0	void *obj;
542	0	int i;
543
544	0	for (i = array->head; i < array->count + array->head; i++)
545	0	{
546	0	obj = array->data + get_size(array, i);
547	0	if (!array->esize)
548	0	{
549		/* dereference if we store store pointers */
550	0	obj = (void*)obj;
551	0	}
552	0	method = (void*)(obj + offset);
553	0	method(obj);
554	0	}
555	0	}
556	2.86k	}
557
558		void array_destroy(array_t *array)
559	2.96k	{
560	2.96k	if (array)
561	23	{
562	23	free(array->data);
563	23	free(array);
564	23	}
565	2.96k	}
566
567		void array_destroy_function(array_t array, array_callback_t cb, void user)
568	14	{
569	14	array_invoke(array, cb, user);
570	14	array_destroy(array);
571	14	}
572
573		void array_destroy_offset(array_t *array, size_t offset)
574	2.86k	{
575	2.86k	array_invoke_offset(array, offset);
576	2.86k	array_destroy(array);
577	2.86k	}
578
579		void arrays_init()
580	2	{
581		#ifndef HAVE_QSORT_R
582		sort_data = thread_value_create(NULL);
583		#endif
584	2	}
585
586		void arrays_deinit()
587	0	{
588		#ifndef HAVE_QSORT_R
589		sort_data->destroy(sort_data);
590		#endif
591	0	}