/*

 * 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.

 */

#ifndef _RDLIST_H_

#define _RDLIST_H_

/**

 *

 * Simple light-weight append-only list to be used as a collection convenience.

 *

 */

typedef struct rd_list_s {

        int    rl_size;

        int    rl_cnt;

        void **rl_elems;

	void (*rl_free_cb) (void *);

	int    rl_flags;

#define RD_LIST_F_ALLOCATED  0x1  /* The rd_list_t is allocated,

				   * will be free on destroy() */

#define RD_LIST_F_SORTED     0x2  /* Set by sort(), cleared by any mutations.

				   * When this flag is set bsearch() is used

				   * by find(), otherwise a linear search. */

#define RD_LIST_F_FIXED_SIZE 0x4  /* Assert on grow */

#define RD_LIST_F_UNIQUE     0x8  /* Don't allow duplicates:

                                   * ONLY ENFORCED BY CALLER. */

} rd_list_t;

/**

 * @brief Initialize a list, preallocate space for 'initial_size' elements

 *       (optional).

 *       List elements will optionally be freed by \p free_cb.

 *

 * @returns \p rl

 */

rd_list_t *

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

/**

 * Allocate a new list pointer and initialize it according to rd_list_init().

 *

 * Use rd_list_destroy() to free.

 */

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

/**

 * @brief Prepare list to for an additional \p size elements.

 *        This is an optimization to avoid incremental grows.

 */

void rd_list_grow (rd_list_t *rl, size_t size);

/**

 * @brief Preallocate elements to avoid having to pass an allocated pointer to

 *        rd_list_add(), instead pass NULL to rd_list_add() and use the returned

 *        pointer as the element.

 *

 * @param elemsize element size

 * @param size number of elements

 *

 * @remark Preallocated element lists can't grow past \p size.

 */

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

/**

 * @brief Free a pointer using the list's free_cb

 *

 * @remark If no free_cb is set, or \p ptr is NULL, dont do anything

 *

 * Typical use is rd_list_free_cb(rd_list_remove_cmp(....));

 */

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

/**

 * @brief Append element to list

 *

 * @returns \p elem. If \p elem is NULL the default element for that index

 *          will be returned (for use with set_elems).

 */

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

/**

 * Remove element from list.

 * This is a slow O(n) + memmove operation.

 * Returns the removed element.

 */

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

/**

 * Remove element from list using comparator.

 * See rd_list_remove()

 */

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

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

/**

 * @brief Remove element at index \p idx.

 *

 * This is a O(1) + memmove operation

 */

void rd_list_remove_elem (rd_list_t *rl, int idx);

/**

 * @brief Remove all elements matching comparator.

 *

 * @returns the number of elements removed.

 *

 * @sa rd_list_remove()

 */

int rd_list_remove_multi_cmp (rd_list_t *rl, void *match_elem,

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

/**

 * Sort list using comparator

 */

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

/**

 * Empties the list (but does not free any memory)

 */

void rd_list_clear (rd_list_t *rl);

/**

 * Empties the list, frees the element array, and optionally frees

 * each element using the registered \c rl->rl_free_cb.

 *

 * If the list was previously allocated with rd_list_new() it will be freed.

 */

void rd_list_destroy (rd_list_t *rl);

/**

 * Returns the element at index 'idx', or NULL if out of range.

 *

 * Typical iteration is:

 *    int i = 0;

 *    my_type_t *obj;

 *    while ((obj = rd_list_elem(rl, i++)))

 *        do_something(obj);

 */

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

#define RD_LIST_FOREACH(elem,listp,idx) \

        for (idx = 0 ; (elem = rd_list_elem(listp, idx)) ; idx++)

#define RD_LIST_FOREACH_REVERSE(elem,listp,idx)                         \

        for (idx = (listp)->rl_cnt-1 ;                                  \

             idx >= 0 && (elem = rd_list_elem(listp, idx)) ; idx--)

/**

 * Returns the number of elements in list.

 */

static RD_INLINE RD_UNUSED int rd_list_cnt (const rd_list_t *rl) {

        return rl->rl_cnt;

}

/**

 * Returns true if list is empty

 */

#define rd_list_empty(rl) (rd_list_cnt(rl) == 0)

/**

 * Find element using comparator

 * 'match' will be the first argument to 'cmp', and each element (up to a match)

 * will be the second argument to 'cmp'.

 */

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

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

/**

 * @brief Compare list \p a to \p b.

 *

 * @returns < 0 if a was "lesser" than b,

 *          > 0 if a was "greater" than b,

 *            0 if a and b are equal.

 */

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

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

/**

 * @brief Simple element pointer comparator

 */

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

/**

 * @brief Apply \p cb to each element in list, if \p cb returns 0

 *        the element will be removed (but not freed).

 */

void rd_list_apply (rd_list_t *rl,

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

/**

 * @brief Copy list \p src, returning a new list,

 *        using optional \p copy_cb (per elem)

 */

rd_list_t *rd_list_copy (const rd_list_t *src,

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

                         void *opaque);

/**

 * @brief Copy list \p src to \p dst using optional \p copy_cb (per elem)

 * @remark The destination list is not initialized or copied by this function.

 * @remark copy_cb() may return NULL in which case no element is added,

 *                   but the copy callback might have done so itself.

 */

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

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

                      void *opaque);

/**

 * @brief String copier for rd_list_copy()

 */

static RD_UNUSED

void *rd_list_string_copy (const void *elem, void *opaque) {

        return rd_strdup((const char *)elem);

}

/**

 * Debugging: Print list to stdout.

 */

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

#endif /* _RDLIST_H_ */