BRL-CAD

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

Collaboration diagram for Linked Lists:

Files

file  list.h
 

Data Structures

struct  bu_list
 

Macros

#define BU_LIST_NULL   ((struct bu_list *)0)
 
#define BU_LIST_MAGIC_SET(_l, _magic)   {(_l)->magic = (_magic);}
 
#define BU_LIST_MAGIC_EQUAL(_l, _magic)   ((_l)->magic == (_magic))
 
#define BU_CK_LIST_HEAD(_p)   BU_CKMAG((_p), BU_LIST_HEAD_MAGIC, "bu_list")
 
#define BU_LIST_INIT(_headp)
 
#define BU_LIST_INIT_MAGIC(_headp, _magic)
 
#define BU_LIST_INIT_ZERO   { 0, BU_LIST_NULL, BU_LIST_NULL }
 
#define BU_LIST_IS_INITIALIZED(_headp)   (((struct bu_list *)(_headp) != BU_LIST_NULL) && LIKELY((_headp)->forw != BU_LIST_NULL))
 
#define BU_LIST_INSERT(old, new)
 
#define BU_LIST_APPEND(old, new)
 
#define BU_LIST_DEQUEUE(cur)
 
#define BU_LIST_DQ(cur)
 
#define BU_LIST_DQ_T(cur, type)
 
#define BU_LIST_DEQUEUE_T(cur, type)
 
#define BU_LIST_PUSH(headp, p)    BU_LIST_APPEND(headp, (struct bu_list *)(p))
 
#define BU_LIST_POP(structure, headp, p)
 
#define BU_LIST_POP_T(headp, type)    (type *)bu_list_pop(headp)
 
#define BU_LIST_INSERT_LIST(dest_headp, src_headp)
 
#define BU_LIST_APPEND_LIST(dest_headp, src_headp)
 
#define BU_LIST_IS_EMPTY(headp)   ((headp)->forw == (headp))
 
#define BU_LIST_NON_EMPTY(headp)   ((headp)->forw != (headp))
 
#define BU_LIST_NON_EMPTY_P(p, structure, headp)    (((p)=(struct structure *)((headp)->forw)) != (struct structure *)(headp))
 
#define BU_LIST_IS_CLEAR(headp)
 
#define BU_LIST_LAST(structure, headp)    ((struct structure *)((headp)->back))
 
#define BU_LIST_BACK(structure, headp)    ((struct structure *)((headp)->back))
 
#define BU_LIST_PREV(structure, headp)    ((struct structure *)((headp)->back))
 
#define BU_LIST_FIRST(structure, headp)    ((struct structure *)((headp)->forw))
 
#define BU_LIST_FORW(structure, headp)    ((struct structure *)((headp)->forw))
 
#define BU_LIST_NEXT(structure, headp)    ((struct structure *)((headp)->forw))
 
#define BU_LIST_IS_HEAD(p, headp)    (((struct bu_list *)(p)) == (struct bu_list *)(headp))
 
#define BU_LIST_NOT_HEAD(p, headp)    (!BU_LIST_IS_HEAD(p, headp))
 
#define BU_LIST_PREV_IS_HEAD(p, headp)    (((struct bu_list *)(p))->back == (struct bu_list *)(headp))
 
#define BU_LIST_PREV_NOT_HEAD(p, headp)    (!BU_LIST_PREV_IS_HEAD(p, headp))
 
#define BU_LIST_NEXT_IS_HEAD(p, headp)    (((struct bu_list *)(p))->forw == (struct bu_list *)(headp))
 
#define BU_LIST_NEXT_NOT_HEAD(p, headp)    (!BU_LIST_NEXT_IS_HEAD(p, headp))
 
#define BU_LIST_EACH(headp, p, type)
 
#define BU_LIST_REVEACH(headp, p, type)
 
#define BU_LIST_TAIL(headp, start, p, type)
 
#define BU_LIST_FOR(p, structure, headp)
 
#define BU_LIST_FOR_BACKWARDS(p, structure, headp)
 
#define BU_LIST_FOR_CIRC(p, structure, headp)
 
#define BU_LIST_FOR2(p1, p2, structure, headp1, headp2)
 
#define BU_LIST_WHILE(p, structure, headp)    (((p)=(struct structure *)((headp)->forw)) != (struct structure *)(headp))
 
#define BU_LIST_FIRST_MAGIC(headp)   ((headp)->forw->magic)
 
#define BU_LIST_LAST_MAGIC(headp)   ((headp)->back->magic)
 
#define BU_LIST_PNEXT(structure, p)    ((struct structure *)(((struct bu_list *)(p))->forw))
 
#define BU_LIST_PLAST(structure, p)    ((struct structure *)(((struct bu_list *)(p))->back))
 
#define BU_LIST_PNEXT_PNEXT(structure, p)    ((struct structure *)(((struct bu_list *)(p))->forw->forw))
 
#define BU_LIST_PNEXT_PLAST(structure, p)    ((struct structure *)(((struct bu_list *)(p))->forw->back))
 
#define BU_LIST_PLAST_PNEXT(structure, p)    ((struct structure *)(((struct bu_list *)(p))->back->forw))
 
#define BU_LIST_PLAST_PLAST(structure, p)    ((struct structure *)(((struct bu_list *)(p))->back->back))
 
#define BU_LIST_PNEXT_CIRC(structure, p)
 
#define BU_LIST_PPREV_CIRC(structure, p)
 
#define BU_LIST_MAIN_PTR(_type, _ptr2, _name2)    ((struct _type *)(((char *)(_ptr2)) - (bu_offsetof(struct _type, _name2) + bu_offsetof(struct bu_list, magic))))
 

Typedefs

typedef struct bu_list bu_list_t
 

Functions

struct bu_listbu_list_new (void)
 
struct bu_listbu_list_pop (struct bu_list *headp)
 
int bu_list_len (const struct bu_list *headp)
 
void bu_list_reverse (struct bu_list *headp)
 
void bu_list_free (struct bu_list *headp)
 
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 *headp, const char *str)
 
void bu_ck_list_magic (const struct bu_list *headp, const char *str, const uint32_t magic)
 

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 "headp", 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 ---
#define BU_LIST_INIT(_headp)
Definition: list.h:161
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:223
#define BU_LIST_WHILE(p, structure, headp)
Definition: list.h:424
#define BU_LIST_PUSH(headp, p)
Definition: list.h:260
int bu_log(const char *,...) _BU_ATTR_PRINTF12
#define BU_PUT(_ptr, _type)
Definition: malloc.h:240
#define BU_GET(_ptr, _type)
Definition: malloc.h:226
Definition: list.h:131

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

Macro Definition Documentation

◆ BU_LIST_NULL

#define BU_LIST_NULL   ((struct bu_list *)0)

Definition at line 137 of file list.h.

◆ BU_LIST_MAGIC_SET

#define BU_LIST_MAGIC_SET (   _l,
  _magic 
)    {(_l)->magic = (_magic);}

macro for setting the magic number of a non-head list node

Definition at line 142 of file list.h.

◆ BU_LIST_MAGIC_EQUAL

#define BU_LIST_MAGIC_EQUAL (   _l,
  _magic 
)    ((_l)->magic == (_magic))

macro for testing whether a list node's magic number is equal to a specific magic number

Definition at line 148 of file list.h.

◆ BU_CK_LIST_HEAD

#define BU_CK_LIST_HEAD (   _p)    BU_CKMAG((_p), BU_LIST_HEAD_MAGIC, "bu_list")

there is no reliable way to assert the integrity of an arbitrary bu_list struct since the magic can be anything, therefore there is no BU_CK_LIST(). we can, however, check for a valid head node.

Definition at line 155 of file list.h.

◆ BU_LIST_INIT

#define BU_LIST_INIT (   _headp)
Value:
{ \
BU_ASSERT((void *)(_headp) != (void *)NULL); \
(_headp)->forw = (_headp)->back = (_headp); \
(_headp)->magic = BU_LIST_HEAD_MAGIC; /* used by circ. macros */ }
#define BU_LIST_HEAD_MAGIC
Definition: magic.h:65

initializes a bu_list struct as a circular list without allocating any memory. call BU_LIST_MAGIC_SET() to change the list type.

Definition at line 161 of file list.h.

◆ BU_LIST_INIT_MAGIC

#define BU_LIST_INIT_MAGIC (   _headp,
  _magic 
)
Value:
{ \
BU_LIST_INIT((_headp)); \
BU_LIST_MAGIC_SET((_headp), (_magic)); \
}

initializes a bu_list struct node with a particular non-head node magic number without allocating any memory.

Definition at line 170 of file list.h.

◆ BU_LIST_INIT_ZERO

#define BU_LIST_INIT_ZERO   { 0, BU_LIST_NULL, BU_LIST_NULL }

macro suitable for declaration statement zero-initialization of a bu_list struct, but not suitably for validation with BU_CK_LIST_HEAD() as the list pointers are NULL. does not allocate memory.

Definition at line 181 of file list.h.

◆ BU_LIST_IS_INITIALIZED

#define BU_LIST_IS_INITIALIZED (   _headp)    (((struct bu_list *)(_headp) != BU_LIST_NULL) && LIKELY((_headp)->forw != BU_LIST_NULL))

returns truthfully whether a bu_list has been initialized via BU_LIST_INIT(). lists initialized with BU_LIST_INIT_ZERO or zero-allocated will not return true as their forward/backward pointers reference nothing.

Definition at line 189 of file list.h.

◆ BU_LIST_INSERT

#define BU_LIST_INSERT (   old,
  new 
)
Value:
{ \
BU_ASSERT((void *)(old) != (void *)NULL); \
BU_ASSERT((void *)(new) != (void *)NULL); \
(new)->back = (old)->back; \
(old)->back = (new); \
(new)->forw = (old); \
BU_ASSERT((void *)((new)->back) != (void *)NULL); \
(new)->back->forw = (new); }

Insert "new" item in front of "old" item. Often, "old" is the head. To put the new item at the tail of the list, insert before the head, e.g. * BU_LIST_INSERT(&(head.l), &((p)->l));

Definition at line 197 of file list.h.

◆ BU_LIST_APPEND

#define BU_LIST_APPEND (   old,
  new 
)
Value:
{ \
BU_ASSERT((void *)(old) != (void *)NULL); \
BU_ASSERT((void *)(new) != (void *)NULL); \
(new)->forw = (old)->forw; \
(new)->back = (old); \
(old)->forw = (new); \
BU_ASSERT((void *)((new)->forw) != (void *)NULL); \
(new)->forw->back = (new); }

Append "new" item after "old" item. Often, "old" is the head. To put the new item at the head of the list, append after the head, e.g. * BU_LIST_APPEND(&(head.l), &((p)->l));

Definition at line 211 of file list.h.

◆ BU_LIST_DEQUEUE

#define BU_LIST_DEQUEUE (   cur)
Value:
{ \
BU_ASSERT((void *)(cur) != (void *)NULL); \
if (LIKELY((cur)->forw != NULL)) (cur)->forw->back = (cur)->back; \
if (LIKELY((cur)->back != NULL)) (cur)->back->forw = (cur)->forw; \
(cur)->forw = (cur)->back = BU_LIST_NULL; /* sanity */ }
#define BU_LIST_NULL
Definition: list.h:137
#define LIKELY(expression)
Definition: common.h:358

Dequeue "cur" item from anywhere in doubly-linked list

Definition at line 223 of file list.h.

◆ BU_LIST_DQ

#define BU_LIST_DQ (   cur)
Value:
{\
BU_ASSERT((void *)(cur) != (void *)NULL); \
if (LIKELY((cur)->forw != NULL)) (cur)->forw->back = (cur)->back; \
if (LIKELY((cur)->back != NULL)) (cur)->back->forw = (cur)->forw; }

Dequeue "cur" but do not fix its links

Definition at line 232 of file list.h.

◆ BU_LIST_DQ_T

#define BU_LIST_DQ_T (   cur,
  type 
)
Value:
(\
(cur)->forw->back = (cur)->back, \
(cur)->back->forw = (cur)->forw, \
(type *)(cur))

Definition at line 237 of file list.h.

◆ BU_LIST_DEQUEUE_T

#define BU_LIST_DEQUEUE_T (   cur,
  type 
)
Value:
(\
(cur)->forw->back = (cur)->back, \
(cur)->back->forw = (cur)->forw, \
(cur)->forw = (cur)->back = BU_LIST_NULL, \
(type *)(cur))

This version of BU_LIST_DEQUEUE uses the comma operator in order to return a typecast version of the dequeued pointer

Definition at line 246 of file list.h.

◆ BU_LIST_PUSH

#define BU_LIST_PUSH (   headp,
 
)     BU_LIST_APPEND(headp, (struct bu_list *)(p))

The Stack Discipline

BU_LIST_PUSH places p at the tail of headp. BU_LIST_POP sets p to last element in headp's list (else NULL) and, if p is non-null, dequeues it.

Definition at line 260 of file list.h.

◆ BU_LIST_POP

#define BU_LIST_POP (   structure,
  headp,
 
)
Value:
{ \
if (BU_LIST_NON_EMPTY(headp)) { \
(p) = ((struct structure *)((headp)->forw)); \
BU_LIST_DEQUEUE((struct bu_list *)(p)); \
} else { \
(p) = (struct structure *) 0; \
} \
}
#define BU_LIST_NON_EMPTY(headp)
Definition: list.h:310

Definition at line 263 of file list.h.

◆ BU_LIST_POP_T

#define BU_LIST_POP_T (   headp,
  type 
)     (type *)bu_list_pop(headp)

Definition at line 273 of file list.h.

◆ BU_LIST_INSERT_LIST

#define BU_LIST_INSERT_LIST (   dest_headp,
  src_headp 
)
Value:
if (LIKELY(BU_LIST_NON_EMPTY(src_headp))) { \
struct bu_list *_first = (src_headp)->forw; \
struct bu_list *_last = (src_headp)->back; \
(dest_headp)->forw->back = _last; \
_last->forw = (dest_headp)->forw; \
(dest_headp)->forw = _first; \
_first->back = (dest_headp); \
(src_headp)->forw = (src_headp)->back = (src_headp); \
}
struct bu_list * forw
"forward", "next"
Definition: list.h:133
struct bu_list * back
"back", "last"
Definition: list.h:134

"Bulk transfer" all elements from the list headed by src_headp onto the list headed by dest_headp, without examining every element in the list. src_headp is left with a valid but empty list.

BU_LIST_INSERT_LIST places src_headp elements at head of dest_headp list, BU_LIST_APPEND_LIST places src_headp elements at end of dest_headp list.

Definition at line 284 of file list.h.

◆ BU_LIST_APPEND_LIST

#define BU_LIST_APPEND_LIST (   dest_headp,
  src_headp 
)
Value:
if (LIKELY(BU_LIST_NON_EMPTY(src_headp))) {\
struct bu_list *_first = (src_headp)->forw; \
struct bu_list *_last = (src_headp)->back; \
_first->back = (dest_headp)->back; \
(dest_headp)->back->forw = _first; \
(dest_headp)->back = _last; \
_last->forw = (dest_headp); \
(src_headp)->forw = (src_headp)->back = (src_headp); \
}

Definition at line 295 of file list.h.

◆ BU_LIST_IS_EMPTY

#define BU_LIST_IS_EMPTY (   headp)    ((headp)->forw == (headp))

Test if a doubly linked list is empty, given head pointer

Definition at line 309 of file list.h.

◆ BU_LIST_NON_EMPTY

#define BU_LIST_NON_EMPTY (   headp)    ((headp)->forw != (headp))

Definition at line 310 of file list.h.

◆ BU_LIST_NON_EMPTY_P

#define BU_LIST_NON_EMPTY_P (   p,
  structure,
  headp 
)     (((p)=(struct structure *)((headp)->forw)) != (struct structure *)(headp))

Definition at line 311 of file list.h.

◆ BU_LIST_IS_CLEAR

#define BU_LIST_IS_CLEAR (   headp)
Value:
((headp)->magic == 0 && \
(headp)->forw == BU_LIST_NULL && \
(headp)->back == BU_LIST_NULL)

Definition at line 313 of file list.h.

◆ BU_LIST_LAST

#define BU_LIST_LAST (   structure,
  headp 
)     ((struct structure *)((headp)->back))

Definition at line 320 of file list.h.

◆ BU_LIST_BACK

#define BU_LIST_BACK (   structure,
  headp 
)     ((struct structure *)((headp)->back))

Definition at line 322 of file list.h.

◆ BU_LIST_PREV

#define BU_LIST_PREV (   structure,
  headp 
)     ((struct structure *)((headp)->back))

Definition at line 324 of file list.h.

◆ BU_LIST_FIRST

#define BU_LIST_FIRST (   structure,
  headp 
)     ((struct structure *)((headp)->forw))

Definition at line 326 of file list.h.

◆ BU_LIST_FORW

#define BU_LIST_FORW (   structure,
  headp 
)     ((struct structure *)((headp)->forw))

Definition at line 328 of file list.h.

◆ BU_LIST_NEXT

#define BU_LIST_NEXT (   structure,
  headp 
)     ((struct structure *)((headp)->forw))

Definition at line 330 of file list.h.

◆ BU_LIST_IS_HEAD

#define BU_LIST_IS_HEAD (   p,
  headp 
)     (((struct bu_list *)(p)) == (struct bu_list *)(headp))

Boolean test to see if current list element is the head

Definition at line 336 of file list.h.

◆ BU_LIST_NOT_HEAD

#define BU_LIST_NOT_HEAD (   p,
  headp 
)     (!BU_LIST_IS_HEAD(p, headp))

Definition at line 338 of file list.h.

◆ BU_LIST_PREV_IS_HEAD

#define BU_LIST_PREV_IS_HEAD (   p,
  headp 
)     (((struct bu_list *)(p))->back == (struct bu_list *)(headp))

Boolean test to see if previous list element is the head

Definition at line 344 of file list.h.

◆ BU_LIST_PREV_NOT_HEAD

#define BU_LIST_PREV_NOT_HEAD (   p,
  headp 
)     (!BU_LIST_PREV_IS_HEAD(p, headp))

Definition at line 346 of file list.h.

◆ BU_LIST_NEXT_IS_HEAD

#define BU_LIST_NEXT_IS_HEAD (   p,
  headp 
)     (((struct bu_list *)(p))->forw == (struct bu_list *)(headp))

Boolean test to see if the next list element is the head

Definition at line 352 of file list.h.

◆ BU_LIST_NEXT_NOT_HEAD

#define BU_LIST_NEXT_NOT_HEAD (   p,
  headp 
)     (!BU_LIST_NEXT_IS_HEAD(p, headp))

Definition at line 354 of file list.h.

◆ BU_LIST_EACH

#define BU_LIST_EACH (   headp,
  p,
  type 
)
Value:
for ((p)=(type *)BU_LIST_FIRST(bu_list, headp); \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=(type *)BU_LIST_PNEXT(bu_list, p)) \
#define BU_LIST_FIRST(structure, headp)
Definition: list.h:326
#define BU_LIST_NOT_HEAD(p, headp)
Definition: list.h:338
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:436

Definition at line 357 of file list.h.

◆ BU_LIST_REVEACH

#define BU_LIST_REVEACH (   headp,
  p,
  type 
)
Value:
for ((p)=(type *)BU_LIST_LAST(bu_list, headp); \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=(type *)BU_LIST_PREV(bu_list, ((struct bu_list *)(p)))) \
#define BU_LIST_PREV(structure, headp)
Definition: list.h:324
#define BU_LIST_LAST(structure, headp)
Definition: list.h:320

Definition at line 362 of file list.h.

◆ BU_LIST_TAIL

#define BU_LIST_TAIL (   headp,
  start,
  p,
  type 
)
Value:
for ((p)=(type *)start; \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=(type *)BU_LIST_PNEXT(bu_list, (p)))

Definition at line 367 of file list.h.

◆ BU_LIST_FOR

#define BU_LIST_FOR (   p,
  structure,
  headp 
)
Value:
(p)=BU_LIST_FIRST(structure, headp); \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=BU_LIST_PNEXT(structure, p)

Intended as innards for a for loop to visit all nodes on list, e.g.:

for (BU_LIST_FOR(p, structure, headp)) { work_on(p); }

Definition at line 379 of file list.h.

◆ BU_LIST_FOR_BACKWARDS

#define BU_LIST_FOR_BACKWARDS (   p,
  structure,
  headp 
)
Value:
(p)=BU_LIST_LAST(structure, headp); \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=BU_LIST_PLAST(structure, p)
#define BU_LIST_PLAST(structure, p)
Definition: list.h:438

Definition at line 384 of file list.h.

◆ BU_LIST_FOR_CIRC

#define BU_LIST_FOR_CIRC (   p,
  structure,
  headp 
)
Value:
(p)=BU_LIST_PNEXT_CIRC(structure, headp); \
(p) && BU_LIST_NOT_HEAD(p, headp); \
(p)=BU_LIST_PNEXT_CIRC(structure, p)
#define BU_LIST_PNEXT_CIRC(structure, p)
Definition: list.h:456

Process all the list members except headp and the actual head. Useful when starting somewhere besides the head.

Definition at line 393 of file list.h.

◆ BU_LIST_FOR2

#define BU_LIST_FOR2 (   p1,
  p2,
  structure,
  headp1,
  headp2 
)
Value:
(p1)=BU_LIST_FIRST(structure, headp1), \
(p2)=BU_LIST_FIRST(structure, headp2); \
(p1) && BU_LIST_NOT_HEAD((struct bu_list *)(p1), (headp1)) && \
(p2) && BU_LIST_NOT_HEAD((struct bu_list *)(p2), (headp2)); \
(p1)=BU_LIST_NEXT(structure, (struct bu_list *)(p1)), \
(p2)=BU_LIST_NEXT(structure, (struct bu_list *)(p2))
#define BU_LIST_NEXT(structure, headp)
Definition: list.h:330

Intended as innards for a for loop to visit elements of two lists in tandem, e.g.:

for (BU_LIST_FOR2(p1, p2, structure, headp1, headp2)) { process(p1, p2); }

Definition at line 406 of file list.h.

◆ BU_LIST_WHILE

#define BU_LIST_WHILE (   p,
  structure,
  headp 
)     (((p)=(struct structure *)((headp)->forw)) != (struct structure *)(headp))

Innards for a while loop that constantly picks off the first element. Useful mostly for a loop that will dequeue every list element, e.g.:

   while (BU_LIST_WHILE(p, structure, headp)) {


BU_LIST_DEQUEUE(&(p->l));
free((char *)p);
}

Definition at line 424 of file list.h.

◆ BU_LIST_FIRST_MAGIC

#define BU_LIST_FIRST_MAGIC (   headp)    ((headp)->forw->magic)

Return the magic number of the first (or last) item on a list

Definition at line 430 of file list.h.

◆ BU_LIST_LAST_MAGIC

#define BU_LIST_LAST_MAGIC (   headp)    ((headp)->back->magic)

Definition at line 431 of file list.h.

◆ BU_LIST_PNEXT

#define BU_LIST_PNEXT (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->forw))

Return pointer to next (or previous) element, which may be the head

Definition at line 436 of file list.h.

◆ BU_LIST_PLAST

#define BU_LIST_PLAST (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->back))

Definition at line 438 of file list.h.

◆ BU_LIST_PNEXT_PNEXT

#define BU_LIST_PNEXT_PNEXT (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->forw->forw))

Return pointer two links away, which may include the head

Definition at line 444 of file list.h.

◆ BU_LIST_PNEXT_PLAST

#define BU_LIST_PNEXT_PLAST (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->forw->back))

Definition at line 446 of file list.h.

◆ BU_LIST_PLAST_PNEXT

#define BU_LIST_PLAST_PNEXT (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->back->forw))

Definition at line 448 of file list.h.

◆ BU_LIST_PLAST_PLAST

#define BU_LIST_PLAST_PLAST (   structure,
 
)     ((struct structure *)(((struct bu_list *)(p))->back->back))

Definition at line 450 of file list.h.

◆ BU_LIST_PNEXT_CIRC

#define BU_LIST_PNEXT_CIRC (   structure,
 
)
Value:
BU_LIST_PNEXT_PNEXT(structure, (struct bu_list *)(p)) : \
BU_LIST_PNEXT(structure, p))
#define BU_LIST_FIRST_MAGIC(headp)
Definition: list.h:430
#define BU_LIST_PNEXT_PNEXT(structure, p)
Definition: list.h:444

Return pointer to circular next element; i.e., ignoring the list head

Definition at line 456 of file list.h.

◆ BU_LIST_PPREV_CIRC

#define BU_LIST_PPREV_CIRC (   structure,
 
)
Value:
BU_LIST_PLAST_PLAST(structure, (struct bu_list *)(p)) : \
BU_LIST_PLAST(structure, p))
#define BU_LIST_PLAST_PLAST(structure, p)
Definition: list.h:450
#define BU_LIST_LAST_MAGIC(headp)
Definition: list.h:431

Return pointer to circular last element; i.e., ignoring the list head

Definition at line 464 of file list.h.

◆ BU_LIST_MAIN_PTR

#define BU_LIST_MAIN_PTR (   _type,
  _ptr2,
  _name2 
)     ((struct _type *)(((char *)(_ptr2)) - (bu_offsetof(struct _type, _name2) + bu_offsetof(struct bu_list, magic))))

Support for membership on multiple linked lists.

When a structure of type '_type' contains more than one bu_list structure within it (such as the NMG edgeuse), this macro can be used to convert a pointer '_ptr2' to a "midway" bu_list structure (an element called '_name2' in structure '_type') back into a pointer to the overall enclosing structure. Examples:

eu = BU_LIST_MAIN_PTR(edgeuse, midway, l2);

eu1 = BU_LIST_MAIN_PTR(edgeuse, BU_LIST_FIRST(bu_list, &eg1->eu_hd2), l2);

Files using BU_LIST_MAIN_PTR will need to include stddef.h

Definition at line 484 of file list.h.

Typedef Documentation

◆ bu_list_t

typedef struct bu_list bu_list_t

Definition at line 136 of file list.h.

Function Documentation

◆ bu_list_new()

struct bu_list * bu_list_new ( void  )

Creates and initializes a bu_list head structure

◆ bu_list_pop()

struct bu_list * bu_list_pop ( struct bu_list headp)

Returns the results of BU_LIST_POP

◆ bu_list_len()

int bu_list_len ( const struct bu_list headp)

Returns the number of elements on a bu_list brand linked list.

◆ bu_list_reverse()

void bu_list_reverse ( struct bu_list headp)

Reverses the order of elements in a bu_list linked list.

◆ bu_list_free()

void bu_list_free ( struct bu_list headp)

Given a list of structures allocated with bu_malloc() or bu_calloc() enrolled on a bu_list head, walk the list and free the structures. This routine can only be used when the structures have no interior pointers.

◆ bu_list_parallel_append()

void bu_list_parallel_append ( struct bu_list headp,
struct bu_list itemp 
)

Simple parallel-safe routine for appending a data structure to the end of a bu_list doubly-linked list.

Issues:
Only one semaphore shared by all list heads.
No portable way to notify waiting thread(s) that are sleeping

◆ bu_list_parallel_dequeue()

struct bu_list * bu_list_parallel_dequeue ( struct bu_list headp)

Simple parallel-safe routine for dequeueing one data structure from the head of a bu_list doubly-linked list. If the list is empty, wait until some other thread puts something on the list.

Issues:
No portable way to not spin and burn CPU time while waiting
for something to show up on the list.

◆ bu_ck_list()

void bu_ck_list ( const struct bu_list headp,
const char *  str 
)

Generic bu_list doubly-linked list checker.

◆ bu_ck_list_magic()

void bu_ck_list_magic ( const struct bu_list headp,
const char *  str,
const uint32_t  magic 
)

bu_list doubly-linked list checker which checks the magic number for all elements in the linked list