30.1 Dllists

Doubly-linked lists (dllists) are widely used throughout the whole source tree. While portions of their API live at the lisp level, they are more common at the C level for various purposes, queues, auxiliary linking of items, or free lists just to name some.

Their head, their tail and their size are protected by mutexes (when pthreads are available) which provides thread-safe operations.

Dllists can link together arbitrary objects at the C level. They provide a void* slot per item. Storing Lisp_Objects requires a cast to void* hence. However, they obey the normal rules of garbage collection, can be marked and collected. Marking an ordinary dllist induces a traversal through all the linked objects (called items) where each item is marked as though it was a Lisp_Object.

So in order to avoid interference with arbitrary objects dllists and the GC’s mark phase there is a special form of allocation, we call ‘noseeum_dllist’s. Consequently noseeum dllists have to be manually observed and freed if necessary.

At the moment we provide following functionality:

Lisp_Dllist *make_dllist(void);
Lisp_Dllist *noseeum_make_dllist(void);
void noseeum_free_dllist(Lisp_Dllist*);

Hereby, the noseeum_ functions are intended to operate independently of the garbage collector.

void *dllist_car(Lisp_Dllist*);
void *dllist_rac(Lisp_Dllist*);

Without altering the dllist in any way these return the element in the head cell or tail cell respectively. Note: These two elements the only ones accessible in general. A dllist is – due to its slightly more complex navigation information overhead – not as flexible as ordinary lisp lists made up of cons cells.

void dllist_prepend_item(Lisp_Dllist*, dllist_item_t*);
void dllist_prepend(Lisp_Dllist*, void*);
void dllist_append_item(Lisp_Dllist*, dllist_item_t*);
void dllist_append(Lisp_Dllist*, void*);

These are modifier functions which add items or elements to the head or tail of the dllist respectively. An item here is a dllist_item_t object which carries the actual element (of type void*) and the navigation information. The navigation cell itself need not have valid navigation information, these are set accordingly in the body of dllist_prepend_item or dllist_append_item. In this speak, a dllist_prepend is rewritten to a dllist_prepend_item after the data element (of type void*) has been properly wrapped into a (newly allocated) navigation cell.

inline dllist_item_t *dllist_transfer_car(Lisp_Dllist*);
void *dllist_pop_car(Lisp_Dllist*);
inline dllist_item_t *dllist_transfer_rac(Lisp_Dllist*);
void *dllist_pop_rac(Lisp_Dllist*);

These are destructive accessors and – in a way – the inverse operations of dllist_append_item, dllist_append, etc. The dllist_transfer form here cuts off the entire head cell or tail cell of the dllist, that is including the navigation information. In contrast, the dllist_pop form essentially does the same, but extracts the actual data element (cast to void*). Moreover, since the navigation cell on its own is quite useless, it is freed after extraction.

Lisp_Dllist *copy_dllist(Lisp_Dllist*);
void dllist_map_inplace(Lisp_Object, Lisp_Object);
void dllist_map_inplace_C(void*(*)(void*), Lisp_Dllist*);
void dllist_map_C(void(*)(void*), Lisp_Dllist*);

Auxiliary stuff, to be documented later.