/* list.c: Routines for list manipulation.
 * This code is not ANSI-conformant, because it allocates memory at the end
 * of List structure and references it with a one-element array. */

#define _POSIX_SOURCE

#include "data.h"
#include "memory.h"

/* Note that we number list elements [0..(len - 1)] internally, while the
 * user sees list elements as numbered [1..len]. */

/* We use MALLOC_DELTA to keep our blocks about 32 bytes less than a power of
 * two.  We also have to account for the size of a List (16 bytes) which gets
 * added in before we allocate.  This works if a Data is sixteen bytes. */

#define MALLOC_DELTA	3
#define STARTING_SIZE	(16 - MALLOC_DELTA)

static List *prepare_to_modify(List *list, int len);

List *list_new(int len)
{
    List *new;
    int size;

    size = STARTING_SIZE;
    while (size < len)
	size = size * 2 + MALLOC_DELTA;
    new = emalloc(sizeof(List) + (size * sizeof(Data)));
    new->len = len;
    new->size = size;
    new->refs = 1;
    return new;
}

List *list_dup(List *list)
{
    list->refs++;
    return list;
}

List *list_from_data(Data *data, int len)
{
    List *list;
    int i;

    list = list_new(len);
    for (i = 0; i < len; i++)
	data_dup(&list->el[i], &data[i]);
    return list;
}

List *list_from_sublist(Sublist *sublist)
{
    List *list = sublist->list;

    if (sublist->span == list->len) {
	return list_dup(list);
    } else {
	return list_from_data(list->el + sublist->start, sublist->span);
    }
}

int list_search(List *list, Data *data)
{
    int i;

    for (i = 0; i < list->len; i++) {
	if (data_cmp(data, &list->el[i]) == 0)
	    return i;
    }
    return -1;
}

/* Effects: Returns 0 if the lists l1 and l2 are equivalent, or 1 if not. */
int list_cmp(List *l1, List *l2)
{
    int i;

    if (l1 == l2)
	return 0;

    /* Lists can only be equal if they're of the same length. */
    if (l1->len != l2->len)
	return 1;

    /* See if any elements differ. */
    for (i = 0; i < l1->len; i++) {
	if (data_cmp(&l1->el[i], &l2->el[i]) != 0)
	    return 1;
    }

    /* No elements differ, so the lists are the same. */
    return 0;
}

/* Error-checking on pos is the job of the calling function. */
List *list_insert(List *list, int pos, Data *elem)
{
    list = prepare_to_modify(list, list->len + 1);
    MEMMOVE(list->el + pos + 1, list->el + pos, Data, list->len - pos);
    data_dup(&list->el[pos], elem);
    list->len++;
    return list;
}

List *list_add(List *list, Data *elem)
{
    list = prepare_to_modify(list, list->len + 1);
    data_dup(&list->el[list->len++], elem);
    return list;
}

/* Error-checking on pos is the job of the calling function. */
List *list_replace(List *list, int pos, Data *elem)
{
    list = prepare_to_modify(list, list->len);
    data_discard(&list->el[pos]);
    data_dup(&list->el[pos], elem);
    return list;
}

/* Error-checking on pos is the job of the calling function. */
List *list_delete(List *list, int pos)
{
    list = prepare_to_modify(list, list->len - 1);
    data_discard(&list->el[pos]);
    MEMMOVE(list->el + pos, list->el + pos + 1, Data, list->len - pos - 1);
    list->len--;
    return list;
}

/* This routine will crash if elem is not in list. */
List *list_delete_element(List *list, Data *elem)
{
    int pos;

    pos = list_search(list, elem);
    return list_delete(list, pos);
}

List *list_append(List *list, Data *d, int len)
{
    int i;

    list = prepare_to_modify(list, list->len + len);
    for (i = 0; i < len; i++)
	data_dup(&list->el[list->len + i], &d[i]);
    list->len += len;
    return list;
}

/* Warning: do not discard a list before initializing its data elements. */
void list_discard(List *list)
{
    int i;

    if (!--list->refs) {
	for (i = 0; i < list->len; i++)
	    data_discard(&list->el[i]);
	free(list);
    }
}

static List *prepare_to_modify(List *list, int len)
{
    List *new;
    int i;

    if (list->refs == 1 && list->size < len) {
	do {
	    list->size = list->size * 2 + MALLOC_DELTA;
	} while (list->size < len);
	list = erealloc(list, sizeof(List) + (list->size * sizeof(Data)));
	return list;
    } else if (list->refs > 1) {
	new = list_new(len);
	new->len = list->len;
	for (i = 0; i < list->len; i++)
	    data_dup(&new->el[i], &list->el[i]);
	list_discard(list);
	return new;
    } else {
	return list;
    }
}