source: trunk/kitgen/8.x/blt/generic/bltList.c

/*
 * bltList.c --
 *
 *      The module implements generic linked lists.
 *
 * Copyright 1991-1998 Lucent Technologies, Inc.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Lucent Technologies disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 */

#include "bltInt.h"
#include "bltList.h"

static struct Blt_ListNodeStruct *
FindString(listPtr, key)
    struct Blt_ListStruct *listPtr; /* List to search */
    CONST char *key;            /* Key to match */
{
    register struct Blt_ListNodeStruct *nodePtr;
    char c;

    c = key[0];
    for (nodePtr = listPtr->headPtr; nodePtr != NULL; 
         nodePtr = nodePtr->nextPtr) {
        if ((c == nodePtr->key.string[0]) &&
            (strcmp(key, nodePtr->key.string) == 0)) {
            return nodePtr;
        }
    }
    return NULL;
}

static Blt_ListNode
FindOneWord(listPtr, key)
    struct Blt_ListStruct *listPtr; /* List to search */
    CONST char *key;            /* Key to match */
{
    register struct Blt_ListNodeStruct *nodePtr;

    for (nodePtr = listPtr->headPtr; nodePtr != NULL; 
         nodePtr = nodePtr->nextPtr) {
        if (key == nodePtr->key.oneWordValue) {
            return nodePtr;
        }
    }
    return NULL;
}

static Blt_ListNode
FindArray(listPtr, key)
    struct Blt_ListStruct *listPtr; /* List to search */
    CONST char *key;            /* Key to match */
{
    register struct Blt_ListNodeStruct *nodePtr;
    int nBytes;

    nBytes = sizeof(int) * listPtr->type;
    for (nodePtr = listPtr->headPtr; nodePtr != NULL; 
         nodePtr = nodePtr->nextPtr) {
        if (memcmp(key, nodePtr->key.words, nBytes) == 0) {
            return nodePtr;
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * FreeNode --
 *
 *      Free the memory allocated for the node.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
static void
FreeNode(nodePtr)
    struct Blt_ListNodeStruct *nodePtr;
{
    Blt_Free(nodePtr);
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListCreate --
 *
 *      Creates a new linked list structure and initializes its pointers
 *
 * Results:
 *      Returns a pointer to the newly created list structure.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
Blt_List 
Blt_ListCreate(type)
    int type;
{
    struct Blt_ListStruct *listPtr;

    listPtr = Blt_Malloc(sizeof(struct Blt_ListStruct));
    if (listPtr != NULL) {
        Blt_ListInit(listPtr, type);
    }
    return listPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListCreateNode --
 *
 *      Creates a list node holder.  This routine does not insert
 *      the node into the list, nor does it no attempt to maintain
 *      consistency of the keys.  For example, more than one node
 *      may use the same key.
 *
 * Results:
 *      The return value is the pointer to the newly created node.
 *
 * Side Effects:
 *      The key is not copied, only the Uid is kept.  It is assumed
 *      this key will not change in the life of the node.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
Blt_ListNode
Blt_ListCreateNode(listPtr, key)
    struct Blt_ListStruct *listPtr;
    CONST char *key;            /* Unique key to reference object */
{
    register struct Blt_ListNodeStruct *nodePtr;
    int keySize;

    if (listPtr->type == BLT_STRING_KEYS) {
        keySize = strlen(key) + 1;
    } else if (listPtr->type == BLT_ONE_WORD_KEYS) {
        keySize = sizeof(int);
    } else {
        keySize = sizeof(int) * listPtr->type;
    }
    nodePtr = Blt_Calloc(1, sizeof(struct Blt_ListNodeStruct) + keySize - 4);
    assert(nodePtr);
    nodePtr->clientData = NULL;
    nodePtr->nextPtr = nodePtr->prevPtr = NULL;
    nodePtr->listPtr = listPtr;
    switch (listPtr->type) {
    case BLT_STRING_KEYS:
        strcpy(nodePtr->key.string, key);
        break;
    case BLT_ONE_WORD_KEYS:
        nodePtr->key.oneWordValue = key;
        break;
    default:
        memcpy(nodePtr->key.words, key, keySize);
        break;
    }
    return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListReset --
 *
 *      Removes all the entries from a list, removing pointers to the
 *      objects and keys (not the objects or keys themselves).  The
 *      node counter is reset to zero.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListReset(listPtr)
    struct Blt_ListStruct *listPtr; /* List to clear */
{
    if (listPtr != NULL) {
        register struct Blt_ListNodeStruct *oldPtr;
        register struct Blt_ListNodeStruct *nodePtr = listPtr->headPtr;

        while (nodePtr != NULL) {
            oldPtr = nodePtr;
            nodePtr = nodePtr->nextPtr;
            FreeNode(oldPtr);
        }
        Blt_ListInit(listPtr, listPtr->type);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListDestroy
 *
 *     Frees all list structures
 *
 * Results:
 *      Returns a pointer to the newly created list structure.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListDestroy(listPtr)
    struct Blt_ListStruct *listPtr;
{
    if (listPtr != NULL) {
        Blt_ListReset(listPtr);
        Blt_Free(listPtr);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListInit --
 *
 *      Initializes a linked list.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListInit(listPtr, type)
    struct Blt_ListStruct *listPtr;
    int type;
{
    listPtr->nNodes = 0;
    listPtr->headPtr = listPtr->tailPtr = NULL;
    listPtr->type = type;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListLinkAfter --
 *
 *      Inserts an node following a given node.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListLinkAfter(listPtr, nodePtr, afterPtr)
    struct Blt_ListStruct *listPtr;
    struct Blt_ListNodeStruct *nodePtr;
    struct Blt_ListNodeStruct *afterPtr;
{
    if (listPtr->headPtr == NULL) {
        listPtr->tailPtr = listPtr->headPtr = nodePtr;
    } else {
        if (afterPtr == NULL) {
            /* Prepend to the front of the list */
            nodePtr->nextPtr = listPtr->headPtr;
            nodePtr->prevPtr = NULL;
            listPtr->headPtr->prevPtr = nodePtr;
            listPtr->headPtr = nodePtr;
        } else {
            nodePtr->nextPtr = afterPtr->nextPtr;
            nodePtr->prevPtr = afterPtr;
            if (afterPtr == listPtr->tailPtr) {
                listPtr->tailPtr = nodePtr;
            } else {
                afterPtr->nextPtr->prevPtr = nodePtr;
            }
            afterPtr->nextPtr = nodePtr;
        }
    }
    nodePtr->listPtr = listPtr;
    listPtr->nNodes++;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListLinkBefore --
 *
 *      Inserts an node preceding a given node.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListLinkBefore(listPtr, nodePtr, beforePtr)
    struct Blt_ListStruct *listPtr; /* List to contain new node */
    struct Blt_ListNodeStruct *nodePtr; /* New node to be inserted */
    struct Blt_ListNodeStruct *beforePtr;       /* Node to link before */
{
    if (listPtr->headPtr == NULL) {
        listPtr->tailPtr = listPtr->headPtr = nodePtr;
    } else {
        if (beforePtr == NULL) {
            /* Append onto the end of the list */
            nodePtr->nextPtr = NULL;
            nodePtr->prevPtr = listPtr->tailPtr;
            listPtr->tailPtr->nextPtr = nodePtr;
            listPtr->tailPtr = nodePtr;
        } else {
            nodePtr->prevPtr = beforePtr->prevPtr;
            nodePtr->nextPtr = beforePtr;
            if (beforePtr == listPtr->headPtr) {
                listPtr->headPtr = nodePtr;
            } else {
                beforePtr->prevPtr->nextPtr = nodePtr;
            }
            beforePtr->prevPtr = nodePtr;
        }
    }
    nodePtr->listPtr = listPtr;
    listPtr->nNodes++;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListUnlinkNode --
 *
 *      Unlinks an node from the given list. The node itself is
 *      not deallocated, but only removed from the list.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListUnlinkNode(nodePtr)
    struct Blt_ListNodeStruct *nodePtr;
{
    struct Blt_ListStruct *listPtr;

    listPtr = nodePtr->listPtr;
    if (listPtr != NULL) {
        if (listPtr->headPtr == nodePtr) {
            listPtr->headPtr = nodePtr->nextPtr;
        }
        if (listPtr->tailPtr == nodePtr) {
            listPtr->tailPtr = nodePtr->prevPtr;
        }
        if (nodePtr->nextPtr != NULL) {
            nodePtr->nextPtr->prevPtr = nodePtr->prevPtr;
        }
        if (nodePtr->prevPtr != NULL) {
            nodePtr->prevPtr->nextPtr = nodePtr->nextPtr;
        }
        nodePtr->listPtr = NULL;
        listPtr->nNodes--;
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListGetNode --
 *
 *      Find the first node matching the key given.
 *
 * Results:
 *      Returns the pointer to the node.  If no node matching
 *      the key given is found, then NULL is returned.
 *
 *----------------------------------------------------------------------
 */

/*LINTLIBRARY*/
Blt_ListNode
Blt_ListGetNode(listPtr, key)
    struct Blt_ListStruct *listPtr; /* List to search */
    CONST char *key;            /* Key to match */
{
    if (listPtr != NULL) {
        switch (listPtr->type) {
        case BLT_STRING_KEYS:
            return FindString(listPtr, key);
        case BLT_ONE_WORD_KEYS:
            return FindOneWord(listPtr, key);
        default:
            return FindArray(listPtr, key);
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListDeleteNode --
 *
 *      Unlinks and deletes the given node.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListDeleteNode(nodePtr)
    struct Blt_ListNodeStruct *nodePtr;
{
    Blt_ListUnlinkNode(nodePtr);
    FreeNode(nodePtr);
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListDeleteNodeByKey --
 *
 *      Find the node and free the memory allocated for the node.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListDeleteNodeByKey(listPtr, key)
    struct Blt_ListStruct *listPtr;
    CONST char *key;
{
    struct Blt_ListNodeStruct *nodePtr;

    nodePtr = Blt_ListGetNode(listPtr, key);
    if (nodePtr != NULL) {
        Blt_ListDeleteNode(nodePtr);
    }
}

/*LINTLIBRARY*/
Blt_ListNode
Blt_ListAppend(listPtr, key, clientData)
    struct Blt_ListStruct *listPtr;
    CONST char *key;
    ClientData clientData;
{
    struct Blt_ListNodeStruct *nodePtr;

    nodePtr = Blt_ListCreateNode(listPtr, key);
    Blt_ListSetValue(nodePtr, clientData);
    Blt_ListAppendNode(listPtr, nodePtr);
    return nodePtr;
}

/*LINTLIBRARY*/
Blt_ListNode
Blt_ListPrepend(listPtr, key, clientData)
    struct Blt_ListStruct *listPtr;
    CONST char *key;
    ClientData clientData;
{
    struct Blt_ListNodeStruct *nodePtr;

    nodePtr = Blt_ListCreateNode(listPtr, key);
    Blt_ListSetValue(nodePtr, clientData);
    Blt_ListPrependNode(listPtr, nodePtr);
    return nodePtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListGetNthNode --
 *
 *      Find the node based upon a given position in list.
 *
 * Results:
 *      Returns the pointer to the node, if that numbered element
 *      exists. Otherwise NULL.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
Blt_ListNode
Blt_ListGetNthNode(listPtr, position, direction)
    struct Blt_ListStruct *listPtr; /* List to traverse */
    int position;               /* Index of node to select from front
                                 * or back of the list. */
    int direction;
{
    register struct Blt_ListNodeStruct *nodePtr;

    if (listPtr != NULL) {
        if (direction > 0) {
            for (nodePtr = listPtr->headPtr; nodePtr != NULL; 
                 nodePtr = nodePtr->nextPtr) {
                if (position == 0) {
                    return nodePtr;
                }
                position--;
            }
        } else {
            for (nodePtr = listPtr->tailPtr; nodePtr != NULL; 
                 nodePtr = nodePtr->prevPtr) {
                if (position == 0) {
                    return nodePtr;
                }
                position--;
            }
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_ListSort --
 *
 *      Find the node based upon a given position in list.
 *
 * Results:
 *      Returns the pointer to the node, if that numbered element
 *      exists. Otherwise NULL.
 *
 *----------------------------------------------------------------------
 */
/*LINTLIBRARY*/
void
Blt_ListSort(listPtr, proc)
    struct Blt_ListStruct *listPtr; /* List to traverse */
    Blt_ListCompareProc *proc;
{
    struct Blt_ListNodeStruct **nodeArr;
    register struct Blt_ListNodeStruct *nodePtr;
    register int i;

    if (listPtr->nNodes < 2) {
        return;
    }
    nodeArr = Blt_Malloc(sizeof(Blt_List) * (listPtr->nNodes + 1));
    if (nodeArr == NULL) {
        return;                 /* Out of memory. */
    }
    i = 0;
    for (nodePtr = listPtr->headPtr; nodePtr != NULL; 
         nodePtr = nodePtr->nextPtr) {
        nodeArr[i++] = nodePtr;
    }
    qsort((char *)nodeArr, listPtr->nNodes, 
                sizeof(struct Blt_ListNodeStruct *), (QSortCompareProc *)proc);

    /* Rethread the list. */
    nodePtr = nodeArr[0];
    listPtr->headPtr = nodePtr;
    nodePtr->prevPtr = NULL;
    for (i = 1; i < listPtr->nNodes; i++) {
        nodePtr->nextPtr = nodeArr[i];
        nodePtr->nextPtr->prevPtr = nodePtr;
        nodePtr = nodePtr->nextPtr;
    }
    listPtr->tailPtr = nodePtr;
    nodePtr->nextPtr = NULL;
    Blt_Free(nodeArr);
}