The current RB tree implementation restricts insertion of nodes with duplicate keys. However, all of the use cases in the cache module (for time, destination node, or bundle hash lookups) may have duplicate entries. To work around this the tree nodes are actually made into a list which is then searched to find the real match. However this is very memory inefficient, as the "normal" case where there is no index collision needs an extra block of memory, effectively doubling the memory requirement for the index.
If the RB tree API allowed for duplicate key/index values directly in the tree, it would remove the need for this extra list layer.
The RB tree balancing algorithm should be agnostic to duplicate keys, it is mainly an issue for the search routine and tree iterators which currently assume there is only one match in the tree and stop at the first one found. This would no longer be true if the tree potentially had duplicate values.
The current RB tree implementation restricts insertion of nodes with duplicate keys. However, all of the use cases in the cache module (for time, destination node, or bundle hash lookups) may have duplicate entries. To work around this the tree nodes are actually made into a list which is then searched to find the real match. However this is very memory inefficient, as the "normal" case where there is no index collision needs an extra block of memory, effectively doubling the memory requirement for the index.
If the RB tree API allowed for duplicate key/index values directly in the tree, it would remove the need for this extra list layer.
The RB tree balancing algorithm should be agnostic to duplicate keys, it is mainly an issue for the search routine and tree iterators which currently assume there is only one match in the tree and stop at the first one found. This would no longer be true if the tree potentially had duplicate values.