/*

 * adcli

 *

 * Copyright (C) 2013 Red Hat Inc.

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU Lesser General Public License as

 * published by the Free Software Foundation; either version 2.1 of

 * the License, or (at your option) any later version.

 *

 * 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,

 * MA 02110-1301 USA

 *

 * Author: Stef Walter <stefw@redhat.com>

 */

#include "config.h"

#include "seq.h"

#include <assert.h>

#include <stdlib.h>

#include <string.h>

/* For detecting clang features */

#ifndef __has_feature

#define __has_feature(x) 0

#endif

#ifndef CLANG_ANALYZER_NORETURN

#if __has_feature(attribute_analyzer_noreturn)

#define CLANG_ANALYZER_NORETURN __attribute__((analyzer_noreturn))

#else

#define CLANG_ANALYZER_NORETURN

#endif

#endif

/* to make coverage simple */

#define bail_on_null(v) do { if ((v) == NULL) return bail_null (); } while (0)

static void *

bail_null (void)

CLANG_ANALYZER_NORETURN;

static void *

bail_null (void)

{

	return NULL;

}

static int

alloc_size (int num)

{

	int n = num ? 1 : 0;

	while (n < num && n > 0)

		n <<= 1;

	return n;

}

int

seq_count (seq_voidp sequence)

{

	void **seq = sequence;

	int count;

	for (count = 0; seq && seq[count]; count++);

	return count;

}

static void **

guarantee_one_more (void **seq,

                    int len)

{

	int alloc;

	alloc = alloc_size (len + 1);

	assert (alloc != 0);

	if (len + 2 > alloc) {

		assert (alloc != 0);

		seq = realloc (seq, alloc * 2 * sizeof (void *));

	}

	return seq;

}

void *

seq_push (seq_voidp sequence,

          int *length,

          void *value)

{

	void **seq = sequence;

	int len;

	assert (length != NULL);

	assert (value != NULL);

	len = *length;

	seq = guarantee_one_more (seq, len);

	if (seq) {

		seq[len++] = value;

		seq[len] = NULL;

		*length = len;

	}

	return seq;

}

static int

linear_search (void **seq,

               int low,

               int high,

               void *match,

               seq_compar compar)

{

	int at;

	for (at = low; at < high; at++) {

		if (compar (match, seq[at]) == 0) {

			break;

		}

	}

	return at;

}

static int

binary_search (void **seq,

               int low,

               int high,

               void *match,

               seq_compar compar)

{

	int res;

	int mid;

	if (low == high)

		return low;

	mid = low + ((high - low) / 2);

	res = compar (match, seq[mid]);

	if (res > 0)

		return binary_search (seq, mid + 1, high, match, compar);

	else if (res < 0)

		return binary_search (seq, low, mid, match, compar);

	return mid;

}

void *

seq_insert (seq_voidp sequence,

            int *length,

            void *value,

            seq_compar compar,

            seq_destroy destroy)

{

	void **seq = sequence;

	int at;

	int len;

	assert (length != NULL);

	assert (compar != NULL);

	assert (value != NULL);

	len = *length;

	at = binary_search (seq, 0, len, value, compar);

	/* We already have a matching value */

	if (at < len && compar (value, seq[at]) == 0) {

		if (destroy != NULL)

			destroy (seq[at]);

	/* Need to insert a value */

	} else {

		seq = guarantee_one_more (seq, len);

		bail_on_null (seq);

		memmove (seq + at + 1, seq + at, (len - at) * sizeof (void *));

		len++;

		seq[len] = NULL;

	}

	seq[at] = value;

	*length = len;

	return seq;

}

static void

seq_remove_int (seq_voidp sequence,

                int *length,

                void *match,

                seq_search search,

                seq_compar compar,

                seq_destroy destroy)

{

	void **seq = sequence;

	int at;

	int len;

	assert (length != NULL);

	assert (compar != NULL);

	assert (match != NULL);

	len = *length;

	at = search (seq, 0, len, match, compar);

	/* We have a matching value */

	if (at < len && compar (match, seq[at]) == 0) {

		if (destroy != NULL)

			destroy (seq[at]);

		memmove (seq + at, seq + at + 1, (len - at) * sizeof (void *));

		len--;

		seq[len] = NULL;

	}

	*length = len;

}

void

seq_remove (seq_voidp sequence,

            int *length,

            void *match,

            seq_compar compar,

            seq_destroy destroy)

{

	return seq_remove_int (sequence, length, match, binary_search, compar, destroy);

}

void

seq_remove_unsorted (seq_voidp sequence,

                     int *length,

                     void *match,

                     seq_compar compar,

                     seq_destroy destroy)

{

	return seq_remove_int (sequence, length, match, linear_search, compar, destroy);

}

void

seq_filter (seq_voidp sequence,

            int *length,

            void *match,

            seq_compar compar,

            seq_destroy destroy)

{

	void **seq = sequence;

	int len;

	int in, out;

	assert (length != NULL);

	assert (compar != NULL);

	if (!sequence)

		return;

	len = *length;

	for (in = 0, out = 0; in < len; in++) {

		if (compar (match, seq[in]) == 0) {

			seq[out++] = seq[in];

		} else {

			if (destroy)

				destroy (seq[in]);

		}

	}

	seq[out] = NULL;

	*length = out;

}

void *

seq_lookup (seq_voidp sequence,

            int *length,

            void *match,

            seq_compar compar)

{

	void **seq = sequence;

	int at;

	int len;

	assert (length != NULL);

	assert (compar != NULL);

	assert (match != NULL);

	len = *length;

	at = binary_search (seq, 0, len, match, compar);

	/* We have a matching value */

	if (at < len && compar (match, seq[at]) == 0)

		return seq[at];

	return NULL;

}

void *

seq_dup (seq_voidp sequence,

         int *length,

         seq_copy copy)

{

	void **seq = sequence;

	void **copied;

	int alloc;

	int len;

	int at;

	assert (length != NULL);

	len = *length;

	alloc = alloc_size (len + 1);

	assert (alloc != 0);

	copied = calloc (alloc, sizeof (void *));

	bail_on_null (copied);

	for (at = 0; at < len; at++) {

		if (copy == NULL) {

			copied[at] = seq[at];

		} else {

			copied[at] = copy (seq[at]);

			bail_on_null (copied[at]);

		}

	}

	copied[len] = NULL;

	return copied;

}

void

seq_free (seq_voidp sequence,

          seq_destroy destroy)

{

	void **seq = sequence;

	int at;

	for (at = 0; destroy && seq && seq[at] != NULL; at++)

		(destroy) (seq[at]);

	free (seq);

}

#ifdef SEQ_TESTS

#include "test.h"

static void

test_push (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_push (seq, &len, "5");

	seq = seq_push (seq, &len, "4");

	seq = seq_push (seq, &len, "3");

	seq = seq_push (seq, &len, "2");

	seq = seq_push (seq, &len, "1");

	assert (seq != NULL);

	assert_str_eq (seq[0], "5");

	assert_str_eq (seq[1], "4");

	assert_str_eq (seq[2], "3");

	assert_str_eq (seq[3], "2");

	assert_str_eq (seq[4], "1");

	assert (seq[5] == NULL);

	assert_num_eq (len, 5);

	seq_free (seq, NULL);

}

static void

test_insert (void)

{

	void **seq = NULL;

	int len = 0;

	/* Note that we have a duplicate ... */

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	/* ... which doesn't show up here */

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "2");

	assert_str_eq (seq[2], "3");

	assert_str_eq (seq[3], "4");

	assert_str_eq (seq[4], "5");

	assert (seq[5] == NULL);

	assert_num_eq (len, 5);

	seq_free (seq, NULL);

}

static void **destroyed = NULL;

static void

steal_destroyed (void *value)

{

	int len = seq_count (destroyed);

	destroyed = seq_push (destroyed, &len, value);

}

static void

test_insert_destroys (void)

{

	void **seq = NULL;

	int len = 0;

	destroyed = NULL;

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, steal_destroyed);

	assert_str_eq (seq[0], "3");

	assert_str_eq (seq[1], "4");

	assert_str_eq (seq[2], "5");

	assert (seq[3] == NULL);

	assert (destroyed != NULL);

	assert_str_eq (destroyed[0], "3");

	assert_str_eq (destroyed[1], "3");

	assert_str_eq (destroyed[2], "4");

	assert (destroyed[3] == NULL);

	seq_free (seq, NULL);

	seq_free (destroyed, NULL);

	destroyed = NULL;

}

static void

test_remove (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "2");

	assert_str_eq (seq[2], "3");

	assert_str_eq (seq[3], "4");

	assert_str_eq (seq[4], "5");

	assert (seq[5] == NULL);

	assert_num_eq (len, 5);

	seq_remove (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq_remove (seq, &len, "2", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "4");

	assert_str_eq (seq[2], "5");

	assert (seq[3] == NULL);

	assert_num_eq (len, 3);

	seq_free (seq, NULL);

}

static void

test_remove_unsorted (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_push (seq, &len, "3");

	seq = seq_push (seq, &len, "5");

	seq = seq_push (seq, &len, "1");

	seq = seq_push (seq, &len, "4");

	seq = seq_push (seq, &len, "2");

	assert_str_eq (seq[0], "3");

	assert_str_eq (seq[1], "5");

	assert_str_eq (seq[2], "1");

	assert_str_eq (seq[3], "4");

	assert_str_eq (seq[4], "2");

	assert (seq[5] == NULL);

	assert_num_eq (len, 5);

	seq_remove_unsorted (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq_remove_unsorted (seq, &len, "2", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "5");

	assert_str_eq (seq[1], "1");

	assert_str_eq (seq[2], "4");

	assert (seq[3] == NULL);

	assert_num_eq (len, 3);

	seq_free (seq, NULL);

}

static void

test_remove_first (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "2");

	assert_str_eq (seq[2], "3");

	assert_str_eq (seq[3], "4");

	assert_str_eq (seq[4], "5");

	assert (seq[5] == NULL);

	assert_num_eq (len, 5);

	seq_remove (seq, &len, "1", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "2");

	assert_str_eq (seq[1], "3");

	assert_str_eq (seq[2], "4");

	assert_str_eq (seq[3], "5");

	assert (seq[4] == NULL);

	assert_num_eq (len, 4);

	seq_free (seq, NULL);

}

static void

test_remove_last (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "2");

	assert_str_eq (seq[2], "3");

	assert_str_eq (seq[3], "4");

	assert (seq[4] == NULL);

	assert_num_eq (len, 4);

	seq_remove (seq, &len, "4", (seq_compar)strcmp, NULL);

	assert_str_eq (seq[0], "1");

	assert_str_eq (seq[1], "2");

	assert_str_eq (seq[2], "3");

	assert (seq[3] == NULL);

	assert_num_eq (len, 3);

	seq_free (seq, NULL);

}

static int

compar_even (void *match,

             void *value)

{

	int val;

	assert_str_eq (match, "even");

	val = atoi (value);

	if (val % 2 == 0)

		return 0;

	return -1;

}

static void

test_filter (void)

{

	void **seq = NULL;

	int len = 0;

	seq = seq_push (seq, &len, "1");

	seq = seq_push (seq, &len, "2");

	seq = seq_push (seq, &len, "3");

	seq = seq_push (seq, &len, "4");

	seq = seq_push (seq, &len, "5");

	seq = seq_push (seq, &len, "6");

	seq = seq_push (seq, &len, "7");

	seq = seq_push (seq, &len, "8");

	assert (len == 8);

	destroyed = NULL;

	seq_filter (seq, &len, "even", compar_even, steal_destroyed);

	assert_str_eq (seq[0], "2");

	assert_str_eq (seq[1], "4");

	assert_str_eq (seq[2], "6");

	assert_str_eq (seq[3], "8");

	assert (seq[4] == NULL);

	assert_num_eq (len, 4);

	assert (destroyed != NULL);

	assert_str_eq (destroyed[0], "1");

	assert_str_eq (destroyed[1], "3");

	assert_str_eq (destroyed[2], "5");

	assert_str_eq (destroyed[3], "7");

	assert (seq[4] == NULL);

	assert_num_eq (len, 4);

	seq_free (destroyed, NULL);

	seq_free (seq, NULL);

}

static void

test_filter_null (void)

{

	int len = 0;

	seq_filter (NULL, &len, "even", compar_even, NULL);

}

static void

test_remove_destroys (void)

{

	void **seq = NULL;

	int len = 0;

	destroyed = NULL;

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, steal_destroyed);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, steal_destroyed);

	assert (destroyed == NULL);

	seq_remove (seq, &len, "5", (seq_compar)strcmp, steal_destroyed);

	seq_remove (seq, &len, "4", (seq_compar)strcmp, steal_destroyed);

	seq_remove (seq, &len, "3", (seq_compar)strcmp, steal_destroyed);

	assert (seq[0] == NULL);

	assert (destroyed != NULL);

	assert_str_eq (destroyed[0], "5");

	assert_str_eq (destroyed[1], "4");

	assert_str_eq (destroyed[2], "3");

	assert (destroyed[3] == NULL);

	seq_free (seq, NULL);

	seq_free (destroyed, NULL);

	destroyed = NULL;

}

static void

test_lookup (void)

{

	void **seq = NULL;

	int len = 0;

	char *one = "1";

	char *two = "2";

	char *three = "3";

	char *four = "4";

	char *five = "5";

	char lookup[2] = { 0, 0 };

	char *check;

	seq = seq_insert (seq, &len, five, (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, two, (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, four, (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, three, (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, one, (seq_compar)strcmp, NULL);

	assert (len == 5);

	/* Make sure not searching for same pointer */

	lookup[0] = '1';

	check = seq_lookup (seq, &len, lookup, (seq_compar)strcmp);

	assert (check == one);

	lookup[0] = '3';

	check = seq_lookup (seq, &len, lookup, (seq_compar)strcmp);

	assert (check == three);

	check = seq_lookup (seq, &len, three, (seq_compar)strcmp);

	assert (check == three);

	lookup[0] = '8';

	check = seq_lookup (seq, &len, lookup, (seq_compar)strcmp);

	assert (check == NULL);

	seq_free (seq, NULL);

}

static void

test_dup (void)

{

	void **seq = NULL;

	void **dup;

	int len = 0;

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	dup = seq_dup (seq, &len, NULL);

	assert (dup != NULL);

	assert_str_eq (dup[0], "1");

	assert_str_eq (dup[1], "2");

	assert_str_eq (dup[2], "3");

	assert_str_eq (dup[3], "4");

	assert_str_eq (dup[4], "5");

	assert (dup[5] == NULL);

	seq_free (seq, NULL);

	seq_free (dup, NULL);

}

static void

test_dup_deep (void)

{

	void **seq = NULL;

	int len = 0;

	void **dup;

	seq = seq_insert (seq, &len, "5", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "2", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "4", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "3", (seq_compar)strcmp, NULL);

	seq = seq_insert (seq, &len, "1", (seq_compar)strcmp, NULL);

	dup = seq_dup (seq, &len, (seq_copy)strdup);

	assert (dup != NULL);

	assert_str_eq (dup[0], "1");

	assert_str_eq (dup[1], "2");

	assert_str_eq (dup[2], "3");

	assert_str_eq (dup[3], "4");

	assert_str_eq (dup[4], "5");

	assert (dup[5] == NULL);

	seq_free (seq, NULL);

	seq_free (dup, free);

}

static void

test_free_null (void)

{

	seq_free (NULL, NULL);

	seq_free (NULL, free);

}

int

main (int argc,

      char *argv[])

{

	test_func (test_push, "/seq/push");

	test_func (test_insert, "/seq/insert");

	test_func (test_insert_destroys, "/seq/insert_destroys");

	test_func (test_remove, "/seq/remove");

	test_func (test_remove_unsorted, "/seq/remove_unsorted");

	test_func (test_remove_first, "/seq/remove_first");

	test_func (test_remove_last, "/seq/remove_last");

	test_func (test_remove_destroys, "/seq/remove_destroys");

	test_func (test_filter, "/seq/filter");

	test_func (test_filter_null, "/seq/filter_null");

	test_func (test_lookup, "/seq/lookup");

	test_func (test_dup, "/seq/dup");

	test_func (test_dup_deep, "/seq/dup_deep");

	test_func (test_free_null, "/seq/free_null");

	return test_run (argc, argv);

}

#endif /* SEQ_TESTS */