/*
 * 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, when prealloc()ed */
#define RD_LIST_F_UNIQUE                                                       \
        0x8              /* Don't allow duplicates:                            \
                          * ONLY ENFORCED BY CALLER. */
        int rl_elemsize; /**< Element size (when prealloc()ed) */
        void *rl_p;      /**< Start of prealloced elements,
                          *   the allocation itself starts at rl_elems
                          */
} rd_list_t;


/**
 * @brief Initialize a list, prepare for 'initial_size' elements
 *        (optional optimization).
 *        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 *));


/**
 * @brief Same as rd_list_init() but uses initial_size and free_cb
 *        from the provided \p src list.
 */
rd_list_t *rd_list_init_copy(rd_list_t *rl, const rd_list_t *src);

/**
 * @brief Allocate a new list pointer and initialize
 *        it according to rd_list_init().
 *
 *        This is the same as calling \c rd_list_init(rd_list_alloc(), ..));
 *
 * 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, or 0 if elements are allocated separately.
 * @param size number of elements
 * @param memzero initialize element memory to zeros.
 *
 * @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,
                            int memzero);

/**
 * @brief Set the number of valid elements, this must only be used
 *        with prealloc_elems() to make the preallocated elements directly
 *        usable.
 */
void rd_list_set_cnt(rd_list_t *rl, size_t cnt);


/**
 * @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);


/**
 * @brief Set element at \p idx to \p ptr.
 *
 * @remark MUST NOT overwrite an existing element.
 * @remark The list will be grown, if needed, any gaps between the current
 *         highest element and \p idx will be set to NULL.
 */
void rd_list_set(rd_list_t *rl, int idx, void *ptr);


/**
 * 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 and return the last element in the list.
 *
 * @returns the last element, or NULL if list is empty. */
void *rd_list_pop(rd_list_t *rl);


/**
 * @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));


/**
 * @brief Sort list using comparator.
 *
 * To sort a list ascendingly the comparator should implement (a - b)
 * and for descending order implement (b - a).
 */
void rd_list_sort(rd_list_t *rl, int (*cmp)(const void *, const void *));


/**
 * Empties the list and frees elements (if there is a free_cb).
 */
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);

/**
 * @brief Wrapper for rd_list_destroy() that has same signature as free(3),
 *        allowing it to be used as free_cb for nested lists.
 */
void rd_list_destroy_free(void *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)


/**
 * @brief Find element index using comparator.
 *
 * \p match is the first argument to \p cmp, and each element (up to a match)
 * is the second argument to \p cmp.
 *
 * @remark this is a O(n) scan.
 * @returns the first matching element or NULL.
 */
int rd_list_index(const rd_list_t *rl,
                  const void *match,
                  int (*cmp)(const void *, const void *));

/**
 * @brief Find element using comparator
 *
 * \p match is the first argument to \p cmp, and each element (up to a match)
 * is the second argument to \p cmp.
 *
 * @remark if the list is sorted bsearch() is used, otherwise an O(n) scan.
 *
 * @returns the first matching element or NULL.
 */
void *rd_list_find(const rd_list_t *rl,
                   const void *match,
                   int (*cmp)(const void *, const void *));



/**
 * @returns the first element of the list, or NULL if list is empty.
 */
void *rd_list_first(const rd_list_t *rl);

/**
 * @returns the last element of the list, or NULL if list is empty.
 */
void *rd_list_last(const rd_list_t *rl);


/**
 * @returns the first duplicate in the list or NULL if no duplicates.
 *
 * @warning The list MUST be sorted.
 */
void *rd_list_find_duplicate(const rd_list_t *rl,
                             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,
                const 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 strcmp comparator where the list elements are strings.
 */
int rd_list_cmp_str(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);



typedef void *(rd_list_copy_cb_t)(const void *elem, 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, rd_list_copy_cb_t *copy_cb, 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 Copy callback to copy elements that are preallocated lists.
 */
void *rd_list_copy_preallocated(const void *elem, 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);
}



/**
 * @brief Move elements from \p src to \p dst.
 *
 * @remark \p dst will be initialized first.
 * @remark \p src will be emptied.
 */
void rd_list_move(rd_list_t *dst, rd_list_t *src);


/**
 * @name Misc helpers for common list types
 * @{
 *
 */

/**
 * @brief Init a new list of int32_t's of maximum size \p max_size
 *        where each element is pre-allocated.
 *
 * @remark The allocation flag of the original \p rl is retained,
 *         do not pass an uninitialized \p rl to this function.
 */
rd_list_t *rd_list_init_int32(rd_list_t *rl, int max_size);


/**
 * Debugging: Print list to stdout.
 */
void rd_list_dump(const char *what, const rd_list_t *rl);



/**
 * @brief Set element at index \p idx to value \p val.
 *
 * @remark Must only be used with preallocated int32_t lists.
 * @remark Allows values to be overwritten.
 */
void rd_list_set_int32(rd_list_t *rl, int idx, int32_t val);

/**
 * @returns the int32_t element value at index \p idx
 *
 * @remark Must only be used with preallocated int32_t lists.
 */
int32_t rd_list_get_int32(const rd_list_t *rl, int idx);

/**@}*/

#endif /* _RDLIST_H_ */