Bug 1419217 - Change comparison functions for red-black trees. r?njn
- This makes all of them return an enum, quite similar to rust.
- This makes all of them derive from a single implementation of an
integer comparison.
- This implements that integer comparison in terms of simple operations,
rather than "smart" computation, which turns out to allow compilers
to do better optimizations.
See https://blogs.msdn.microsoft.com/oldnewthing/20171117-00/?p=97416
--- a/memory/build/Utils.h
+++ b/memory/build/Utils.h
@@ -14,26 +14,46 @@
template<size_t N>
struct Log2 : mozilla::tl::CeilingLog2<N>
{
using mozilla::tl::CeilingLog2<N>::value;
static_assert(1ULL << value == N, "Number is not a power of 2");
};
#define LOG2(N) Log2<N>::value
-// Compare two addresses. Returns whether the first address is smaller (-1),
-// equal (0) or greater (1) than the second address.
+enum class Order
+{
+ eLess = -1,
+ eEqual = 0,
+ eGreater = 1,
+};
+
+// Compare two integers. Returns whether the first integer is Less,
+// Equal or Greater than the second integer.
template<typename T>
-int
+Order
+CompareInt(T aValue1, T aValue2)
+{
+ static_assert(mozilla::IsIntegral<T>::value, "Type must be integral");
+ if (aValue1 < aValue2) {
+ return Order::eLess;
+ }
+ if (aValue1 > aValue2) {
+ return Order::eGreater;
+ }
+ return Order::eEqual;
+}
+
+// Compare two addresses. Returns whether the first address is Less,
+// Equal or Greater than the second address.
+template<typename T>
+Order
CompareAddr(T* aAddr1, T* aAddr2)
{
- uintptr_t addr1 = reinterpret_cast<uintptr_t>(aAddr1);
- uintptr_t addr2 = reinterpret_cast<uintptr_t>(aAddr2);
-
- return (addr1 > addr2) - (addr1 < addr2);
+ return CompareInt(uintptr_t(aAddr1), uintptr_t(aAddr2));
}
// User-defined literals to make constants more legible
constexpr size_t operator"" _KiB(unsigned long long int aNum)
{
return size_t(aNum) * 1024;
}
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -640,50 +640,51 @@ struct extent_node_t
struct ExtentTreeSzTrait
{
static RedBlackTreeNode<extent_node_t>& GetTreeNode(extent_node_t* aThis)
{
return aThis->mLinkBySize;
}
- static inline int Compare(extent_node_t* aNode, extent_node_t* aOther)
+ static inline Order Compare(extent_node_t* aNode, extent_node_t* aOther)
{
- int ret = (aNode->mSize > aOther->mSize) - (aNode->mSize < aOther->mSize);
- return ret ? ret : CompareAddr(aNode->mAddr, aOther->mAddr);
+ Order ret = CompareInt(aNode->mSize, aOther->mSize);
+ return (ret != Order::eEqual) ? ret
+ : CompareAddr(aNode->mAddr, aOther->mAddr);
}
};
struct ExtentTreeTrait
{
static RedBlackTreeNode<extent_node_t>& GetTreeNode(extent_node_t* aThis)
{
return aThis->mLinkByAddr;
}
- static inline int Compare(extent_node_t* aNode, extent_node_t* aOther)
+ static inline Order Compare(extent_node_t* aNode, extent_node_t* aOther)
{
return CompareAddr(aNode->mAddr, aOther->mAddr);
}
};
struct ExtentTreeBoundsTrait : public ExtentTreeTrait
{
- static inline int Compare(extent_node_t* aKey, extent_node_t* aNode)
+ static inline Order Compare(extent_node_t* aKey, extent_node_t* aNode)
{
uintptr_t key_addr = reinterpret_cast<uintptr_t>(aKey->mAddr);
uintptr_t node_addr = reinterpret_cast<uintptr_t>(aNode->mAddr);
size_t node_size = aNode->mSize;
// Is aKey within aNode?
if (node_addr <= key_addr && key_addr < node_addr + node_size) {
- return 0;
+ return Order::eEqual;
}
- return (key_addr > node_addr) - (key_addr < node_addr);
+ return CompareAddr(aKey->mAddr, aNode->mAddr);
}
};
// Describe size classes to which allocations are rounded up to.
// TODO: add large and huge types when the arena allocation code
// changes in a way that allows it to be beneficial.
class SizeClass
{
@@ -788,45 +789,48 @@ struct ArenaChunkMapLink
arena_chunk_map_t* aThis)
{
return aThis->link;
}
};
struct ArenaRunTreeTrait : public ArenaChunkMapLink
{
- static inline int Compare(arena_chunk_map_t* aNode, arena_chunk_map_t* aOther)
+ static inline Order Compare(arena_chunk_map_t* aNode,
+ arena_chunk_map_t* aOther)
{
MOZ_ASSERT(aNode);
MOZ_ASSERT(aOther);
return CompareAddr(aNode, aOther);
}
};
struct ArenaAvailTreeTrait : public ArenaChunkMapLink
{
- static inline int Compare(arena_chunk_map_t* aNode, arena_chunk_map_t* aOther)
+ static inline Order Compare(arena_chunk_map_t* aNode,
+ arena_chunk_map_t* aOther)
{
size_t size1 = aNode->bits & ~gPageSizeMask;
size_t size2 = aOther->bits & ~gPageSizeMask;
- int ret = (size1 > size2) - (size1 < size2);
- return ret ? ret
- : CompareAddr((aNode->bits & CHUNK_MAP_KEY) ? nullptr : aNode,
- aOther);
+ Order ret = CompareInt(size1, size2);
+ return (ret != Order::eEqual)
+ ? ret
+ : CompareAddr((aNode->bits & CHUNK_MAP_KEY) ? nullptr : aNode,
+ aOther);
}
};
struct ArenaDirtyChunkTrait
{
static RedBlackTreeNode<arena_chunk_t>& GetTreeNode(arena_chunk_t* aThis)
{
return aThis->link_dirty;
}
- static inline int Compare(arena_chunk_t* aNode, arena_chunk_t* aOther)
+ static inline Order Compare(arena_chunk_t* aNode, arena_chunk_t* aOther)
{
MOZ_ASSERT(aNode);
MOZ_ASSERT(aOther);
return CompareAddr(aNode, aOther);
}
};
#ifdef MALLOC_DOUBLE_PURGE
@@ -1092,21 +1096,21 @@ public:
struct ArenaTreeTrait
{
static RedBlackTreeNode<arena_t>& GetTreeNode(arena_t* aThis)
{
return aThis->mLink;
}
- static inline int Compare(arena_t* aNode, arena_t* aOther)
+ static inline Order Compare(arena_t* aNode, arena_t* aOther)
{
MOZ_ASSERT(aNode);
MOZ_ASSERT(aOther);
- return (aNode->mId > aOther->mId) - (aNode->mId < aOther->mId);
+ return CompareInt(aNode->mId, aOther->mId);
}
};
// Bookkeeping for all the arenas used by the allocator.
// Arenas are separated in two categories:
// - "private" arenas, used through the moz_arena_* API
// - all the other arenas: the default arena, and thread-local arenas,
// used by the standard API.
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -42,25 +42,25 @@
// thus making node linkage as compact as is possible for red-black trees.
//
// The RedBlackTree template expects two type arguments: the type of the nodes,
// containing a RedBlackTreeNode, and a trait providing two methods:
// - a GetTreeNode method that returns a reference to the RedBlackTreeNode
// corresponding to a given node with the following signature:
// static RedBlackTreeNode<T>& GetTreeNode(T*)
// - a Compare function with the following signature:
-// static int Compare(T* aNode, T* aOther)
-// ^^^^^
-// or aKey
+// static Order Compare(T* aNode, T* aOther)
+// ^^^^^
+// or aKey
//
// Interpretation of comparision function return values:
//
-// -1 : aNode < aOther
-// 0 : aNode == aOther
-// 1 : aNode > aOther
+// Order::eLess: aNode < aOther
+// Order::eEqual: aNode == aOther
+// Order::eGreater: aNode > aOther
//
// In all cases, the aNode or aKey argument is the first argument to the
// comparison function, which makes it possible to write comparison functions
// that treat the first argument specially.
//
// ***************************************************************************
#ifndef RB_H_
@@ -200,21 +200,21 @@ private:
TreeNode* ret;
if (aNode->Right()) {
ret = First(aNode->Right());
} else {
TreeNode* rbp_n_t = mRoot;
MOZ_ASSERT(rbp_n_t);
ret = nullptr;
while (true) {
- int rbp_n_cmp = Trait::Compare(aNode, rbp_n_t);
- if (rbp_n_cmp < 0) {
+ Order rbp_n_cmp = Trait::Compare(aNode, rbp_n_t);
+ if (rbp_n_cmp == Order::eLess) {
ret = rbp_n_t;
rbp_n_t = rbp_n_t->Left();
- } else if (rbp_n_cmp > 0) {
+ } else if (rbp_n_cmp == Order::eGreater) {
rbp_n_t = rbp_n_t->Right();
} else {
break;
}
MOZ_ASSERT(rbp_n_t);
}
}
return ret;
@@ -225,71 +225,71 @@ private:
TreeNode* ret;
if (aNode->Left()) {
ret = Last(aNode->Left());
} else {
TreeNode* rbp_p_t = mRoot;
MOZ_ASSERT(rbp_p_t);
ret = nullptr;
while (true) {
- int rbp_p_cmp = Trait::Compare(aNode, rbp_p_t);
- if (rbp_p_cmp < 0) {
+ Order rbp_p_cmp = Trait::Compare(aNode, rbp_p_t);
+ if (rbp_p_cmp == Order::eLess) {
rbp_p_t = rbp_p_t->Left();
- } else if (rbp_p_cmp > 0) {
+ } else if (rbp_p_cmp == Order::eGreater) {
ret = rbp_p_t;
rbp_p_t = rbp_p_t->Right();
} else {
break;
}
MOZ_ASSERT(rbp_p_t);
}
}
return ret;
}
TreeNode* Search(TreeNode* aKey)
{
TreeNode* ret = mRoot;
- int rbp_se_cmp;
- while (ret && (rbp_se_cmp = Trait::Compare(aKey, ret)) != 0) {
- if (rbp_se_cmp < 0) {
+ Order rbp_se_cmp;
+ while (ret && (rbp_se_cmp = Trait::Compare(aKey, ret)) != Order::eEqual) {
+ if (rbp_se_cmp == Order::eLess) {
ret = ret->Left();
} else {
ret = ret->Right();
}
}
return ret;
}
TreeNode* SearchOrNext(TreeNode* aKey)
{
TreeNode* ret = nullptr;
TreeNode* rbp_ns_t = mRoot;
while (rbp_ns_t) {
- int rbp_ns_cmp = Trait::Compare(aKey, rbp_ns_t);
- if (rbp_ns_cmp < 0) {
+ Order rbp_ns_cmp = Trait::Compare(aKey, rbp_ns_t);
+ if (rbp_ns_cmp == Order::eLess) {
ret = rbp_ns_t;
rbp_ns_t = rbp_ns_t->Left();
- } else if (rbp_ns_cmp > 0) {
+ } else if (rbp_ns_cmp == Order::eGreater) {
rbp_ns_t = rbp_ns_t->Right();
} else {
ret = rbp_ns_t;
break;
}
}
return ret;
}
void Insert(TreeNode* aNode)
{
// rbp_i_s is only used as a placeholder for its RedBlackTreeNode. Use
// AlignedStorage2 to avoid running the TreeNode base class constructor.
mozilla::AlignedStorage2<TreeNode> rbp_i_s;
TreeNode *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;
- int rbp_i_cmp = 0;
+ Order rbp_i_cmp = Order::eEqual;
rbp_i_g = nullptr;
rbp_i_p = rbp_i_s.addr();
rbp_i_p->SetLeft(mRoot);
rbp_i_p->SetRight(nullptr);
rbp_i_p->SetColor(NodeColor::Black);
rbp_i_c = mRoot;
// Iteratively search down the tree for the insertion point,
// splitting 4-nodes as they are encountered. At the end of each
@@ -320,40 +320,40 @@ private:
if (rbp_i_g->Left() == rbp_i_p) {
rbp_i_g->SetLeft(rbp_i_u);
} else {
MOZ_ASSERT(rbp_i_g->Right() == rbp_i_p);
rbp_i_g->SetRight(rbp_i_u);
}
rbp_i_p = rbp_i_u;
rbp_i_cmp = Trait::Compare(aNode, rbp_i_p);
- if (rbp_i_cmp < 0) {
+ if (rbp_i_cmp == Order::eLess) {
rbp_i_c = rbp_i_p->Left();
} else {
- MOZ_ASSERT(rbp_i_cmp > 0);
+ MOZ_ASSERT(rbp_i_cmp == Order::eGreater);
rbp_i_c = rbp_i_p->Right();
}
continue;
}
}
rbp_i_g = rbp_i_p;
rbp_i_p = rbp_i_c;
rbp_i_cmp = Trait::Compare(aNode, rbp_i_c);
- if (rbp_i_cmp < 0) {
+ if (rbp_i_cmp == Order::eLess) {
rbp_i_c = rbp_i_c->Left();
} else {
- MOZ_ASSERT(rbp_i_cmp > 0);
+ MOZ_ASSERT(rbp_i_cmp == Order::eGreater);
rbp_i_c = rbp_i_c->Right();
}
}
// rbp_i_p now refers to the node under which to insert.
aNode->SetLeft(nullptr);
aNode->SetRight(nullptr);
aNode->SetColor(NodeColor::Red);
- if (rbp_i_cmp > 0) {
+ if (rbp_i_cmp == Order::eGreater) {
rbp_i_p->SetRight(aNode);
rbp_i_t = LeanLeft(rbp_i_p);
if (rbp_i_g->Left() == rbp_i_p) {
rbp_i_g->SetLeft(rbp_i_t);
} else if (rbp_i_g->Right() == rbp_i_p) {
rbp_i_g->SetRight(rbp_i_t);
}
} else {
@@ -365,66 +365,66 @@ private:
}
void Remove(TreeNode* aNode)
{
// rbp_r_s is only used as a placeholder for its RedBlackTreeNode. Use
// AlignedStorage2 to avoid running the TreeNode base class constructor.
mozilla::AlignedStorage2<TreeNode> rbp_r_s;
TreeNode *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;
- int rbp_r_cmp;
+ Order rbp_r_cmp;
rbp_r_p = rbp_r_s.addr();
rbp_r_p->SetLeft(mRoot);
rbp_r_p->SetRight(nullptr);
rbp_r_p->SetColor(NodeColor::Black);
rbp_r_c = mRoot;
rbp_r_xp = nullptr;
// Iterate down the tree, but always transform 2-nodes to 3- or
// 4-nodes in order to maintain the invariant that the current
// node is not a 2-node. This allows simple deletion once a leaf
// is reached. Handle the root specially though, since there may
// be no way to convert it from a 2-node to a 3-node.
rbp_r_cmp = Trait::Compare(aNode, rbp_r_c);
- if (rbp_r_cmp < 0) {
+ if (rbp_r_cmp == Order::eLess) {
rbp_r_t = rbp_r_c->Left();
rbp_r_u = rbp_r_t ? rbp_r_t->Left() : nullptr;
if ((!rbp_r_t || rbp_r_t->IsBlack()) &&
(!rbp_r_u || rbp_r_u->IsBlack())) {
// Apply standard transform to prepare for left move.
rbp_r_t = MoveRedLeft(rbp_r_c);
rbp_r_t->SetColor(NodeColor::Black);
rbp_r_p->SetLeft(rbp_r_t);
rbp_r_c = rbp_r_t;
} else {
// Move left.
rbp_r_p = rbp_r_c;
rbp_r_c = rbp_r_c->Left();
}
} else {
- if (rbp_r_cmp == 0) {
+ if (rbp_r_cmp == Order::eEqual) {
MOZ_ASSERT(aNode == rbp_r_c);
if (!rbp_r_c->Right()) {
// Delete root node (which is also a leaf node).
if (rbp_r_c->Left()) {
rbp_r_t = LeanRight(rbp_r_c);
rbp_r_t->SetRight(nullptr);
} else {
rbp_r_t = nullptr;
}
rbp_r_p->SetLeft(rbp_r_t);
} else {
// This is the node we want to delete, but we will
// instead swap it with its successor and delete the
// successor. Record enough information to do the
// swap later. rbp_r_xp is the aNode's parent.
rbp_r_xp = rbp_r_p;
- rbp_r_cmp = 1; // Note that deletion is incomplete.
+ rbp_r_cmp = Order::eGreater; // Note that deletion is incomplete.
}
}
- if (rbp_r_cmp == 1) {
+ if (rbp_r_cmp == Order::eGreater) {
if (rbp_r_c->Right() && (!rbp_r_c->Right()->Left() ||
rbp_r_c->Right()->Left()->IsBlack())) {
rbp_r_t = rbp_r_c->Left();
if (rbp_r_t->IsRed()) {
// Standard transform.
rbp_r_t = MoveRedRight(rbp_r_c);
} else {
// Root-specific transform.
@@ -444,21 +444,21 @@ private:
rbp_r_c = rbp_r_t;
} else {
// Move right.
rbp_r_p = rbp_r_c;
rbp_r_c = rbp_r_c->Right();
}
}
}
- if (rbp_r_cmp != 0) {
+ if (rbp_r_cmp != Order::eEqual) {
while (true) {
MOZ_ASSERT(rbp_r_p);
rbp_r_cmp = Trait::Compare(aNode, rbp_r_c);
- if (rbp_r_cmp < 0) {
+ if (rbp_r_cmp == Order::eLess) {
rbp_r_t = rbp_r_c->Left();
if (!rbp_r_t) {
// rbp_r_c now refers to the successor node to
// relocate, and rbp_r_xp/aNode refer to the
// context for the relocation.
if (rbp_r_xp->Left() == aNode) {
rbp_r_xp->SetLeft(rbp_r_c);
} else {
@@ -487,17 +487,17 @@ private:
rbp_r_c = rbp_r_t;
} else {
rbp_r_p = rbp_r_c;
rbp_r_c = rbp_r_c->Left();
}
} else {
// Check whether to delete this node (it has to be
// the correct node and a leaf node).
- if (rbp_r_cmp == 0) {
+ if (rbp_r_cmp == Order::eEqual) {
MOZ_ASSERT(aNode == rbp_r_c);
if (!rbp_r_c->Right()) {
// Delete leaf node.
if (rbp_r_c->Left()) {
rbp_r_t = LeanRight(rbp_r_c);
rbp_r_t->SetRight(nullptr);
} else {
rbp_r_t = nullptr;