summaryrefslogtreecommitdiff
path: root/core
diff options
context:
space:
mode:
authorRĂ©mi Verschelde <rverschelde@gmail.com>2017-09-25 23:53:18 +0200
committerGitHub <noreply@github.com>2017-09-25 23:53:18 +0200
commite9e1753c3cf96015893d4d138d6f085995f00035 (patch)
tree30576d178d0a33edf29091a342b8ca952b0175a6 /core
parentc79fc6716e0ccfec5f05e1ae1f5e90d79e6689d2 (diff)
parent98f8e7df1634826b719039adeca1b8a5b326b0f9 (diff)
Merge pull request #11445 from Cradmon/refactorCoreMap
Refactor core/map.h
Diffstat (limited to 'core')
-rw-r--r--core/map.h319
-rw-r--r--core/set.h130
2 files changed, 217 insertions, 232 deletions
diff --git a/core/map.h b/core/map.h
index a37d898a9c..f01062ebed 100644
--- a/core/map.h
+++ b/core/map.h
@@ -31,6 +31,7 @@
#define MAP_H
#include "set.h"
+
/**
@author Juan Linietsky <reduzio@gmail.com>
*/
@@ -52,7 +53,6 @@ public:
private:
friend class Map<K, V, C, A>;
- //Color color;
int color;
Element *right;
Element *left;
@@ -61,7 +61,6 @@ public:
Element *_prev;
K _key;
V _value;
-
//_Data *data;
public:
@@ -147,7 +146,6 @@ private:
#ifdef GLOBALNIL_DISABLED
memdelete_allocator<Element, A>(_nil);
#endif
- //memdelete_allocator<Element,A>(_root);
}
};
@@ -158,6 +156,7 @@ private:
ERR_FAIL_COND(p_node == _data._nil && p_color == RED);
p_node->color = p_color;
}
+
inline void _rotate_left(Element *p_node) {
Element *r = p_node->right;
@@ -206,8 +205,9 @@ private:
while (node == node->parent->right) {
node = node->parent;
}
+
if (node->parent == _data._root)
- return NULL;
+ return NULL; // No successor, as p_node = last node
return node->parent;
}
}
@@ -225,10 +225,11 @@ private:
} else {
while (node == node->parent->left) {
- if (node->parent == _data._root)
- return NULL;
node = node->parent;
}
+
+ if (node == _data._root)
+ return NULL; // No predecessor, as p_node = first node
return node->parent;
}
}
@@ -239,16 +240,15 @@ private:
C less;
while (node != _data._nil) {
-
if (less(p_key, node->_key))
node = node->left;
else if (less(node->_key, p_key))
node = node->right;
else
- break; // found
+ return node; // found
}
- return (node != _data._nil) ? node : NULL;
+ return NULL;
}
Element *_find_closest(const K &p_key) const {
@@ -265,24 +265,68 @@ private:
else if (less(node->_key, p_key))
node = node->right;
else
- break; // found
+ return node; // found
}
- if (node == _data._nil) {
- if (prev == NULL)
- return NULL;
- if (less(p_key, prev->_key)) {
+ if (prev == NULL)
+ return NULL; // tree empty
- prev = prev->_prev;
- }
+ if (less(p_key, prev->_key))
+ prev = prev->_prev;
- return prev;
+ return prev;
+ }
- } else
- return node;
+ void _insert_rb_fix(Element *p_new_node) {
+
+ Element *node = p_new_node;
+ Element *nparent = node->parent;
+ Element *ngrand_parent;
+
+ while (nparent->color == RED) {
+ ngrand_parent = nparent->parent;
+
+ if (nparent == ngrand_parent->left) {
+ if (ngrand_parent->right->color == RED) {
+ _set_color(nparent, BLACK);
+ _set_color(ngrand_parent->right, BLACK);
+ _set_color(ngrand_parent, RED);
+ node = ngrand_parent;
+ nparent = node->parent;
+ } else {
+ if (node == nparent->right) {
+ _rotate_left(nparent);
+ node = nparent;
+ nparent = node->parent;
+ }
+ _set_color(nparent, BLACK);
+ _set_color(ngrand_parent, RED);
+ _rotate_right(ngrand_parent);
+ }
+ } else {
+ if (ngrand_parent->left->color == RED) {
+ _set_color(nparent, BLACK);
+ _set_color(ngrand_parent->left, BLACK);
+ _set_color(ngrand_parent, RED);
+ node = ngrand_parent;
+ nparent = node->parent;
+ } else {
+ if (node == nparent->left) {
+ _rotate_right(nparent);
+ node = nparent;
+ nparent = node->parent;
+ }
+ _set_color(nparent, BLACK);
+ _set_color(ngrand_parent, RED);
+ _rotate_left(ngrand_parent);
+ }
+ }
+ }
+
+ _set_color(_data._root->left, BLACK);
}
- Element *_insert(const K &p_key, bool &r_exists) {
+ Element *_insert(const K &p_key, const V &p_value) {
Element *new_parent = _data._root;
Element *node = _data._root->left;
@@ -297,27 +341,25 @@ private:
else if (less(node->_key, p_key))
node = node->right;
else {
- r_exists = true;
- return node;
+ node->_value = p_value;
+ return node; // Return existing node with new value
}
}
Element *new_node = memnew_allocator(Element, A);
-
new_node->parent = new_parent;
new_node->right = _data._nil;
new_node->left = _data._nil;
new_node->_key = p_key;
+ new_node->_value = p_value;
//new_node->data=_data;
- if (new_parent == _data._root || less(p_key, new_parent->_key)) {
+ if (new_parent == _data._root || less(p_key, new_parent->_key)) {
new_parent->left = new_node;
} else {
new_parent->right = new_node;
}
- r_exists = false;
-
new_node->_next = _successor(new_node);
new_node->_prev = _predecessor(new_node);
if (new_node->_next)
@@ -325,168 +367,113 @@ private:
if (new_node->_prev)
new_node->_prev->_next = new_node;
- return new_node;
- }
-
- Element *_insert_rb(const K &p_key, const V &p_value) {
-
- bool exists = false;
- Element *new_node = _insert(p_key, exists);
-
- if (new_node) {
- new_node->_value = p_value;
- }
- if (exists)
- return new_node;
-
- Element *node = new_node;
_data.size_cache++;
-
- while (node->parent->color == RED) {
-
- if (node->parent == node->parent->parent->left) {
-
- Element *aux = node->parent->parent->right;
-
- if (aux->color == RED) {
- _set_color(node->parent, BLACK);
- _set_color(aux, BLACK);
- _set_color(node->parent->parent, RED);
- node = node->parent->parent;
- } else {
- if (node == node->parent->right) {
- node = node->parent;
- _rotate_left(node);
- }
- _set_color(node->parent, BLACK);
- _set_color(node->parent->parent, RED);
- _rotate_right(node->parent->parent);
- }
- } else {
- Element *aux = node->parent->parent->left;
-
- if (aux->color == RED) {
- _set_color(node->parent, BLACK);
- _set_color(aux, BLACK);
- _set_color(node->parent->parent, RED);
- node = node->parent->parent;
- } else {
- if (node == node->parent->left) {
- node = node->parent;
- _rotate_right(node);
- }
- _set_color(node->parent, BLACK);
- _set_color(node->parent->parent, RED);
- _rotate_left(node->parent->parent);
- }
- }
- }
- _set_color(_data._root->left, BLACK);
+ _insert_rb_fix(new_node);
return new_node;
}
- void _erase_fix(Element *p_node) {
+ void _erase_fix_rb(Element *p_node) {
Element *root = _data._root->left;
- Element *node = p_node;
-
- while ((node->color == BLACK) && (root != node)) {
- if (node == node->parent->left) {
- Element *aux = node->parent->right;
- if (aux->color == RED) {
- _set_color(aux, BLACK);
- _set_color(node->parent, RED);
- _rotate_left(node->parent);
- aux = node->parent->right;
- }
- if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) {
- _set_color(aux, RED);
- node = node->parent;
+ Element *node = _data._nil;
+ Element *sibling = p_node;
+ Element *parent = sibling->parent;
+
+ while (node != root) { // If red node found, will exit at a break
+ if (sibling->color == RED) {
+ _set_color(sibling, BLACK);
+ _set_color(parent, RED);
+ if (sibling == parent->right) {
+ sibling = sibling->left;
+ _rotate_left(parent);
} else {
- if (aux->right->color == BLACK) {
- _set_color(aux->left, BLACK);
- _set_color(aux, RED);
- _rotate_right(aux);
- aux = node->parent->right;
- }
- _set_color(aux, node->parent->color);
- _set_color(node->parent, BLACK);
- _set_color(aux->right, BLACK);
- _rotate_left(node->parent);
- node = root; /* this is to exit while loop */
+ sibling = sibling->right;
+ _rotate_right(parent);
}
- } else { /* the code below is has left and right switched from above */
- Element *aux = node->parent->left;
- if (aux->color == RED) {
- _set_color(aux, BLACK);
- _set_color(node->parent, RED);
- _rotate_right(node->parent);
- aux = node->parent->left;
+ }
+ if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) {
+ _set_color(sibling, RED);
+ if (parent->color == RED) {
+ _set_color(parent, BLACK);
+ break;
+ } else { // loop: haven't found any red nodes yet
+ node = parent;
+ parent = node->parent;
+ sibling = (node == parent->left) ? parent->right : parent->left;
}
- if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) {
- _set_color(aux, RED);
- node = node->parent;
+ } else {
+ if (sibling == parent->right) {
+ if (sibling->right->color == BLACK) {
+ _set_color(sibling->left, BLACK);
+ _set_color(sibling, RED);
+ _rotate_right(sibling);
+ sibling = sibling->parent;
+ }
+ _set_color(sibling, parent->color);
+ _set_color(parent, BLACK);
+ _set_color(sibling->right, BLACK);
+ _rotate_left(parent);
+ break;
} else {
- if (aux->left->color == BLACK) {
- _set_color(aux->right, BLACK);
- _set_color(aux, RED);
- _rotate_left(aux);
- aux = node->parent->left;
+ if (sibling->left->color == BLACK) {
+ _set_color(sibling->right, BLACK);
+ _set_color(sibling, RED);
+ _rotate_left(sibling);
+ sibling = sibling->parent;
}
- _set_color(aux, node->parent->color);
- _set_color(node->parent, BLACK);
- _set_color(aux->left, BLACK);
- _rotate_right(node->parent);
- node = root;
+
+ _set_color(sibling, parent->color);
+ _set_color(parent, BLACK);
+ _set_color(sibling->left, BLACK);
+ _rotate_right(parent);
+ break;
}
}
}
- _set_color(node, BLACK);
-
ERR_FAIL_COND(_data._nil->color != BLACK);
}
void _erase(Element *p_node) {
- Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : _successor(p_node);
- if (!rp)
- rp = _data._nil;
+ Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : p_node->_next;
Element *node = (rp->left == _data._nil) ? rp->right : rp->left;
node->parent = rp->parent;
- if (_data._root == node->parent) {
- _data._root->left = node;
+ Element *sibling;
+ if (rp == rp->parent->left) {
+ rp->parent->left = node;
+ sibling = rp->parent->right;
} else {
- if (rp == rp->parent->left) {
- rp->parent->left = node;
- } else {
- rp->parent->right = node;
- }
+ rp->parent->right = node;
+ sibling = rp->parent->left;
+ }
+
+ if (node->color == RED) {
+ node->parent = rp->parent;
+ _set_color(node, BLACK);
+ } else if (rp->color == BLACK && rp->parent != _data._root) {
+ _erase_fix_rb(sibling);
}
if (rp != p_node) {
ERR_FAIL_COND(rp == _data._nil);
- if (rp->color == BLACK)
- _erase_fix(node);
-
rp->left = p_node->left;
rp->right = p_node->right;
rp->parent = p_node->parent;
rp->color = p_node->color;
- p_node->left->parent = rp;
- p_node->right->parent = rp;
+ if (p_node->left != _data._nil)
+ p_node->left->parent = rp;
+ if (p_node->right != _data._nil)
+ p_node->right->parent = rp;
if (p_node == p_node->parent->left) {
p_node->parent->left = rp;
} else {
p_node->parent->right = rp;
}
- } else {
- if (p_node->color == BLACK)
- _erase_fix(node);
}
if (p_node->_next)
@@ -501,11 +488,12 @@ private:
void _calculate_depth(Element *p_element, int &max_d, int d) const {
- if (p_element == _data._nil) {
+ if (p_element == _data._nil)
return;
- }
+
_calculate_depth(p_element->left, max_d, d + 1);
_calculate_depth(p_element->right, max_d, d + 1);
+
if (d > max_d)
max_d = d;
}
@@ -544,6 +532,7 @@ public:
if (!_data._root)
return NULL;
+
Element *res = _find(p_key);
return res;
}
@@ -552,6 +541,7 @@ public:
if (!_data._root)
return NULL;
+
const Element *res = _find_closest(p_key);
return res;
}
@@ -560,21 +550,28 @@ public:
if (!_data._root)
return NULL;
+
Element *res = _find_closest(p_key);
return res;
}
+ bool has(const K &p_key) const {
+
+ return find(p_key) != NULL;
+ }
+
Element *insert(const K &p_key, const V &p_value) {
if (!_data._root)
_data._create_root();
- return _insert_rb(p_key, p_value);
+ return _insert(p_key, p_value);
}
void erase(Element *p_element) {
- if (!_data._root)
+ if (!_data._root || !p_element)
return;
+
_erase(p_element);
if (_data.size_cache == 0 && _data._root)
_data._free_root();
@@ -584,20 +581,17 @@ public:
if (!_data._root)
return false;
+
Element *e = find(p_key);
if (!e)
return false;
+
_erase(e);
+ if (_data.size_cache == 0 && _data._root)
+ _data._free_root();
return true;
}
- bool has(const K &p_key) const {
-
- if (!_data._root)
- return false;
- return find(p_key) != NULL;
- }
-
const V &operator[](const K &p_key) const {
CRASH_COND(!_data._root);
@@ -605,6 +599,7 @@ public:
CRASH_COND(!e);
return e->_value;
}
+
V &operator[](const K &p_key) {
if (!_data._root)
@@ -614,7 +609,6 @@ public:
if (!e)
e = insert(p_key, V());
- CRASH_COND(!e);
return e->_value;
}
@@ -637,6 +631,7 @@ public:
if (!_data._root)
return NULL;
+
Element *e = _data._root->left;
if (e == _data._nil)
return NULL;
@@ -649,10 +644,12 @@ public:
inline bool empty() const { return _data.size_cache == 0; }
inline int size() const { return _data.size_cache; }
+
int calculate_depth() const {
// used for debug mostly
if (!_data._root)
return 0;
+
int max_d = 0;
_calculate_depth(_data._root->left, max_d, 0);
return max_d;
@@ -662,10 +659,10 @@ public:
if (!_data._root)
return;
+
_cleanup_tree(_data._root->left);
_data._root->left = _data._nil;
_data.size_cache = 0;
- _data._nil->parent = _data._nil;
_data._free_root();
}
diff --git a/core/set.h b/core/set.h
index d91dd9b3ea..0f48e07520 100644
--- a/core/set.h
+++ b/core/set.h
@@ -100,17 +100,15 @@ private:
Element *_nil;
int size_cache;
- _Data() {
+ _FORCE_INLINE_ _Data() {
#ifdef GLOBALNIL_DISABLED
_nil = memnew_allocator(Element, A);
_nil->parent = _nil->left = _nil->right = _nil;
_nil->color = BLACK;
#else
-
_nil = (Element *)&_GlobalNilClass::_nil;
#endif
_root = NULL;
-
size_cache = 0;
}
@@ -132,6 +130,7 @@ private:
~_Data() {
_free_root();
+
#ifdef GLOBALNIL_DISABLED
memdelete_allocator<Element, A>(_nil);
#endif
@@ -196,7 +195,7 @@ private:
}
if (node->parent == _data._root)
- return NULL; // No successor, as p_node is the last node.
+ return NULL; // No successor, as p_node = last node
return node->parent;
}
}
@@ -218,7 +217,7 @@ private:
}
if (node == _data._root)
- return NULL; // No predecessor, as p_node is the first node.
+ return NULL; // No predecessor, as p_node = first node.
return node->parent;
}
}
@@ -266,65 +265,13 @@ private:
return prev;
}
- Element *_insert(const T &p_value, bool &r_exists) {
-
- Element *new_parent = _data._root;
- Element *node = _data._root->left;
- C less;
-
- while (node != _data._nil) {
-
- new_parent = node;
-
- if (less(p_value, node->value))
- node = node->left;
- else if (less(node->value, p_value))
- node = node->right;
- else {
- r_exists = true;
- return node;
- }
- }
-
- r_exists = false;
+ void _insert_rb_fix(Element *p_new_node) {
- Element *new_node = memnew_allocator(Element, A);
- new_node->parent = new_parent;
- new_node->right = _data._nil;
- new_node->left = _data._nil;
- new_node->value = p_value;
- //new_node->data=_data;
-
- if (new_parent == _data._root || less(p_value, new_parent->value)) {
- new_parent->left = new_node;
- } else {
- new_parent->right = new_node;
- }
-
- new_node->_next = _successor(new_node);
- new_node->_prev = _predecessor(new_node);
- if (new_node->_next)
- new_node->_next->_prev = new_node;
- if (new_node->_prev)
- new_node->_prev->_next = new_node;
-
- return new_node;
- }
-
- Element *_insert_rb(const T &p_value) {
-
- bool exists = false;
- Element *new_node = _insert(p_value, exists);
- if (exists)
- return new_node;
-
- _data.size_cache++;
- Element *node = new_node;
+ Element *node = p_new_node;
Element *nparent = node->parent;
Element *ngrand_parent;
while (nparent->color == RED) {
-
ngrand_parent = nparent->parent;
if (nparent == ngrand_parent->left) {
@@ -365,11 +312,53 @@ private:
}
_set_color(_data._root->left, BLACK);
+ }
+
+ Element *_insert(const T &p_value) {
+
+ Element *new_parent = _data._root;
+ Element *node = _data._root->left;
+ C less;
+
+ while (node != _data._nil) {
+
+ new_parent = node;
+
+ if (less(p_value, node->value))
+ node = node->left;
+ else if (less(node->value, p_value))
+ node = node->right;
+ else {
+ return node; // Return existing node
+ }
+ }
+ Element *new_node = memnew_allocator(Element, A);
+ new_node->parent = new_parent;
+ new_node->right = _data._nil;
+ new_node->left = _data._nil;
+ new_node->value = p_value;
+ //new_node->data=_data;
+
+ if (new_parent == _data._root || less(p_value, new_parent->value)) {
+ new_parent->left = new_node;
+ } else {
+ new_parent->right = new_node;
+ }
+
+ new_node->_next = _successor(new_node);
+ new_node->_prev = _predecessor(new_node);
+ if (new_node->_next)
+ new_node->_next->_prev = new_node;
+ if (new_node->_prev)
+ new_node->_prev->_next = new_node;
+
+ _data.size_cache++;
+ _insert_rb_fix(new_node);
return new_node;
}
- void _erase_fix(Element *p_node) {
+ void _erase_fix_rb(Element *p_node) {
Element *root = _data._root->left;
Element *node = _data._nil;
@@ -450,7 +439,7 @@ private:
node->parent = rp->parent;
_set_color(node, BLACK);
} else if (rp->color == BLACK && rp->parent != _data._root) {
- _erase_fix(sibling);
+ _erase_fix_rb(sibling);
}
if (rp != p_node) {
@@ -485,11 +474,12 @@ private:
void _calculate_depth(Element *p_element, int &max_d, int d) const {
- if (p_element == _data._nil) {
+ if (p_element == _data._nil)
return;
- }
+
_calculate_depth(p_element->left, max_d, d + 1);
_calculate_depth(p_element->right, max_d, d + 1);
+
if (d > max_d)
max_d = d;
}
@@ -533,10 +523,13 @@ public:
return res;
}
+ Element *lower_bound(const T &p_value) const {
+
+ return _lower_bound(p_value);
+ }
+
bool has(const T &p_value) const {
- if (!_data._root)
- return false;
return find(p_value) != NULL;
}
@@ -544,7 +537,7 @@ public:
if (!_data._root)
_data._create_root();
- return _insert_rb(p_value);
+ return _insert(p_value);
}
void erase(Element *p_element) {
@@ -602,11 +595,6 @@ public:
return e;
}
- Element *lower_bound(const T &p_value) const {
-
- return _lower_bound(p_value);
- }
-
inline int size() const { return _data.size_cache; }
int calculate_depth() const {