1.. _data_structures: 2 3Data Structures 4############### 5 6Zephyr provides a library of common general purpose data structures 7used within the kernel, but useful by application code in general. 8These include list and balanced tree structures for storing ordered 9data, and a ring buffer for managing "byte stream" data in a clean 10way. 11 12Note that in general, the collections are implemented as "intrusive" 13data structures. The "node" data is the only struct used by the 14library code, and it does not store a pointer or other metadata to 15indicate what user data is "owned" by that node. Instead, the 16expectation is that the node will be itself embedded within a 17user-defined struct. Macros are provided to retrieve a user struct 18address from the embedded node pointer in a clean way. The purpose 19behind this design is to allow the collections to be used in contexts 20where dynamic allocation is disallowed (i.e. there is no need to 21allocate node objects because the memory is provided by the user). 22 23Note also that these libraries are uniformly unsynchronized; access to 24them is not threadsafe by default. These are data structures, not 25synchronization primitives. The expectation is that any locking 26needed will be provided by the user. 27 28.. toctree:: 29 :maxdepth: 1 30 31 slist.rst 32 dlist.rst 33 mpsc_pbuf.rst 34 spsc_pbuf.rst 35 rbtree.rst 36 ring_buffers.rst 37 mpsc_lockfree.rst 38 spsc_lockfree.rst 39
