Remove ZixSortedArray

5 files changed, 0 insertions, 636 deletions

diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c
index 9e399ba..4da7228 100644
--- a/benchmark/tree_bench.c
+++ b/benchmark/tree_bench.c
@@ -35,8 +35,6 @@ ZIX_RESTORE_WARNINGS
 #include <stdlib.h>
 #include <time.h>
 
-// #define BENCH_SORTED_ARRAY 1
-
 static int
 int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
 {
@@ -210,106 +208,6 @@ bench_zix_btree(size_t n_elems,
   return EXIT_SUCCESS;
 }
 
-#ifdef BENCH_SORTED_ARRAY
-
-static int
-int_ptr_cmp(const void* a, const void* b, void* user_data)
-{
-  const intptr_t ia = *(const intptr_t*)a;
-  const intptr_t ib = *(const intptr_t*)b;
-  return ia - ib;
-}
-
-static int
-bench_zix_sorted_array(size_t n_elems,
-                       FILE*  insert_dat,
-                       FILE*  search_dat,
-                       FILE*  iter_dat,
-                       FILE*  del_dat)
-{
-  start_test("ZixSortedArray");
-
-  intptr_t           r  = 0;
-  ZixSortedArrayIter ti = NULL;
-  ZixSortedArray*    t =
-    zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t));
-
-  // Insert n_elems elements
-  struct timespec insert_start = bench_start();
-  for (size_t i = 0; i < n_elems; ++i) {
-    r          = unique_rand(i);
-    int status = zix_sorted_array_insert(t, &r, &ti);
-    if (status) {
-      return test_fail("Insert failed\n");
-    }
-
-    if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
-      return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n",
-                       *(intptr_t*)zix_sorted_array_get_data(ti),
-                       r);
-    }
-  }
-  fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
-
-  // Search for all elements
-  struct timespec search_start = bench_start();
-  for (size_t i = 0; i < n_elems; ++i) {
-    r = unique_rand(i);
-    if (zix_sorted_array_find(t, &r, &ti)) {
-      return test_fail("Find failed\n");
-    }
-
-    if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
-      return test_fail("Data corrupt (saw %" PRIdPTR ", expected %zu)\n",
-                       *(intptr_t*)zix_sorted_array_get_data(ti),
-                       r);
-    }
-  }
-  fprintf(search_dat, "\t%lf", bench_end(&search_start));
-
-  // Iterate over all elements
-  struct timespec iter_start = bench_start();
-  size_t          i          = 0;
-  intptr_t        last       = -1;
-  for (ZixSortedArrayIter iter = zix_sorted_array_begin(t);
-       !zix_sorted_array_iter_is_end(t, iter);
-       iter = zix_sorted_array_iter_next(t, iter), ++i) {
-    r                        = unique_rand(i);
-    const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter);
-    if (iter_data < last) {
-      return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n", iter_data, last);
-    }
-
-    last = iter_data;
-  }
-  fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
-
-  // Delete all elements
-  struct timespec del_start = bench_start();
-  for (i = 0; i < n_elems; i++) {
-    r = unique_rand(i);
-    ZixSortedArrayIter item;
-    if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) {
-      return test_fail("Failed to find item to remove\n");
-    }
-
-    if (zix_sorted_array_remove(t, item)) {
-      return test_fail("Error removing item\n");
-    }
-  }
-  fprintf(del_dat, "\t%lf", bench_end(&del_start));
-
-  if (zix_sorted_array_size(t) != 0) {
-    return test_fail("Array is not empty after removing all items\n");
-  }
-
-  zix_sorted_array_free(t);
-
-  return EXIT_SUCCESS;
-}
-
-#endif // BENCH_SORTED_ARRAY
-
 static int
 bench_glib(size_t n_elems,
            FILE*  insert_dat,
@@ -401,9 +299,6 @@ main(int argc, char** argv)
     fprintf(iter_dat, "%zu", n);
     fprintf(del_dat, "%zu", n);
     bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat);
-#ifdef BENCH_SORTED_ARRAY
-    bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat);
-#endif
     bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat);
     bench_glib(n, insert_dat, search_dat, iter_dat, del_dat);
     fprintf(insert_dat, "\n");
diff --git a/include/zix/sorted_array.h b/include/zix/sorted_array.h
deleted file mode 100644
index 580551e..0000000
--- a/include/zix/sorted_array.h
+++ /dev/null
@@ -1,122 +0,0 @@
-/*
-  Copyright 2011-2020 David Robillard <d@drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#ifndef ZIX_SORTED_ARRAY_H
-#define ZIX_SORTED_ARRAY_H
-
-#include "zix/common.h"
-
-#include <stdbool.h>
-#include <stddef.h>
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
-   @addtogroup zix
-   @{
-   @name SortedArray
-   @{
-*/
-
-/// A sorted array
-typedef struct ZixSortedArrayImpl ZixSortedArray;
-
-/// An iterator over a ZixSortedArray
-typedef void* ZixSortedArrayIter;
-
-/// Create a new (empty) sorted array
-ZIX_API
-ZixSortedArray*
-zix_sorted_array_new(bool          allow_duplicates,
-                     ZixComparator cmp,
-                     void*         cmp_data,
-                     size_t        elem_size);
-
-/// Free `a`
-ZIX_API
-void
-zix_sorted_array_free(ZixSortedArray* a);
-
-/// Return the number of elements in `a`
-ZIX_PURE_API
-size_t
-zix_sorted_array_size(const ZixSortedArray* a);
-
-/// Insert the element `e` into `a` and point `ai` at the new element
-ZIX_API
-ZixStatus
-zix_sorted_array_insert(ZixSortedArray*     a,
-                        const void*         e,
-                        ZixSortedArrayIter* ai);
-
-/// Remove the item pointed at by `ai` from `a`
-ZIX_API
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai);
-
-/**
-   Set `ai` to be the largest element <= `e` in `a`.
-
-   If no such item exists, `ai` is set to NULL.
-*/
-ZIX_API
-ZixStatus
-zix_sorted_array_find(const ZixSortedArray* a,
-                      const void*           e,
-                      ZixSortedArrayIter*   ai);
-
-/// Return the element at index `index`
-ZIX_PURE_API
-void*
-zix_sorted_array_index(const ZixSortedArray* a, size_t index);
-
-/// Return the data associated with the given array item
-ZIX_CONST_API
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai);
-
-/// Return an iterator to the first (smallest) element in `a`
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a);
-
-/// Return an iterator the the element one past the last element in `a`
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a);
-
-/// Return true iff `a` is an iterator to the end of its tree
-ZIX_PURE_API
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i);
-
-/// Return an iterator that points to the element one past `a`
-ZIX_PURE_API
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i);
-
-/**
-   @}
-   @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_SORTED_ARRAY_H */
diff --git a/meson.build b/meson.build
index d429513..5651c0c 100644
--- a/meson.build
+++ b/meson.build
@@ -177,7 +177,6 @@ sources = [
   'src/digest.c',
   'src/hash.c',
   'src/ring.c',
-  'src/sorted_array.c',
   'src/strindex.c',
   'src/tree.c',
 ]
@@ -216,7 +215,6 @@ headers = [
   'include/zix/hash.h',
   'include/zix/ring.h',
   'include/zix/sem.h',
-  'include/zix/sorted_array.h',
   'include/zix/strindex.h',
   'include/zix/thread.h',
   'include/zix/tree.h',
@@ -236,7 +234,6 @@ tests = [
   'hash_test',
   'ring_test',
   'sem_test',
-  'sorted_array_test',
   'strindex_test',
   'tree_test',
 ]
diff --git a/src/sorted_array.c b/src/sorted_array.c
deleted file mode 100644
index eb48fe1..0000000
--- a/src/sorted_array.c
+++ /dev/null
@@ -1,193 +0,0 @@
-/*
-  Copyright 2011-2020 David Robillard <d@drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#include "zix/sorted_array.h"
-
-#include "zix/common.h"
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-// #define ZIX_SORTED_ARRAY_DUMP 1
-
-struct ZixSortedArrayImpl {
-  void*         array;
-  ZixComparator cmp;
-  void*         cmp_data;
-  size_t        elem_size;
-  size_t        num_elems;
-  bool          allow_duplicates;
-};
-
-#ifdef ZIX_SORTED_ARRAY_DUMP
-static void
-zix_sorted_array_print(ZixSortedArray* a)
-{
-  for (size_t i = 0; i < a->num_elems; ++i) {
-    printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size)));
-  }
-  printf("\n");
-}
-#  define DUMP(a) zix_sorted_array_print(a)
-#else
-#  define DUMP(a)
-#endif
-
-ZixSortedArray*
-zix_sorted_array_new(bool          allow_duplicates,
-                     ZixComparator cmp,
-                     void*         cmp_data,
-                     size_t        elem_size)
-{
-  ZixSortedArray* a   = (ZixSortedArray*)malloc(sizeof(ZixSortedArray));
-  a->array            = NULL;
-  a->cmp              = cmp;
-  a->cmp_data         = cmp_data;
-  a->elem_size        = elem_size;
-  a->num_elems        = 0;
-  a->allow_duplicates = allow_duplicates;
-  return a;
-}
-
-void
-zix_sorted_array_free(ZixSortedArray* a)
-{
-  free(a->array);
-  free(a);
-}
-
-size_t
-zix_sorted_array_size(const ZixSortedArray* a)
-{
-  return a->num_elems;
-}
-
-ZixStatus
-zix_sorted_array_insert(ZixSortedArray*     a,
-                        const void*         e,
-                        ZixSortedArrayIter* ai)
-{
-  if (a->num_elems == 0) {
-    assert(!a->array);
-    a->array = malloc(a->elem_size);
-    memcpy(a->array, e, a->elem_size);
-    ++a->num_elems;
-    *ai = a->array;
-    return ZIX_STATUS_SUCCESS;
-  }
-
-  zix_sorted_array_find(a, e, ai);
-  assert(*ai);
-  const size_t i = (size_t)((char*)*ai - (char*)a->array) / a->elem_size;
-
-  a->array = realloc(a->array, ++a->num_elems * a->elem_size);
-  memmove((char*)a->array + ((i + 1) * a->elem_size),
-          (char*)a->array + (i * a->elem_size),
-          (a->num_elems - i - 1) * a->elem_size);
-  memcpy((char*)a->array + (i * a->elem_size), e, a->elem_size);
-
-  *ai = (char*)a->array + (i * a->elem_size);
-  DUMP(t);
-  return ZIX_STATUS_SUCCESS;
-}
-
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai)
-{
-  const size_t i = (size_t)((char*)ai - (char*)a->array) / a->elem_size;
-  memmove((char*)a->array + (i * a->elem_size),
-          (char*)a->array + ((i + 1) * a->elem_size),
-          (a->num_elems - i - 1) * a->elem_size);
-  --a->num_elems;
-  DUMP(a);
-  return ZIX_STATUS_SUCCESS;
-}
-
-static inline void*
-zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index)
-{
-  return (char*)a->array + (a->elem_size * index);
-}
-
-void*
-zix_sorted_array_index(const ZixSortedArray* a, size_t index)
-{
-  if (index >= a->num_elems) {
-    return NULL;
-  }
-
-  return zix_sorted_array_index_unchecked(a, index);
-}
-
-ZixStatus
-zix_sorted_array_find(const ZixSortedArray* a,
-                      const void*           e,
-                      ZixSortedArrayIter*   ai)
-{
-  intptr_t lower = 0;
-  intptr_t upper = a->num_elems - 1;
-  while (upper >= lower) {
-    const intptr_t i      = lower + ((upper - lower) / 2);
-    void* const    elem_i = zix_sorted_array_index_unchecked(a, i);
-    const int      cmp    = a->cmp(elem_i, e, a->cmp_data);
-
-    if (cmp == 0) {
-      *ai = elem_i;
-      return ZIX_STATUS_SUCCESS;
-    }
-
-    if (cmp > 0) {
-      upper = i - 1;
-    } else {
-      lower = i + 1;
-    }
-  }
-
-  *ai = zix_sorted_array_index_unchecked(a, lower);
-  return ZIX_STATUS_NOT_FOUND;
-}
-
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai)
-{
-  return ai;
-}
-
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a)
-{
-  return a->array;
-}
-
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a)
-{
-  return (char*)a->array + (a->elem_size * a->num_elems);
-}
-
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i)
-{
-  return i >= zix_sorted_array_end(a);
-}
-
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i)
-{
-  return (char*)i + a->elem_size;
-}
diff --git a/test/sorted_array_test.c b/test/sorted_array_test.c
deleted file mode 100644
index cc87619..0000000
--- a/test/sorted_array_test.c
+++ /dev/null
@@ -1,213 +0,0 @@
-/*
-  Copyright 2011-2020 David Robillard <d@drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#include "test_data.h"
-
-#include "zix/common.h"
-#include "zix/sorted_array.h"
-
-#include <inttypes.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-static unsigned seed = 1;
-
-static int
-int_cmp(const void* a, const void* b, const void* ZIX_UNUSED(user_data))
-{
-  const intptr_t ia = *(const intptr_t*)a;
-  const intptr_t ib = *(const intptr_t*)b;
-
-  return ia < ib ? -1 : ia > ib ? 1 : 0;
-}
-
-static intptr_t
-ith_elem(unsigned test_num, unsigned n_elems, unsigned i)
-{
-  switch (test_num % 3) {
-  case 0:
-    return i; // Increasing (worst case)
-  case 1:
-    return n_elems - i; // Decreasing (worse case)
-  case 2:
-  default:
-    return lcg64(seed + i) % 100u; // Pseudo-random
-  }
-}
-
-static int
-test_fail(void)
-{
-  return EXIT_FAILURE;
-}
-
-static int
-stress(unsigned test_num, unsigned n_elems)
-{
-  intptr_t           r  = 0;
-  ZixSortedArrayIter ti = NULL;
-
-  ZixSortedArray* t =
-    zix_sorted_array_new(true, int_cmp, NULL, sizeof(intptr_t));
-
-  // Insert n_elems elements
-  for (unsigned i = 0; i < n_elems; ++i) {
-    r          = ith_elem(test_num, n_elems, i);
-    int status = zix_sorted_array_insert(t, &r, &ti);
-    if (status) {
-      fprintf(stderr, "Insert failed\n");
-      return test_fail();
-    }
-
-    if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
-      fprintf(stderr,
-              "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
-              *(intptr_t*)zix_sorted_array_get_data(ti),
-              r);
-      return test_fail();
-    }
-  }
-
-  // Search for all elements
-  for (unsigned i = 0; i < n_elems; ++i) {
-    r = ith_elem(test_num, n_elems, i);
-    if (zix_sorted_array_find(t, &r, &ti)) {
-      fprintf(stderr, "Find failed\n");
-      return test_fail();
-    }
-
-    if (*(intptr_t*)zix_sorted_array_get_data(ti) != r) {
-      fprintf(stderr,
-              "Data corrupt (%" PRIdPTR " != %" PRIdPTR ")\n",
-              *(intptr_t*)zix_sorted_array_get_data(ti),
-              r);
-      return test_fail();
-    }
-  }
-
-  // Iterate over all elements
-  unsigned i    = 0;
-  intptr_t last = -1;
-  for (ZixSortedArrayIter iter = zix_sorted_array_begin(t);
-       !zix_sorted_array_iter_is_end(t, iter);
-       iter = zix_sorted_array_iter_next(t, iter), ++i) {
-    r = ith_elem(test_num, n_elems, i);
-
-    const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter);
-    if (iter_data < last) {
-      fprintf(stderr,
-              "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
-              iter_data,
-              last);
-      return test_fail();
-    }
-    last = iter_data;
-  }
-
-  if (i != zix_sorted_array_size(t)) {
-    fprintf(stderr,
-            "Iterated over only %u/%" PRIuPTR " elements\n",
-            i,
-            zix_sorted_array_size(t));
-    return test_fail();
-  }
-
-  if (zix_sorted_array_index(t, zix_sorted_array_size(t))) {
-    fprintf(stderr, "Got element past end\n");
-    return test_fail();
-  }
-
-  // Iterate over all elements by index
-  last = -1;
-  for (i = 0; i < zix_sorted_array_size(t); ++i) {
-    r = ith_elem(test_num, n_elems, i);
-
-    const intptr_t iter_data = *(intptr_t*)zix_sorted_array_index(t, i);
-    if (iter_data < last) {
-      fprintf(stderr,
-              "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
-              iter_data,
-              last);
-      return test_fail();
-    }
-
-    last = iter_data;
-  }
-
-  // Delete all elements
-  for (unsigned e = 0; e < n_elems; e++) {
-    r = ith_elem(test_num, n_elems, e);
-
-    ZixSortedArrayIter item = NULL;
-    if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) {
-      fprintf(stderr, "Failed to find item to remove\n");
-      return test_fail();
-    }
-
-    if (zix_sorted_array_remove(t, item)) {
-      fprintf(stderr, "Error removing item\n");
-    }
-  }
-
-  if (zix_sorted_array_size(t) != 0) {
-    fprintf(stderr, "Array is not empty after removing all items\n");
-    return test_fail();
-  }
-
-  zix_sorted_array_free(t);
-
-  return EXIT_SUCCESS;
-}
-
-int
-main(int argc, char** argv)
-{
-  const unsigned n_tests = 3;
-  unsigned       n_elems = 0;
-
-  if (argc == 1) {
-    n_elems = 4096;
-  } else {
-    n_elems = (unsigned)strtoul(argv[1], NULL, 10);
-    if (argc > 2) {
-      seed = (unsigned)strtoul(argv[2], NULL, 10);
-    } else {
-      seed = (unsigned)time(NULL);
-    }
-  }
-
-  if (n_elems == 0) {
-    fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]);
-    return 1;
-  }
-
-  printf(
-    "Running %u tests with %u elements (seed %u)\n", n_tests, n_elems, seed);
-
-  for (unsigned i = 0; i < n_tests; ++i) {
-    printf(".");
-    fflush(stdout);
-    if (stress(i, n_elems)) {
-      fprintf(stderr, "FAIL: Random seed %u\n", seed);
-      return test_fail();
-    }
-  }
-  printf("\n");
-  return EXIT_SUCCESS;
-}