Objects are linked together using bpo_Node_t structures and are collected together by linking to a bpo_List_t structure. These nodes and lists can each be parts of larger structures or can exist seperately from the structures they refer to.
The two structures used have typedefs available for ease of use.
typedef struct bpo_Node bpo_Node_t;
typedef struct bpo_List bpo_List_t;
Because there is a issue with sychronisation within shared memory the bpo_List_t structure contains a number of elements to ensure the list remains consistent. The first of these is a bpo_pid_lock structure which is used to lock the list before any modifications are performed on the list header or the list itself. The second item is a serial number which is updated every time a list is modified in any way.
bpo_Node_t *bpo_Init_Node( bpo_Node_t *node, char *name, void *item );
The Init_Node function is used to initialise a node. All non-NULL
parameters should be in the same segment. The item pointer can be
used with subsequent functions as a pointer to the beginning of the
meta-structure referenced (rather than having to work out its
base by subtracting the node's offset into the structure from the
node pointer returned).
bpo_List_t * bpo_Init_List( bpo_List_t *list, int flags );
The bpo_Init_List function is used to initialise a bpo_List_t structure.
The only flag that may be passed (other than 0) is LN_IGNORECASE which
causes searchs on the list to be case-insensitive.
Since the latter sub-group return pointers to meta-objects it is likely that these are the most commonly used.
bpo_Node_t *bpo_Remove_Node( bpo_Node_t *node1 );
bpo_Node_t *bpo_Remove_Head( bpo_List_t *list );
bpo_Node_t *bpo_Remove_Tail( bpo_List_t *list );
void *bpo_Remove_Head_Item( bpo_List_t *list );
void *bpo_Remove_Tail_Item( bpo_List_t *list );
These functions return either a pointer to the node added, or NULL if there was a problem (node and list not in same segment, etc).
bpo_Node_t *bpo_Add_Head( bpo_List_t *list, bpo_Node_t *node );
bpo_Node_t *bpo_Add_Tail( bpo_List_t *list, bpo_Node_t *node );
There are also to two add functions to place an item at a specific relative position within a list.
bpo_Node_t *bpo_Add_Node_After( bpo_Node_t *node1, bpo_Node_t *node2 );
bpo_Node_t *bpo_Add_Node_Before( bpo_Node_t *node1, bpo_Node_t *node2 );
These functions add node2 After or Before node1 respectively.
void *bpo_Find_Item_By_Name( bpo_List_t *list, char *name );
This function searches the list for the named item. If the list
was initialised with the LN_IGNORE_CASE flag, then the search will
be case insensitive (stricmp).
The function returns either a pointer to the first item matching
the search, or NULL. Note that the item is not removed from the
list. To remove the item use the bpo_Remove_Node function described
above.
void *bpo_Find_Next_Item_By_Name( bpo_Node_t *node, char *name );
The bpo_Find_Next_Item_By_Name function
searches the list which the provided node is on for the first item
after the provided node which matches the name parameter.
The function returns either a pointer to the located item, or NULL.
As with the bpo_Find_Item_By_Name function a found item is not removed
from the list.
bpo_Node_t *bpo_Find_Node_By_Item( bpo_List_t *list, void *item );
This function searches the provided list for a node
which points to the supplied item. It either returns
a pointer to the first node that points to the item
or NULL.
void *bpo_Find_Item_From_Node( bpo_Node_t *node );
This function returns the item pointed to by the supplied
node, or NULL if it does not point to one. This is of use for
programs that do not want to deal with the internals of a
bpo_Node_t structure.
void bpo_Walk_List( struct bpo_List_t *l_ptr,
bpo_Walk_List_t disp,
void *param );
int bpo_Walk_List2( struct bpo_List_t *l_ptr,
bpo_Walk_List2_t disp,
void *param );
where the typedefs are defined as
typedef void (*bpo_Walk_List_t) ( void *, void * );
typedef int (*bpo_Walk_List2_t) ( void *, void * );
These two functions walk the supplied list and call the supplied
function with a pointer to each item and the supplied parameter.
The bpo_Walk_List
function calls the function for every item on the list. The
bpo_Walk_List2 function calls the function for each item
on the list until the function returns a non-zero value. bpo_Walk_List2
returns either the non-zero value, or reachs the end of the list and returns 0.
The only permitted modification operation on the list whilst it is being walked is to remove the supplied node, any other operation may seriously impair system integrity. It is permissable to call the bpo_Find_Item_From_Node function.
To illustrate, consider a structure containing a node and a string.
struct demo
{
bpo_Node_t demo_node;
char name[80];
};
If a list structure has been allocated demo_list_ptr and
has number of these structures
on it, it is possible to list the contents by calling the
print_demo_list() function shown below.
static void print_demo_item( void *vp1, void *vp2 )
{
FILE *fh;
struct demo *dp;
dp = vp1;
fh = vp2;
fprintf( fh, "Item: %s\n", qp->name );
return;
}
void print_demo_list( FILE *fh )
{
bpo_Walk_List( demo_list_ptr, print_demo_item, fh );)
return;
}
int bpo_Work_List( bpo_List_t *list,
bpo_Work_List_t work,
void *param );
int bpo_Work_List2( bpo_List_t *list,
bpo_Work_List2_t work,
void *param1, void *param2 );
where the function typedefs are defined as
typedef int (*bpo_Work_List_t) ( bpo_List_t *, void * );
typedef int (*bpo_Work_List2_t) ( bpo_List_t *, void *, void * );
The reason for providing these functions instead of a pair of Lock/Unlock
functions is to ensure that the unlock does actually occur instead of
possibly being forgotten and leaving the list in a locked state which
the owning process is not aware of and blocking access for other
procceses.
There are another pair of functions which are similar the Work_List functions but which are designed to only call the work routine when the list has changed.
int bpo_May_Work_List( bpo_List_t *list,
unsigned long *last_ser_nbr,
bpo_Work_List_t work,
void *param );
int bpo_May_Work_List2( bpo_List_t *list,
unsigned long *last_ser_nbr,
bpo_Work_List2_t work,
void *param1, void *param2 );
These functions lock the list and then
check whether the serial number pointed to by the
supplied parameter is less than the serial number contained within
the list structure (which, as mentioned above gets incremented every
time there is a list modification). If it is then the work function
is called, on its return the value pointed to by last_ser_nbr
is updated to the current value held on the list.
In either case, the list is then unlocked and the function returns;
There is also a function
unsigned long bpo_Touch_List( bpo_List_t *list );
which increments the serial number of a list and returns the current
value.
typedef int (* bpo_sort_i_t)(const void *, const void *);
int bpo_sort_i( bpo_List_t *sort_list, bpo_sort_i_t compar );
int bpo_sort_n( bpo_List_t *sort_list );
The first function takes a pointer to a comparison function
which will be called with two pointers to items on the list to be
compared. The value returned from the function should be >0, 0,
of <0 just like qsort & lmsort.
The second function sorts the list by name observing the case matching rules on the list.
int bpo_Any_In_List( bpo_List_t *list );
This function returns the number of items in the list. Note that
unless the list already locked via a call to one of the work list
functions then the value may change due to some other process modifying
the list before your own process can perform its task.
int bpo_Transfer_Lists( bpo_List_t *fl_ptr, bpo_List_t *tl_ptr );
This function transfers the items from the fl_ptr list to the
tl_ptr list. It does this as a sequence of
bpo_Remove_Head & bpo_Add_Tail operations to avoid
possible deadlock conditions with the two lists.
void bpo_Free_List( bpo_List_t *list, int flags );
void bpo_Free_Node( bpo_Node_t *node, int flags );
where the flags are a bit-wise or of the following defines
BPO_REMOVE_NODES
BPO_FREE_NODES
BPO_FREE_ITEMS
BPO_FREE_NAMES
The bpo_Free_List function provides a mechanism to free up the
various elements of items on a list. It is, not surprisingly, implemented
as a call to bpo_Walk_List with bpo_Free_Node as the supplied
function.
The bpo_Free_Node function takes a pointer to a node and a set of flags. It then performs the following operations
typedef int (*p_func_t)(FILE *,const char *,...);
int bpo_List_Chk( bpo_List_t *rlp,
p_func_t p_func,
FILE *fh );
int bpo_Validate_List( bpo_List_t *rlp );
int node_list_header( p_func_t p_func, FILE *fh );
int node_list_details( void *base, bpo_Node_t *bnp,
p_func_t p_func,
FILE *fh );
The bpo_List_Chk function provides a way to validate the
integrity of the supplied list. It returns a non-zero value if the
list has problems.
The parameters are a list pointer, a pointer to a print function and a file handle. The print function should take a file pointer, a format string and a variable number of additional arguments exactly like fprintf and fprintfile. It is permissable to pass NULL for the print function to avoid any output.
The validation checks the list header contains the correct list header information, the linkage between each of the nodes on the list in both directions, and that the items claim to be on the list supplied.
The bpo_Validate_List function is simply a wrapper around bpo_List_Chk where the print function is fprintf and the file handle is stderr.
The node_list_header function provides the column headings for a node display. The node_list_details function prints out details of the node itself. These functions are used in the validate functions above to display details of the node or nodes with problems. They can also be used to show the contents of a node when a display of the details is required, as in the following example.
static void show_node( bpo_Node_t *node, FILE *fh )
{
void *base;
base = Get_SODB_Base( node );
node_list_details( base, node, fprintf, fh );
return;
}
static int show_list( bpo_List_t *list, FILE *fh )
{
if (bpo_Any_In_List( list ))
{
node_list_header( fprintf, fh );
bpo_Walk_List_N( list, (bpo_Walk_List_N_t)show_node, fh );
}else
{
fprintf( fh, "list is empty\n" );
}
return(0);
}
int
Show_This_List( bpo_List_t *list, FILE *fh )
{
return(bpo_Work_List( list, (bpo_Work_List_t)show_list, fh );
}