/*

 * container_binary_array.c

 *

 * see comments in header file.

 *

 * Portions of this file are subject to the following copyright(s).  See

 * the Net-SNMP's COPYING file for more details and other copyrights

 * that may apply:

 *

 * Portions of this file are copyrighted by:

 * Copyright (c) 2016 VMware, Inc. All rights reserved.

 * Use is subject to license terms specified in the COPYING file

 * distributed with the Net-SNMP package.

 */

#include <net-snmp/net-snmp-config.h>

#if HAVE_IO_H

#include <io.h>

#endif

#include <stdio.h>

#if HAVE_STDLIB_H

#include <stdlib.h>

#endif

#if HAVE_MALLOC_H

#include <malloc.h>

#endif

#include <sys/types.h>

#if HAVE_STRING_H

#include <string.h>

#else

#include <strings.h>

#endif

#include <net-snmp/net-snmp-includes.h>

#include <net-snmp/types.h>

#include <net-snmp/library/snmp_api.h>

#include <net-snmp/library/container.h>

#include <net-snmp/library/container_binary_array.h>

#include <net-snmp/library/tools.h>

#include <net-snmp/library/snmp_assert.h>

typedef struct binary_array_table_s {

    size_t                     max_size;   /* Size of the current data table */

    size_t                     count;      /* Index of the next free entry */

    int                        dirty;

    void                     **data;       /* The table itself */

} binary_array_table;

typedef struct binary_array_iterator_s {

    netsnmp_iterator base;

    size_t           pos;

} binary_array_iterator;

static netsnmp_iterator *_ba_iterator_get(netsnmp_container *c);

/**********************************************************************

 *

 * 

 *

 */

static void

array_qsort(void **data, int first, int last, netsnmp_container_compare *f)

{

    int i, j;

    void *mid, *tmp;

    i = first;

    j = last;

    mid = data[(first+last)/2];

    do {

        while (i < last && (*f)(data[i], mid) < 0)

            ++i;

        while (j > first && (*f)(mid, data[j]) < 0)

            --j;

        if(i < j) {

            tmp = data[i];

            data[i] = data[j];

            data[j] = tmp;

            ++i;

            --j;

        }

        else if (i == j) {

            ++i;

            --j;

            break;

        }

    } while(i <= j);

    if (j > first)

        array_qsort(data, first, j, f);

    if (i < last)

        array_qsort(data, i, last, f);

}

static int

Sort_Array(netsnmp_container *c)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    netsnmp_assert(t!=NULL);

    netsnmp_assert(c->compare!=NULL);

    if (c->flags & CONTAINER_KEY_UNSORTED)

        return 0;

    if (t->dirty) {

        /*

         * Sort the table 

         */

        if (t->count > 1)

            array_qsort(t->data, 0, t->count - 1, c->compare);

        t->dirty = 0;

        /*

         * no way to know if it actually changed... just assume so.

         */

        ++c->sync;

    }

    return 1;

}

static int

linear_search(const void *val, netsnmp_container *c)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    size_t             pos = 0;

    if (!t->count)

        return -1;

    if (! (c->flags & CONTAINER_KEY_UNSORTED)) {

        snmp_log(LOG_ERR, "linear search on sorted container %s?!?\n",

                 c->container_name);

        return -1;

    }

    for (; pos < t->count; ++pos) {

        if (c->compare(t->data[pos], val) == 0)

            break;

    }

    if (pos >= t->count)

        return -1;

    return pos;

}

static int

binary_search(const void *val, netsnmp_container *c, int exact, size_t *next)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    size_t             len = t->count;

    size_t             half;

    size_t             first = 0;

    size_t             middle = 0; /* init not needed; keeps compiler happy */

    int                result = 0; /* init not needed; keeps compiler happy */

    if (!len) {

        if (NULL != next)

            *next = 0;

        return -1;

    }

    if (c->flags & CONTAINER_KEY_UNSORTED) {

        if (!exact) {

            snmp_log(LOG_ERR, "non-exact search on unsorted container %s?!?\n",

                     c->container_name);

            return -1;

        }

        return linear_search(val, c);

    }

    if (t->dirty)

        Sort_Array(c);

    while (len > 0) {

        half = len >> 1;

        middle = first + half;

        if ((result = c->compare(t->data[middle], val)) < 0) {

            first = middle + 1;

            len = len - half - 1;

        } else if (result == 0) {

            first = middle;

            break;

        } else {

            len = half;

        }

    }

    if (first >= t->count) {

        if (exact && NULL != next)

            *next = t->count;

        return -1;

    }

    if (first != middle) {

        /* last compare wasn't against first, so get actual result */

        result = c->compare(t->data[first], val);

    }

    if(result == 0) {

        if (exact && NULL != next)

            *next = first+1;

        else if (!exact && ++first == t->count) {

            if (NULL != next)

                *next = first;

            first = -1;

        }

    } else if(exact) {

        if (NULL != next) {

            if (result > 0)

                *next = first;

            else

                *next = t->count;

        }

        first = -1;

    }

    return first;

}

NETSNMP_STATIC_INLINE binary_array_table *

netsnmp_binary_array_initialize(void)

{

    binary_array_table *t;

    t = SNMP_MALLOC_TYPEDEF(binary_array_table);

    if (t == NULL)

        return NULL;

    t->max_size = 0;

    t->count = 0;

    t->dirty = 0;

    t->data = NULL;

    return t;

}

void

netsnmp_binary_array_release(netsnmp_container *c)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    SNMP_FREE(t->data);

    SNMP_FREE(t);

    SNMP_FREE(c);

}

int

netsnmp_binary_array_options_set(netsnmp_container *c, int set, u_int flags)

{

#define BA_FLAGS (CONTAINER_KEY_ALLOW_DUPLICATES|CONTAINER_KEY_UNSORTED)

    if (set) {

        if ((flags & BA_FLAGS) == flags) {

            /** if turning off unsorted, do sort */

            int sort = ((c->flags & CONTAINER_KEY_UNSORTED) &&

                        ! (flags & CONTAINER_KEY_UNSORTED));

            c->flags = flags;

            if (sort) {

                binary_array_table *t = (binary_array_table*)c->container_data;

                t->dirty = 1; /* force sort */

                Sort_Array(c);

            }

        } else

            flags = (u_int)-1; /* unsupported flag */

    }

    else

        return ((c->flags & flags) == flags);

    return flags;

}

NETSNMP_STATIC_INLINE size_t

netsnmp_binary_array_count(netsnmp_container *c)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    /*

     * return count

     */

    return t ? t->count : 0;

}

NETSNMP_STATIC_INLINE void           *

netsnmp_binary_array_get(netsnmp_container *c, const void *key, int exact)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    int             index = 0;

    /*

     * if there is no data, return NULL;

     */

    if (!t->count)

        return NULL;

    /*

     * if the table is dirty, sort it.

     */

    if (t->dirty)

        Sort_Array(c);

    /*

     * if there is a key, search. Otherwise default is 0;

     */

    if (key) {

        if ((index = binary_search(key, c, exact, NULL)) == -1)

            return NULL;

        if (!exact &&

            c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) {

            int result;

            /*

             * If duplicates are allowed, we have to be extra

             * sure that we didn't just increment to a duplicate,

             * thus causing a getnext loop.

             */

            result = c->compare(t->data[index], key);

            while (result == 0) {

		DEBUGMSGTL(("container","skipping duplicate key in %s\n",

					    c->container_name));

                if (++index == t->count)

                   return NULL;

                result = c->compare(t->data[index], key);

            }

        }

    }

    return t->data[index];

}

static int

netsnmp_binary_array_get_at(netsnmp_container *c, size_t pos, void **entry)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    /*

     * if there is no data, return NULL;

     */

    if (!t->count || pos >= t->count || NULL == entry)

        return -1;

    *entry = t->data[pos];

    return 0;

}

int

netsnmp_binary_array_remove_at(netsnmp_container *c, size_t index, void **save)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    if (save)

        *save = NULL;

    /*

     * if there is no data, return NULL;

     */

    if (!t->count)

        return -1;

    /*

     * find old data and save it, if ptr provided

     */

    if (save)

        *save = t->data[index];

    /*

     * if entry was last item, just decrement count

     */

    --t->count;

    if (index != t->count) {

        /*

         * otherwise, shift array down

         */

        memmove(&t->data[index], &t->data[index+1],

                sizeof(void*) * (t->count - index));

        ++c->sync;

    }

    return 0;

}

int

netsnmp_binary_array_remove(netsnmp_container *c, const void *key, void **save)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    int                index = 0;

    if (save)

        *save = NULL;

    /*

     * if there is no data, return NULL;

     */

    if (!t->count)

        return 0;

    /*

     * if the table is dirty, sort it.

     */

    if (t->dirty)

        Sort_Array(c);

    /*

     * search

     */

    if ((index = binary_search(key, c, 1, NULL)) == -1)

        return -1;

    return netsnmp_binary_array_remove_at(c, (size_t)index, save);

}

NETSNMP_STATIC_INLINE void

netsnmp_binary_array_for_each(netsnmp_container *c,

                              netsnmp_container_obj_func *fe,

                              void *context, int sort)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    size_t             i;

    if (sort && t->dirty)

        Sort_Array(c);

    for (i = 0; i < t->count; ++i)

        (*fe) (t->data[i], context);

}

NETSNMP_STATIC_INLINE void

netsnmp_binary_array_clear(netsnmp_container *c,

                           netsnmp_container_obj_func *fe,

                           void *context)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    if( NULL != fe ) {

        size_t             i;

        for (i = 0; i < t->count; ++i)

            (*fe) (t->data[i], context);

    }

    t->count = 0;

    t->dirty = 0;

    ++c->sync;

}

static int

_ba_resize_check(binary_array_table *t)

{

    size_t new_max;

    void ** new_data;

    if (t->max_size > t->count)

        return 0; /* resize not needed */

    /*

     * Table is full, so extend it to double the size, or use 10 elements

     * if it is empty.

     */

    new_max = t->max_size > 0 ? 2 * t->max_size : 10;

    new_data = (void**) realloc(t->data, new_max * sizeof(void*));

    if (new_data == NULL) {

        snmp_log(LOG_ERR, "malloc failed in _ba_resize_check\n");

        return -1; /* error */

    }

    memset(new_data + t->max_size, 0x0,

           (new_max - t->max_size) * sizeof(void*));

    t->data = new_data;

    t->max_size = new_max;

    return 1; /* resized */

}

static int

netsnmp_binary_array_insert_before(netsnmp_container *c, size_t index,

                                   const void *entry, int dirty)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    if (NULL == entry)

        return -1;

    if (index > (t->count + 1)) {

        DEBUGMSGTL(("container:insert:before", "index out of range\n"));

        return -1;

    }

     /*

      * check if we need to resize the array

      */

    _ba_resize_check(t);

    /*

     * shift array

     */

    memmove(&t->data[index+1], &t->data[index],

            sizeof(void*) * (t->count - index));

    /*

     * Insert the new entry into the data array

     */

    t->data[index] = NETSNMP_REMOVE_CONST(void *, entry);

    ++t->count;

    if (dirty)

        t->dirty = 1;

    ++c->sync;

    return 0;

}

NETSNMP_STATIC_INLINE int

netsnmp_binary_array_insert(netsnmp_container *c, const void *const_entry)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    int             dirty = 0, i = -2;

    size_t          next, pos;

    void           *entry = NETSNMP_REMOVE_CONST(void *, const_entry);

    if (NULL == entry)

        return -1;

    /*

     * check key if we have at least 1 item and duplicates aren't allowed

     */

    if (! (c->flags & CONTAINER_KEY_ALLOW_DUPLICATES) && t->count) {

        i = binary_search(entry, c, 1, &next;;

        if (i > 0) {

            DEBUGMSGTL(("container","not inserting duplicate key\n"));

            return -1;

        }

    }

    /*

     * if unsorted, just add at the end

     */

    if (c->flags & CONTAINER_KEY_UNSORTED) {

        pos = t->count;

        dirty = 1;

    } else {

        /** if we haven't searched for key yet, do it now */

        if (-2 == i) {

            if (0 == t->count) {

                next = 0;

                i = -1;

            } else

                i = binary_search(entry, c, 1, &next;;

        }

        pos = next;

        if ( i > 0 )  /* if key found, advance past any dups */

            while (pos < t->count && c->compare(t->data[pos], entry) == 0)

                ++pos;

    }

    return netsnmp_binary_array_insert_before(c, pos, entry, dirty);

}

/**********************************************************************

 *

 * Special case support for subsets

 *

 */

static int

binary_search_for_start(netsnmp_index *val, netsnmp_container *c)

{

    binary_array_table *t = (binary_array_table*)c->container_data;

    size_t             len = t->count;

    size_t             half;

    size_t             middle;

    size_t             first = 0;

    int                result = 0;

    if (!len)

        return -1;

    if (t->dirty)

        Sort_Array(c);

    while (len > 0) {

        half = len >> 1;

        middle = first + half;

        if ((result = c->ncompare(t->data[middle], val)) < 0) {

            first = middle + 1;

            len = len - half - 1;

        } else

            len = half;

    }

    if ((first >= t->count) ||

        c->ncompare(t->data[first], val) != 0)

        return -1;

    return first;

}

void          **

netsnmp_binary_array_get_subset(netsnmp_container *c, void *key, int *len)

{

    binary_array_table *t;

    void          **subset;

    int             start, end;

    size_t          i;

    /*

     * if there is no data, return NULL;

     */

    if (!c || !key || !len)

        return NULL;

    t = (binary_array_table*)c->container_data;

    netsnmp_assert(c->ncompare);

    if (!t->count || !c->ncompare)

        return NULL;

    /*

     * if the table is dirty, sort it.

     */

    if (t->dirty)

        Sort_Array(c);

    /*

     * find matching items

     */

    start = end = binary_search_for_start((netsnmp_index *)key, c);

    if (start == -1)

        return NULL;

    for (i = start + 1; i < t->count; ++i) {

        if (0 != c->ncompare(t->data[i], key))

            break;

        ++end;

    }

    *len = end - start + 1;

    if (*len <= 0)

        return NULL;

    subset = (void **)malloc((*len) * sizeof(void*));

    if (subset)

        memcpy(subset, &t->data[start], sizeof(void*) * (*len));

    return subset;

}

/**********************************************************************

 *

 * container

 *

 */

static void *

_ba_find(netsnmp_container *container, const void *data)

{

    return netsnmp_binary_array_get(container, data, 1);

}

static void *

_ba_find_next(netsnmp_container *container, const void *data)

{

    return netsnmp_binary_array_get(container, data, 0);

}

static int

_ba_insert(netsnmp_container *container, const void *data)

{

    return netsnmp_binary_array_insert(container, data);

}

static int

_ba_insert_before(netsnmp_container *container, size_t index, void *data)

{

    /** don't trust users direct-acces inserts, mark array dirty */

    return netsnmp_binary_array_insert_before(container, index, data, 1);

}

static int

_ba_remove(netsnmp_container *container, const void *data)

{

    return netsnmp_binary_array_remove(container,data, NULL);

}

static int

_ba_free(netsnmp_container *container)

{

    netsnmp_binary_array_release(container);

    return 0;

}

static size_t

_ba_size(netsnmp_container *container)

{

    return netsnmp_binary_array_count(container);

}

static void

_ba_for_each(netsnmp_container *container, netsnmp_container_obj_func *f,

             void *context)

{

    netsnmp_binary_array_for_each(container, f, context, 1);

}

static void

_ba_clear(netsnmp_container *container, netsnmp_container_obj_func *f,

             void *context)

{

    netsnmp_binary_array_clear(container, f, context);

}

static netsnmp_void_array *

_ba_get_subset(netsnmp_container *container, void *data)

{

    netsnmp_void_array * va;

    void ** rtn;

    int len;

    rtn = netsnmp_binary_array_get_subset(container, data, &len;;

    if (NULL==rtn)

        return NULL;

    va = SNMP_MALLOC_TYPEDEF(netsnmp_void_array);

    if (va == NULL) {

        free(rtn);

        return NULL;

    }

    va->size = len;

    va->array = rtn;

    return va;

}

static int _ba_options(netsnmp_container *c, int set, u_int flags)

{

    return netsnmp_binary_array_options_set(c, set, flags);

}

static netsnmp_container *

_ba_duplicate(netsnmp_container *c, void *ctx, u_int flags)

{

    netsnmp_container *dup;

    binary_array_table *dupt, *t;

    if (flags) {

        snmp_log(LOG_ERR, "binary arry duplicate does not supprt flags yet\n");

        return NULL;

    }

    dup = netsnmp_container_get_binary_array();

    if (NULL == dup) {

        snmp_log(LOG_ERR," no memory for binary array duplicate\n");

        return NULL;

    }

    /*

     * deal with container stuff

     */

    if (netsnmp_container_data_dup(dup, c) != 0) {

        netsnmp_binary_array_release(dup);

        return NULL;

    }

    /*

     * deal with data

     */

    dupt = (binary_array_table*)dup->container_data;

    t = (binary_array_table*)c->container_data;

    dupt->max_size = t->max_size;

    dupt->count = t->count;

    dupt->dirty = t->dirty;

    /*

     * shallow copy

     */

    dupt->data = (void**) malloc(dupt->max_size * sizeof(void*));

    if (NULL == dupt->data) {

        snmp_log(LOG_ERR, "no memory for binary array duplicate\n");

        netsnmp_binary_array_release(dup);

        return NULL;

    }

    memcpy(dupt->data, t->data, dupt->max_size * sizeof(void*));

    return dup;

}

netsnmp_container *

netsnmp_container_get_binary_array(void)

{

    /*

     * allocate memory

     */

    netsnmp_container *c = SNMP_MALLOC_TYPEDEF(netsnmp_container);

    if (NULL==c) {

        snmp_log(LOG_ERR, "couldn't allocate memory\n");

        return NULL;

    }

    c->container_data = netsnmp_binary_array_initialize();

    /*

     * NOTE: CHANGES HERE MUST BE DUPLICATED IN duplicate AS WELL!!

     */

    netsnmp_init_container(c, NULL, _ba_free, _ba_size, NULL, _ba_insert,

                           _ba_remove, _ba_find);

    c->find_next = _ba_find_next;

    c->get_subset = _ba_get_subset;

    c->get_iterator = _ba_iterator_get;

    c->for_each = _ba_for_each;

    c->clear = _ba_clear;

    c->options = _ba_options;

    c->duplicate = _ba_duplicate;

    c->get_at = netsnmp_binary_array_get_at;

    c->remove_at = netsnmp_binary_array_remove_at;

    c->insert_before = _ba_insert_before;

    return c;

}

netsnmp_factory *

netsnmp_container_get_binary_array_factory(void)

{

    static netsnmp_factory f = { "binary_array",

                                 (netsnmp_factory_produce_f*)

                                 netsnmp_container_get_binary_array };

    return &f;

}

void

netsnmp_container_binary_array_init(void)

{

    netsnmp_container_register("binary_array",

                               netsnmp_container_get_binary_array_factory());

}

/**********************************************************************

 *

 * iterator

 *

 */

NETSNMP_STATIC_INLINE binary_array_table *

_ba_it2cont(binary_array_iterator *it)

{

    if(NULL == it) {

        netsnmp_assert(NULL != it);

        return NULL;

    }

    if(NULL == it->base.container) {

        netsnmp_assert(NULL != it->base.container);

        return NULL;

    }

    if(NULL == it->base.container->container_data) {

        netsnmp_assert(NULL != it->base.container->container_data);

        return NULL;

    }

    return (binary_array_table*)(it->base.container->container_data);

}

NETSNMP_STATIC_INLINE void *

_ba_iterator_position(binary_array_iterator *it, size_t pos)

{

    binary_array_table *t = _ba_it2cont(it);

    if (NULL == t)

        return t; /* msg already logged */

    if(it->base.container->sync != it->base.sync) {

        DEBUGMSGTL(("container:iterator", "out of sync\n"));

        return NULL;

    }

    if(0 == t->count) {

        DEBUGMSGTL(("container:iterator", "empty\n"));

        return NULL;