Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/misc/volume38/menushell/part03/dl.c

C/C++ Source or Header | 1993-07-30 | 5.3 KB | 333 lines

/* ============================== dl.c ============================== */
#include "dl.h"

void *malloc();

char *getnode(size)
{
    DL_NODE *n;

    if (n = (DL_NODE *) malloc(size)) {
        memset(n, '\0', size);
        n->size = size;
    }
    return(n);
}

freenode(n)
DL_NODE *n;
{
    free(n);
}

/*
 * Create an empty list
 */
DLIST dl_create(flags)
int flags;
{
    DLIST l;

    if ((l = (DLIST) malloc(sizeof(struct dl))) == NULL)
        return NULL;

    l->head = l->tail = l->curr = NULL;
    l->size = 0;
    l->flags = flags;
    return(l);
}

/*
 * Free entire list
 */
dl_destroy(l)
DLIST l;
{
    while (dl_shead(l))
        dl_delete(l);
    /*
     * it is assumed that the list head structure itself was
     * from dl_create, thus will always be free'd.
     */
    free(l);
}

/*
 * Delete specific node
 */
dl_delete_node(l, n)
DLIST l;
DL_NODE *n;
{
    if (n) {
        dl_detach_node(l, n);

        if ((l->flags & DL_FREE) == DL_FREE)
            freenode(n);
    }
}

/*
 * Delete node, but leave memory alone
 */
dl_detach_node(l, n)
DLIST l;
DL_NODE *n;
{
    l->size--;

    l->curr = n->next;
    if (n->prev)
        n->prev->next = n->next;
    else
        l->head = n->next;
    if (n->next)
        n->next->prev = n->prev;
    else
        l->tail = n->prev;
}

/*
 * Insert node n before the current location in list l
 */
dl_ins_before_node(l, n_on_list, new_n)
DLIST l;
DL_NODE *n_on_list, *new_n;
{
    l->size++;

    if (l->head == NULL) {
        l->head = l->tail = l->curr = new_n;
        new_n->next = new_n->prev = NULL;
        return;
    }

    dl_set(l, n_on_list);
    if (l->curr == NULL)
        l->curr = l->head;

    new_n->prev = l->curr->prev;
    new_n->next = l->curr;
    if (l->curr->prev)
        l->curr->prev->next = new_n;
    else
        l->head = new_n;        /* else l->curr == l->head */
    l->curr->prev = new_n;

    l->curr = new_n;
}

dl_ins_after_node(l, n_on_list, new_n)
DLIST l;
DL_NODE *n_on_list, *new_n;
{
    l->size++;

    if (l->head == NULL) {
        l->head = l->tail = l->curr = new_n;
        new_n->next = new_n->prev = NULL;
        return;
    }

    dl_set(l, n_on_list);
    if (l->curr == NULL)
        l->curr = l->tail;

    new_n->prev = l->curr;
    new_n->next = l->curr->next;
    if (l->curr->next)
        l->curr->next->prev = new_n;
    else
        l->tail = new_n;        /* else l->curr == l->tail */
    l->curr->next = new_n;

    l->curr = new_n;
}

/*
 * Join l2 to the end of l1; l2 is no longer usable
 */
dl_cat(l1, l2)
DLIST l1, l2;
{
    l1->size += l2->size;
    l1->tail->next = l2->head;
    l2->head->prev = l1->tail;
    l1->tail = l2->tail;

    free(l2);
}

/*
 *  Split list 'l' into two, so that 'n' is the first node of the new list,
 *  return pointer to new list.
 */
/*  Uncomment and do as exercise
DLIST dl_split_at_node(l, n)
DLIST l;
DL_NODE *n;
{
    DLIST newl;

    if ((newl = dl_create(dl_flags(l))) == NULL)
        return(NULL);

    newl->size = count from current pos to end
    l->size = count up to current pos (l->size - newl->size)

    adjust pointers (last of l, first of newl (i.e., n))

    return newl
}
*/

DLIST dl_copy(l)
DLIST l;
{
    DLIST newl;
    DL_NODE *n, *newn;

    if ((newl = dl_create(dl_flags(l))) == NULL)
        return(NULL);

    foreachnode(l, n) {
        newn = getnode(n->size);
        if (newn == NULL) {
            dl_destroy(newl);
            return(NULL);
        }
        memcpy(newn, n, n->size);    /* copies ptrs, but is ok */
        dl_append(newl, newn);
    }

    return(newl);
}

dl_compare(l1, l2, func)
DLIST l1, l2;
int (*func)();
{
    int comp;

    for (dl_shead(l1), dl_shead(l2);
         dl_curr(l1) && dl_curr(l2);
         dl_snext(l1), dl_snext(l2))
        if ((comp = (*func)(dl_curr(l1), dl_curr(l2))) != 0)
            return(comp);

    if (dl_curr(l1))
        return(1);    /* l2 ran out first */
    else if (dl_curr(l2))
        return(-1);    /* l1 ran out first */
    else
        return(0);    /* both ran out at same time */
}

dl_apply(l, func, arg)
DLIST l;
int (*func)();
char *arg;
{
    foreach(l)
        (*func)(dl_curr(l), arg);
}

/*
 * Do a linear search on the list, given a start/end point
 */
dl_lsearch(l, begin, end, key, func)
DLIST l;
DL_NODE *begin, *end;
void *key;
int (*func)();
{
    DL_NODE *n;

    for (n = begin; n != end; n = n->next)
        if ((*func)(n, key)) {
            l->curr = n;
            return(TRUE);
        }

    return(FALSE);
}

/*
 * dl_sort - take a list and a 'qsort' type cmp func & sort
 *
 * since we make an array of ptrs, qsort really needs a cmp func
 * that follows a pointer to pointer to user struct; but this is
 * ugly for users, so dl_sort_cmp_fun does one indirection then
 * calls the users cmp func.
 */

static int (*dl_sort_user_cmp_fun)();

dl_sort_cmp_fun(p1, p2)
DL_NODE **p1, **p2;
{
    return((*dl_sort_user_cmp_fun)(*p1, *p2));
}

dl_sort(l, func)
DLIST l;
int (*func)();
{
    DL_NODE **array;
    int i, last;

    if (l->size <= 1)
        return(0);

    if ((array = dl_l2a(l)) == NULL)
        return(-1);

    dl_sort_user_cmp_fun = func;
    qsort(array, l->size, sizeof(DL_NODE *), dl_sort_cmp_fun);

    dl_a2l(l, array);

    free(array);

    return(0);
}

/* from a list, make an array of pointers to the list items */
DL_NODE **
dl_l2a(l)
DLIST l;
{
    DL_NODE *n, **array, **a;

    array = (DL_NODE **) malloc(l->size*sizeof(DL_NODE *));
    if (array == NULL)
        return(NULL);

    for (n = l->head, a = array; n != NULL; n = n->next, a++)
        *a = n;

    return(array);
}

/* turn an array of pointers to the list items into a list */
dl_a2l(l, array)
DLIST l;
DL_NODE **array;
{
    int i, last;

    l->head = array[0];
    l->head->prev = NULL;
    l->head->next = array[1];

    last = l->size - 1;
    for (i = 1; i < last; i++) {
        array[i]->next = array[i+1];
        array[i]->prev = array[i-1];
    }

    l->tail = array[last];
    l->tail->next = NULL;
    l->tail->prev = array[last-1];
}