Manages a double linked circular list of objects.
| DoubleLinkedList | Manages a double linked circular list of objects. |
| Copyright | This program is free software. |
| Files | |
| C-kern/ | Header file DoubleLinkedList. |
| C-kern/ | Implementation file DoubleLinkedList impl. |
| Types | |
| struct dlist_t | Export dlist_t into global namespace. |
| struct dlist_iterator_t | Export dlist_iterator_t. |
| Functions | |
| test | |
| unittest_ds_inmem_dlist | Test dlist_t functionality. |
| dlist_iterator_t | Iterates over elements contained in dlist_t. |
| lifetime | |
| dlist_iterator_FREE | Static initializer. |
| initfirst_dlistiterator | Initializes an iterator for dlist_t. |
| initlast_dlistiterator | Initializes an iterator for dlist_t. |
| free_dlistiterator | Frees an iterator for dlist_t. |
| iterate | |
| next_dlistiterator | Returns all elements from first to last node of list. |
| prev_dlistiterator | Returns all elements from last to first node of list. |
| dlist_t | Double linked circular list. |
| lifetime | |
| dlist_INIT | Static initializer. |
| dlist_INIT_LAST | Static initializer. |
| init_dlist | Initializes a dlist_t object. |
| free_dlist | Frees all resources. |
| query | |
| isempty_dlist | Returns true if list contains no elements else false. |
| first_dlist | Returns the first element in the list. |
| last_dlist | Returns the last element in the list. |
| next_dlist | Returns the node coming after this node. |
| prev_dlist | Returns the node coming before this node. |
| isinlist_dlist | Returns true if node is stored in a list else false. |
| foreach-support | |
| iteratortype_dlist | Declaration to associate dlist_iterator_t with dlist_t. |
| iteratedtype_dlist | Declaration to associate dlist_node_t with dlist_t. |
| change | |
| insertfirst_dlist | Makes new_node the new first element of list. |
| insertlast_dlist | Makes new_node the new last element of list. |
| insertafter_dlist | Inserts new_node after prev_node into the list. |
| insertbefore_dlist | Inserts new_node before next_node into the list. |
| removefirst_dlist | Removes the first node from the list. |
| removelast_dlist | Removes the last node from the list. |
| remove_dlist | Removes the node from the list. |
| replacenode_dlist | Removes oldnode from list and replaces it with newnode. |
| set-ops | |
| removeall_dlist | Removes all nodes from the list. |
| transfer_dlist | Transfer ownership of all nodes from fromlist to tolist. |
| generic | |
| genericcast_dlist | Casts list into dlist_t if that is possible. |
| dlist_IMPLEMENT | Generates interface of double linked list storing elements of type object_t. |
| inline implementation | |
| dlist_iterator_t | |
| free_dlistiterator | Implements dlist_iterator_t.free_dlistiterator. |
| initfirst_dlistiterator | Implements dlist_iterator_t.initfirst_dlistiterator. |
| initlast_dlistiterator | Implements dlist_iterator_t.initlast_dlistiterator. |
| next_dlistiterator | Implements dlist_iterator_t.next_dlistiterator. |
| prev_dlistiterator | Implements dlist_iterator_t.prev_dlistiterator. |
| dlist_t | |
| genericcast_dlist | Implements dlist_t.genericcast_dlist. |
| first_dlist | Implements dlist_t.first_dlist. |
| last_dlist | Implements dlist_t.last_dlist. |
| init_dlist | Implements dlist_t.init_dlist. |
| isempty_dlist | Implements dlist_t.isempty_dlist. |
| isinlist_dlist | Implements dlist_t.isinlist_dlist. |
| next_dlist | Implements dlist_t.next_dlist. |
| prev_dlist | Implements dlist_t.prev_dlist. |
| removeall_dlist | Implements dlist_t.removeall_dlist with a call to dlist_t.free_dlist. |
| dlist_IMPLEMENT | Implements dlist_t.dlist_IMPLEMENT. |
This program is free software. You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
© 2012 Jörg Seebohn
Header file DoubleLinkedList.
Implementation file DoubleLinkedList impl.
typedef struct dlist_t dlist_t
Export dlist_t into global namespace.
typedef struct dlist_iterator_t dlist_iterator_t
Export dlist_iterator_t.
| test | |
| unittest_ds_inmem_dlist | Test dlist_t functionality. |
int unittest_ds_inmem_dlist( void )
Test dlist_t functionality.
struct dlist_iterator_t
Iterates over elements contained in dlist_t. The iterator supports removing or deleting of the current node.
dlist_t list ;
fill_list(&list) ;
foreach (_dlist, &list, node) {
if (need_to_remove(node)) {
err = remove_dlist(&list, node) ;
}
}| lifetime | |
| dlist_iterator_FREE | Static initializer. |
| initfirst_dlistiterator | Initializes an iterator for dlist_t. |
| initlast_dlistiterator | Initializes an iterator for dlist_t. |
| free_dlistiterator | Frees an iterator for dlist_t. |
| iterate | |
| next_dlistiterator | Returns all elements from first to last node of list. |
| prev_dlistiterator | Returns all elements from last to first node of list. |
int initfirst_dlistiterator( /*out*/dlist_iterator_t * iter, dlist_t * list )
Initializes an iterator for dlist_t.
int initlast_dlistiterator( /*out*/dlist_iterator_t * iter, dlist_t * list )
Initializes an iterator for dlist_t.
int free_dlistiterator( dlist_iterator_t * iter )
Frees an iterator for dlist_t.
bool next_dlistiterator( dlist_iterator_t * iter, /*out*/struct dlist_node_t ** node )
Returns all elements from first to last node of list. The first call after initfirst_dlistiterator returns the first list element if list is not empty.
| true | node contains a pointer to the next valid node in the list. |
| false | There is no next node. The last element was already returned or the list is empty. |
bool prev_dlistiterator( dlist_iterator_t * iter, /*out*/struct dlist_node_t ** node )
Returns all elements from last to first node of list. The first call after initlast_dlistiterator returns the last list element if list is not empty.
| true | node contains a pointer to the next valid node in the list. |
| false | There is no next node. The last element was already returned or the list is empty. |
struct dlist_t
Double linked circular list. The last node’s next pointer points to the first node. The first node’s previous pointer points to the last node. If the list contains only one node the node’s next and prev pointers point to this node.
| EINVAL | Either the inserted nodes dlist_node_t.next pointer is not 0. Or insertafter_dlist, insertbefore_dlist, removefirst_dlist, or removelast_dlist is called for an empty list. |
| lifetime | |
| dlist_INIT | Static initializer. |
| dlist_INIT_LAST | Static initializer. |
| init_dlist | Initializes a dlist_t object. |
| free_dlist | Frees all resources. |
| query | |
| isempty_dlist | Returns true if list contains no elements else false. |
| first_dlist | Returns the first element in the list. |
| last_dlist | Returns the last element in the list. |
| next_dlist | Returns the node coming after this node. |
| prev_dlist | Returns the node coming before this node. |
| isinlist_dlist | Returns true if node is stored in a list else false. |
| foreach-support | |
| iteratortype_dlist | Declaration to associate dlist_iterator_t with dlist_t. |
| iteratedtype_dlist | Declaration to associate dlist_node_t with dlist_t. |
| change | |
| insertfirst_dlist | Makes new_node the new first element of list. |
| insertlast_dlist | Makes new_node the new last element of list. |
| insertafter_dlist | Inserts new_node after prev_node into the list. |
| insertbefore_dlist | Inserts new_node before next_node into the list. |
| removefirst_dlist | Removes the first node from the list. |
| removelast_dlist | Removes the last node from the list. |
| remove_dlist | Removes the node from the list. |
| replacenode_dlist | Removes oldnode from list and replaces it with newnode. |
| set-ops | |
| removeall_dlist | Removes all nodes from the list. |
| transfer_dlist | Transfer ownership of all nodes from fromlist to tolist. |
| generic | |
| genericcast_dlist | Casts list into dlist_t if that is possible. |
| dlist_IMPLEMENT | Generates interface of double linked list storing elements of type object_t. |
#define dlist_INIT { (void*)0 }
Static initializer. You can use it instead of init_dlist. After assigning you can call free_dlist or any other function safely.
#define dlist_INIT_LAST( lastnode ) { (lastnode) }
Static initializer. Sets the last pointer in dlist_t to lastnode.
void init_dlist( /*out*/dlist_t * list )
Initializes a dlist_t object. Same as assigning dlist_INIT.
int free_dlist( dlist_t * list, uint16_t nodeoffset, struct typeadapt_t * typeadp/*0 = >no free called*/ )
Frees all resources. For every removed node the typeadapter callback typeadapt_lifetime_it.delete_object is called. See typeadapt_t how to construct a typeadapter. Set typeadp to 0 if you do not want to call a free memory on every node.
typedef dlist_iterator_t iteratortype_dlist
Declaration to associate dlist_iterator_t with dlist_t.
typedef struct dlist_node_t * iteratedtype_dlist
Declaration to associate dlist_node_t with dlist_t.
void insertfirst_dlist( dlist_t * list, struct dlist_node_t * new_node )
Makes new_node the new first element of list. Ownership is transfered from caller to dlist_t.
void insertlast_dlist( dlist_t * list, struct dlist_node_t * new_node )
Makes new_node the new last element of list. Ownership is transfered from caller to dlist_t.
void insertafter_dlist( dlist_t * list, struct dlist_node_t * prev_node, struct dlist_node_t * new_node )
Inserts new_node after prev_node into the list. Ownership is transfered from caller to dlist_t. new_node will be made the new last node if prev_node is the <last_dlist>(list) node.
void insertbefore_dlist( struct dlist_node_t * next_node, struct dlist_node_t * new_node )
Inserts new_node before next_node into the list. Ownership is transfered from caller to dlist_t. new_node will be made the new first node if next_node is the <first_dlist>(list) node.
int removefirst_dlist( dlist_t * list, struct dlist_node_t ** removed_node )
Removes the first node from the list. Ownership is transfered from dlist_t to caller. If the list contains no elements EINVAL is returned else removed_node points to the formerly first element of the list.
int removelast_dlist( dlist_t * list, struct dlist_node_t ** removed_node )
Removes the last node from the list. Ownership is transfered from dlist_t to caller. If the list contains no elements EINVAL is returned else removed_node points to the formerly last element of the list.
int remove_dlist( dlist_t * list, struct dlist_node_t * node )
Removes the node from the list. Ownership is transfered from dlist_t to caller.
Make sure that node is part of this list and not any other else undefined behaviour could happen.
void replacenode_dlist( dlist_t * list, struct dlist_node_t * newnode, struct dlist_node_t * oldnode )
Removes oldnode from list and replaces it with newnode. Ownership of oldnode is transfered back to caller. Ownership of newnode is transfered from caller to dlist_t. oldnode’s prev and next pointer are cleared.
int removeall_dlist( dlist_t * list, uint16_t nodeoffset, struct typeadapt_t * typeadp/*0 = >no free called*/ )
Removes all nodes from the list. For every removed node typeadapt_lifetime_it.delete_object is called. Set typeadp to 0 if you do not want to call a free memory on every node.
dlist_t * genericcast_dlist( void * list )
Casts list into dlist_t if that is possible. The generic object list must have a last pointer as first member.
void dlist_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, IDNAME nodeprefix ) ;
Generates interface of double linked list storing elements of type object_t.
| _fsuffix | The suffix of the generated list interface functions, e.g. “init##_fsuffix”. |
| object_t | The type of object which can be stored and retrieved from this list. The object must contain a field of type dlist_node_t. |
| nodeprefix | The access path of the field dlist_node_t in type object_t including “.”. if next and prev pointers are part of object_t leave this field emtpy. |
| dlist_iterator_t | |
| free_dlistiterator | Implements dlist_iterator_t.free_dlistiterator. |
| initfirst_dlistiterator | Implements dlist_iterator_t.initfirst_dlistiterator. |
| initlast_dlistiterator | Implements dlist_iterator_t.initlast_dlistiterator. |
| next_dlistiterator | Implements dlist_iterator_t.next_dlistiterator. |
| prev_dlistiterator | Implements dlist_iterator_t.prev_dlistiterator. |
| dlist_t | |
| genericcast_dlist | Implements dlist_t.genericcast_dlist. |
| first_dlist | Implements dlist_t.first_dlist. |
| last_dlist | Implements dlist_t.last_dlist. |
| init_dlist | Implements dlist_t.init_dlist. |
| isempty_dlist | Implements dlist_t.isempty_dlist. |
| isinlist_dlist | Implements dlist_t.isinlist_dlist. |
| next_dlist | Implements dlist_t.next_dlist. |
| prev_dlist | Implements dlist_t.prev_dlist. |
| removeall_dlist | Implements dlist_t.removeall_dlist with a call to dlist_t.free_dlist. |
| dlist_IMPLEMENT | Implements dlist_t.dlist_IMPLEMENT. |
#define free_dlistiterator( iter ) (((iter)->next = 0), 0)
Implements dlist_iterator_t.free_dlistiterator.
#define initfirst_dlistiterator( iter, list ) ( __extension__ ({ typeof(iter) _iter = (iter) ; typeof(list) _list = (list) ; *_iter = (typeof(*_iter)) { first_dlist(_list), _list } ; 0 ; }))
Implements dlist_iterator_t.initfirst_dlistiterator.
#define initlast_dlistiterator( iter, list ) ( __extension__ ({ typeof(iter) _iter = (iter) ; typeof(list) _list = (list) ; *_iter = (typeof(*_iter)) { last_dlist(_list), _list } ; 0 ; }))
Implements dlist_iterator_t.initlast_dlistiterator.
#define next_dlistiterator( iter, node ) ( __extension__ ({ typeof(iter) _iter = (iter) ; bool _isNext = (0 != _iter->next) ; if (_isNext) { *(node) = _iter->next ; if (_iter->list->last == _iter->next) _iter->next = 0 ; else _iter->next = next_dlist(_iter->next) ; } _isNext ; }))
Implements dlist_iterator_t.next_dlistiterator.
#define prev_dlistiterator( iter, node ) ( __extension__ ({ typeof(iter) _iter = (iter) ; bool _isNext = (0 != _iter->next) ; if (_isNext) { *(node) = _iter->next ; _iter->next = prev_dlist(_iter->next) ; if (_iter->list->last == _iter->next) { _iter->next = 0 ; } } _isNext ; }))
Implements dlist_iterator_t.prev_dlistiterator.
#define genericcast_dlist( list ) ( __extension__ ({ static_assert( sizeof((list)->last) == sizeof(((dlist_t*)0)->last) && offsetof(typeof(*(list)), last) == offsetof(dlist_t, last) && (typeof((list)->last))0 == (dlist_node_t*)0, "ensure compatible structure" ) ; (dlist_t*) (list) ; }))
Implements dlist_t.genericcast_dlist.
#define first_dlist( list ) ((list)->last ? (list)->last->next : (struct dlist_node_t*)0)
Implements dlist_t.first_dlist.
#define last_dlist( list ) ((list)->last)
Implements dlist_t.last_dlist.
#define init_dlist( list ) ((void)(*(list) = (dlist_t)dlist_INIT))
Implements dlist_t.init_dlist.
#define isempty_dlist( list ) (0 == (list)->last)
Implements dlist_t.isempty_dlist.
#define isinlist_dlist( node ) (0 != (node)->next)
Implements dlist_t.isinlist_dlist.
#define next_dlist( node ) ((node)->next)
Implements dlist_t.next_dlist.
#define prev_dlist( node ) ((node)->prev)
Implements dlist_t.prev_dlist.
#define removeall_dlist( list, nodeoffset, typeadp ) (free_dlist((list), (nodeoffset), (typeadp)))
Implements dlist_t.removeall_dlist with a call to dlist_t.free_dlist.
#define dlist_IMPLEMENT( _fsuffix, object_t, nodeprefix ) typedef dlist_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) __attribute__ ((always_inline)) ; static inline int initlast##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(dlist_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline bool prev##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline void init##_fsuffix(dlist_t * list) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int isempty##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * first##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * last##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * next##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline object_t * prev##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline bool isinlist##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline void insertfirst##_fsuffix(dlist_t * list, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertlast##_fsuffix(dlist_t * list, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertafter##_fsuffix(dlist_t * list, object_t * prev_node, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertbefore##_fsuffix(object_t* next_node, object_t * new_node) __attribute__ ((always_inline)) ; static inline int removefirst##_fsuffix(dlist_t * list, object_t ** removed_node) __attribute__ ((always_inline)) ; static inline int removelast##_fsuffix(dlist_t * list, object_t ** removed_node) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(dlist_t * list, object_t * node) __attribute__ ((always_inline)) ; static inline void replacenode##_fsuffix(dlist_t * list, object_t * newnode, object_t * oldnode) __attribute__ ((always_inline)) ; static inline int removeall##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline void transfer##_fsuffix(dlist_t * tolist, dlist_t * fromlist) __attribute__ ((always_inline)) ; static inline uint16_t nodeoffset##_fsuffix(void) __attribute__ ((always_inline)) ; static inline uint16_t nodeoffset##_fsuffix(void) { static_assert(UINT16_MAX > (uintptr_t) & (((object_t*)0)->nodeprefix next), "offset fits in uint16_t") ; return (uint16_t) (uintptr_t) & (((object_t*)0)->nodeprefix next) ; } static inline dlist_node_t * asnode##_fsuffix(object_t * object) { static_assert(&(((object_t*)0)->nodeprefix next) == (dlist_node_t**)((uintptr_t)nodeoffset##_fsuffix()), "correct type") ; static_assert(&(((object_t*)0)->nodeprefix prev) == (dlist_node_t**)(nodeoffset##_fsuffix() + sizeof(dlist_node_t*)), "correct type and offset") ; return (dlist_node_t *) ((uintptr_t)object + nodeoffset##_fsuffix()) ; } static inline object_t * asobject##_fsuffix(dlist_node_t * node) { return (object_t *) ((uintptr_t)node - nodeoffset##_fsuffix()) ; } static inline object_t * asobjectnull##_fsuffix(dlist_node_t * node) { return node ? (object_t *) ((uintptr_t)node - nodeoffset##_fsuffix()) : 0 ; } static inline void init##_fsuffix(dlist_t * list) { init_dlist(list) ; } static inline int free##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) { return free_dlist(list, nodeoffset##_fsuffix(), typeadp) ; } static inline int isempty##_fsuffix(const dlist_t * list) { return isempty_dlist(list) ; } static inline object_t * first##_fsuffix(const dlist_t * list) { return asobjectnull##_fsuffix(first_dlist(list)) ; } static inline object_t * last##_fsuffix(const dlist_t * list) { return asobjectnull##_fsuffix(last_dlist(list)) ; } static inline object_t * next##_fsuffix(object_t * node) { return asobject##_fsuffix(next_dlist(asnode##_fsuffix(node))) ; } static inline object_t * prev##_fsuffix(object_t * node) { return asobject##_fsuffix(prev_dlist(asnode##_fsuffix(node))) ; } static inline bool isinlist##_fsuffix(object_t * node) { return isinlist_dlist(asnode##_fsuffix(node)) ; } static inline void insertfirst##_fsuffix(dlist_t * list, object_t * new_node) { insertfirst_dlist(list, asnode##_fsuffix(new_node)) ; } static inline void insertlast##_fsuffix(dlist_t * list, object_t * new_node) { insertlast_dlist(list, asnode##_fsuffix(new_node)) ; } static inline void insertafter##_fsuffix(dlist_t * list, object_t * prev_node, object_t * new_node) { insertafter_dlist(list, asnode##_fsuffix(prev_node), asnode##_fsuffix(new_node)) ; } static inline void insertbefore##_fsuffix(object_t * next_node, object_t * new_node) { insertbefore_dlist(asnode##_fsuffix(next_node), asnode##_fsuffix(new_node)) ; } static inline int removefirst##_fsuffix(dlist_t * list, object_t ** removed_node) { int err = removefirst_dlist(list, (dlist_node_t**)removed_node) ; if (!err) *removed_node = asobject##_fsuffix(*(dlist_node_t**)removed_node) ; return err ; } static inline int removelast##_fsuffix(dlist_t * list, object_t ** removed_node) { int err = removelast_dlist(list, (dlist_node_t**)removed_node) ; if (!err) *removed_node = asobject##_fsuffix(*(dlist_node_t**)removed_node) ; return err ; } static inline int remove##_fsuffix(dlist_t * list, object_t * node) { return remove_dlist(list, asnode##_fsuffix(node)) ; } static inline void replacenode##_fsuffix(dlist_t * list, object_t * newnode, object_t * oldnode) { replacenode_dlist(list, asnode##_fsuffix(newnode), asnode##_fsuffix(oldnode)) ; } static inline int removeall##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) { return removeall_dlist(list, nodeoffset##_fsuffix(), typeadp) ; } static inline void transfer##_fsuffix(dlist_t * tolist, dlist_t * fromlist) { transfer_dlist(tolist, fromlist) ; } static inline int initfirst##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) { return initfirst_dlistiterator(iter, list) ; } static inline int initlast##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) { return initlast_dlistiterator(iter, list) ; } static inline int free##_fsuffix##iterator(dlist_iterator_t * iter) { return free_dlistiterator(iter) ; } static inline bool next##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) { bool isNext = next_dlistiterator(iter, (dlist_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(dlist_node_t**)node) ; return isNext ; } static inline bool prev##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) { bool isNext = prev_dlistiterator(iter, (dlist_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(dlist_node_t**)node) ; return isNext ; }
Implements dlist_t.dlist_IMPLEMENT.
Export dlist_t into global namespace.
typedef struct dlist_t dlist_t
Double linked circular list.
struct dlist_t
Export dlist_iterator_t.
typedef struct dlist_iterator_t dlist_iterator_t
Iterates over elements contained in dlist_t.
struct dlist_iterator_t
Test dlist_t functionality.
int unittest_ds_inmem_dlist( void )
Static initializer.
#define dlist_iterator_FREE { 0, 0 }
Initializes an iterator for dlist_t.
int initfirst_dlistiterator( /*out*/dlist_iterator_t * iter, dlist_t * list )
Initializes an iterator for dlist_t.
int initlast_dlistiterator( /*out*/dlist_iterator_t * iter, dlist_t * list )
Frees an iterator for dlist_t.
int free_dlistiterator( dlist_iterator_t * iter )
Returns all elements from first to last node of list.
bool next_dlistiterator( dlist_iterator_t * iter, /*out*/struct dlist_node_t ** node )
Returns all elements from last to first node of list.
bool prev_dlistiterator( dlist_iterator_t * iter, /*out*/struct dlist_node_t ** node )
Static initializer.
#define dlist_INIT { (void*)0 }
Static initializer.
#define dlist_INIT_LAST( lastnode ) { (lastnode) }
Initializes a dlist_t object.
void init_dlist( /*out*/dlist_t * list )
Frees all resources.
int free_dlist( dlist_t * list, uint16_t nodeoffset, struct typeadapt_t * typeadp/*0 = >no free called*/ )
Returns true if list contains no elements else false.
int isempty_dlist( const dlist_t * list )
Returns the first element in the list.
struct dlist_node_t * first_dlist( dlist_t * list )
Returns the last element in the list.
struct dlist_node_t * last_dlist( dlist_t * list )
Returns the node coming after this node.
struct dlist_node_t * next_dlist( struct dlist_node_t * node )
Returns the node coming before this node.
struct dlist_node_t * prev_dlist( struct dlist_node_t * node )
Returns true if node is stored in a list else false.
bool isinlist_dlist( const struct dlist_node_t * node )
Declaration to associate dlist_iterator_t with dlist_t.
typedef dlist_iterator_t iteratortype_dlist
Declaration to associate dlist_node_t with dlist_t.
typedef struct dlist_node_t * iteratedtype_dlist
Provides the means for linking an object to two others of the same type.
struct dlist_node_t
Makes new_node the new first element of list.
void insertfirst_dlist( dlist_t * list, struct dlist_node_t * new_node )
Makes new_node the new last element of list.
void insertlast_dlist( dlist_t * list, struct dlist_node_t * new_node )
Inserts new_node after prev_node into the list.
void insertafter_dlist( dlist_t * list, struct dlist_node_t * prev_node, struct dlist_node_t * new_node )
Inserts new_node before next_node into the list.
void insertbefore_dlist( struct dlist_node_t * next_node, struct dlist_node_t * new_node )
Removes the first node from the list.
int removefirst_dlist( dlist_t * list, struct dlist_node_t ** removed_node )
Removes the last node from the list.
int removelast_dlist( dlist_t * list, struct dlist_node_t ** removed_node )
Removes the node from the list.
int remove_dlist( dlist_t * list, struct dlist_node_t * node )
Removes oldnode from list and replaces it with newnode.
void replacenode_dlist( dlist_t * list, struct dlist_node_t * newnode, struct dlist_node_t * oldnode )
Removes all nodes from the list.
int removeall_dlist( dlist_t * list, uint16_t nodeoffset, struct typeadapt_t * typeadp/*0 = >no free called*/ )
Transfer ownership of all nodes from fromlist to tolist.
void transfer_dlist( dlist_t * tolist, dlist_t * fromlist )
Casts list into dlist_t if that is possible.
dlist_t * genericcast_dlist( void * list )
Generates interface of double linked list storing elements of type object_t.
void dlist_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, IDNAME nodeprefix ) ;
Implements dlist_iterator_t.free_dlistiterator.
#define free_dlistiterator( iter ) (((iter)->next = 0), 0)
Implements dlist_iterator_t.initfirst_dlistiterator.
#define initfirst_dlistiterator( iter, list ) ( __extension__ ({ typeof(iter) _iter = (iter) ; typeof(list) _list = (list) ; *_iter = (typeof(*_iter)) { first_dlist(_list), _list } ; 0 ; }))
Implements dlist_iterator_t.initlast_dlistiterator.
#define initlast_dlistiterator( iter, list ) ( __extension__ ({ typeof(iter) _iter = (iter) ; typeof(list) _list = (list) ; *_iter = (typeof(*_iter)) { last_dlist(_list), _list } ; 0 ; }))
Implements dlist_iterator_t.next_dlistiterator.
#define next_dlistiterator( iter, node ) ( __extension__ ({ typeof(iter) _iter = (iter) ; bool _isNext = (0 != _iter->next) ; if (_isNext) { *(node) = _iter->next ; if (_iter->list->last == _iter->next) _iter->next = 0 ; else _iter->next = next_dlist(_iter->next) ; } _isNext ; }))
Implements dlist_iterator_t.prev_dlistiterator.
#define prev_dlistiterator( iter, node ) ( __extension__ ({ typeof(iter) _iter = (iter) ; bool _isNext = (0 != _iter->next) ; if (_isNext) { *(node) = _iter->next ; _iter->next = prev_dlist(_iter->next) ; if (_iter->list->last == _iter->next) { _iter->next = 0 ; } } _isNext ; }))
Implements dlist_t.genericcast_dlist.
#define genericcast_dlist( list ) ( __extension__ ({ static_assert( sizeof((list)->last) == sizeof(((dlist_t*)0)->last) && offsetof(typeof(*(list)), last) == offsetof(dlist_t, last) && (typeof((list)->last))0 == (dlist_node_t*)0, "ensure compatible structure" ) ; (dlist_t*) (list) ; }))
Implements dlist_t.first_dlist.
#define first_dlist( list ) ((list)->last ? (list)->last->next : (struct dlist_node_t*)0)
Implements dlist_t.last_dlist.
#define last_dlist( list ) ((list)->last)
Implements dlist_t.init_dlist.
#define init_dlist( list ) ((void)(*(list) = (dlist_t)dlist_INIT))
Implements dlist_t.isempty_dlist.
#define isempty_dlist( list ) (0 == (list)->last)
Implements dlist_t.isinlist_dlist.
#define isinlist_dlist( node ) (0 != (node)->next)
Implements dlist_t.next_dlist.
#define next_dlist( node ) ((node)->next)
Implements dlist_t.prev_dlist.
#define prev_dlist( node ) ((node)->prev)
Implements dlist_t.removeall_dlist with a call to dlist_t.free_dlist.
#define removeall_dlist( list, nodeoffset, typeadp ) (free_dlist((list), (nodeoffset), (typeadp)))
Implements dlist_t.dlist_IMPLEMENT.
#define dlist_IMPLEMENT( _fsuffix, object_t, nodeprefix ) typedef dlist_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) __attribute__ ((always_inline)) ; static inline int initlast##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(dlist_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline bool prev##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline void init##_fsuffix(dlist_t * list) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int isempty##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * first##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * last##_fsuffix(const dlist_t * list) __attribute__ ((always_inline)) ; static inline object_t * next##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline object_t * prev##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline bool isinlist##_fsuffix(object_t * node) __attribute__ ((always_inline)) ; static inline void insertfirst##_fsuffix(dlist_t * list, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertlast##_fsuffix(dlist_t * list, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertafter##_fsuffix(dlist_t * list, object_t * prev_node, object_t * new_node) __attribute__ ((always_inline)) ; static inline void insertbefore##_fsuffix(object_t* next_node, object_t * new_node) __attribute__ ((always_inline)) ; static inline int removefirst##_fsuffix(dlist_t * list, object_t ** removed_node) __attribute__ ((always_inline)) ; static inline int removelast##_fsuffix(dlist_t * list, object_t ** removed_node) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(dlist_t * list, object_t * node) __attribute__ ((always_inline)) ; static inline void replacenode##_fsuffix(dlist_t * list, object_t * newnode, object_t * oldnode) __attribute__ ((always_inline)) ; static inline int removeall##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline void transfer##_fsuffix(dlist_t * tolist, dlist_t * fromlist) __attribute__ ((always_inline)) ; static inline uint16_t nodeoffset##_fsuffix(void) __attribute__ ((always_inline)) ; static inline uint16_t nodeoffset##_fsuffix(void) { static_assert(UINT16_MAX > (uintptr_t) & (((object_t*)0)->nodeprefix next), "offset fits in uint16_t") ; return (uint16_t) (uintptr_t) & (((object_t*)0)->nodeprefix next) ; } static inline dlist_node_t * asnode##_fsuffix(object_t * object) { static_assert(&(((object_t*)0)->nodeprefix next) == (dlist_node_t**)((uintptr_t)nodeoffset##_fsuffix()), "correct type") ; static_assert(&(((object_t*)0)->nodeprefix prev) == (dlist_node_t**)(nodeoffset##_fsuffix() + sizeof(dlist_node_t*)), "correct type and offset") ; return (dlist_node_t *) ((uintptr_t)object + nodeoffset##_fsuffix()) ; } static inline object_t * asobject##_fsuffix(dlist_node_t * node) { return (object_t *) ((uintptr_t)node - nodeoffset##_fsuffix()) ; } static inline object_t * asobjectnull##_fsuffix(dlist_node_t * node) { return node ? (object_t *) ((uintptr_t)node - nodeoffset##_fsuffix()) : 0 ; } static inline void init##_fsuffix(dlist_t * list) { init_dlist(list) ; } static inline int free##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) { return free_dlist(list, nodeoffset##_fsuffix(), typeadp) ; } static inline int isempty##_fsuffix(const dlist_t * list) { return isempty_dlist(list) ; } static inline object_t * first##_fsuffix(const dlist_t * list) { return asobjectnull##_fsuffix(first_dlist(list)) ; } static inline object_t * last##_fsuffix(const dlist_t * list) { return asobjectnull##_fsuffix(last_dlist(list)) ; } static inline object_t * next##_fsuffix(object_t * node) { return asobject##_fsuffix(next_dlist(asnode##_fsuffix(node))) ; } static inline object_t * prev##_fsuffix(object_t * node) { return asobject##_fsuffix(prev_dlist(asnode##_fsuffix(node))) ; } static inline bool isinlist##_fsuffix(object_t * node) { return isinlist_dlist(asnode##_fsuffix(node)) ; } static inline void insertfirst##_fsuffix(dlist_t * list, object_t * new_node) { insertfirst_dlist(list, asnode##_fsuffix(new_node)) ; } static inline void insertlast##_fsuffix(dlist_t * list, object_t * new_node) { insertlast_dlist(list, asnode##_fsuffix(new_node)) ; } static inline void insertafter##_fsuffix(dlist_t * list, object_t * prev_node, object_t * new_node) { insertafter_dlist(list, asnode##_fsuffix(prev_node), asnode##_fsuffix(new_node)) ; } static inline void insertbefore##_fsuffix(object_t * next_node, object_t * new_node) { insertbefore_dlist(asnode##_fsuffix(next_node), asnode##_fsuffix(new_node)) ; } static inline int removefirst##_fsuffix(dlist_t * list, object_t ** removed_node) { int err = removefirst_dlist(list, (dlist_node_t**)removed_node) ; if (!err) *removed_node = asobject##_fsuffix(*(dlist_node_t**)removed_node) ; return err ; } static inline int removelast##_fsuffix(dlist_t * list, object_t ** removed_node) { int err = removelast_dlist(list, (dlist_node_t**)removed_node) ; if (!err) *removed_node = asobject##_fsuffix(*(dlist_node_t**)removed_node) ; return err ; } static inline int remove##_fsuffix(dlist_t * list, object_t * node) { return remove_dlist(list, asnode##_fsuffix(node)) ; } static inline void replacenode##_fsuffix(dlist_t * list, object_t * newnode, object_t * oldnode) { replacenode_dlist(list, asnode##_fsuffix(newnode), asnode##_fsuffix(oldnode)) ; } static inline int removeall##_fsuffix(dlist_t * list, struct typeadapt_t * typeadp) { return removeall_dlist(list, nodeoffset##_fsuffix(), typeadp) ; } static inline void transfer##_fsuffix(dlist_t * tolist, dlist_t * fromlist) { transfer_dlist(tolist, fromlist) ; } static inline int initfirst##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) { return initfirst_dlistiterator(iter, list) ; } static inline int initlast##_fsuffix##iterator(dlist_iterator_t * iter, dlist_t * list) { return initlast_dlistiterator(iter, list) ; } static inline int free##_fsuffix##iterator(dlist_iterator_t * iter) { return free_dlistiterator(iter) ; } static inline bool next##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) { bool isNext = next_dlistiterator(iter, (dlist_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(dlist_node_t**)node) ; return isNext ; } static inline bool prev##_fsuffix##iterator(dlist_iterator_t * iter, object_t ** node) { bool isNext = prev_dlistiterator(iter, (dlist_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(dlist_node_t**)node) ; return isNext ; }
Points to next node in the list.
dlist_node_t * next
Function frees memory and associated resources of object.
int ( * delete_object ) (struct typeadapt_t * typeadp, struct typeadapt_object_t ** object)