/******************************************************************************
* Product: # # # # # ### ######
* # # # # # # # #
* # # # # # # # #
* # # # # # ######
* # # # # # # # #
* # # # # # # # #
* ##### # # ####### ####### ### ######
*
* File: ux_linkl.c
* Description: A library of linked list functions for creating, deleting,
* searching (etc..) linked lists.
*
* Version: %I%
* Dated: %D%
* Copyright: P.D. Smart, 1994-2019.
*
* History: 1.0 - Initial Release.
*
******************************************************************************
* This source file is free software: you can redistribute it and#or modify
* it under the terms of the GNU General Public License as published
* by the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This source file is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
******************************************************************************/
/* Bring in system header files.
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#if defined(SUNOS) || defined(SOLARIS) || defined(LINUX)
#include
#include
#include
#endif
#if defined(SOLARIS)
#include
#endif
#if defined(LINUX)
#include
#endif
#if defined(_WIN32)
#include
#include
#endif
#if defined(SUNOS) || defined(SOLARIS)
#include
#include
#endif
/* Indicate that we are a C module for any header specifics.
*/
#define UX_LINKEDLIST_C
/* Bring in specific header files.
*/
#include "ux.h"
/******************************************************************************
* Function: AddItem
* Description: A simplistic mechanism to compose a linked list. The link
* is only singly linked, and items are only added to the tail
* of the list.
* Returns: R_OK - Item added successfully.
* R_FAIL - Failure in addition, see Errno.
* E_NOMEM - Memory exhaustion.
* E_BADHEAD - Head pointer is bad.
* E_BADTAIL - Tail pointer is bad.
* E_NOKEY - No search key provided.
******************************************************************************/
int AddItem( LINKLIST **spHead, /* IO: Pointer to head of list */
LINKLIST **spTail, /* IO: Pointer to tail of list */
int nMode, /* I: Mode of addition to link */
UINT *nKey, /* I: Integer based search key */
ULNG *lKey, /* I: Long based search key */
UCHAR *szKey, /* I: String based search key */
void *spData ) /* I: Address of carried data */
{
/* Local variables.
*/
char *szFunc = "AddItem";
LINKLIST *pTmpLRec;
LINKLIST *pTailRec;
LINKLIST *spCur;
LINKLIST *spPrev;
/* Quick check, no point adding to list if there is no data.
*/
if(spData == NULL)
{
Errno = E_NODATA;
return(R_FAIL);
}
/* Allocate enough memory for a linklist control block. This will be
* tagged on to the end of the list... eventually!
*/
if( (pTmpLRec=(LINKLIST *)malloc(sizeof(LINKLIST))) == NULL)
{
Lgr(LOG_DEBUG, szFunc, "Couldnt malloc (%d) bytes",
sizeof(LINKLIST));
Errno = E_NOMEM;
return(R_FAIL);
}
memset((UCHAR *)pTmpLRec, '\0', sizeof(LINKLIST));
/* If a text based search key provided, need to allocate space in which
* to store it. If allocation succeeds, dup key.
*/
if(szKey != NULL)
{
if( (pTmpLRec->szKey=(UCHAR *)malloc(strlen(szKey)+1)) == NULL)
{
Lgr(LOG_DEBUG, szFunc, "Couldnt malloc (%d) bytes",
strlen(szKey)+1);
free(pTmpLRec);
Errno = E_NOMEM;
return(R_FAIL);
} else
{
strcpy(pTmpLRec->szKey, szKey);
}
}
/* Populate linklist.
*/
pTmpLRec->nKey = (nKey == NULL ? 0 : *nKey);
pTmpLRec->lKey = (lKey == NULL ? 0L : *lKey);
pTmpLRec->spData = spData;
/* Right, we have a record, so where do we add it.
*/
if(*spHead == NULL)
{
/* Both pointers look at new element.
*/
*spHead = pTmpLRec;
*spTail = pTmpLRec;
pTmpLRec->spNext = NULL;
} else
{
/* If were sorting the list as we go along, then we need to scan it and
* find the required location.
*/
if(nMode != SORT_NONE)
{
for(spPrev=NULL, spCur= *spHead; spCur != NULL;
spPrev=spCur, spCur=spCur->spNext)
{
if(nMode == SORT_INT_UP && pTmpLRec->nKey < spCur->nKey)
break;
else
if(nMode == SORT_INT_DOWN && pTmpLRec->nKey > spCur->nKey)
break;
else
if(nMode == SORT_LONG_UP && pTmpLRec->lKey < spCur->lKey)
break;
else
if(nMode == SORT_LONG_DOWN && pTmpLRec->lKey > spCur->lKey)
break;
}
/* Error condition, should not occur?
*/
if(spPrev == NULL && spCur == NULL)
{
if(pTmpLRec->szKey != NULL)
free(pTmpLRec->szKey);
free(pTmpLRec);
return(R_FAIL);
} else
/* Insert at very beginning of list?
*/
if(spPrev == NULL && spCur != NULL)
{
pTmpLRec->spNext = *spHead;
*spHead = pTmpLRec;
} else
/* Insert in the middle of the list?
*/
if(spPrev != NULL && spCur != NULL)
{
pTmpLRec->spNext = spPrev->spNext;
spPrev->spNext = pTmpLRec;
} else
/* Insert at the end of the list!
*/
{
/* Add to tail of list by making tail point to new item, then
* new item becomes the tail.
*/
pTailRec = *spTail;
pTailRec->spNext = pTmpLRec;
*spTail = pTmpLRec;
pTmpLRec->spNext = NULL;
}
} else
{
/* Add to tail of list by making tail point to new item, then
* new item becomes the tail.
*/
pTailRec = *spTail;
pTailRec->spNext = pTmpLRec;
*spTail = pTmpLRec;
pTmpLRec->spNext = NULL;
}
}
/* Return success or fail...?
*/
return(R_OK);
}
/******************************************************************************
* Function: DelItem
* Description: Delete an element from a given linked list. The underlying
* carried data is not freed, it is assumed that the caller
* will free that, as it was the caller that allocated it.
* Returns: R_OK - Item deleted successfully.
* R_FAIL - Failure in deletion, see Errno.
* E_BADHEAD - Head pointer is bad.
* E_BADTAIL - Tail pointer is bad.
* E_MEMFREE - Couldnt free memory to sys pool.
* E_NOKEY - No search key provided.
******************************************************************************/
int DelItem( LINKLIST **spHead, /* IO: Pointer to head of list */
LINKLIST **spTail, /* IO: Pointer to tail of list */
void *spKey, /* I: Addr of item, direct update */
UINT *nKey, /* I: Integer based search key */
ULNG *lKey, /* I: Long based search key */
UCHAR *szKey ) /* I: String based search key */
{
/* Local variables.
*/
int nResult = R_FAIL;
LINKLIST *spCur;
LINKLIST *spPrev;
/* Check input values. Is head valid?
*/
if(*spHead == NULL)
{
Errno = E_BADHEAD;
return(nResult);
}
/* Is tail valid?
*/
if(*spTail == NULL)
{
Errno = E_BADTAIL;
return(nResult);
}
/* Have search keys been provided.
*/
if(spKey == NULL && nKey == NULL && lKey == NULL && szKey == NULL)
{
Errno = E_NOKEY;
return(nResult);
}
/* Locate item by scanning the list. This may get updated in years to
* come to be a hash/btree lookup/delete.... dream on!!
*/
for(spPrev=NULL, spCur= *spHead; spCur != NULL;
spPrev=spCur, spCur=spCur->spNext)
{
/* See if we have a match!
*/
if( (spKey != NULL && spCur->spData != spKey) ||
(nKey != NULL && *nKey != spCur->nKey) ||
(lKey != NULL && *lKey != spCur->lKey) ||
(szKey != NULL && spCur->szKey != NULL &&
strcmp(szKey, spCur->szKey) != 0))
continue;
/* OK, found the one.
*/
break;
}
/* If records not null, then we have located the required record, remove
* it.
*/
if(spCur != NULL)
{
/* Item at beginning of list?
*/
if(spPrev == NULL)
{
/* Point head at next in list. If next is NULL, then list empty,
* so update Tail.
*/
if((*spHead = spCur->spNext) == NULL)
*spTail = NULL;
} else
{
if((spPrev->spNext = spCur->spNext) == NULL)
*spTail = spPrev;
}
/* Free memory used by removed element.
*/
if(spCur->szKey != NULL)
free(spCur->szKey);
free(spCur);
nResult = R_OK;
}
/* Return success or fail...?
*/
return(nResult);
}
/******************************************************************************
* Function: FindItem
* Description: Find an element in a given linked list.
* Returns: NOTNULL - Item found, address returned.
* NULL - Item not found, see Errno.
* E_BADHEAD - Head pointer is bad.
* E_BADTAIL - Tail pointer is bad.
* E_NOKEY - No search key provided.
******************************************************************************/
void *FindItem( LINKLIST *spHead, /* I: Pointer to head of list */
UINT *nKey, /* I: Integer based search key */
ULNG *lKey, /* I: Long based search key */
UCHAR *szKey ) /* I: String based search key */
{
/* Local variables.
*/
UCHAR *spResult = NULL;
LINKLIST *spCur;
/* Quite simple at the momoko, just loop through the list and see if an
* entry exists. Eventually, (he hopes) this could be enhanced to inc
* btree/hash lookup.
*/
for(spCur=spHead; spCur != NULL; spCur=spCur->spNext)
{
if(nKey != NULL && spCur->nKey == *nKey)
break;
if(lKey != NULL && spCur->lKey == *lKey)
break;
if(szKey != NULL && strcmp(szKey, spCur->szKey) == 0)
break;
}
/* Found a record?
*/
if( spCur != NULL )
spResult = spCur->spData;
/* Return success or fail...?
*/
return(spResult);
}
/******************************************************************************
* Function: StartItem
* Description: Setup pointers for a complete list scan. Return the top most
* list 'data item' to caller.
* Returns: NOTNULL - Item found, address returned.
* NULL - Item not found, see Errno.
* E_BADHEAD - Head pointer is bad.
******************************************************************************/
void *StartItem( LINKLIST *spHead, /* I: Pointer to head of list */
LINKLIST **spNext ) /* O: Pointer to next item in list */
{
/* Local variables.
*/
void *spResult = NULL;
/* Does the list exist yet?
*/
if( spHead == NULL )
{
Errno = E_BADHEAD;
} else
{
/* Setup pointer to next in link and return pointer to data to caller.
*/
*spNext = (LINKLIST *)spHead->spNext;
spResult = (UCHAR *)spHead->spData;
}
/* Return success or fail...?
*/
return(spResult);
}
/******************************************************************************
* Function: NextItem
* Description: Move to next item in a given list. Return the current 'data
* item' to caller.
* Returns: NOTNULL - Item found, address returned.
* NULL - Item not found, see Errno.
* E_BADPARM - Bad parameter passed to function.
******************************************************************************/
void *NextItem( LINKLIST **spNext ) /* O: Pointer to next item in list */
{
/* Local variables.
*/
void *spResult = NULL;
LINKLIST *spLink = *spNext;
/* Check parameter, maybe at end of list already.
*/
if( *spNext == NULL )
{
Errno = E_BADPARM;
} else
{
/* Extract pointer to data and move down link.
*/
spResult = (UCHAR *)spLink->spData;
*spNext = (LINKLIST *)spLink->spNext;
}
/* Return success or fail...?
*/
return(spResult);
}
/******************************************************************************
* Function: MergeLists
* Description: Merge two list together. The Source list is merged into the
* target list. Lists are re-sorted if required.
* Returns: R_OK - Item added successfully.
* R_FAIL - Failure in addition, see Errno.
* E_NOMEM - Memory exhaustion.
* E_BADHEAD - Head pointer is bad.
* E_BADTAIL - Tail pointer is bad.
* E_NOKEY - No search key provided.
******************************************************************************/
int MergeLists( LINKLIST **spDstHead, /* IO: Pointer to head of dest list */
LINKLIST **spDstTail, /* IO: Pointer to tail of dest list */
LINKLIST *spSrcHead, /* I: Pointer to head of src list */
LINKLIST *spSrcTail, /* I: Pointer to tail of src list */
int nMode ) /* I: Mode of list merging */
{
/* Local variables.
*/
LINKLIST *spNext;
LINKLIST *spSrc;
LINKLIST *pTailRec;
LINKLIST *spCur;
LINKLIST *spPrev;
/* Go through each record in the source list and add onto the destination
* list.
*/
if((spSrc = spSrcHead) != NULL)
spNext = spSrcHead->spNext;
else
spNext = NULL;
/* Loop through the entire source list and merge into the destination list.
*/
while(spSrc != NULL)
{
/* Right, we have a record, so where do we add it.
*/
if(*spDstHead == NULL)
{
/* Both pointers look at new element.
*/
*spDstHead = spSrc;
*spDstTail = spSrc;
spSrc->spNext = NULL;
} else
{
/* If were sorting the list as we go along, then we need to scan it
* and find the required location.
*/
if(nMode != SORT_NONE)
{
for(spPrev=NULL, spCur= *spDstHead; spCur != NULL;
spPrev=spCur, spCur=spCur->spNext)
{
if(nMode == SORT_INT_UP && spSrc->nKey < spCur->nKey)
break;
else
if(nMode == SORT_INT_DOWN && spSrc->nKey > spCur->nKey)
break;
else
if(nMode == SORT_LONG_UP && spSrc->lKey < spCur->lKey)
break;
else
if(nMode == SORT_LONG_DOWN && spSrc->lKey > spCur->lKey)
break;
}
/* Insert at very beginning of list?
*/
if(spPrev == NULL && spCur != NULL)
{
spSrc->spNext = *spDstHead;
*spDstHead = spSrc;
} else
/* Insert in the middle of the list?
*/
if(spPrev != NULL && spCur != NULL)
{
spSrc->spNext = spPrev->spNext;
spPrev->spNext = spSrc;
} else
/* Insert at the end of the list!
*/
{
/* Add to tail of list by making tail point to new item,
* then new item becomes the tail.
*/
pTailRec = *spDstTail;
pTailRec->spNext = spSrc;
*spDstTail = spSrc;
spSrc->spNext = NULL;
}
} else
{
/* Add to tail of list by making tail point to new item, then
* new item becomes the tail.
*/
pTailRec = *spDstTail;
pTailRec->spNext = spSrc;
*spDstTail = spSrc;
spSrc->spNext = NULL;
}
}
/* Move to next element.
*/
if((spSrc = spNext) != NULL)
spNext = spSrc->spNext;
}
/* Return success or fail...?
*/
return(R_OK);
}
/******************************************************************************
* Function: DelList
* Description: Delete an entire list and free memory used by the list and the
* underlying carried data.
* Returns: R_OK - List deleted successfully.
* R_FAIL - Failed to delete list, see Errno.
* E_BADHEAD - Head pointer is bad.
* E_BADTAIL - Tail pointer is bad.
******************************************************************************/
int DelList( LINKLIST **spHead, /* IO: Pointer to head of list */
LINKLIST **spTail ) /* IO: Pointer to tail of list */
{
/* Local variables.
*/
LINKLIST *spTmp;
LINKLIST *spNext;
/* Check input values. Is head valid?
*/
if(*spHead == NULL)
{
Errno = E_BADHEAD;
return(R_FAIL);
}
/* Is tail valid?
*/
if(*spTail == NULL)
{
Errno = E_BADTAIL;
return(R_FAIL);
}
/* Quite simple, breeze through list, deleting everything.
*/
for(spTmp= *spHead; spTmp != NULL; spTmp=spNext)
{
/* Free any memory allocated for text search buffer.
*/
if(spTmp->szKey != NULL)
free(spTmp->szKey);
/* Free any memory allocated for data record.
*/
if(spTmp->spData != NULL)
free(spTmp->spData);
/* Get next element then release element memory.
*/
spNext=spTmp->spNext;
free(spTmp);
}
/* Tidy up callers pointers.
*/
*spHead = *spTail = NULL;
/* Got here, perhaps everything worked...!
*/
return(R_OK);
}
/******************************************************************************
* Function: SizeList
* Description: Find the total number of elements in a given list by scanning
* it.
* Returns: R_OK - List size calculated.
* R_FAIL - Failed to calculate list size, see Errno.
* E_BADHEAD - Head pointer is bad.
******************************************************************************/
int SizeList( LINKLIST *spHead, /* I: Pointer to head of list */
UINT *nCnt ) /* O: Count of elements in list */
{
/* Local variables.
*/
LINKLIST *spTmp;
/* Check input values. Is head valid?
*/
if(spHead == NULL)
{
Errno = E_BADHEAD;
return(R_FAIL);
}
/* Quite simple, breeze through list, counting.
*/
for(*nCnt=0,spTmp=spHead; spTmp != NULL; *nCnt += 1, spTmp=spTmp->spNext);
/* Got here, perhaps everything worked...!
*/
return(R_OK);
}