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 generally 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. Some of the provided data 27structures are thread safe in specific usage scenarios (see 28:ref:`spsc_lockfree` and :ref:`mpsc_lockfree`). 29 30.. toctree:: 31 :maxdepth: 1 32 33 slist.rst 34 dlist.rst 35 mpsc_pbuf.rst 36 spsc_pbuf.rst 37 rbtree.rst 38 ring_buffers.rst 39 mpsc_lockfree.rst 40 spsc_lockfree.rst 41
