/*
 * ilist.c
 *
 * Generic lists in C.
 *
 * Author: MontaVista Software, Inc.
 *         Corey Minyard <minyard@mvista.com>
 *         source@mvista.com
 *
 * Copyright 2002,2003,2004,2005 MontaVista Software Inc.
 *
 * This software is available to you under a choice of one of two
 * licenses.  You may choose to be licensed under the terms of the GNU
 * Lesser General Public License (GPL) Version 2 or the modified BSD
 * license below.  The following disclamer applies to both licenses:
 *
 *  THIS SOFTWARE IS PROVIDED ``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 AUTHOR 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.
 *
 * GNU Lesser General Public Licence
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public License
 *  as published by the Free Software Foundation; either version 2 of
 *  the License, or (at your option) any later version.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this program; if not, write to the Free
 *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Modified BSD Licence
 *
 * 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.
 *   3. The name of the author may not be used to endorse or promote
 *      products derived from this software without specific prior
 *      written permission.
 */

#include <stdlib.h>
#include <errno.h>

#include <OpenIPMI/internal/ilist.h>

ilist_t *
alloc_ilist(void)
{
    ilist_t *rv;

    rv = ilist_mem_alloc(sizeof(*rv));
    if (!rv)
	return NULL;

    rv->head = ilist_mem_alloc(sizeof(*(rv->head)));
    if (!rv->head) {
	ilist_mem_free(rv);
	return NULL;
    }

    rv->head->malloced = 1;
    rv->head->next = rv->head;
    rv->head->prev = rv->head;
    rv->head->item = NULL;

    return rv;
}

ilist_iter_t *
alloc_ilist_iter(ilist_t *list)
{
    ilist_iter_t *rv;

    rv = ilist_mem_alloc(sizeof(*rv));
    if (!rv)
	return NULL;

    rv->list = list;
    rv->curr = list->head;

    return rv;
}

void free_ilist(ilist_t *list)
{
    ilist_item_t *curr, *next;

    curr = list->head->next;
    while (curr != list->head) {
	next = curr->next;
	if (curr->malloced)
	    ilist_mem_free(curr);
	curr = next;
    }
    ilist_mem_free(list->head);
    ilist_mem_free(list);
}

void
free_ilist_iter(ilist_iter_t *iter)
{
    ilist_mem_free(iter);
}

static int
add_after(ilist_item_t *pos, void *item, ilist_item_t *entry)
{
    ilist_item_t *new_item;

    if (entry) {
	new_item = entry;
	new_item->malloced = 0;
    } else {
	new_item = ilist_mem_alloc(sizeof(*new_item));
	if (!new_item)
	    return 0;
	new_item->malloced = 1;
    }

    new_item->item = item;
    new_item->next = pos->next;
    new_item->prev = pos;
    new_item->prev->next = new_item;
    new_item->next->prev = new_item;
    return 1;
}

static int
add_before(ilist_item_t *pos, void *item, ilist_item_t *entry)
{
    ilist_item_t *new_item;

    if (entry) {
	new_item = entry;
	new_item->malloced = 0;
    } else {
	new_item = ilist_mem_alloc(sizeof(*new_item));
	if (!new_item)
	    return 0;
	new_item->malloced = 1;
    }

    new_item->item = item;
    new_item->next = pos;
    new_item->prev = pos->prev;
    new_item->prev->next = new_item;
    new_item->next->prev = new_item;
    return 1;
}

int
ilist_add_head(ilist_t *list, void *item, ilist_item_t *entry)
{
    return add_after(list->head, item, entry);
}

int
ilist_add_tail(ilist_t *list, void *item, ilist_item_t *entry)
{
    return add_before(list->head, item, entry);
}

int
ilist_add_before(ilist_iter_t *iter, void *item, ilist_item_t *entry)
{
    return add_before(iter->curr, item, entry);
}

int 
ilist_add_after(ilist_iter_t *iter, void *item, ilist_item_t *entry)
{
    return add_after(iter->curr, item, entry);
}

int
ilist_empty(ilist_t *list)
{
    return list->head->next == list->head;
}

int
ilist_first(ilist_iter_t *iter)
{
    iter->curr = iter->list->head->next;
    if (iter->curr == iter->list->head)
	return 0;
    return 1;
}

int
ilist_last(ilist_iter_t *iter)
{
    iter->curr = iter->list->head->prev;
    if (iter->curr == iter->list->head)
	return 0;
    return 1;
}

int
ilist_next(ilist_iter_t *iter)
{
    if (iter->curr->next == iter->list->head)
	return 0;
    iter->curr = iter->curr->next;
    return 1;
}

int
ilist_prev(ilist_iter_t *iter)
{
    if (iter->curr->prev == iter->list->head)
	return 0;
    iter->curr = iter->curr->prev;
    return 1;
}

void *
ilist_get(ilist_iter_t *iter)
{
    if (iter->curr == iter->list->head)
	return NULL;
    return iter->curr->item;
}

int
ilist_delete(ilist_iter_t *iter)
{
    ilist_item_t *curr;

    if (ilist_empty(iter->list))
	return 0;
    curr = iter->curr;
    iter->curr = curr->next;
    curr->next->prev = curr->prev;
    curr->prev->next = curr->next;
    if (curr->malloced)
	ilist_mem_free(curr);
    return 1;
}

void
ilist_unpositioned(ilist_iter_t *iter)
{
    iter->curr = iter->list->head;
}

void *
ilist_search_iter(ilist_iter_t *iter, ilist_search_cb cmp, void *cb_data)
{
    ilist_item_t *curr;

    curr = iter->curr->next;
    while (curr != iter->list->head) {
	if (cmp(curr->item, cb_data)) {
	    iter->curr = curr;
	    return curr->item;
	}
	curr = curr->next;
    }
    return NULL;
}

void *
ilist_search(ilist_t *list, ilist_search_cb cmp, void *cb_data)
{
    ilist_item_t *curr;

    curr = list->head->next;
    while (curr != list->head) {
	if (cmp(curr->item, cb_data)) {
	    return curr->item;
	}
	curr = curr->next;
    }
    return NULL;
}

void
ilist_iter(ilist_t *list, ilist_iter_cb handler, void *cb_data)
{
    ilist_item_t *curr, *next;
    ilist_iter_t iter;

    iter.list = list;
    iter.curr = list->head->next;
    while (iter.curr != list->head) {
	curr = iter.curr;
	next = curr->next;
	handler(&iter, curr->item, cb_data);
	iter.curr = next;
    }
}

void
ilist_iter_rev(ilist_t *list, ilist_iter_cb handler, void *cb_data)
{
    ilist_item_t *curr, *prev;
    ilist_iter_t iter;

    iter.list = list;
    iter.curr = list->head->prev;
    while (iter.curr != list->head) {
	curr = iter.curr;
	prev = curr->prev;
	handler(&iter, curr->item, cb_data);
	iter.curr = prev;
    }
}

void
ilist_init_iter(ilist_iter_t *iter, ilist_t *list)
{
    iter->list = list;
    iter->curr = list->head->next;
}

void
ilist_sort(ilist_t *list, ilist_sort_cb cmp)
{
    ilist_item_t *curr, *next;
    int          changed = 1;

    if (ilist_empty(list))
	return;

    /* An improved bubble sort. */
    while (changed) {
	curr = list->head->next;
	changed = 0;
	while (curr->next != list->head) {
	    next = curr->next;
	    if (cmp(curr->item, next->item) > 0) {
		changed = 1;
		/* Swap the places of next and curr. */
		curr->prev->next = next;
		next->next->prev = curr;
		curr->next = next->next;
		next->prev = curr->prev;
		curr->prev = next;
		next->next = curr;
	    } else {
		curr = curr->next;
	    }
	}
    }
}

void *
ilist_remove_first(ilist_t *list)
{
    ilist_item_t *curr;
    void         *item;

    if (ilist_empty(list))
	return NULL;

    curr = list->head->next;
    curr->next->prev = curr->prev;
    curr->prev->next = curr->next;
    item = curr->item;
    if (curr->malloced)
	ilist_mem_free(curr);
    return item;
}

void *
ilist_remove_last(ilist_t *list)
{
    ilist_item_t *curr;
    void         *item;

    if (ilist_empty(list))
	return NULL;

    curr = list->head->prev;
    curr->next->prev = curr->prev;
    curr->prev->next = curr->next;
    item = curr->item;
    if (curr->malloced)
	ilist_mem_free(curr);
    return item;
}

int
ilist_remove_item_from_list(ilist_t *list, void *item)
{
    ilist_item_t *curr;

    curr = list->head->next;
    while (curr != list->head) {
	if (curr->item == item)
	    break;
	curr = curr->next;
    }
    if (curr == list->head)
	return 0;

    curr->next->prev = curr->prev;
    curr->prev->next = curr->next;
    if (curr->malloced)
	ilist_mem_free(curr);
    return 1;
}

typedef struct ilist_twoitem_entry_s
{
    void         *cb_data1;
    void         *cb_data2;
    ilist_item_t entry;
} ilist_twoitem_entry_t;

static int twoitem_cmp(void *item, void *data)
{
    ilist_twoitem_entry_t *e = item;
    ilist_twoitem_entry_t *c = data;

    return ((e->cb_data1 == c->cb_data1) && (e->cb_data2 == c->cb_data2));
}

static int
find_twoitem(ilist_iter_t *iter, ilist_t *list, void *cb_data1, void *cb_data2)
{
    ilist_twoitem_entry_t *val, tmp = { cb_data1, cb_data2 };

    ilist_init_iter(iter, list);
    ilist_unpositioned(iter);
    val = ilist_search_iter(iter, twoitem_cmp, &tmp);
    return (val != NULL);
}

int
ilist_add_twoitem(ilist_t *list, void *cb_data1, void *cb_data2)
{
    ilist_twoitem_entry_t *entry;

    entry = ilist_mem_alloc(sizeof(*entry));
    if (!entry)
	return 0;
    entry->cb_data1 = cb_data1;
    entry->cb_data2 = cb_data2;

    ilist_add_tail(list, entry, &entry->entry);
    return 1;
}

int
ilist_remove_twoitem(ilist_t *list, void *cb_data1, void *cb_data2)
{
    ilist_iter_t          iter;
    ilist_twoitem_entry_t *entry;

    if (! find_twoitem(&iter, list, cb_data1, cb_data2))
	return 0;

    entry = ilist_get(&iter);
    ilist_delete(&iter);
    ilist_mem_free(entry);
    return 1;
}

int
ilist_twoitem_exists(ilist_t *list, void *cb_data1, void *cb_data2)
{
    ilist_iter_t     iter;

    if (! find_twoitem(&iter, list, cb_data1, cb_data2))
	return 0;

    return 1;
}

typedef struct twoitem_data_s
{
    ilist_twoitem_cb handler;
    void             *data;
} twoitem_data_t;

static void twoitem_iter(ilist_iter_t *iter, void *item, void *cb_data)
{
    ilist_twoitem_entry_t *entry = item;
    twoitem_data_t        *info = cb_data;

    info->handler(info->data, entry->cb_data1, entry->cb_data2);
}

void
ilist_iter_twoitem(ilist_t *list, ilist_twoitem_cb handler, void *data)
{
    twoitem_data_t info = { handler, data };
    ilist_iter(list, twoitem_iter, &info);
}

void
ilist_twoitem_destroy(ilist_t *list)
{
    ilist_iter_t          iter;
    ilist_twoitem_entry_t *entry;

    ilist_init_iter(&iter, list);
    while (ilist_first(&iter)) {
	entry = ilist_get(&iter);
	ilist_delete(&iter);
	ilist_mem_free(entry);
    }
    free_ilist(list);
}