/*
 * 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_ */