/*

 * librdkafka - Apache Kafka C library

 *

 * Copyright (c) 2012-2015, Magnus Edenhill

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE

 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

 * POSSIBILITY OF SUCH DAMAGE.

 */

#include "rd.h"

#include "rdlist.h"

void rd_list_dump (const char *what, const rd_list_t *rl) {

        int i;

        printf("%s: (rd_list_t*)%p cnt %d, size %d, elems %p:\n",

               what, rl, rl->rl_cnt, rl->rl_size, rl->rl_elems);

        for (i = 0 ; i < rl->rl_cnt ; i++)

                printf("  #%d: %p at &%p\n", i,

                       rl->rl_elems[i], &rl->rl_elems[i]);

}

void rd_list_grow (rd_list_t *rl, size_t size) {

        rd_assert(!(rl->rl_flags & RD_LIST_F_FIXED_SIZE));

        rl->rl_size += (int)size;

        if (unlikely(rl->rl_size == 0))

                return; /* avoid zero allocations */

        rl->rl_elems = rd_realloc(rl->rl_elems,

                                  sizeof(*rl->rl_elems) * rl->rl_size);

}

rd_list_t *

rd_list_init (rd_list_t *rl, int initial_size, void (*free_cb) (void *)) {

        memset(rl, 0, sizeof(*rl));

	if (initial_size > 0)

		rd_list_grow(rl, initial_size);

        rl->rl_free_cb = free_cb;

        return rl;

}

rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *)) {

	rd_list_t *rl = malloc(sizeof(*rl));

	rd_list_init(rl, initial_size, free_cb);

	rl->rl_flags |= RD_LIST_F_ALLOCATED;

	return rl;

}

void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size) {

	size_t allocsize;

	char *p;

	size_t i;

	rd_assert(!rl->rl_elems);

	/* Allocation layout:

	 *   void *ptrs[cnt];

	 *   elems[elemsize][cnt];

	 */

	allocsize = (sizeof(void *) * size) + (elemsize * size);

	rl->rl_elems = rd_malloc(allocsize);

	/* p points to first element's memory. */

	p = (char *)&rl->rl_elems[size];

	/* Pointer -> elem mapping */

	for (i = 0 ; i < size ; i++, p += elemsize)

		rl->rl_elems[i] = p;

	rl->rl_size = (int)size;

	rl->rl_cnt = 0;

	rl->rl_flags |= RD_LIST_F_FIXED_SIZE;

}

void rd_list_free_cb (rd_list_t *rl, void *ptr) {

        if (rl->rl_free_cb && ptr)

                rl->rl_free_cb(ptr);

}

void *rd_list_add (rd_list_t *rl, void *elem) {

        if (rl->rl_cnt == rl->rl_size)

                rd_list_grow(rl, rl->rl_size ? rl->rl_size * 2 : 16);

	rl->rl_flags &= ~RD_LIST_F_SORTED;

	if (elem)

		rl->rl_elems[rl->rl_cnt] = elem;

	return rl->rl_elems[rl->rl_cnt++];

}

void rd_list_remove_elem (rd_list_t *rl, int idx) {

        rd_assert(idx < rl->rl_cnt);

        if (idx + 1 < rl->rl_cnt)

                memmove(&rl->rl_elems[idx],

                        &rl->rl_elems[idx+1],

                        sizeof(*rl->rl_elems) * (rl->rl_cnt - (idx+1)));

        rl->rl_cnt--;

}

void *rd_list_remove (rd_list_t *rl, void *match_elem) {

        void *elem;

        int i;

        RD_LIST_FOREACH(elem, rl, i) {

                if (elem == match_elem) {

                        rd_list_remove_elem(rl, i);

                        return elem;

                }

        }

        return NULL;

}

void *rd_list_remove_cmp (rd_list_t *rl, void *match_elem,

                          int (*cmp) (void *_a, void *_b)) {

        void *elem;

        int i;

        RD_LIST_FOREACH(elem, rl, i) {

                if (elem == match_elem ||

                    !cmp(elem, match_elem)) {

                        rd_list_remove_elem(rl, i);

                        return elem;

                }

        }

        return NULL;

}

int rd_list_remove_multi_cmp (rd_list_t *rl, void *match_elem,

                              int (*cmp) (void *_a, void *_b)) {

        void *elem;

        int i;

        int cnt = 0;

        /* Scan backwards to minimize memmoves */

        RD_LIST_FOREACH_REVERSE(elem, rl, i) {

                if (match_elem == cmp ||

                    !cmp(elem, match_elem)) {

                        rd_list_remove_elem(rl, i);

                        cnt++;

                }

        }

        return cnt;

}

/**

 * Trampoline to avoid the double pointers in callbacks.

 *

 * rl_elems is a **, but to avoid having the application do the cumbersome

 * ** -> * casting we wrap this here and provide a simple * pointer to the

 * the callbacks.

 *

 * This is true for all list comparator uses, i.e., both sort() and find().

 */

static RD_TLS int (*rd_list_cmp_curr) (const void *, const void *);

static RD_INLINE

int rd_list_cmp_trampoline (const void *_a, const void *_b) {

	const void *a = *(const void **)_a, *b = *(const void **)_b;

	return rd_list_cmp_curr(a, b);

}

void rd_list_sort (rd_list_t *rl, int (*cmp) (const void *, const void *)) {

	rd_list_cmp_curr = cmp;

        qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems),

	      rd_list_cmp_trampoline);

	rl->rl_flags |= RD_LIST_F_SORTED;

}

void rd_list_clear (rd_list_t *rl) {

        rl->rl_cnt = 0;

	rl->rl_flags &= ~RD_LIST_F_SORTED;

}

void rd_list_destroy (rd_list_t *rl) {

        if (rl->rl_elems) {

                int i;

                if (rl->rl_free_cb) {

                        for (i = 0 ; i < rl->rl_cnt ; i++)

                                if (rl->rl_elems[i])

                                        rl->rl_free_cb(rl->rl_elems[i]);

                }

		rd_free(rl->rl_elems);

        }

	if (rl->rl_flags & RD_LIST_F_ALLOCATED)

		rd_free(rl);

}

void *rd_list_elem (const rd_list_t *rl, int idx) {

        if (likely(idx < rl->rl_cnt))

                return (void *)rl->rl_elems[idx];

        return NULL;

}

void *rd_list_find (const rd_list_t *rl, const void *match,

                    int (*cmp) (const void *, const void *)) {

        int i;

        const void *elem;

	if (rl->rl_flags & RD_LIST_F_SORTED) {

		void **r;

		rd_list_cmp_curr = cmp;

		r = bsearch(&match/*ptrptr to match elems*/,

			    rl->rl_elems, rl->rl_cnt,

			    sizeof(*rl->rl_elems), rd_list_cmp_trampoline);

		return r ? *r : NULL;

	}

        RD_LIST_FOREACH(elem, rl, i) {

                if (!cmp(match, elem))

                        return (void *)elem;

        }

        return NULL;

}

int rd_list_cmp (const rd_list_t *a, rd_list_t *b,

		 int (*cmp) (const void *, const void *)) {

	int i;

	i = a->rl_cnt - b->rl_cnt;

	if (i)

		return i;

	for (i = 0 ; i < a->rl_cnt ; i++) {

		int r = cmp(a->rl_elems[i], b->rl_elems[i]);

		if (r)

			return r;

	}

	return 0;

}

/**

 * @brief Simple element pointer comparator

 */

int rd_list_cmp_ptr (const void *a, const void *b) {

        if (a < b)

                return -1;

        else if (a > b)

                return 1;

        return 0;

}

void rd_list_apply (rd_list_t *rl,

                    int (*cb) (void *elem, void *opaque), void *opaque) {

        void *elem;

        int i;

        RD_LIST_FOREACH(elem, rl, i) {

                if (!cb(elem, opaque)) {

                        rd_list_remove_elem(rl, i);

                        i--;

                }

        }

        return;

}

/**

 * @brief Default element copier that simply assigns the original pointer.

 */

static void *rd_list_nocopy_ptr (const void *elem, void *opaque) {

        return (void *)elem;

}

rd_list_t *rd_list_copy (const rd_list_t *src,

                         void *(*copy_cb) (const void *elem, void *opaque),

                         void *opaque) {

        rd_list_t *dst;

        dst = rd_list_new(src->rl_cnt, src->rl_free_cb);

        rd_list_copy_to(dst, src, copy_cb, opaque);

        return dst;

}

void rd_list_copy_to (rd_list_t *dst, const rd_list_t *src,

                      void *(*copy_cb) (const void *elem, void *opaque),

                      void *opaque) {

        void *elem;

        int i;

        if (!copy_cb)

                copy_cb = rd_list_nocopy_ptr;

        RD_LIST_FOREACH(elem, src, i) {

                void *celem = copy_cb(elem, opaque);

                if (celem)

                        rd_list_add(dst, celem);

        }

}