BRL-CAD

Support routines for doubly-linked lists. More...

#include "common.h"
#include <stdio.h>
#include "bu/list.h"
#include "bu/log.h"
#include "bu/malloc.h"
#include "bu/parallel.h"
Include dependency graph for list.c:

Go to the source code of this file.

Functions

struct bu_listbu_list_new (void)
 
struct bu_listbu_list_pop (struct bu_list *hp)
 
int bu_list_len (register const struct bu_list *hd)
 
void bu_list_reverse (register struct bu_list *hd)
 
void bu_list_free (struct bu_list *hd)
 
void bu_list_parallel_append (struct bu_list *headp, struct bu_list *itemp)
 
struct bu_listbu_list_parallel_dequeue (struct bu_list *headp)
 
void bu_ck_list (const struct bu_list *hd, const char *str)
 
void bu_ck_list_magic (const struct bu_list *hd, const char *str, const uint32_t magic)
 
struct bu_listbu_list_dequeue_next (struct bu_list *hp, struct bu_list *p)
 

Detailed Description

Support routines for doubly-linked lists.

These macros assume that all user-provided structures will have a "struct bu_list" as their first element (often named "l" [ell]). Thus, a pointer to the bu_list struct is a "pun" for the user-provided structure as well, and the pointers can be converted back and forth safely with type casts.

Furthermore, the head of the linked list could be a full instance of the user-provided structure (although the storage-conscious programmer could make the head just an bu_list structure, with careful type casting). This results in a doubly-linked circular list, with the head having the same shape as all the list members. The application is free to make use of this symmetry and store data values in the head, or the extra storage in the head can be ignored.

Where a macro expects an argument "p", it should be a pointer to a user-provided structure.

Where a macro expects an argument "hp", it should be a pointer to a "struct bu_list" located in the list head, e.g., &(head.l).

Where a macro expects an argument "old", "new", or "cur", it should be a pointer to the "struct bu_list" located either in a user-provided structure, e.g. &((p)->l), or for the case of "old" it may also be in the list head.

--- BEGIN EXAMPLE ---
// make bu_list the first element in your structure
struct my_structure {
struct bu_list l;
int my_data;
};
// your actual list
struct my_structure *my_list = NULL;
// allocate and initialize your list head
BU_GET(my_list, struct my_structure);
BU_LIST_INIT(&(my_list->l));
my_list->my_data = -1;
// add a new element to your list
struct my_structure *new_entry;
BU_GET(new_entry, struct my_structure);
new_entry->my_data = rand();
BU_LIST_PUSH(&(my_list->l), &(new_entry->l));
// iterate over your list, remove all items
struct my_structure *entry;
while (BU_LIST_WHILE(entry, my_structure, &(my_list->l))) {
bu_log("Entry value is %d\n", entry->my_data);
BU_LIST_DEQUEUE(&(entry->l));
BU_PUT(entry, struct my_structure);
}
BU_PUT(my_list, struct my_structure);
--- END EXAMPLE ---

Dequeueing the head of a list is a valid and well defined operation which should be performed with caution. Unless a pointer to some other element of the list is retained by the application, the rest of the linked list can no longer be referred to.

The "magic" field of the list header must be set to the constant BU_LIST_HEAD_MAGIC, but the "magic" field of all list members should be established by user code, to identify the type of structure that the bu_list structure is embedded in. It is permissible for one list to contain an arbitrarily mixed set of user "magic" numbers, as long as the head is properly marked.

There is a dual set of terminology used in some of the macros:

FIRST/ LAST - from the point of view of the list head NEXT / PREV - from the point of view of a list member forw / back - the actual pointer names

Definition in file list.c.

Function Documentation

int bu_list_len ( register const struct bu_list hd)

Definition at line 51 of file list.c.

References BU_LIST_FOR.

void bu_list_reverse ( register struct bu_list hd)
struct bu_list* bu_list_dequeue_next ( struct bu_list hp,
struct bu_list p 
)

Definition at line 218 of file list.c.

References BU_LIST_DEQUEUE, and BU_LIST_NEXT.