list.c

一个很棒的视频服务器

    /* assert no overflows */
    assert (source->count - moved <= source->count);
    assert (dest->count + moved >= dest->count);

    /* assert no weirdness */
    assert (moved <= source->count);

    source->count -= moved;
    dest->count += moved;

    /* assert list sanity */
    assert (list_verify(source));
    assert (list_verify(dest));
}


/*
 * Split off a trailing sequence of nodes from the source list and relocate
 * them to the tail of the destination list. The trailing sequence begins
 * with node ``first'' and terminates with the last node of the source
 * list. The nodes are added to the end of the new list in their original
 * order.
 */

void list_transfer(list_t *dest, list_t *source, lnode_t *first)
{
    listcount_t moved = 1;
    lnode_t *last;

    assert (first == NULL || list_contains(source, first));

    if (first == NULL)
	return;

    last = source->nilnode.prev;

    source->nilnode.prev = first->prev;
    first->prev->next = &source->nilnode;

    last->next = &dest->nilnode;
    first->prev = dest->nilnode.prev;
    dest->nilnode.prev->next = first;
    dest->nilnode.prev = last;

    while (first != last) {
	first = first->next;
	moved++;
    }
    
    /* assert no overflows */
    assert (source->count - moved <= source->count);
    assert (dest->count + moved >= dest->count);

    /* assert no weirdness */
    assert (moved <= source->count);

    source->count -= moved;
    dest->count += moved;

    /* assert list sanity */
    assert (list_verify(source));
    assert (list_verify(dest));
}

void list_merge(list_t *dest, list_t *sour,
	int compare (const void *, const void *))
{
    lnode_t *dn, *sn, *tn;
    lnode_t *d_nil = list_nil(dest), *s_nil = list_nil(sour);

    /* overflow check */
    assert (list_count(sour) + list_count(dest) > list_count(sour));

    /* lists must be sorted */
    assert (list_is_sorted(sour, compare));
    assert (list_is_sorted(dest, compare));

    dn = list_first_priv(dest);
    sn = list_first_priv(sour);

    while (dn != d_nil && sn != s_nil) {
	if (compare(lnode_get(dn), lnode_get(sn)) >= 0) {
	    tn = lnode_next(sn);
	    list_delete(sour, sn);
	    list_ins_before(dest, sn, dn);
	    sn = tn;
	} else {
	    dn = lnode_next(dn);
	}
    }

    if (dn != d_nil)
	return;

    if (sn != s_nil)
	list_transfer(dest, sour, sn);
}

void list_sort(list_t *list, int compare(const void *, const void *))
{
    list_t extra;
    listcount_t middle;
    lnode_t *node;

    if (list_count(list) > 1) {
	middle = list_count(list) / 2;
	node = list_first_priv(list);

	list_init(&extra, list_count(list) - middle);

	while (middle--)
	    node = lnode_next(node);
	
	list_transfer(&extra, list, node);
	list_sort(list, compare);
	list_sort(&extra, compare);
	list_merge(list, &extra, compare);
    } 
    assert (list_is_sorted(list, compare));
}

/*
 * Return 1 if the list is in sorted order, 0 otherwise
 */

int list_is_sorted(list_t *list, int compare(const void *, const void *))
{
    lnode_t *node, *next, *nil;

    next = nil = list_nil(list);
    node = list_first_priv(list);

    if (node != nil)
	next = lnode_next(node);

    for (; next != nil; node = next, next = lnode_next(next)) {
	if (compare(lnode_get(node), lnode_get(next)) > 0)
	    return 0;
    }

    return 1;
}

/*
 * Get rid of macro functions definitions so they don't interfere
 * with the actual definitions
 */

#undef list_isempty
#undef list_isfull
#undef lnode_pool_isempty
#undef list_append
#undef list_prepend
#undef list_first
#undef list_last
#undef list_next
#undef list_prev
#undef list_count
#undef list_del_first
#undef list_del_last
#undef lnode_put
#undef lnode_get

/*
 * Return 1 if the list is empty, 0 otherwise
 */

int list_isempty(list_t *list)
{
    return list->count == 0;
}

/*
 * Return 1 if the list is full, 0 otherwise
 * Permitted only on bounded lists. 
 */

int list_isfull(list_t *list)
{
    return list->count == list->maxcount;
}

/*
 * Check if the node pool is empty.
 */

int lnode_pool_isempty(lnodepool_t *pool)
{
    return (pool->fre == NULL);
}

/*
 * Add the given node at the end of the list
 */

void list_append(list_t *list, lnode_t *node)
{
    list_ins_before(list, node, &list->nilnode);
}

/*
 * Add the given node at the beginning of the list.
 */

void list_prepend(list_t *list, lnode_t *node)
{
    list_ins_after(list, node, &list->nilnode);
}

/*
 * Retrieve the first node of the list
 */

lnode_t *list_first(list_t *list)
{
    if (list->nilnode.next == &list->nilnode)
	return NULL;
    return list->nilnode.next;
}

/*
 * Retrieve the last node of the list
 */

lnode_t *list_last(list_t *list)
{
    if (list->nilnode.prev == &list->nilnode)
	return NULL;
    return list->nilnode.prev;
}

/*
 * Retrieve the count of nodes in the list
 */

listcount_t list_count(list_t *list)
{
    return list->count;
}

/*
 * Remove the first node from the list and return it.
 */

lnode_t *list_del_first(list_t *list)
{
    return list_delete(list, list->nilnode.next);
}

/*
 * Remove the last node from the list and return it.
 */

lnode_t *list_del_last(list_t *list)
{
    return list_delete(list, list->nilnode.prev);
}


/*
 * Associate a data item with the given node.
 */

void lnode_put(lnode_t *lnode, void *data)
{
    lnode->data = data;
}

/*
 * Retrieve the data item associated with the node.
 */

void *lnode_get(lnode_t *lnode)
{
    return lnode->data;
}

/*
 * Retrieve the node's successor. If there is no successor, 
 * the sentinel ``nilnode'' of the list is returned; that is, the
 * returned value compares true to list_nil(L), where L is the
 * list which contains the node.
 */

lnode_t *list_next(list_t *list, lnode_t *lnode)
{
    assert (list_contains(list, lnode));

    if (lnode->next == list_nil(list))
	return NULL;
    return lnode->next;
}

/*
 * Retrieve the node's predecessor. See comment for lnode_next().
 */

lnode_t *list_prev(list_t *list, lnode_t *lnode)
{
    assert (list_contains(list, lnode));

    if (lnode->prev == list_nil(list))
	return NULL;
    return lnode->prev;
}

/*
 * Return 1 if the lnode is in some list, otherwise return 0.
 */

int lnode_is_in_a_list(lnode_t *lnode)
{
    return (lnode->next != NULL || lnode->prev != NULL);
}


int list_verify(list_t *list)
{
    lnode_t *node = list_first_priv(list), *nil = list_nil(list);
    listcount_t count = list_count(list);

    if (node->prev != nil)
	return 0;

    if (count > list->maxcount)
	return 0;

    while (node != nil && count--) {
	if (node->next->prev != node)
	    return 0;
	node = node->next;
    }

    if (count != 0 || node != nil)
	return 0;
    
    return 1;
}

#ifdef KAZLIB_TEST_MAIN

#include <stdio.h>
#include <string.h>

#ifndef EXIT_FAILURE
#define EXIT_FAILURE 1
#endif

static void print(list_t *list, lnode_t *node, void *v)
{
    char *str = lnode_get(node);
    fputs(str, stdout);
    putchar('\n');
}

static int compare(const void *left, const void *right)
{
    return strcmp(left, right);
}

int main(void)
{
    list_t listobj;
    char linebuf[1024];
    char *p;
    lnode_t *n;

    list_init(&listobj, -1);

    while (fgets(linebuf, 1024, stdin)) {
	if ((p = strchr(linebuf, '\n')))
	    *p = 0;
	p = malloc(strlen(linebuf) + 1);
	if (!p)
	    exit(EXIT_FAILURE);
	strcpy(p, linebuf);
	list_append(&listobj, lnode_create(p));
    }

    n = list_first(&listobj);
    #if 0
    list_append(&listobj, list_first(&listobj));
    #endif
    #if 0
    list_destroy(&listobj);
    #endif
    #if 0
    list_delete(&listobj, n);
    list_delete(&listobj, n);
    #endif

    #if 1
    if (list_is_sorted(&listobj, compare))
	puts("already sorted");
    #endif
    list_sort(&listobj, compare);
    #if 1
    list_process(&listobj, NULL, print);
    #endif

    return 0;
}

#endif	/* defined TEST_MAIN */