(binary_search): Fix assertion.

[pspp-builds.git] / src / libpspp / array.c

diff --git a/src/libpspp/array.c b/src/libpspp/array.c
index da2c76e9ef2642f23ad6fa62f5e7072b4b1ab3f0..56afb1ae960abf3ab95fef0b9424cda2ed05e946 100644 (file)
--- a/src/libpspp/array.c
+++ b/src/libpspp/array.c
@@ -1,6 +1,5 @@
 /* PSPP - computes sample statistics.
    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
-   Written by Ben Pfaff <blp@gnu.org>.
 
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License as
@@ -91,7 +90,6 @@
 
 #include <config.h>
 #include "array.h"
-#include <gsl/gsl_rng.h>
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
@@ -362,6 +360,31 @@ remove_element (void *array, size_t count, size_t size,
   remove_range (array, count, size, idx, 1);
 }
 
+/* Makes room for N elements starting at IDX in ARRAY, which
+   initially consists of COUNT elements of SIZE bytes each, by
+   shifting elements IDX...COUNT (exclusive) to the right by N
+   positions. */
+void
+insert_range (void *array_, size_t count, size_t size,
+              size_t idx, size_t n) 
+{
+  char *array = array_;
+
+  assert (idx <= count);
+  memmove (array + (idx + n) * size, array + idx * size, (count - idx) * size);
+}
+
+/* Makes room for a new element at IDX in ARRAY, which initially
+   consists of COUNT elements of SIZE bytes each, by shifting
+   elements IDX...COUNT (exclusive) to the right by one
+   positions. */
+void
+insert_element (void *array, size_t count, size_t size,
+                size_t idx) 
+{
+  insert_range (array, count, size, idx, 1);
+}
+
 /* Moves an element in ARRAY, which consists of COUNT elements of
    SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
    other elements as needed.  Runs in O(abs(OLD_IDX - NEW_IDX))
@@ -392,6 +415,36 @@ move_element (void *array_, size_t count, size_t size,
     }
 }
 
+/* Moves N elements in ARRAY starting at OLD_IDX, which consists
+   of COUNT elements of SIZE bytes each, so that they now start
+   at NEW_IDX, shifting around other elements as needed. */
+void
+move_range (void *array_, size_t count, size_t size,
+            size_t old_idx, size_t new_idx, size_t n)
+{
+  assert (array_ != NULL || count == 0);
+  assert (n <= count);
+  assert (old_idx + n <= count);
+  assert (new_idx + n <= count);
+  
+  if (old_idx != new_idx && n > 0) 
+    {
+      char *array = array_;
+      char *range = xmalloc (size * n);
+      char *new = array + new_idx * size;
+      char *old = array + old_idx * size;
+
+      memcpy (range, old, size * n);
+      if (new < old)
+        memmove (new + size * n, new, (old_idx - new_idx) * size);
+      else
+        memmove (old, old + size * n, (new_idx - old_idx) * size);
+      memcpy (new, range, size * n);
+
+      free (range);
+    }
+}
+
 /* A predicate and its auxiliary data. */
 struct pred_aux 
   {
@@ -478,7 +531,7 @@ binary_search (const void *array, size_t count, size_t size,
                void *value,
                algo_compare_func *compare, const void *aux) 
 {
-  assert (array != NULL);
+  assert (array != NULL || count == 0);
   assert (count <= INT_MAX);
   assert (compare != NULL);