#ifndef LINK_LIST_H_
#define LINK_LIST_H_

#include <systemDefs.h>
#include <locks.h>


// ----------------------------------------------------------------------------------
// generic link list
// can be used with ANY User data type
// each data item can be a different size - allocate using listItemType
// data is allocated dynamically
//
// multiple readers/writers allowed depending on locks used
// 
// each "list user"  allows a different view of the list - i.e. different location ptrs
// into the list. Unlimited list users allowed for each list.
// ----------------------------------------------------------------------------------


#ifdef __cplusplus
extern "C"
{
#endif
    
    
      
typedef void *LIST_USER_ID; // user access to list
typedef void *LIST_ITEM;    // user data type  (your stuff)

typedef struct listItemType {
    UINT      size;  // bytes
    LIST_ITEM item;
};


// ----------------------------------------------------------------------------------

#define LIST_USER_ID_ERROR       0  

#if defined(USE_LOCKS)

// can specify the interrupt locking strategy(if any) via params 
LIST_USER_ID createListWithNewLock(struct lockType lockInfo); 

// if already have a lock to use
LIST_USER_ID createListWithLock(LOCK_ID lockId); 

#else
LIST_USER_ID createList(); 
#endif // USE_LOCKS

 
LIST_USER_ID deleteListUser(LIST_USER_ID userId);                        // when user finished with access
LIST_USER_ID cloneListUser(LIST_USER_ID userId);                         // create new User - same as original - inc current ptr                        
boolean copyListUser(LIST_USER_ID origUserId, LIST_USER_ID copyUserId);  // copy current ptr

// ----------------------------------------------------------------------------------

UINT itemsInlist(LIST_USER_ID userId);
UINT memorySizeofList(LIST_USER_ID userId);  // bytes

// status returned
#define LIST_DELETED                6
#define LIST_ITEM_STALE             5
#define LIST_EMPTY                  4
#define LIST_MEMORY_EXHAUSTED       3
#define LIST_ITEM_INVALID           2
#define LIST_USER_ID_INVALID        1
#define LIST_SUCCESS                0

BYTE sortList(LIST_USER_ID userId, boolean(*sortCriteria)(LIST_ITEM itemA, LIST_ITEM itemB));
BYTE deleteList(LIST_USER_ID userId); 
BYTE cleanList(LIST_USER_ID userId);                                    // remove all items

BYTE addItem(LIST_USER_ID userId, struct listItemType newItem);         // to end of list (current ptr = new item)
BYTE addItemToFront(LIST_USER_ID userId, struct listItemType newItem);  // to start of list (current ptr = new item)
BYTE insertItem(LIST_USER_ID userId, struct listItemType newItem);      // insert before (current ptr = new item)
BYTE updateItem(LIST_USER_ID userId, struct listItemType newItem);      // realloc
BYTE removeItem(LIST_USER_ID userId);                                   // (current ptr = prev item)
BYTE moveItem(LIST_USER_ID userId);                                     // to end of list
BYTE moveItemToFront(LIST_USER_ID userId);                              // to start of list

// ----------------------------------------------------------------------------------

#define NO_LIST_ITEM    0    // returned when no more items in list or invalid userId

LIST_ITEM firstItem(LIST_USER_ID userId);  // can loop through the list using these
LIST_ITEM lastItem(LIST_USER_ID userId);
LIST_ITEM nextItem(LIST_USER_ID userId);
LIST_ITEM prevItem(LIST_USER_ID userId);
LIST_ITEM currentItem(LIST_USER_ID userId);

LIST_ITEM findFirst(LIST_USER_ID userId, 
                    LIST_ITEM itemToMatch, 
                    boolean(*matchCriteria)(LIST_ITEM item, LIST_ITEM matchItem));

LIST_ITEM findNext(LIST_USER_ID userId, 
                   LIST_ITEM itemToMatch, 
                   boolean(*matchCriteria)(LIST_ITEM item, LIST_ITEM matchItem));



#ifdef __cplusplus
}
#endif


#endif // LINK_LIST_H_

 
#include <linkList.h>
#include <systemRAM.h> 
#include <locks.h> 

#include <malloc.h>
#include <string.h>
#include <stdlib.h>



#ifdef __cplusplus
extern "C"
{
#endif

    
    
#define MIN_LIST_ITEM_SIZE   1   // bytes
    
#define VALID_LIST  0x3AC66CA3
#define VALID_NODE  0xC63AA36C
#define INVALID_KEY     0

typedef void *LIST_ID;

typedef struct nodeType {    
    struct nodeType *prev;
    struct nodeType *next;
    LIST_ITEM        item;    // user data item 
    UINT            itemSize;
    UINT             nodeValid;
};

typedef struct listType {    
    struct nodeType *head;
    struct nodeType *tail;    
    UINT             numNodes;
    UINT             listValid;  // simple ptr security
    UINT             listKey;    // rand generated
    struct nodeType *spare;    

#if defined(USE_LOCKS)
    enum lockClassType     lockClass;
    LOCK_ID             lockId;
    boolean             reuseLock;
#endif // USE_LOCKS

};

typedef struct listUserType {    
    struct nodeType *current;    
    LIST_ID            listId; 
    UINT            userKey;
};


typedef struct listType      * LIST;
typedef struct nodeType      * NODE;
typedef struct listUserType  * USER;    



// *****************************************************
// locals
// *****************************************************

// ---------------------------------------------------------------------------
// user should create own file of find/sort functions specific to their datatypes
// ---------------------------------------------------------------------------

// simple example matchCriteria

boolean findEquals(LIST_ITEM item, LIST_ITEM matchItem) {        
    return item == matchItem ? TRUE : FALSE;
}

// simple example sortCriteria
// this will sort based on ptr not contents 

boolean sortAscending(LIST_ITEM itemA, LIST_ITEM itemB) {
    return itemA > itemB ? TRUE : FALSE;    
}

// ---------------------------------------------------------------------------

boolean validReader(LIST_USER_ID userId) {

#if defined(USE_LOCKS)
    USER user = (USER)userId;    
    LIST linkList = (LIST)user->listId;        

    if (linkList->lockClass == NO_LOCKS) {
        // no checks
        return TRUE;
    } else {
        boolean validStatus = FALSE;
        
        USER user = (USER)userId;
        
        if ((userId != LIST_USER_ID_ERROR) && validHeapAddress(user->listId)) {
            
            LIST linkList = (LIST)user->listId;    

            if ((linkList->listValid == VALID_LIST) && (user->userKey == linkList->listKey)) {
                validStatus = TRUE;
            }         
        }
        return validStatus;
    }
#else
    // no checks
    return TRUE;
#endif // USE_LOCKS
        

}

BYTE validWriter(LIST_USER_ID userId) {
    BYTE status = LIST_USER_ID_INVALID;
    
    USER user = (USER)userId;
    
    if ((userId != LIST_USER_ID_ERROR) && validHeapAddress(user->listId)) {
        
        LIST linkList = (LIST)user->listId;    
        
#if defined(USE_LOCKS)
    lockAll();
#endif // USE_LOCKS
    
        // make sure our list is valid (then lock onto it)

        if ((linkList->listValid == VALID_LIST) && 
            (user->userKey == linkList->listKey)) {
            
            status = LIST_SUCCESS;

#if defined(USE_LOCKS)
            lock(linkList->lockId);
#endif // USE_LOCKS
                
        } else {                
            status = LIST_DELETED;
        } 
        
#if defined(USE_LOCKS)
    unLockAll();
#endif // USE_LOCKS        
    
    }
    
    return status;
}


boolean validNode(NODE node) {        
    return ((node != NO_LIST_ITEM) && (node->nodeValid == VALID_NODE)) ? TRUE : FALSE;    
}


NODE findNode(NODE currentNode, 
              LIST_ITEM itemToMatch,
              boolean(*matchCriteria)(LIST_ITEM, LIST_ITEM)) {
    
    boolean found = FALSE;  // default
    NODE node = currentNode; 
    
    if (matchCriteria == NULL) {
        matchCriteria = findEquals;
    }
        
    while (node != NO_LIST_ITEM) {    
        if ((*matchCriteria)(node->item, itemToMatch)) {    
            found = TRUE;
            break; // found
        }
        node = node->next;
    } // loop        
    
    return found ? node : NULL;
}

        
NODE findNodeWithChecks(NODE currentNode, 
                          LIST_ITEM itemToMatch,
                          boolean(*matchCriteria)(LIST_ITEM, LIST_ITEM)) {
    
    boolean found = FALSE;  // default
    NODE node = currentNode; 
    
    if (matchCriteria == NULL) {
        matchCriteria = findEquals;
    }
    
    while (validNode(node)) {    
        if ((*matchCriteria)(node->item, itemToMatch)) {    
            found = TRUE;
            break; // found
        }
        node = node->next;
    } // loop    

    return found ? node : NULL;
}

void swapNodes(LIST linkList, NODE nodeA, NODE nodeB) {
    
    NODE nodeAPrev = nodeA->prev;        

    if ((nodeA != NULL) && (nodeB != NULL)) {
                
        // nodeA
        nodeA->next = nodeB->next;
        nodeA->prev = nodeB;
        if (nodeB->next != NULL) {
            nodeB->next->prev = nodeA;         
        } else {
            // new tail
            linkList->tail = nodeA;
        }
        
        // nodeB
        nodeB->next = nodeA;
        nodeB->prev = nodeAPrev;
        if (nodeAPrev != NULL) {
            nodeAPrev->next = nodeB;    
        } else {
            // new head
            linkList->head = nodeB;            
        }    
    }    
}


BYTE allocateItemMemory(NODE node, struct listItemType newItem) {
    
    if ((newItem.size >= MIN_LIST_ITEM_SIZE) && (newItem.item != NULL)) {
        // get memory for the data item
        LIST_ITEM pNewItem = malloc(newItem.size);
    
        if (pNewItem != NULL) {    
            node->itemSize = newItem.size;

            // setup ptr and copy user data to linklist memory
            node->item = pNewItem;
            memcpy(node->item, newItem.item, newItem.size);    
            
            return LIST_SUCCESS;
            
        } else {
            return LIST_MEMORY_EXHAUSTED;            
        }
    } else {
        return LIST_ITEM_INVALID;
    }
}

void resetList(LIST_ID listId) {
    LIST linkList = (LIST)listId;
    linkList->head = NULL;
    linkList->tail = NULL;
    linkList->numNodes = 0;        
    linkList->listValid = VALID_LIST;
}


void removeAllNodes(LIST_USER_ID userId) {
    
    NODE node;
    NODE nextNode;
    USER user = (USER)userId;    
    LIST linkList = (LIST)user->listId;        
        
    node = linkList->head;

    // delete all nodes and item data
    while (node != NULL) {
        nextNode = node->next;
       
        node->item = freeMemory(node->item); // user data
        node->prev = NO_LIST_ITEM;
        node->next = NO_LIST_ITEM;
        node->itemSize = 0;
        node->nodeValid = INVALID_KEY;
      
        node = (NODE)freeMemory(node);
          node = nextNode;
    } // loop

    resetList(linkList);    
}



// *****************************************************
// implementations
// *****************************************************


#if defined(USE_LOCKS)
    LIST_USER_ID createListWithReuseLock(LOCK_ID lockId, boolean reuseLock) {
#else    
    LIST_USER_ID createList(void) {
#endif // USE_LOCKS
    
    
#if defined(USE_LOCKS)
    lockAll();
#endif // USE_LOCKS

    USER user = LIST_USER_ID_ERROR;
    LIST_ID listId = malloc(sizeof(struct listType));

    if (listId != LIST_USER_ID_ERROR) {
        
        resetList(listId);
        
        LIST linkList = (LIST)listId;        
        linkList->listKey = rand();
        linkList->spare = (NODE)malloc(sizeof(struct nodeType));
        
        if (linkList->spare != LIST_USER_ID_ERROR) {    
                                    
            user = (USER)malloc(sizeof(struct listUserType));
                    
            if (user != LIST_USER_ID_ERROR) {
                user->current = linkList->head;
                user->listId = listId;
                user->userKey = linkList->listKey;
                                
#if defined(USE_LOCKS)
                linkList->lockClass = getLockClass(lockId);            
                linkList->lockId = lockId;     
                linkList->reuseLock = reuseLock;
#endif // USE_LOCKS            
                
            } else {
                listId = freeMemory(linkList->spare);                
                listId = freeMemory(listId);
            }                        
            
        } else {
            listId = freeMemory(listId);
        }            
    }
    
#if defined(USE_LOCKS)                
    //tidy
    if ((user == LIST_USER_ID_ERROR) && !reuseLock) {
        lockId = deleteLock(lockId);
    }
#endif // USE_LOCKS
    
#if defined(USE_LOCKS)
    unLockAll();
#endif // USE_LOCKS    

    return user;
}


#if defined(USE_LOCKS)

LIST_USER_ID createListWithLock(LOCK_ID lockId) {
    return createListWithReuseLock(lockId, TRUE);
}


LIST_USER_ID createListWithNewLock(struct lockType lockInfo) {
    
    LOCK_ID lockId = getLockId(lockInfo); 
    
    if (lockId == NULL) {
        return LIST_USER_ID_ERROR;
    } 
    
    return createListWithReuseLock(lockId, FALSE);
}

#endif // USE_LOCKS


LIST_USER_ID cloneListUser(LIST_USER_ID userId) {
    
    USER newUser = LIST_USER_ID_ERROR;

#if defined(USE_LOCKS)
    lockAll();
#endif // USE_LOCKS

    if (validReader(userId)) {
        USER user = (USER)userId;    
                    
        newUser = (USER)malloc(sizeof(struct listUserType));

        if (newUser != LIST_USER_ID_ERROR) {
            newUser->current = user->current;
            newUser->listId = user->listId;
            newUser->userKey = user->userKey;
        }
    }
    
#if defined(USE_LOCKS)
    unLockAll();
#endif // USE_LOCKS    
    
    return (LIST_USER_ID)newUser;        
}


boolean copyListUser(LIST_USER_ID origUserId, LIST_USER_ID copyUserId) {
    
    boolean success = FALSE;
    
    if (validReader(origUserId) && validReader(copyUserId)) {
        USER origUser = (USER)origUserId;    
        USER copyUser = (USER)copyUserId;    
        
        copyUser->current = origUser->current;
        copyUser->listId = origUser->listId;
        copyUser->userKey = origUser->userKey;
        
        success = TRUE;
    }
    return success;        
}


LIST_USER_ID deleteListUser(LIST_USER_ID userId) {

    if (!validHeapAddress(userId)) { 
        return userId;
    }
    
#if defined(USE_LOCKS)
    lockAll();
#endif // USE_LOCKS
        
    USER user = (USER)userId;    
    user->userKey = INVALID_KEY; // reset
    user->current = NO_LIST_ITEM;
    user->listId = NO_LIST_ITEM;
    user = freeMemory(user);
    
#if defined(USE_LOCKS)
    unLockAll();
#endif // USE_LOCKS    
        
    return LIST_USER_ID_ERROR;
}


BYTE deleteList(LIST_USER_ID userId) {    
    
    BYTE status = validWriter(userId);
                
    if (status == LIST_SUCCESS) {    
        
        removeAllNodes(userId);

        USER user = (USER)userId;            
        LIST linkList = (LIST)user->listId;    
        linkList->listValid = INVALID_KEY;         
        linkList->listKey++;  // ano value
            
        linkList->spare = freeMemory(linkList->spare);

#if defined(USE_LOCKS)
        unLock(linkList->lockId);
#endif // USE_LOCKS
        
#if defined(USE_LOCKS)    
        if (!linkList->reuseLock) {
            linkList->lockId = deleteLock(linkList->lockId);
        }
#endif // USE_LOCKS    
        
        user->listId = freeMemory(user->listId);        

        deleteListUser(userId);
    }

    return status;    
}


BYTE cleanList(LIST_USER_ID userId) {
            
    BYTE status = validWriter(userId);
    
    if (status == LIST_SUCCESS) {        
        USER user = (USER)userId;    
        LIST linkList = (LIST)user->listId;    

        removeAllNodes(userId);    

#if defined(USE_LOCKS)
    unLock(linkList->lockId);
#endif // USE_LOCKS

    }        
    
    return status;
}


// simple sort using supplied user sortCriteria

BYTE sortList(LIST_USER_ID userId, boolean(*sortCriteria)(LIST_ITEM itemA, LIST_ITEM itemB)) {
    
    if (sortCriteria == NULL) {
        sortCriteria = sortAscending;
    }

    NODE node;
    UINT i;
    
    BYTE status = validWriter(userId);
            
    if (status == LIST_SUCCESS) {    
                
        USER user = (USER)userId;    
        LIST linkList = (LIST)user->listId;        

        for (i = 0; i < linkList->numNodes; i++) {
            node = linkList->head;
            
            while ((node != NULL) && (node->next != NULL)) {
                
                if ((*sortCriteria)(node->item, node->next->item)) {
                    swapNodes(linkList, node, node->next);                    
                } else {        
                    node = node->next;
                }
            }// loop                        
        } // loop all nodes    

#if defined(USE_LOCKS)
    unLock(linkList->lockId);
#endif // USE_LOCKS

    }
        
    return status;    
}

// -----------------------------------------------------------------------------

UINT itemsInlist(LIST_USER_ID userId) {
    
    UINT numItems = 0;
    USER user = (USER)userId;
    
    if ((userId != LIST_USER_ID_ERROR) && validHeapAddress(user->listId)) {
        
        LIST linkList = (LIST)user->listId;    

        if ((linkList->listValid == VALID_LIST) && (user->userKey == linkList->listKey)) {
            numItems = linkList->numNodes;
        }
    }
    return numItems;        
}


// byte size of the whole list (as far as linkList is concerned (not inc malloc overheads))
UINT memorySizeofList(