|
Linked lists are fundamental tools used by any application that deals with variable types and data. Garyl discusses linked-list theory and presents a generic linked-list toolkit written in C.
August 01, 1993
URL:http://www.drdobbs.com/cpp/strategies-for-better-linked-lists/184409050
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Copyright © 1993, Dr. Dobb's Journal
Garyl is the author of programming tools, connectivity products, and related subsystems. He can be reached via CompuServe at 76507,1503 or through DDJ.
Linked lists are fundamental tools used by any application that deals with variable types and data. The problem with linked lists, however, is that when more than one is being used in an application, duplicate code is required to handle each list. This is because the type of data being managed by each list is different, and there is no simple way to educate the logic about the kind of data being managed at any particular moment. Linked lists also tend to diffuse when small pieces of data are being stored.
This article discusses linked-list theory and presents a generic linked-list toolkit written in C that will reduce, if not eliminate, management problems. (The entire toolkit is available electronically; see "Availability" on page 5.) This discussion focuses on doubly linked lists, but with a little effort the algorithms can be used for singly linked lists. This package was developed using Microsoft C 6.0; the Microsoft extensions were disabled for ANSI C conformance.
Figure 1 shows a traditional linked list with three links, called "atoms." An atom has three parts: the previous pointer, which contains the address of the predecessor or Nil if this is the first atom; the next pointer, which contains the address of the successor or Nil if this is the final atom; and the atom data itself. The previous and next pointers form the bindery of the atom.
The atom's data area can be of any type and size, and is usually composed of multiple fields. An atom is easily defined in C using a structure definition like that in Example 1.
Head and tail pointers define the ends of a list. The head pointer is an anchor whose value records the address of the first atom in the list, while the tail pointer records the address of the last atom in the list. Even though the tail pointer is not required (the terminating link can be determined by traversing the list and looking for an atom whose next pointer is Nil), it is worth the extra code and processing time to implement a tail pointer. With doubly linked lists, the tail pointer allows you to start at the end of the list and traverse upward. Head and tail pointers both must be declared as pointers to their specific atom types, as in FOOATOM*pHead.
The algorithm for creating and adding an atom to the end of a linked list is shown in Example 2. In this example, h and t are the head and tail pointers, a is a pointer to an atom, and s is the atom size. Note that the data portion of the atom is never referenced. Using this basic template, we can create a routine to process any type of atom.
To implement more generic code, start by defining a generic bindery type, then include that type as the first member of any atom definition; see Example 3(a). When processing the list, the atom-specific pointer is cast to a pointer of type BIND and subsequently passed to the generic logic shown in Example 3(b).
By placing the bindery as the first member of any atom structure, we can fool the generic logic into handling the head and tail as pointers to simple BIND structures rather than complex FOO-
ATOM structures. This method works well in most situations but is rather tedious. As an alternative, define a standard structure to hold head and tail pointers, as in Example 4. This way, only the address of the ENDS structure--not the two pointers--can be passed.
While this method is easier, it requires you to cast the head and tail pointers to a pointer of the appropriate type whenever needed. We can avoid this inconvenience by declaring pointers as type void, indicating they have no assumed type. Pointers of type void can be assigned to a pointer of a specific type without casting. Notice in Example 5 that the value of void pointer pHead is assigned directly to the pFooAtom pointer (a pointer to a specific data type): Believe me when I say that even lint won't complain about these types of assignments.
Linked-list algorithms make heavy use of dynamic memory functions like malloc() and free(). A single call to malloc() returns a pointer to a memory block n bytes long. However, for free() to work properly, the block must contain information describing the nature of the block. This additional overhead is referred to as a "memory control block" (MCB). If k is the size of the MCB, then the actual amount of core being occupied by a block of n bytes is n+k bytes. The actual size of the MCB is system dependent; in some implementations it is as small as one word, while in others it is as large as a paragraph (eight words)!
MCB size is important because it affects the list density, which is calculated by contrasting the size of the data being stored (the bang) with the amount of memory required to store it (the buck). This relationship can be expressed as Density=nd/(k+n(b+d)), where n is the number of atoms stored in a malloc()ed block, d the size of the stored data, k the MCB size, and b the bindery size. This is the generic formula. Since n is almost always 1, the accepted form is d/(k+b+d). As the density approaches 1, the list becomes more efficient. For example, a list of integers kept in an array has a density of 1 because there is no overhead: The amount of core required to maintain the list is exactly that of the data being stored. When the value of n is 1, the only means of achieving higher densities is to increase the size of d by storing larger pieces of data. This makes linked lists impractical for storing small pieces of data (integers, for instance) because the buck drastically outweighs the bang.
Taking all of this into account, a generic linked-list toolkit should:
For requirement #2, the linked-list manager handles the allocation and management of binderies. In effect, you request that an instance of the atom data be allocated. The linked-list manager then tacks on the size of the bindery, requests a block of that size from malloc(), and retains that pointer. The pointer returned to the caller is to the atom data only; see Figure 2. This lets the user employ the linked list as a subsystem, requesting next and previous pointers, adding and deleting atoms, and so forth. However, this approach does not fully satisfy requirement #3 because multiple malloc() calls are required.
Requirements #3 and #4 are best satisfied by allocating space for more than one atom at a time. By creating blocks of atoms at once, we increase the value for n, and thus the list density. However, there is a trade-off in that memory is allocated and can go unused. Therefore, you should specify the appropriate size of a block for the application. An application that will require hundreds of atoms will have a larger block size than one using only a few. Also, it is possible to store an entire list in a single block, thus achieving maximum density but requiring the user to estimate the maximum size of the list.
The linked-list control block (LLCB) and the list boundary (LLST) govern the linked list. The LLCB contains two sets of head/tail pointers, the size of the atom data, and the number of atoms to create per block. The LLST contains one set of head/tail pointers and a pointer to the LLCB; see Listing One, page 100.
There are three types of verbs in the toolkit: primitives, management, and insert/move/swap. The primitives, defined in llprim.c (Listing Two, page 100), are ll_open(), ll_close(), ll_mklist(), ll_
rmlist(), ll_alloc(), and ll_free(). ll_open creates a list and ll_close destroys it. (Table 1 describes these calls.) ll_open() accepts the address of an LLCB, the size of the atom data, and the number of atoms to create per block, and returns the address of the LLCB passed to it.
Once the LLCB is set up, one or more linked lists can be created using ll_
mklist(), which associates a LLST with an LLCB. ll_mklist() accepts the address of a LLCB and LLST, returning the address of the LLST. Multiple lists, consisting of individual lists of separate atom chains, can be associated with a single LLCB. Neither ll_mklist() nor ll_open() allocate memory; they only initialize structures passed to them.
Atoms are created and destroyed using ll_alloc() and ll_free(), respectively. ll_alloc() accepts a pointer to a LLST, and returns a pointer of type void. Whenever ll_alloc() is called, the LLCB (taken from the LLST) is checked for atoms that may exist in its free chain. If available, a free atom is removed from the free chain and appended to the list managed by LLST. The address of the atom data is returned.
If free atoms are not available, an attempt is made to create a fresh block of atoms. A pointer to the atom data is returned if successful, else NULL to signal that no atoms are available nor could be created. A block is organized as shown in Figure 2. The atoms in a block are logically created, and because they are all unused, are "sewn" together by linking their binderies. The first atom in the block is added to the end of the free list in the LLCB. Figure 3 shows the results of a few ll_alloc() and ll_free() calls.
The ll_free() call accepts as arguments the address of an atom and the address of the LLST to which the atom belongs. The atom is removed from the current list and added to the end of the free chain maintained in the LLCB. Note that a usage count is maintained within the block bindery information. When an atom is allocated from the block, the usage count is increased. When an atom is returned to the free chain, the usage count is decreased. When this usage count reaches 0, the block itself is removed.
The file llbase.c (available electronically) defines the management verbs employed by the primitives to manage a linked list properly. The management verbs should never be referenced directly by the application program. The management verbs are ll_appatom (append atom to end of list), ll_mkblock (create atom block), ll_unbatom (unbind atom from list), ll_inblock (find block that contains an atom), ll_frstatom (return the first atom in a list), ll_lastatom (return the last atom in a list), ll_getbind (get the bindery of a neighbor), and ll_rmblock (remove a block of atoms).
The verbs ll_mkblock() and ll_rmblock() deserve some explanation. Using malloc(), ll_mkblock() allocates a block of memory large enough to hold the desired number of atoms (from the LLCB) and the block-control information (LLBC). This block must be carved up into many logical atoms, then added to the end of the free atom chain for the LLCB. This is done with simple pointer arithmetic. Start by calculating the size of an atom block. The atom block contains three basic types of objects: the block header, the atom bindery (one per atom), and the atom data itself (again, one per atom). Figure 2 illustrates the internal arrangement of an atom block. The formulas for calculating the overall size of a block of atoms are shown in Example 6(a).
The SizeofAtomData and AtomCount (which were specified when the LLCB was created) are taken from the LLCB. Given that a call to malloc() will return a pointer to a block of memory of exactly BlockSize bytes, our task is to carve the region into usable atoms. The first step is to calculate the address of the first atom bindery. This will be the first byte past the LLBC, as in Example 6(b), which should give us the address of the first bindery, right? Wrong.
Now is a good time to point out a dangerous thing about pointer arithmetic: The compiler is very smart, and to make things easier for the programmer, adding an offset to a pointer is the same as taking a subscript to the pointer, or pBlock+sizeof(LLBC) is equivalent to pBlock[sizeof(LLBC)]. Because the elements of an array have an inherent size associated with them, the actual calculation performed by the compiler is: pBind=(PLLBIND)(pBlock+(sizeof
(LLBC)*sizeof(LLBC))), which is not what we wanted. To get a better feel for what is happening here, consider an array of integers. The size of an integer on 80x86 computers is two bytes. Let's assume that the base address of the array (the address of the first integer in the array) is 0x8000, and let's also assume that we want the address of the fourth integer in the array. In C, we have to do as shown in Example 6(c).
The inherent size of an integer is two bytes, so the compiler multiplies the size of the array item by the index to get the relative offset, and then adds that offset to the base address to achieve the absolute address, or, from our example, 3*2+0x80006+0x80000x8006.
If we obtained the address of the fourth element with the statement int*j=a+3, nothing would be different. The compiler knows that a is a pointer to an integer, and the index (3) would be modified by the size of the item being pointed to. This fact about pointer arithmetic gives us pause before proceeding.
How do we calculate the true address of the first bindery? Again we use the power of type casting. By changing the compiler's assumption about the type of item being pointed to, we can avoid the nasty problem of inherent sizes. By casting the pointer pBlock into a character pointer (char*), the compiler believes that pBlock points to a character, which has an inherent size of 1. Therefore,the calculation, pBind=(PLLBIND)((char*)pBlock+sizeof(LLBC)); will indeed yield the address of the first bindery. Further, the address of the first atom data is sizeof(LLBIND)--bytes from pBind. However, we must again cast pBind into a character pointer so that wearen'tsurprised: void*pAtom=(void*)
((char*)pBind+sizeof(LLBIND));.
At this point, however, we are not interested in the atom data area. Our task is to ascertain the addresses of each of the binderies, link them to each other, and then append them to the end of the free atom chain in the LLCB. Because we are creating a set of new atoms, it follows that they are all unused and will end up in the free chain anyway. By doing a little magic here, we avoid calling ll_appatom() for each of the logical atoms as we locate them, which would use up many more cycles than it is worth.
Now that we have discovered the address of the first bindery, and because we know that this is the first of many atoms to be created, we can go ahead and append this bindery to the end of the free list with a call to ll_fappend(). This done, we "sew" the remaining atoms together with the logic in Example 6(d). We do this once for each atom. When we are done, pBind contains the address of the last bindery in the block. Because we know this to be the final bindery of all free binderies, we will set the free-list tail to pBind after setting pBind->pNext to NULL.
The destructor function, ll_rmblock(), has a similar task--only in reverse. The atoms contained within a block must be removed from the free chain before the block is destroyed--or else, disaster! The problem is that the atoms contained within the block will more than likely not be in sequential order, as they were when they were created. They must, therefore, be removed one at a time using the ll_funbind (unbind atom from free chain) call. The problem then becomes how to identify which atoms in the free chain belong to the block being destroyed so they can be removed in a graceful manner.
One method is to traverse the free chain, using the ll_inblock() function to determine if an atom is a member of the doomed block, and if so, remove it. With the potential of a rather lengthy free chain, this approach is undesirable.
But remember that we would have all of the atoms readily available if only we could calculate their addresses. We did it once when we created them, and we do it again. We calculate the address of the first bindery, then call ll_funbind() with that address. Next we calculate the address of the next bindery, and so on until all of the atoms have been removed from the free chain. Finally, we remove the block from the block chain itself, and free() the block.
The first step in using the linked-list toolkit is to declare the LLCB and the LLST variables and a structure to hold the atom data; see Example 7(a).
The next step is to initialize the LLCB using ll_open(), passing the address of the LLCB, the size of the atom data, and the number of atoms to create per block, as in Example 7(b). Once the LLCB is initialized, we can attach an LLST structure to it using ll_mklist(), as in Example 7(c).
Now the linked list is ready to use. To get an atom from the list, use ll_
alloc(); Example 7(d). To traverse the list, use ll_first() and ll_next(), as in Example 7(e). To remove a certain atom from the list, use ll_free() and specify the atom to remove; see Example 7(f). To remove all of the atoms from the list, destroy the list using ll_rmlist(); see Example 7(g). Finally, to destroy all lists associated with a particular LLCB, use ll_close(); see Example 7(h).
The test program, lltest.c (available electronically), exercises every function in the toolkit and provides an excellent template for its use.
The end analysis indicates that the worst case of employing a blocking method is as good as a nonblocking one, but is generally better with smaller atom sizes. However, this consideration pales when compared to the benefits of using a standardized toolkit vs. customizing each linked list from scratch.
typedef struct FOO_ATOM
{
struct FOO_ATOM *pPrev; /* pointer to previous atom */
struct FOO_ATOM *pNext; /* pointer to next atom */
char szName[ 30 ]; /* foo name */
char szPhone[ 15 ]; /* foo phone number */
} FOOATOM;
if((a = malloc(s))!= NULL)
{
if(h==NULL)
h = a;
if(t!=NULL)
t->next = a;
a->prev = t;
a->next = NULL;
}
(a)
typedef struct BINDERY
{
struct BINDERY *pPrev; /* pointer to previous bindary */
struct BINDERY *pNext; /* pointer to next bindery */
} BIND;
typedef struct FOO_ATOM
{
BIND b; /* atom bindery */
char szName[ 30 ]; /* foo name */
char szPhone[ 15 ]; /* foo phone */
} FOOATOM;
(b)
void MyFunc( ... )
{
FOOATOM *pHead, *pTail, *pAtom;
pHead = pTail = NULL;
pAtom = (FOOATOM *) AddAtom((BIND **)&pHead,
(BIND **)&pTail, sizeof(FOOATOM));
[ other program statements ]
}
BIND *AddAtom(BIND **ppHead,BIND **ppTail,unsigned usDataSize)
{
BIND *pRet;
if( ( pRet = malloc( usDataSize ) ) != NULL )
{
if( *ppHead == NULL )
*ppHead = pRet;
if( *ppTail != NULL )
(*ppTail)->pNext = pRet;
pRet->pPrev = *ppTail;
pRet->pNext = NULL;
*ppTail = pRet;
}
return( pRet );
}
typedef struct LIST--ENDS
{
BIND *pHead;
BIND *pTail;
} ENDS;
FOOATOM *pFooAtom;
ENDS FooEnds;
for(pFooAtom=(FOOATOM*)FooEnds.pHead;
pFooAtom;pFooAtom=pFooAtom->pNext)
{
[other program statements]
};
LLCB *ll_open( LLCB *pList, unsigned usAtomSize, unsigned usAtomCnt );
Initializes a linked-list control structure. Must be the first call performed for a linked-list control. usAtomSize indicates the size of the atom data, and usAtomCnt indicates the number of atoms to create per block. This call does not allocate any memory; it only initializes the linked-list control structure with the values supplied.
LLST *ll_mklist( LLCB *pListCntl, LLST *pList );
Creates a linked list as part of the linked-list control addressed by pListCntl.
void *ll_alloc( LLST *pList );
Allocates a new atom in pList. Returns a pointer to atom data area if successful, or NULL if no atoms are available and none can be generated by creating new blocks.
void ll_free( LLST *pList, void *pAtom );
Releases an atom to the free list.
void ll_rmlist( LLST *pList );
Closes pList and releases all resources currently allocated by pList.
void ll_close( LLCB *pListCntl );
Closes the linked-list control. Any resources owned by any linked lists associated with the control are released to the system pool.
void *ll_first( LLST*pList );
Returns the first atom in pList, or NULL if pList is empty.
void *ll_last( LLST *pList );
Returns the last atom in pList, or NULL if pList is empty.
void *ll_next( void *pAtom );
Returns the next atom relative to pAtom or NULL if pAtom is the last atom in the list.
void *ll_prev( void *pAtom );
Returns the previous atom relative to pAtom, or NULL if pAtom is first on the list.
void ll_swap( LLST *pList, void *pSrcAtom, void *pTrgAtom );
Effectively swaps the places of pSrcAtom and pTrgAtom in pList. Both atoms are assumed to be members of pList, and are not checked. This can cause significant problems if atoms from two different lists are swapped.
void ll_mvbefore( LLST*pList, void *pSrcAtom, void *pTrgAtom );
Moves pSrcAtom before pTrgAtom in pList. Both atoms are assumed to be members of pList, and are not checked.
void ll_mvafter( LLST *pList, void *pSrcAtom, void *pTrgAtom );
Moves pSrcAtom after pTrgAtom in pList. Both atoms are assumed to be members of pList, and are not checked.
(a)
TrueAtomSize=sizeof(LLBIND)+SizeofAtomData
BlockSize =sizeof(LLBC)+(AtomCount*TrueAtomSize)
(b)
pBlock=malloc(BlockSize);
pBind =(PLLBIND)(pBlock+sizeof(LLBC));
(c)
int a[ 10 ];
int *j = &a[ 3 ];
/* get address of fourth integer */
(d)
for( ... )
{
/* calc address of next bindery */
pBind->pNext = (PLLBIND)( (char *)pBind + TrueAtomSize );
/* setup back reference */
pBind->pNext->pPrev = pBind;
/* go on to the next bindery */
pBind = pBind->pNext;
}
(a)
#include "ll.h"
LLCB ListCB;
LLST List;
typedef struct
{
char szName[ 30 ];
char szPhone[ 15 ];
} FOOATOM;
(b)
ll_open( &ListCB, sizeof
( FOOATOM ), 10 );
(c)
ll_mklist( &ListCB, &List );
(d)
FOOATOM *pAtom;
pAtom = ll_alloc( &List );
(e)
for( pAtom = ll_first( &List );
pAtom; pAtom = ll_next( pAtom ))
printf("Name:%-30s Phone:%s\n",
pAtom->szName,
pAtom->szPhone);
(f)
ll_free( &List, pAtom );
(g)
ll_rmlist( &List );
(h)
ll_close( &ListCB );
(Text begins on page 32.)
/* LINKED LIST TOOLKIT -- Copyright (C) 1990 by Garyl Lee Hester
* ll.h -- Global header file */
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif
#define _LL_NEXT 1
#define _LL_PREV 2
#define _LL_BEFORE 3
#define _LL_AFTER 4
typedef void * PATOM; /* pointer to atom */
typedef void * PGEN; /* generic pointer */
/* Link List Bind Structure (LLBIND) */
typedef struct LL_BIND
{
struct LL_BIND *pPrev; /* reference to next link */
struct LL_BIND *pNext; /* reference to prev link */
} LLBIND, *PLLBIND;
/* Link List Head & Tail Structure (LLENDS) */
typedef struct LL_ENDS
{
PGEN pHead; /* generic head pointer */
PGEN pTail; /* generic tail pointer */
} LLENDS, *PLLENDS;
/* Link List Block Control Strucure (LLBC) */
typedef struct LL_BLOKCNTL
{
struct LL_BLOKCNTL *pPrev; /* ref to prev block */
struct LL_BLOKCNTL *pNext; /* ref to next block */
unsigned usUsageCnt; /* usage count */
} LLBC, *PLLBC;
/* Link List Control Structure (LL) */
typedef struct LL_CNTL
{
LLENDS Block; /* ends of block list */
LLENDS Free; /* ends of "free" atom list */
unsigned usAtomSize; /* size of link Atom */
unsigned usAtomCnt; /* number of Atoms per block */
} LLCB, *PLLCB;
typedef struct LL_LIST
{
PLLCB pLL; /* reference to master list */
LLENDS Ends; /* ends of the current sub-list */
} LLST, *PLLST;
typedef int (*COMPFUNC)( void *, void * );
/* Macros used by ll package only: MAKEPBIND(p), converts an atom ptr to a
* bindary ptr; MAKEPATOM(p), converts a bindary ptr to an atom ptr */
#define MAKEPBIND(p) ((PLLBIND)((char *)(p) - sizeof(LLBIND)))
#define MAKEPATOM(p) ( (PATOM) ((char *)(p) + sizeof(LLBIND)))
/* User Functions supplied by Macros */
#define ll_next(p) ll_getbind(_LL_NEXT,(PATOM)(p))
#define ll_prev(p) ll_getbind(_LL_PREV,(PATOM)(p))
#define ll_mvbefore(l,s,t) ll_mvatom((s),_LL_BEFORE,(t),&(l)->Ends)
#define ll_mvafter(l,s,t) ll_mvatom((s),_LL_AFTER, (t),&(l)->Ends)
#define ll_insbefore(l,s,t) ll_insatom((s),_LL_BEFORE,(t),&(l)->Ends)
#define ll_insafter(l,s,t) ll_insatom((s),_LL_AFTER, (t),&(l)->Ends)
#define ll_first(p) ll_frstatom((p),(p)->Ends.pHead)
#define ll_last(p) ll_lastatom((p),(p)->Ends.pTail)
#define ll_swap(l,s,t) ll_swapatom((s),(t),&(l)->Ends)
#define ll_append(l,s) ll_appatom((s),&(l)->Ends)
#define ll_unbind(l,s) ll_unbatom((s),&(l)->Ends)
#define ll_memoff(p,m) (unsigned)((char *)(&(p)->m)-(char *)(p))
/* Similar Functions for Handling the Free List */
#define ll_fmvbefore(l,s,t) ll_mvatom((s),_LL_BEFORE,(t),&(l)->Free)
#define ll_fmvafter(l,s,t) ll_mvatom((s),_LL_AFTER, (t),&(l)->Free)
#define ll_finsbefore(l,s,t) ll_insatom((s),_LL_BEFORE,(t),&(l)->Free)
#define ll_finsafter(l,s,t) ll_insatom((s),_LL_AFTER, (t),&(l)->Free)
#define ll_ffirst(p) ll_frstatom((p),(p)->Free.pHead)
#define ll_flast(p) ll_lastatom((p),(p)->Free.pTail)
#define ll_fappend(l,s) ll_appatom((s),&(l)->Free)
#define ll_funbind(l,s) ll_unbatom((s),&(l)->Free)
/* Function prototypes: llprim.c - linked list primitives */
PLLCB ll_open( PLLCB, unsigned, unsigned );
void ll_close( PLLCB );
PLLST ll_mklist( PLLCB, PLLST );
void ll_rmlist( PLLST );
PATOM ll_alloc( PLLST );
void ll_free( PLLST, PATOM );
/* llbase.c - linked list management */
void ll_appatom( PATOM, PLLENDS );
void ll_mkblock( PLLCB );
void ll_rmblock( PLLCB, PLLBC );
PLLBC ll_inblock( PLLCB, PATOM );
void ll_unbatom( PATOM, PLLENDS );
PATOM ll_frstatom( PLLST, PLLBIND );
PATOM ll_lastatom( PLLST, PLLBIND );
PATOM ll_getbind( unsigned, PATOM );
/* llins.c - insert and move atom routines */
void ll_mvatom( PATOM, unsigned, PATOM, PLLENDS );
void ll_insatom( PATOM, unsigned, PATOM, PLLENDS );
/* llswap.c - atom swap routine */
void ll_swapatom( PATOM, PATOM, PLLENDS );
/* llsort.c - shell sort routine */
void ll_sort( PLLST, short, unsigned, COMPFUNC );
/* LINKED LIST TOOLKIT -- Copyright (C) 1990 by Garyl Lee Hester
* llprim.c -- Routines for Linked List Primitives */
#include <stdio.h>
#include <memory.h>
#include <malloc.h>
#include "ll.h"
/* ll_open - initialize a new linked list control */
PLLCB ll_open( PLLCB pLL, unsigned usAtomSize, unsigned usAtomCnt )
{
unsigned usRet = 0;
if( pLL )
{
/* if the list is already active, destroy it */
if( pLL->Block.pHead )
ll_close( pLL );
memset( (PGEN)pLL, 0x00, sizeof( LLCB ) );
pLL->usAtomSize = usAtomSize;
pLL->usAtomCnt = usAtomCnt;
}
return( pLL );
}
/* ll_close - closes a linked list */
void ll_close( PLLCB pLL )
{
if( pLL )
{
while( pLL->Block.pHead )
ll_rmblock( pLL, (PLLBC)( pLL->Block.pHead ) );
memset( (PGEN)pLL, 0x00, sizeof( LLCB ) );
}
}
/* ll_mklist - make a new sub list */
PLLST ll_mklist( PLLCB pLL, PLLST pList )
{
if( pList && pLL )
{
pList->pLL = pLL;
pList->Ends.pHead = NULL;
pList->Ends.pTail = NULL;
}
return( pList );
}
/* ll_rmlist - destroys a sub list */
void ll_rmlist( PLLST pList )
{
if( pList )
{
while( pList->Ends.pHead )
ll_free( pList, MAKEPATOM( pList->Ends.pHead ) );
}
}
/* ll_alloc - return ptr to new atom, else NULL */
PATOM ll_alloc( PLLST pList )
{
PLLBIND pRet = NULL;
PLLBC pBlock;
PLLCB pLL;
if( pList )
{
pLL = pList->pLL;
/* if pFreeHead is NULL, then a new block needs to be created. */
if( pLL->Free.pHead == NULL )
ll_mkblock( pLL );
/* if pFreeHead is STILL NULL, then there is no more memory */
if( pLL->Free.pHead )
{
pRet = (PLLBIND)( pLL->Free.pHead );
if( ( pBlock = ll_inblock( pLL, pRet ) ) )
pBlock->usUsageCnt++;
ll_unbatom( MAKEPATOM( pRet ), &pLL->Free );
ll_appatom( MAKEPATOM( pRet ), &pList->Ends );
pRet = MAKEPATOM( pRet );
}
}
return( (PATOM) pRet );
}
/* ll_free - remove pAtom from pList and add to global free chain */
void ll_free( PLLST pList, PATOM pAtom )
{
PLLBIND pBind;
PLLBC pBlock;
PLLCB pLL;
if( pList && pAtom )
{
pLL = pList->pLL;
pBind = MAKEPBIND( pAtom );
ll_unbind( pList, pAtom );
ll_appatom( pAtom, &pLL->Free );
if( ( pBlock = ll_inblock( pLL, pAtom ) ) )
if( !( --pBlock->usUsageCnt ) )
ll_rmblock( pLL, pBlock );
}
}
End Listings
Copyright © 1993, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.