This is a sorted dynamic array. It allows finding elements in O(log n) time, the same as for a binary search tree. Inserting or deleting elements is in amortized O(n) time because of the need to shift elements to make room or fill gaps.
The main advantages of a sorted array over a binary search tree are:
- Simpler implementation
- Better locality of reference, so improved cache performance
- Iteration does not involve following pointers, just increasing an index variable
- Finding the nth element is O(1), while it is O(n) in a binary search tree
- The array, or a range from it, can be copied to another memory location easily without iteration
Here is the header file:
#ifndef SORTEDARRAY_H #define SORTEDARRAY_H #include <dynarray.h> typedef int (*sortedarray_cmpfn)(const void*, const void*); typedef void (*sortedarray_forfn)(void*); struct sortedarray { dynarray *array; sortedarray_cmpfn compare; }; typedef struct sortedarray sortedarray; sortedarray * sortedarray_create(sortedarray_cmpfn compare); void sortedarray_delete(sortedarray * array); void * sortedarray_add(sortedarray * array, void * data); void * sortedarray_remove(sortedarray * array, const void * data); void * sortedarray_find(const sortedarray * array, const void * data); void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn); unsigned int sortedarray_get_count(const sortedarray *array); void * sortedarray_get(const sortedarray *array, unsigned int pos); void * sortedarray_remove_at(sortedarray *array, unsigned int pos); int sortedarray_find_index(const sortedarray *array, const void *data); #endif /* SORTEDARRAY_H */
The implementation:
#include <stdlib.h> #include <sortedarray.h> sortedarray * sortedarray_create(sortedarray_cmpfn compare) { sortedarray *array = malloc(sizeof(sortedarray)); if (array) { array->array = dynarray_create(0); array->compare = compare; } return array; } void sortedarray_delete(sortedarray * array) { if (array) { dynarray_delete(array->array); free(array); } } typedef struct { void * data; unsigned int pos; } search_result; static search_result sortedarray_search(const sortedarray *array, const void *data) { search_result sr; unsigned int elements = array->array->count; unsigned int offset = 0; unsigned int middle = 0; sr.data = NULL; while (elements > 0 && !sr.data) { int result; middle = elements / 2; result = array->compare(data, dynarray_get(array->array, offset + middle)); if (result > 0) { offset = offset + middle + 1; elements = elements - (middle + 1); } else if (result < 0) { elements = middle; } else { sr.data = dynarray_get(array->array, offset + middle); offset += middle; } } sr.pos = offset; return sr; } void * sortedarray_add(sortedarray * array, void * data) { search_result result = sortedarray_search(array, data); void *existing = result.data; if (existing) { /* Replace */ dynarray_set(array->array, result.pos, data); } else { /* Add new */ dynarray_insert(array->array, result.pos, data); } return existing; } void * sortedarray_remove(sortedarray * array, const void * data) { search_result result = sortedarray_search(array, data); if (result.data) { dynarray_remove(array->array, result.pos); } return result.data; } void * sortedarray_find(const sortedarray * array, const void * data) { search_result result = sortedarray_search(array, data); return result.data; } void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn) { dynarray_for_each(array->array, forfn); } unsigned int sortedarray_get_count(const sortedarray *array) { return array->array->count; } void * sortedarray_get(const sortedarray *array, unsigned int pos) { return dynarray_get(array->array, pos); } void * sortedarray_remove_at(sortedarray * array, unsigned int pos) { return dynarray_remove(array->array, pos); } int sortedarray_find_index(const sortedarray *array, const void *data) { int index = -1; search_result result = sortedarray_search(array, data); if (result.data) { index = result.pos; } return index; }
An example program:
#include <stdio.h> #include <string.h> #include <sortedarray.h> int main(void) { sortedarray * array; const char * result; unsigned int e; char * elements[] = {"orange", "apple", "pear", "grapefruit", "cherry", "plum"}; const unsigned int n = sizeof(elements) / sizeof(const char*); array = sortedarray_create((sortedarray_cmpfn)strcmp); for (e = 0; e < n; e++) { sortedarray_add(array, elements[e]); } sortedarray_for_each(array, (sortedarray_forfn)puts); for (e = 0; e < n; e++) { result = sortedarray_find(array, elements[e]); if (result) { printf("Found: %s at %d\n", result, sortedarray_find_index(array, elements[e])); } else { printf("Couldn't find %s\n", elements[e]); } } for (e = 0; e < n; e++) { result = sortedarray_remove(array, elements[e]); if (result) { printf("Removed: %s\n", result); } else { printf("Couldn't remove %s\n", elements[e]); } } sortedarray_delete(array); return 0; }