summaryrefslogtreecommitdiffstats
path: root/cpukit/score/src/rbtreeinsert.c (unfollow)
Commit message (Collapse)AuthorFilesLines
2017-09-27score: Simplify red-black tree debug supportSebastian Huber1-4/+0
Make the RBTree_Node layout independent of RTEMS_DEBUG (and all other build configuration options). This allows the use of this structure in Newlib. Update #3112.
2016-09-06score: Improve red-black tree debug supportSebastian Huber1-0/+4
Ensure that we extract a node only from the right tree.
2016-06-22score: Move _RBTree_Insert()Sebastian Huber1-43/+0
The _RBTree_Insert() is no longer used in the score. Move it to sapi and make it rtems_rbtree_insert().
2015-12-14score: Help GCC to inline a functionSebastian Huber1-1/+1
2015-09-03rbtree: Replace implementationSebastian Huber1-102/+26
Use the BSD <sys/tree.h> implementation since it is faster, more flexible and uses less storage. See https://github.com/sebhub/rb-bench.
2014-08-07rbtree: Simplify insert and extractSebastian Huber1-21/+36
Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more superfluous NULL pointer checks. Change _RBTree_Is_root() to use only the node. Add parent parameter to _RBTree_Sibling(). Delete _RBTree_Grandparent() and _RBTree_Parent_sibling().
2014-08-05rbtree: Add and use RBTree_Compare_resultSebastian Huber1-1/+12
2014-07-26rbtree: Update maximum node in LIFO orderSebastian Huber1-2/+2
The test sptests/sp35 showed a NULL pointer access due to an invalid maximum node field (e.g. a tree with one element and NULL as the maximum node).
2014-07-22rbtree: Remove superfluous NULL pointer checksSebastian Huber1-4/+0
2014-07-22rbtree: FormatSebastian Huber1-31/+39
2014-07-15rbtree: Reduce RBTree_Control sizeSebastian Huber1-22/+10
Remove compare function and is unique indicator from the control structure. Rename RBTree_Compare_function to RBTree_Compare. Rename rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++ compatible initializers. Add compare function and is unique indicator to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and rtems_rbtree_insert(). Remove _RBTree_Is_unique() and rtems_rbtree_is_unique(). Remove compare function and is unique indicator from _RBTree_Initialize_empty() and rtems_rbtree_initialize_empty().
2014-03-21Change all references of rtems.com to rtems.org.Chris Johns1-1/+1
2013-11-21score/rbtree: Remove "unprotected" from APISebastian Huber1-3/+3
2013-11-21score/rbtree: Delete protected operationsSebastian Huber1-31/+0
The user of the red-black tree container must now ensure that at most one thread at once can access an instance.
2013-07-23score: Create rbtree implementation headerSebastian Huber1-3/+1
Move implementation specific parts of rbtree.h and rbtree.inl into new header file rbtreeimpl.h. The rbtree.h contains now only the application visible API.
2012-05-13PR2065: RBTree: Insert function (protected) does not enable interruptsGedare Bloom1-2/+4
Save the return value from the unprotected version and return it after enabling interrupts to their previous level.
2012-05-11Remove All CVS Id Strings Possible Using a ScriptJoel Sherrill1-2/+0
Script does what is expected and tries to do it as smartly as possible. + remove occurrences of two blank comment lines next to each other after Id string line removed. + remove entire comment blocks which only exited to contain CVS Ids + If the processing left a blank line at the top of a file, it was removed.
2012-05-08PR2061: RBTree: updating min and max on insert with duplicatesGedare Bloom1-1/+6
When inserting to a red-black tree with duplicates the min and max pointers are not updated properly. We need to check the key of the min/max node against the insert node since the insert point could be the child of a node with an identical key to the min/max node.
2012-03-29PR1994: RBTree Compare Result ChangeGedare Bloom1-2/+2
Change the meaning of the compare result to simplify comparison of integer keys.
2011-12-022011-12-02 Ralf Corsépius <ralf.corsepius@rtems.org>Ralf Corsepius1-1/+1
* score/src/rbtreeextract.c: Make _RBTree_Extract_validate_unprotected static. * score/src/rbtreeinsert.c: Make _RBTree_Validate_insert_unprotected static.
2011-08-212011-08-21 Petr Benes <benesp16@fel.cvut.cz>Joel Sherrill1-4/+5
PR 1886/cpukit * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreeinsert.c: This patch enables inserting duplicate keys into rbtree. It is possible to turn on this feature when initializing the tree.
2011-08-022011-08-02 Joel Sherrill <joel.sherrill@oarcorp.com>Joel Sherrill1-3/+5
PR 1877/cpukit * libfs/src/imfs/imfs_mknod.c, libfs/src/imfs/memfile.c, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreefind.c, score/src/rbtreeinsert.c: Add comparison function for RBTrees.
2011-05-24Remove white-spaces.Ralf Corsepius1-8/+8
2011-04-042010-07-28 Gedare Bloom <giddyup44@yahoo.com>Joel Sherrill1-0/+149
PR 1641/cpukit * sapi/Makefile.am, sapi/preinstall.am, score/Makefile.am, score/preinstall.am: Add Red Black Tree data structure to score. * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreeextract.c, score/src/rbtreefind.c, score/src/rbtreefindheader.c, score/src/rbtreeget.c, score/src/rbtreeinsert.c, score/src/rbtreepeek.c: New files.
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-19 13:35:50 +0000