/*
 * 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_init_copy (rd_list_t *dst, const rd_list_t *src) {

        if (src->rl_flags & RD_LIST_F_FIXED_SIZE) {
                /* Source was preallocated, prealloc new dst list */
                rd_list_init(dst, 0, src->rl_free_cb);

                rd_list_prealloc_elems(dst, src->rl_elemsize, src->rl_size,
                                       1/*memzero*/);
        } else {
                /* Source is dynamic, initialize dst the same */
                rd_list_init(dst, rd_list_cnt(src), src->rl_free_cb);

        }

        return dst;
}

static RD_INLINE rd_list_t *rd_list_alloc (void) {
        return rd_malloc(sizeof(rd_list_t));
}

rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *)) {
	rd_list_t *rl = rd_list_alloc();
	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 cnt,
                             int memzero) {
	size_t allocsize;
	char *p;
	size_t i;

	rd_assert(!rl->rl_elems);

	/* Allocation layout:
	 *   void *ptrs[cnt];
	 *   elems[elemsize][cnt];
	 */

	allocsize = (sizeof(void *) * cnt) + (elemsize * cnt);
        if (memzero)
                rl->rl_elems = rd_calloc(1, allocsize);
        else
                rl->rl_elems = rd_malloc(allocsize);

        /* p points to first element's memory, unless elemsize is 0. */
        if (elemsize > 0)
                p = rl->rl_p = (char *)&rl->rl_elems[cnt];
        else
                p = rl->rl_p = NULL;

	/* Pointer -> elem mapping */
	for (i = 0 ; i < cnt ; i++, p += elemsize)
		rl->rl_elems[i] = p;

	rl->rl_size = (int)cnt;
	rl->rl_cnt = 0;
	rl->rl_flags |= RD_LIST_F_FIXED_SIZE;
        rl->rl_elemsize = (int)elemsize;
}


void rd_list_set_cnt (rd_list_t *rl, size_t cnt) {
        rd_assert(rl->rl_flags & RD_LIST_F_FIXED_SIZE);
        rd_assert((int)cnt <= rl->rl_size);
        rl->rl_cnt = (int)cnt;
}


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_set (rd_list_t *rl, int idx, void *ptr) {
        if (idx >= rl->rl_size)
                rd_list_grow(rl, idx+1);

        if (idx >= rl->rl_cnt) {
                memset(&rl->rl_elems[rl->rl_cnt], 0,
                       sizeof(*rl->rl_elems) * (idx-rl->rl_cnt));
                rl->rl_cnt = idx+1;
        } else {
                /* Not allowed to replace existing element. */
                rd_assert(!rl->rl_elems[idx]);
        }

        rl->rl_elems[idx] = ptr;
}



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;
}


void *rd_list_pop (rd_list_t *rl) {
        void *elem;
        int idx = rl->rl_cnt - 1;

        if (idx < 0)
                return NULL;

        elem = rl->rl_elems[idx];
        rd_list_remove_elem(rl, idx);

        return elem;
}


/**
 * 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 *)) {
        if (unlikely(rl->rl_elems == NULL))
                return;

	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;
}

static void rd_list_destroy_elems (rd_list_t *rl) {
        int i;

        if (!rl->rl_elems)
                return;

        if (rl->rl_free_cb) {
                /* Free in reverse order to allow deletions */
                for (i = rl->rl_cnt - 1 ; i >= 0 ; i--)
                        if (rl->rl_elems[i])
                                rl->rl_free_cb(rl->rl_elems[i]);
        }

        rd_free(rl->rl_elems);
        rl->rl_elems = NULL;
        rl->rl_cnt = 0;
        rl->rl_size = 0;
        rl->rl_flags &= ~RD_LIST_F_SORTED;
}


void rd_list_clear (rd_list_t *rl) {
        rd_list_destroy_elems(rl);
}


void rd_list_destroy (rd_list_t *rl) {
        rd_list_destroy_elems(rl);
        if (rl->rl_flags & RD_LIST_F_ALLOCATED)
                rd_free(rl);
}

void rd_list_destroy_free (void *rl) {
        rd_list_destroy((rd_list_t *)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;
}

int rd_list_index (const rd_list_t *rl, const void *match,
                   int (*cmp) (const void *, const void *)) {
        int i;
        const void *elem;

        RD_LIST_FOREACH(elem, rl, i) {
                if (!cmp(match, elem))
                        return i;
        }

        return -1;
}


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;
}


void *rd_list_first (const rd_list_t *rl) {
        if (rl->rl_cnt == 0)
                return NULL;
        return rl->rl_elems[0];
}

void *rd_list_last (const rd_list_t *rl) {
        if (rl->rl_cnt == 0)
                return NULL;
        return rl->rl_elems[rl->rl_cnt-1];
}


void *rd_list_find_duplicate (const rd_list_t *rl,
                              int (*cmp) (const void *, const void *)) {
        int i;

        rd_assert(rl->rl_flags & RD_LIST_F_SORTED);

        for (i = 1 ; i < rl->rl_cnt ; i++) {
                if (!cmp(rl->rl_elems[i-1],
                         rl->rl_elems[i]))
                        return rl->rl_elems[i];
        }

        return NULL;
}

int rd_list_cmp (const rd_list_t *a, const rd_list_t *b,
		 int (*cmp) (const void *, const void *)) {
	int i;

	i = RD_CMP(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) {
        return RD_CMP(a, b);
}

int rd_list_cmp_str (const void *a, const void *b) {
        return strcmp((const char *)a, (const char *)b);
}

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,
                         rd_list_copy_cb_t *copy_cb, 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;

        rd_assert(dst != src);

        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);
        }
}


/**
 * @brief Copy elements of preallocated \p src to preallocated \p dst.
 *
 * @remark \p dst will be overwritten and initialized, but its
 *         flags will be retained.
 *
 * @returns \p dst
 */
static rd_list_t *rd_list_copy_preallocated0 (rd_list_t *dst,
                                              const rd_list_t *src) {
        int dst_flags = dst->rl_flags & RD_LIST_F_ALLOCATED;

        rd_assert(dst != src);

        rd_list_init_copy(dst, src);
        dst->rl_flags |= dst_flags;

        rd_assert((dst->rl_flags & RD_LIST_F_FIXED_SIZE));
        rd_assert((src->rl_flags & RD_LIST_F_FIXED_SIZE));
        rd_assert(dst->rl_elemsize == src->rl_elemsize &&
                  dst->rl_size == src->rl_size);

        memcpy(dst->rl_p, src->rl_p, src->rl_elemsize * src->rl_size);
        dst->rl_cnt = src->rl_cnt;

        return dst;
}

void *rd_list_copy_preallocated (const void *elem, void *opaque) {
        return rd_list_copy_preallocated0(rd_list_new(0, NULL),
                                          (const rd_list_t *)elem);
}


/**
 * @name Misc helpers for common list types
 * @{
 *
 */
rd_list_t *rd_list_init_int32 (rd_list_t *rl, int max_size) {
        int rl_flags = rl->rl_flags & RD_LIST_F_ALLOCATED;
        rd_list_init(rl, 0, NULL);
        rl->rl_flags |= rl_flags;
        rd_list_prealloc_elems(rl, sizeof(int32_t), max_size, 1/*memzero*/);
        return rl;
}

void rd_list_set_int32 (rd_list_t *rl, int idx, int32_t val) {
        rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
                  rl->rl_elemsize == sizeof(int32_t));
        rd_assert(idx < rl->rl_size);

        memcpy(rl->rl_elems[idx], &val, sizeof(int32_t));

        if (rl->rl_cnt <= idx)
                rl->rl_cnt = idx+1;
}

int32_t rd_list_get_int32 (const rd_list_t *rl, int idx) {
        rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
                  rl->rl_elemsize == sizeof(int32_t) &&
                  idx < rl->rl_cnt);
        return *(int32_t *)rl->rl_elems[idx];
}




/**@}*/