summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/rbtree.h
AgeCommit message (Collapse)AuthorFilesLines
2020-02-25svm: refactor fifoFlorin Coras1-0/+1
Type: refactor Switch from a wrapped byte space to a "continuous" one wherein fifo chunks are appended to the fifo as more data is enqueued and chunks are removed as data is dequeued. The fifo is still subject to a maximum size, i.e., maximum number of bytes that can be enqueued, so the max number of chunks associated to the fifo is also constrained. When enqueueing data, which must fit within the available free space, if not enough "supporting" chunk memory is available, the fifo asks the fifo segment for enough chunk memory to ensure that the write can succeed. To avoid allocating large amounts of small chunks due to small writes, if possible, the size of the chunks requested is lower capped by min_alloc. When dequeuing data, all the chunks that have been completely drained, i.e., head moved beyond the chunks’ end bytes, are unlinked from the fifo and returned to the fifo segment. The one exception to this is the last chunk which is never unlinked. Change-Id: I98c1dbd9135fb79650365c7e40c29238b96cd4ee Signed-off-by: Florin Coras <fcoras@cisco.com>
2020-02-25svm: refactor fifo chunk trackingFlorin Coras1-0/+1
Avoid tracking with rbtrees all of the chunks associated to a fifo. Instead, only track chunks when doing out-of-order operations (peek or ooo enqueue). Type: refactor Change-Id: I9f8bd266211746637d98e6a12ffc4b2d6346950a Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-06-18vppinfra: rbtree custom insert/search/delFlorin Coras1-0/+7
Type: feature Add support for insert/search/del with custom compare function. Change-Id: Ibb740afc224d8adc29d3e1b51b46cdd738d1bd93 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-24svm: fifo ooo reads/writes with multiple chunksFlorin Coras1-2/+20
Change-Id: If23a04623a7138c9f6c98ee9ecfa587396618a60 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-19rbtree: add successor and predecessor functionsFlorin Coras1-0/+2
Change-Id: I6934beaf5c08bae2d4f0bd3a6bb811810407c1f9 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-16vppinfra: add basic rbtreeFlorin Coras1-0/+84
Algorithm from CLRS, Introduction to Algorithms 3rd Edition, Ch. 13 Change-Id: I5bc2c507593770939cd5584f21dacf36ebd2b4c1 Signed-off-by: Florin Coras <fcoras@cisco.com>