summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/rbtree.c
AgeCommit message (Collapse)AuthorFilesLines
2020-02-25svm: refactor fifoFlorin Coras1-10/+20
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>
2019-06-19vppinfra: fix rbtree node deleteFlorin Coras1-3/+7
Type:fix Make sure tnil color is black and that the right node colors are updated. Change-Id: Ibd9d7ea9438df4dab977202955957824723a865d Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-06-18vppinfra: rbtree custom insert/search/delFlorin Coras1-24/+92
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-26svm: fifo segment support for chunk allocationFlorin Coras1-2/+2
Change-Id: Ie96706b4d8bcb32d2d5f065bc765f95f4e9369e7 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-24svm: fifo ooo reads/writes with multiple chunksFlorin Coras1-19/+1
Change-Id: If23a04623a7138c9f6c98ee9ecfa587396618a60 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-19rbtree: add successor and predecessor functionsFlorin Coras1-0/+34
Change-Id: I6934beaf5c08bae2d4f0bd3a6bb811810407c1f9 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-16vppinfra: add basic rbtreeFlorin Coras1-0/+411
Algorithm from CLRS, Introduction to Algorithms 3rd Edition, Ch. 13 Change-Id: I5bc2c507593770939cd5584f21dacf36ebd2b4c1 Signed-off-by: Florin Coras <fcoras@cisco.com>