#include <pub/List.h>
Unlike std::List, pub::List elements are links, not copies. The various List types do not own the Link objects; they only control their position on a List.
Advantages:
- List handling is optimized, especially when copying is expensive.
Disdvantages:
- Since pub::List classes do not own List::Link objects it becomes the application's responsibility to create and delete them. (While this is similar to that of a std::list<T*>, accessing a pub::List::Link requires one less load operation.)
Differences:
- ++pub::List::end() == pub::List::end()
- ++std::list::end() == std::list::begin()
- --pub::List::end() == pub::List::end()
- --std::list::end() == std::list::rbegin()
- --pub::List::begin() == pub::List::end()
- --std::list::begin() == std::list::rend()
- Methods *List::end() and List::end()-> throw an exception rather than act in an undefined manner.
- std::list has methods not available in pub::List. It handle arrays extremely well.
- pub::AI_list provides a lock-free atomic insertion capability not available in std::list.
Notes:
- pub::List::Link construction and destruction is always an application's responsibility. For example, pub::~List does nothing.
- For all List classes, the is_coherent and is_on_list methods run in linear linear time, examining the entire list. However, is_coherent reports FALSE should a List contains more than an implementation defined (Currently 1G) Link count. Other methods assume that the List is coherent and either ignore or do not check for usage errors.
The List types:
- AI_list: Atomic Insert singly linked list. (Thread safe)
- DHDL_list: Doubly Headed Doubly Linked list.
- DHSL_list: Doubly Headed Singly Linked list.
- SHSL_list: Singly Headed Singly Linked list.
- List: Alias for DHDL_list.
The associated Link class is defined within the List class. Link classes must be derived from that List::Link class.
Example List declaration and usage-
class My_link : public List<My_link>::Link {
public:
My_link(...) : List<My_link>::Link(), ... { ... } // Constructor
// Remainder of My_link definiion
}; // class My_link, the elements to be put on a class List<My_link>
List<My_link> my_list1; // A List containing My_link elements
List<My_link> my_list2; // Another List contining My_link Links
My_link* link1= new My_link(); // Create a new My_link
my_list1.fifo(link1); // Insert it (FIFO) onto my_list1
My_link* link2= my_list1.remq(); // Then remove it, emptying my_list1
assert( link1 == link2 ); // The link added is the link removed
my_list2.lifo(link2); // Insert it (LIFO) onto my_list2
// my_list1 is empty, my_list2 only contains link2 (which == link1)
The Atomic Insert list is a lock free list. Any number of threads may insert Links, but only a single thread may check or remove links.
| Method | Purpose |
|---|---|
| begin | Create a begin() iterator |
| end | Create an end() iterator |
| fifo | Thread-safe FIFO order link insertion |
| get_tail | Obtain the tail link |
| is_coherent | (Debugging) Consistency check |
| is_empty | Check whether the List is empty |
| is_on_list | Check whether the List contains a Link |
| reset(void) | Reset (empty) the List |
| reset(void*) | Empty the List, replacing it with a dummy Link |