Hi, I am referring to the red-black tree implementation in the linux kernel. I have read in an article (http://lwn.net/Articles/184495/) that " ... There is an important assumption built into the above example: the new value being inserted into the tree is not already present there. If that assumption is not warranted, a corrupted tree could result. If the possibility of a duplicated insertion exists, the code must be careful to test for an exact match (as is done in the search case) and stop (without inserting the node) if that match is found. ... " What needs to be done to ensure that two different nodes having same key value co-exist in a (red black tree) rb-tree without causing trouble ? >From the CFS code (kernel/sched_fair.c) I found nothing special needs to be done (which contradicts what the above article has to say). static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; struct rb_node *parent = NULL; struct sched_entity *entry; s64 key = entity_key(cfs_rq, se); int leftmost = 1; /* * Find the right place in the rbtree: */ while (*link) { parent = *link; entry = rb_entry(parent, struct sched_entity, run_node); /* * We dont care about collisions. Nodes with * the same key stay together. */ if (key < entity_key(cfs_rq, entry)) { link = &parent->rb_left; } else { link = &parent->rb_right; leftmost = 0; } } /* * Maintain a cache of leftmost tree entries (it is frequently * used): */ if (leftmost) { cfs_rq->rb_leftmost = &se->run_node; /* * maintain cfs_rq->min_vruntime to be a monotonic increasing * value tracking the leftmost vruntime in the tree. */ cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, se->vruntime); } rb_link_node(&se->run_node, parent, link); rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline); } Please clarify. -- Regards, Sukanto Ghosh -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
