/*

 * container_list_sl.c

 * $Id$

 *

 */

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

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

#include <stdio.h>

#ifdef HAVE_STDLIB_H

#include <stdlib.h>

#endif

#ifdef HAVE_MALLOC_H

#include <malloc.h>

#endif

#include <sys/types.h>

#ifdef 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/tools.h>

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

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

#include "factory.h"

netsnmp_feature_child_of(container_linked_list, container_types);

netsnmp_feature_child_of(container_fifo, container_types);

netsnmp_feature_child_of(container_lifo, container_types);

/* this is a fancy way of cleaning up ifdefs */

#ifdef NETSNMP_FEATURE_REQUIRE_CONTAINER_FIFO

netsnmp_feature_require(container_linked_list);

#endif /* NETSNMP_FEATURE_REQUIRE_CONTAINER_FIFO */

#ifdef NETSNMP_FEATURE_REQUIRE_CONTAINER_LIFO

netsnmp_feature_require(container_linked_list);

#endif /* NETSNMP_FEATURE_REQUIRE_CONTAINER_LIFO */

#ifndef NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST

typedef struct sl_node {

   void           *data;

   struct sl_node *next;

} sl_node;

typedef struct sl_container_s {

   netsnmp_container          c;

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

   sl_node                   *head;       /* head of list */

   int                        unsorted;   /* unsorted list? */

   int                        fifo;       /* lifo or fifo? */

} sl_container;

typedef struct ssll_iterator_s {

    netsnmp_iterator base;

    sl_node         *pos;

    sl_node         *last;

} ssll_iterator;

static netsnmp_iterator *_ssll_iterator_get(netsnmp_container *c);

static void *

_get(netsnmp_container *c, const void *key, int return_next)

{

    sl_container *sl = (sl_container *)c;

    sl_node *curr = sl->head;

    int rc = 0;

    /* If the key is NULL, return the first item in the container. */

    if (!key)

        return curr ? curr->data : NULL;

    for ( ; curr; curr = curr->next) {

        rc = sl->c.compare(curr->data, key);

        if (rc < 0)

            continue;

        if (rc == 0) {

            if (return_next)

                curr = curr->next;

            break;

        }

        if (!sl->unsorted) {

            /* If sorted, we can stop. */

            if (!return_next)

                curr = NULL;

            break;

        }

    }

    return curr ? curr->data : NULL;

}

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

 *

 *

 *

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

static int

_ssll_free(netsnmp_container *c)

{

    if(c) {

        free(c);

    }

    return 0;

}

static void *

_ssll_find(netsnmp_container *c, const void *data)

{

    if((NULL == c) || (NULL == data))

        return NULL;

    return _get(c, data, 0);

}

static void *

_ssll_find_next(netsnmp_container *c, const void *data)

{

    if(NULL == c)

        return NULL;

    return _get(c, data, 1);

}

static int

_ssll_insert(netsnmp_container *c, const void *data)

{

    sl_container *sl = (sl_container*)c;

    sl_node  *new_node, *curr;

    if (c == NULL)

        return -1;

    curr = sl->head;

    new_node = SNMP_MALLOC_TYPEDEF(sl_node);

    if (new_node == NULL)

        return -1;

    new_node->data = NETSNMP_REMOVE_CONST(void *, data);

    ++sl->count;

    ++c->sync;

    /*

     * first node?

     */

    if(NULL == sl->head) {

        sl->head = new_node;

        return 0;

    }

    /*

     * sorted or unsorted insert?

     */

    if (1 == sl->unsorted) {

        /*

         * unsorted: fifo, or lifo?

         */

        if (1 == sl->fifo) {

            /*

             * fifo: insert at tail

             */

            while(NULL != curr->next)

                curr = curr->next;

            curr->next = new_node;

        }

        else {

            /*

             * lifo: insert at head

             */

            new_node->next = sl->head;

            sl->head = new_node;

        }

    }

    else {

        /*

         * sorted

         */

        sl_node *last = NULL;

        for( ; curr; last = curr, curr = curr->next) {

            if(sl->c.compare(curr->data, data) > 0)

                break;

        }

        if(NULL == last) {

            new_node->next = sl->head;

            sl->head = new_node;

        }

        else {

            new_node->next = last->next;

            last->next = new_node;

        }

    }

    return 0;

}

static int

_ssll_remove(netsnmp_container *c, const void *data)

{

    sl_container *sl = (sl_container*)c;

    sl_node  *curr;

    if (c == NULL)

        return -1;

    curr = sl->head;

    if (curr == NULL)

        return -1;

    /*

     * special case for NULL data, act like stack

     */

    if ((NULL == data) ||

        (sl->c.compare(sl->head->data, data) == 0)) {

        curr = sl->head;

        sl->head = sl->head->next;

    }

    else {

        sl_node *last = sl->head;

        int rc;

        for(curr = sl->head->next ; curr; last = curr, curr = curr->next) {

            rc = sl->c.compare(curr->data, data);

            if (rc == 0) {

                last->next = curr->next;

                break;

            }

            else if ((rc > 0) && (0 == sl->unsorted)) {

                /*

                 * if sorted and rc > 0, didn't find entry

                 */

                curr = NULL;

                break;

            }

        }

    }

    if(NULL == curr)

        return -2;

    /*

     * free our node structure, but not the data

     */

    free(curr);

    --sl->count;

    ++c->sync;

    return 0;

}

static size_t

_ssll_size(netsnmp_container *c)

{

    sl_container *sl = (sl_container*)c;

    if(NULL == c)

        return 0;

    return sl->count;

}

static void

_ssll_for_each(netsnmp_container *c, netsnmp_container_obj_func *f,

             void *context)

{

    sl_container *sl = (sl_container*)c;

    sl_node  *curr;

    if(NULL == c)

        return;

    for(curr = sl->head; curr; curr = curr->next)

        (*f) ((void *)curr->data, context);

}

static void

_ssll_clear(netsnmp_container *c, netsnmp_container_obj_func *f,

             void *context)

{

    sl_container *sl = (sl_container*)c;

    sl_node  *curr, *next;

    if(NULL == c)

        return;

    for(curr = sl->head; curr; curr = next) {

        next = curr->next;

        if( NULL != f ) {

            curr->next = NULL;

            (*f) ((void *)curr->data, context);

        }

        /*

         * free our node structure, but not the data

         */

        free(curr);

    }

    sl->head = NULL;

    sl->count = 0;

    ++c->sync;

}

static netsnmp_container *netsnmp_container_get_ssll(void);

static netsnmp_container *

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

{

    netsnmp_transport_config *item;

    netsnmp_container *dup;

    netsnmp_iterator *iter;

    if (flags) {

        snmp_log(LOG_ERR, "%s does not support flags yet\n", __func__);

        return NULL;

    }

    dup = netsnmp_container_get_ssll();

    if (!dup) {

        snmp_log(LOG_ERR, "%s: out of memory\n", __func__);

        return NULL;

    }

    /*

     * deal with container stuff

     */

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

        goto fail;

    /* deep copy */

    iter = CONTAINER_ITERATOR(c);

    for (item = ITERATOR_FIRST(iter); item; item = ITERATOR_NEXT(iter))

        CONTAINER_INSERT(dup, netsnmp_transport_create_config(item->key,

                                                              item->value));

    ITERATOR_RELEASE(iter);

    return dup;

fail:

    _ssll_free(dup);

    return NULL;

}

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

 *

 *

 *

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

static netsnmp_container *

netsnmp_container_get_ssll(void)

{

    /*

     * allocate memory

     */

    sl_container *sl = SNMP_MALLOC_TYPEDEF(sl_container);

    if (NULL==sl) {

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

        return NULL;

    }

    netsnmp_init_container((netsnmp_container *)sl, NULL, _ssll_free,

                           _ssll_size, NULL, _ssll_insert, _ssll_remove,

                           _ssll_find);

    sl->c.find_next = _ssll_find_next;

    sl->c.get_subset = NULL;

    sl->c.get_iterator =_ssll_iterator_get;

    sl->c.for_each = _ssll_for_each;

    sl->c.clear = _ssll_clear;

    sl->c.duplicate = _ssll_duplicate;

    return &sl->c;

}

netsnmp_container *

netsnmp_container_get_usll(void)

{

    /*

     * allocate memory

     */

    sl_container *sl = (sl_container *)netsnmp_container_get_ssll();

    if (NULL==sl)

        return NULL; /* msg already logged */

    sl->unsorted = 1;

    return (netsnmp_container*)sl;

}

netsnmp_container *

netsnmp_container_get_singly_linked_list(int fifo)

{

    sl_container *sl = (sl_container *)netsnmp_container_get_usll();

    if (NULL == sl)

        return NULL; /* error already logged */

    sl->fifo = fifo;

    return (netsnmp_container *)sl;

}

netsnmp_container *

netsnmp_container_get_fifo(void)

{

    return netsnmp_container_get_singly_linked_list(1);

}

void

netsnmp_container_ssll_init(void)

{

    static netsnmp_factory ssll = {

        "sorted_singly_linked_list",

        netsnmp_container_get_ssll

    };

    static netsnmp_factory usll = {

        "unsorted_singly_linked_list-lifo",

        netsnmp_container_get_usll

    };

    static netsnmp_factory fifo = {

        "unsorted_singly_linked_list-fifo",

        netsnmp_container_get_fifo

    };

    netsnmp_container_register("sorted_singly_linked_list", &ssll);

    netsnmp_container_register("unsorted_singly_linked_list", &usll);

    netsnmp_container_register("lifo", &usll);

    netsnmp_container_register("fifo", &fifo);

}

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

 *

 * iterator

 *

 */

NETSNMP_STATIC_INLINE sl_container *

_ssll_it2cont(ssll_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(it->base.container->sync != it->base.sync) {

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

        return NULL;

    }

    return (sl_container *)it->base.container;

}

static void *

_ssll_iterator_curr(netsnmp_iterator *p)

{

    ssll_iterator *it = (void *)p;

    sl_container *t = _ssll_it2cont(it);

    if ((NULL == t) || (NULL == it->pos))

        return NULL;

    return it->pos->data;

}

static void *

_ssll_iterator_first(netsnmp_iterator *p)

{

    ssll_iterator *it = (void *)p;

    sl_container *t = _ssll_it2cont(it);

    if ((NULL == t) || (NULL == t->head))

        return NULL;

    return t->head->data;

}

static void *

_ssll_iterator_next(netsnmp_iterator *p)

{

    ssll_iterator *it = (void *)p;

    sl_container *t = _ssll_it2cont(it);

    if ((NULL == t) || (NULL == it->pos))

        return NULL;

    it->pos = it->pos->next;

    if (NULL == it->pos)

        return NULL;

    return it->pos->data;

}

static void *

_ssll_iterator_last(netsnmp_iterator *p)

{

    ssll_iterator *it = (void *)p;

    sl_node      *n;

    sl_container *t = _ssll_it2cont(it);

    if(NULL == t)

        return NULL;

    if (it->last)

        return it->last;

    n = it->pos ? it->pos : t->head;

    if (NULL == n)

        return NULL;

    while (n->next)

        n = n->next;

    it->last = n;

    return it->last->data;

}

static int

_ssll_iterator_reset(netsnmp_iterator *p)

{

    ssll_iterator *it = (void *)p;

    sl_container *t;

    /** can't use it2conf cuz we might be out of sync */

    if(NULL == it) {

        netsnmp_assert(NULL != it);

        return 0;

    }

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

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

        return 0;

    }

    t = (sl_container *)it->base.container;

    if(NULL == t)

        return -1;

    it->last = NULL;

    it->pos = t->head;

    /*

     * save sync count, to make sure container doesn't change while

     * iterator is in use.

     */

    it->base.sync = it->base.container->sync;

    return 0;

}

static int

_ssll_iterator_release(netsnmp_iterator *it)

{

    free(it);

    return 0;

}

static netsnmp_iterator *

_ssll_iterator_get(netsnmp_container *c)

{

    ssll_iterator* it;

    if(NULL == c)

        return NULL;

    it = SNMP_MALLOC_TYPEDEF(ssll_iterator);

    if(NULL == it)

        return NULL;

    it->base.container = c;

    it->base.first = _ssll_iterator_first;

    it->base.next = _ssll_iterator_next;

    it->base.curr = _ssll_iterator_curr;

    it->base.last = _ssll_iterator_last;

    it->base.reset = _ssll_iterator_reset;

    it->base.release = _ssll_iterator_release;

    (void)_ssll_iterator_reset(&it->base);

    return &it->base;

}

#else /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */

netsnmp_feature_unused(container_linked_list);

#endif /* NETSNMP_FEATURE_REMOVE_CONTAINER_LINKED_LIST */