Ingres CL LL
From Ingres Community Wiki
|
Ingres Compatability Library |
Compatibility Library Specification - LL
Abstract
This is the specification of the Linked List (LL) facility provided by the compatibility library to maintain a circular, doubly linked list of objects.
Revision: 1.0, 4-June-2008
Document History
- Revision 1.0, 4-June-2008
- original
Specification
Introduction
The Linked List (LL) facility maintains a circular, doubly linked list of objects. It is used in conjunction with an object structure to create, maintain, and search a linked list of those objects.
The linked list structure (LNKDEF) must be included in the structure definition of the object. The LNKDEF structure contains forward and backward pointers as well as a pointer to the beginning of the object.
Note that this is naive code, i.e., it always trusts its caller. Many of the simple routines are in macro form.
LL Functions
The following functions are provided for the Linked List facility.
Click on the name of a function to see detailed information.
| Name | Description |
|---|---|
| LL_Init | Initialize a linked list entry |
| LL_Unlink | Unlink a list entry |
| LL_LinkBefore | Insert an entry before this one |
| LL_LinkAfter | Insert an entry after this one |
| LL_GetNext | Point to the next entry in the list |
| LL_GetPrev | Point to the previous entry in the list |
| LL_GetObject | Point to the object represented by this entry |
| LL_GetNextObject | Point to the object represented by the next entry |
| LL_GetPrevObject | Point to the object represented by the previous entry |
| LL_Last | Is this the last entry in the list? |
| LL_Apply | Apply a function to each object in the list |
| LL_Count | Count the number of objects in the list |
| LL_GetNth | Get a pointer to the nth entry in the list |
| LL_GetNthObject | Get the address of the nth object in the list |
| LL_Find | Look for a particular object in the list |
| LL_FindBin | Find an object in the list that matches a binary key |
| LL_FindStr | Find an object in the list that matches a C string key |
Library
GL
Header File <ll.h>
The header file <ll.h> must be included before using any of the functions provided.
The LNKDEF structure must be included in the structure definition of the object to be placed on a doubly linked list. It contains forward and backward pointers as well as a pointer to the beginning of the object itself.
The LNKDEF structure can optionally be used to define the head of the linked list, and in this case the object pointer would be zero. This allows scanning routines to use a null object pointer as the end of list indicator. Otherwise, the scanning routines will have to save a pointer to the first element and use that pointer to detect when the list has been completely scanned.
_LNKDEF
struct _LNKDEF
{
struct _LNKDEF *lnknxt; /* ptr to next list item */
struct _LNKDEF *lnkprv; /* ptr to previous list itme */
void *lnkobj; /* ptr to list item's object */
};
LNKDEF
The LNKDEF structure type must be included within an object's structure definition for that object to be used in the Linked List facility.
typedef struct _LNKDEF LNKDEF;
LL_ApplyFun
This typedef defines a type of function that can be applied to every object in a Linked List. To set up, define your own function as an instance of type LL_ApplyFun. To execute, call the LL_Apply function; for each object in the Linked List, your function will be called with two parameter values:
- a pointer to the object instance
- the value of the user_control_blk.
typedef void LL_ApplyFun (void *object, void *user_control_blk);
Executable Interface
The following macros and functions are provided.
LL_Init - Initialize a linked list entry
Initialize a linked list entry:
- Set the next and previous pointers to point to this entry
- Set the object pointer to point to the object provided
Inputs:
| lnk | the item to be initialized |
| obj | pointer to the object |
Outputs:
| none |
Returns:
| none |
Definition:
# define LL_Init(lnk, obj) \
{ \
((LNKDEF *)(lnk))->lnknxt = ((LNKDEF*)(lnk))->lnkprv = (LNKDEF*)(lnk); \
((LNKDEF *)(lnk))->lnkobj = (void*)(obj); \
}
LL_Unlink - Unlink a list entry
Remove an entry from the linked list.
Inputs:
| lnk | the item to be removed from the linked list |
Outputs:
| none |
Returns:
| none |
Side Effects
| The removed item's next and previous pointers point to the removed item. |
Definition:
# define LL_Unlink(lnk) \
{ \
LNKDEF *nextlnk; \
LNKDEF *prevlnk; \
nextlnk = ((LNKDEF*)(lnk))->lnknxt; \
prevlnk = ((LNKDEF*)(lnk))->lnkprv; \
prevlnk->lnknxt = nextlnk; \
nextlnk->lnkprv = prevlnk; \
((LNKDEF*)(lnk))->lnknxt = ((LNKDEF*)(lnk))->lnkprv = ((LNKDEF*)(lnk));\
}
LL_LinkBefore - Insert an entry before this one
Insert an entry before this one and link it into the linked list.
Inputs:
| listlnk | the existing entry in the linked list |
| lnk | the item to be inserted into the linked list |
Outputs:
| none |
Returns:
| none |
Definition:
# define LL_LinkBefore(listlnk, lnk) \
{ \
((LNKDEF*)(lnk))->lnknxt = ((LNKDEF*)(listlnk)); \
((LNKDEF*)(lnk))->lnkprv = ((LNKDEF*)(listlnk))->lnkprv; \
((LNKDEF*)(listlnk))->lnkprv = ((LNKDEF*)(lnk)); \
((LNKDEF*)(lnk))->lnkprv->lnknxt = ((LNKDEF*)(lnk)); \
}
LL_LinkAfter - Insert an entry after this one
Insert an entry after this one and link it into the linked list.
Inputs:
| listlnk | the existing entry in the linked list |
| lnk | the item to be inserted into the linked list |
Outputs:
| none |
Returns:
| none |
Definition:
# define LL_LinkAfter(listlnk, lnk) \
{ \
((LNKDEF*)(lnk))->lnknxt = ((LNKDEF*)(listlnk))->lnknxt; \
((LNKDEF*)(lnk))->lnkprv = ((LNKDEF*)(listlnk)); \
((LNKDEF*)(listlnk))->lnknxt = ((LNKDEF*)(lnk)); \
((LNKDEF*)(lnk))->lnknxt->lnkprv = ((LNKDEF*)(lnk)); \
}
LL_GetNext - Point to the next entry in the list
Point to the next entry in the list.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| pointer to the next entry |
Definition:
# define LL_GetNext(lnk) ((lnk)->lnknxt)
LL_GetPrev - Point to the previous entry in the list
Point to the previous entry in the list.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| pointer to the previous entry |
Definition:
# define LL_GetPrev(lnk) ((lnk)->lnkprv)
LL_GetObject - Point to the object represented by this entry
Point to the object represented by this entry.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| pointer to the object represented by this entry |
Definition:
# define LL_GetObject(lnk) ((lnk)->lnkobj)
LL_GetNextObject - Point to the object represented by the next entry
Point to the object represented by the next entry.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| pointer to the object |
Definition:
# define LL_GetNextObject(lnk) ((lnk)->lnknxt->lnkobj)
LL_GetPrevObject - Point to the object represented by the previous entry
Point to the object represented by the previous entry.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| pointer to the object |
Definition:
# define LL_GetPrevObject(lnk) ((lnk)->lnkprv->lnkobj)
LL_Last - Is this the last entry?
If this is the last entry, return TRUE; otherwise FALSE. The last entry is flagged by having its next pointer pointing to itself.
Inputs:
| lnk | pointer to an entry in the linked list |
Outputs:
| none |
Returns:
| TRUE | if this is the last entry in the linked list |
| FALSE | otherwise |
Definition:
# define LL_Last(lnk) (((lnk)->lnknxt == lnk)? TRUE: FALSE)
LL_Apply - Apply a function to each object in the list
Apply a user-defined function to every object represented by a list entry. You define the function by using LL_ApplyFun.
Inputs:
| lnk | the entry to which the function is to be applied |
| apply_fun | the function that is applied to each object |
| user_control_block | an optional control block pointer |
| This parameter is passed to the user function for each object in the linked list. |
Outputs:
| none |
Returns:
| OK | if succeeded |
| error status | if other reportable error |
Definition:
void LL_Apply(LNKDEF *lnk, LL_ApplyFun apply_fun, void *user_control_blk);
See LL_ApplyFun for the type definition of the function apply_fun.
LL_Count - Count the number of objects in the list
Count the number of objects represented by this list.
Note that this function does not count entries with NULL object pointers.
Inputs:
| lnk | the head of the list |
Outputs:
| none |
Returns:
| the number of objects in the list |
Definition:
i4 LL_Count(LNKDEF *lnk);
LL_GetNth - Get the Nth entry
Return the address of the nth entry in the list.
Note that this function does not count entries with NULL object pointers.
Inputs:
| lnk | the head of the list |
| n | number of the entry to get |
Outputs:
| none |
Returns:
| pointer to the Nth entry |
Definition:
LNKDEF *LL_GetNth(LNKDEF *lnk, i4 n);
LL_GetNthObject - Get the address of the Nth object in the list
Return the address of the nth object in the list.
Note that this function does not count entries with NULL object pointers.
Inputs:
| lnk | the head of the list |
| n | number of the object to get |
Outputs:
| none |
Returns:
| pointer to the object |
Definition:
void *LL_GetNthObject(LNKDEF *lnk, i4 n);
LL_Find - Look for a particular object in the list
Apply a compare function to every object represented by a list item. Return the object if the compare returns TRUE. If the compare routine returns FALSE, keep progressing in the list. If there is no match, return NULL.
Inputs:
| lnk | the item at which the function is to be applied |
| Since the linked list is circular, this does not need to be the beginning of the list. | |
| key | pointer to the key to search for |
Outputs:
| none |
Returns:
| pointer to the item | if found |
| NULL | otherwise |
Definition:
LNKDEF *LL_Find(LNKDEF *lnk, void *key);
LL_FindBin - Find an object in the list that matches a binary key
Apply a binary compare function to every object represented by a list item. Return the object if the compare returns TRUE. If the compare routine returns FALSE, keep progressing in the list. If there is no match, return NULL.
Inputs:
| lnk | the item at which the function is to be applied |
| Since the linked list is circular, this does not need to be the beginning of the list. | |
| keyoffset | the offset of the key within the object |
| keylen | the length of the key |
| key | pointer to the key to search for |
Outputs:
| none |
Returns:
| pointer to the item | if found |
| NULL | otherwise |
Definition:
LNKDEF *LL_FindBin(LNKDEF *lnk, i4 keyoffset, i4 keylen, void *key);
LL_FindStr - Find an object in the list that matches a C string key
Apply a string compare function to every object represented by a list item. Return the object if the compare returns TRUE. If the compare routine returns FALSE, keep progressing in the list. If there is no match, return NULL.
Inputs:
| lnk | the item at which the function is to be applied |
| Since the linked list is circular, this does not need to be the beginning of the list. | |
| keyoffset | the offset of the key within the object |
| key | pointer to the key to search for |
Outputs:
| none |
Returns:
| pointer to the item | if found |
| NULL | otherwise |
Definition:
LNKDEF *LL_FindStr(LNKDEF *lnk, i4 keyoffset, void *key);
|
Ingres Compatability Library |
