Restoring authorship annotation for <[email protected]>. Commit 1 of 2.

1 files changed, 291 insertions, 291 deletions

diff --git a/contrib/libs/jemalloc/src/rtree.c b/contrib/libs/jemalloc/src/rtree.c
index 4ae41fe2fec..87f385e3b4f 100644
--- a/contrib/libs/jemalloc/src/rtree.c
+++ b/contrib/libs/jemalloc/src/rtree.c
@@ -1,320 +1,320 @@
-#define JEMALLOC_RTREE_C_
-#include "jemalloc/internal/jemalloc_preamble.h"
-#include "jemalloc/internal/jemalloc_internal_includes.h"
+#define JEMALLOC_RTREE_C_ 
+#include "jemalloc/internal/jemalloc_preamble.h" 
+#include "jemalloc/internal/jemalloc_internal_includes.h" 
 
-#include "jemalloc/internal/assert.h"
-#include "jemalloc/internal/mutex.h"
+#include "jemalloc/internal/assert.h" 
+#include "jemalloc/internal/mutex.h" 
 
-/*
- * Only the most significant bits of keys passed to rtree_{read,write}() are
- * used.
- */
-bool
-rtree_new(rtree_t *rtree, bool zeroed) {
-#ifdef JEMALLOC_JET
-	if (!zeroed) {
-		memset(rtree, 0, sizeof(rtree_t)); /* Clear root. */
-	}
-#else
-	assert(zeroed);
-#endif
+/* 
+ * Only the most significant bits of keys passed to rtree_{read,write}() are 
+ * used. 
+ */ 
+bool 
+rtree_new(rtree_t *rtree, bool zeroed) { 
+#ifdef JEMALLOC_JET 
+	if (!zeroed) { 
+		memset(rtree, 0, sizeof(rtree_t)); /* Clear root. */ 
+	} 
+#else 
+	assert(zeroed); 
+#endif 
 
-	if (malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE,
-	    malloc_mutex_rank_exclusive)) {
-		return true;
+	if (malloc_mutex_init(&rtree->init_lock, "rtree", WITNESS_RANK_RTREE, 
+	    malloc_mutex_rank_exclusive)) { 
+		return true; 
 	}
 
-	return false;
-}
-
-static rtree_node_elm_t *
-rtree_node_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
-	return (rtree_node_elm_t *)base_alloc(tsdn, b0get(), nelms *
-	    sizeof(rtree_node_elm_t), CACHELINE);
-}
-rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc = rtree_node_alloc_impl;
-
-static void
-rtree_node_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *node) {
-	/* Nodes are never deleted during normal operation. */
-	not_reached();
-}
-rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc =
-    rtree_node_dalloc_impl;
+	return false; 
+} 
 
-static rtree_leaf_elm_t *
-rtree_leaf_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) {
-	return (rtree_leaf_elm_t *)base_alloc(tsdn, b0get(), nelms *
-	    sizeof(rtree_leaf_elm_t), CACHELINE);
-}
-rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc = rtree_leaf_alloc_impl;
-
-static void
-rtree_leaf_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *leaf) {
-	/* Leaves are never deleted during normal operation. */
-	not_reached();
-}
-rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc =
-    rtree_leaf_dalloc_impl;
-
-#ifdef JEMALLOC_JET
-#  if RTREE_HEIGHT > 1
-static void
-rtree_delete_subtree(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *subtree,
-    unsigned level) {
-	size_t nchildren = ZU(1) << rtree_levels[level].bits;
-	if (level + 2 < RTREE_HEIGHT) {
-		for (size_t i = 0; i < nchildren; i++) {
-			rtree_node_elm_t *node =
-			    (rtree_node_elm_t *)atomic_load_p(&subtree[i].child,
-			    ATOMIC_RELAXED);
-			if (node != NULL) {
-				rtree_delete_subtree(tsdn, rtree, node, level +
-				    1);
-			}
-		}
-	} else {
-		for (size_t i = 0; i < nchildren; i++) {
-			rtree_leaf_elm_t *leaf =
-			    (rtree_leaf_elm_t *)atomic_load_p(&subtree[i].child,
-			    ATOMIC_RELAXED);
-			if (leaf != NULL) {
-				rtree_leaf_dalloc(tsdn, rtree, leaf);
-			}
-		}
+static rtree_node_elm_t * 
+rtree_node_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 
+	return (rtree_node_elm_t *)base_alloc(tsdn, b0get(), nelms * 
+	    sizeof(rtree_node_elm_t), CACHELINE); 
+} 
+rtree_node_alloc_t *JET_MUTABLE rtree_node_alloc = rtree_node_alloc_impl; 
+ 
+static void 
+rtree_node_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *node) { 
+	/* Nodes are never deleted during normal operation. */ 
+	not_reached(); 
+} 
+rtree_node_dalloc_t *JET_MUTABLE rtree_node_dalloc = 
+    rtree_node_dalloc_impl; 
+ 
+static rtree_leaf_elm_t * 
+rtree_leaf_alloc_impl(tsdn_t *tsdn, rtree_t *rtree, size_t nelms) { 
+	return (rtree_leaf_elm_t *)base_alloc(tsdn, b0get(), nelms * 
+	    sizeof(rtree_leaf_elm_t), CACHELINE); 
+} 
+rtree_leaf_alloc_t *JET_MUTABLE rtree_leaf_alloc = rtree_leaf_alloc_impl; 
+ 
+static void 
+rtree_leaf_dalloc_impl(tsdn_t *tsdn, rtree_t *rtree, rtree_leaf_elm_t *leaf) { 
+	/* Leaves are never deleted during normal operation. */ 
+	not_reached(); 
+} 
+rtree_leaf_dalloc_t *JET_MUTABLE rtree_leaf_dalloc = 
+    rtree_leaf_dalloc_impl; 
+ 
+#ifdef JEMALLOC_JET 
+#  if RTREE_HEIGHT > 1 
+static void 
+rtree_delete_subtree(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *subtree, 
+    unsigned level) { 
+	size_t nchildren = ZU(1) << rtree_levels[level].bits; 
+	if (level + 2 < RTREE_HEIGHT) { 
+		for (size_t i = 0; i < nchildren; i++) { 
+			rtree_node_elm_t *node = 
+			    (rtree_node_elm_t *)atomic_load_p(&subtree[i].child, 
+			    ATOMIC_RELAXED); 
+			if (node != NULL) { 
+				rtree_delete_subtree(tsdn, rtree, node, level + 
+				    1); 
+			} 
+		} 
+	} else { 
+		for (size_t i = 0; i < nchildren; i++) { 
+			rtree_leaf_elm_t *leaf = 
+			    (rtree_leaf_elm_t *)atomic_load_p(&subtree[i].child, 
+			    ATOMIC_RELAXED); 
+			if (leaf != NULL) { 
+				rtree_leaf_dalloc(tsdn, rtree, leaf); 
+			} 
+		} 
 	}
 
-	if (subtree != rtree->root) {
-		rtree_node_dalloc(tsdn, rtree, subtree);
+	if (subtree != rtree->root) { 
+		rtree_node_dalloc(tsdn, rtree, subtree); 
 	}
-}
-#  endif
+} 
+#  endif 
 
-void
-rtree_delete(tsdn_t *tsdn, rtree_t *rtree) {
-#  if RTREE_HEIGHT > 1
-	rtree_delete_subtree(tsdn, rtree, rtree->root, 0);
-#  endif
+void 
+rtree_delete(tsdn_t *tsdn, rtree_t *rtree) { 
+#  if RTREE_HEIGHT > 1 
+	rtree_delete_subtree(tsdn, rtree, rtree->root, 0); 
+#  endif 
 }
-#endif
+#endif 
 
-static rtree_node_elm_t *
-rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level,
-    atomic_p_t *elmp) {
-	malloc_mutex_lock(tsdn, &rtree->init_lock);
-	/*
-	 * If *elmp is non-null, then it was initialized with the init lock
-	 * held, so we can get by with 'relaxed' here.
-	 */
-	rtree_node_elm_t *node = atomic_load_p(elmp, ATOMIC_RELAXED);
-	if (node == NULL) {
-		node = rtree_node_alloc(tsdn, rtree, ZU(1) <<
-		    rtree_levels[level].bits);
-		if (node == NULL) {
-			malloc_mutex_unlock(tsdn, &rtree->init_lock);
-			return NULL;
-		}
-		/*
-		 * Even though we hold the lock, a later reader might not; we
-		 * need release semantics.
-		 */
-		atomic_store_p(elmp, node, ATOMIC_RELEASE);
-	}
-	malloc_mutex_unlock(tsdn, &rtree->init_lock);
+static rtree_node_elm_t * 
+rtree_node_init(tsdn_t *tsdn, rtree_t *rtree, unsigned level, 
+    atomic_p_t *elmp) { 
+	malloc_mutex_lock(tsdn, &rtree->init_lock); 
+	/* 
+	 * If *elmp is non-null, then it was initialized with the init lock 
+	 * held, so we can get by with 'relaxed' here. 
+	 */ 
+	rtree_node_elm_t *node = atomic_load_p(elmp, ATOMIC_RELAXED); 
+	if (node == NULL) { 
+		node = rtree_node_alloc(tsdn, rtree, ZU(1) << 
+		    rtree_levels[level].bits); 
+		if (node == NULL) { 
+			malloc_mutex_unlock(tsdn, &rtree->init_lock); 
+			return NULL; 
+		} 
+		/* 
+		 * Even though we hold the lock, a later reader might not; we 
+		 * need release semantics. 
+		 */ 
+		atomic_store_p(elmp, node, ATOMIC_RELEASE); 
+	} 
+	malloc_mutex_unlock(tsdn, &rtree->init_lock); 
 
-	return node;
-}
+	return node; 
+} 
 
-static rtree_leaf_elm_t *
-rtree_leaf_init(tsdn_t *tsdn, rtree_t *rtree, atomic_p_t *elmp) {
-	malloc_mutex_lock(tsdn, &rtree->init_lock);
-	/*
-	 * If *elmp is non-null, then it was initialized with the init lock
-	 * held, so we can get by with 'relaxed' here.
-	 */
-	rtree_leaf_elm_t *leaf = atomic_load_p(elmp, ATOMIC_RELAXED);
-	if (leaf == NULL) {
-		leaf = rtree_leaf_alloc(tsdn, rtree, ZU(1) <<
-		    rtree_levels[RTREE_HEIGHT-1].bits);
-		if (leaf == NULL) {
-			malloc_mutex_unlock(tsdn, &rtree->init_lock);
-			return NULL;
+static rtree_leaf_elm_t * 
+rtree_leaf_init(tsdn_t *tsdn, rtree_t *rtree, atomic_p_t *elmp) { 
+	malloc_mutex_lock(tsdn, &rtree->init_lock); 
+	/* 
+	 * If *elmp is non-null, then it was initialized with the init lock 
+	 * held, so we can get by with 'relaxed' here. 
+	 */ 
+	rtree_leaf_elm_t *leaf = atomic_load_p(elmp, ATOMIC_RELAXED); 
+	if (leaf == NULL) { 
+		leaf = rtree_leaf_alloc(tsdn, rtree, ZU(1) << 
+		    rtree_levels[RTREE_HEIGHT-1].bits); 
+		if (leaf == NULL) { 
+			malloc_mutex_unlock(tsdn, &rtree->init_lock); 
+			return NULL; 
 		}
-		/*
-		 * Even though we hold the lock, a later reader might not; we
-		 * need release semantics.
-		 */
-		atomic_store_p(elmp, leaf, ATOMIC_RELEASE);
-	}
-	malloc_mutex_unlock(tsdn, &rtree->init_lock);
-
-	return leaf;
-}
-
-static bool
-rtree_node_valid(rtree_node_elm_t *node) {
-	return ((uintptr_t)node != (uintptr_t)0);
-}
-
-static bool
-rtree_leaf_valid(rtree_leaf_elm_t *leaf) {
-	return ((uintptr_t)leaf != (uintptr_t)0);
-}
-
-static rtree_node_elm_t *
-rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) {
-	rtree_node_elm_t *node;
-
-	if (dependent) {
-		node = (rtree_node_elm_t *)atomic_load_p(&elm->child,
-		    ATOMIC_RELAXED);
-	} else {
-		node = (rtree_node_elm_t *)atomic_load_p(&elm->child,
-		    ATOMIC_ACQUIRE);
+		/* 
+		 * Even though we hold the lock, a later reader might not; we 
+		 * need release semantics. 
+		 */ 
+		atomic_store_p(elmp, leaf, ATOMIC_RELEASE); 
 	}
-
-	assert(!dependent || node != NULL);
-	return node;
+	malloc_mutex_unlock(tsdn, &rtree->init_lock); 
+ 
+	return leaf; 
 }
 
-static rtree_node_elm_t *
-rtree_child_node_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm,
-    unsigned level, bool dependent) {
-	rtree_node_elm_t *node;
+static bool 
+rtree_node_valid(rtree_node_elm_t *node) { 
+	return ((uintptr_t)node != (uintptr_t)0); 
+} 
 
-	node = rtree_child_node_tryread(elm, dependent);
-	if (!dependent && unlikely(!rtree_node_valid(node))) {
-		node = rtree_node_init(tsdn, rtree, level + 1, &elm->child);
-	}
-	assert(!dependent || node != NULL);
-	return node;
+static bool 
+rtree_leaf_valid(rtree_leaf_elm_t *leaf) { 
+	return ((uintptr_t)leaf != (uintptr_t)0); 
 }
 
-static rtree_leaf_elm_t *
-rtree_child_leaf_tryread(rtree_node_elm_t *elm, bool dependent) {
-	rtree_leaf_elm_t *leaf;
+static rtree_node_elm_t * 
+rtree_child_node_tryread(rtree_node_elm_t *elm, bool dependent) { 
+	rtree_node_elm_t *node; 
 
-	if (dependent) {
-		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child,
-		    ATOMIC_RELAXED);
-	} else {
-		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child,
-		    ATOMIC_ACQUIRE);
-	}
-
-	assert(!dependent || leaf != NULL);
-	return leaf;
+	if (dependent) { 
+		node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 
+		    ATOMIC_RELAXED); 
+	} else { 
+		node = (rtree_node_elm_t *)atomic_load_p(&elm->child, 
+		    ATOMIC_ACQUIRE); 
+	} 
+ 
+	assert(!dependent || node != NULL); 
+	return node; 
 }
 
-static rtree_leaf_elm_t *
-rtree_child_leaf_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm,
-    unsigned level, bool dependent) {
-	rtree_leaf_elm_t *leaf;
+static rtree_node_elm_t * 
+rtree_child_node_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 
+    unsigned level, bool dependent) { 
+	rtree_node_elm_t *node; 
 
-	leaf = rtree_child_leaf_tryread(elm, dependent);
-	if (!dependent && unlikely(!rtree_leaf_valid(leaf))) {
-		leaf = rtree_leaf_init(tsdn, rtree, &elm->child);
-	}
-	assert(!dependent || leaf != NULL);
-	return leaf;
+	node = rtree_child_node_tryread(elm, dependent); 
+	if (!dependent && unlikely(!rtree_node_valid(node))) { 
+		node = rtree_node_init(tsdn, rtree, level + 1, &elm->child); 
+	} 
+	assert(!dependent || node != NULL); 
+	return node; 
 }
 
-rtree_leaf_elm_t *
-rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx,
-    uintptr_t key, bool dependent, bool init_missing) {
-	rtree_node_elm_t *node;
-	rtree_leaf_elm_t *leaf;
-#if RTREE_HEIGHT > 1
-	node = rtree->root;
-#else
-	leaf = rtree->root;
-#endif
-
-	if (config_debug) {
-		uintptr_t leafkey = rtree_leafkey(key);
-		for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) {
-			assert(rtree_ctx->cache[i].leafkey != leafkey);
-		}
-		for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) {
-			assert(rtree_ctx->l2_cache[i].leafkey != leafkey);
-		}
-	}
-
-#define RTREE_GET_CHILD(level) {					\
-		assert(level < RTREE_HEIGHT-1);				\
-		if (level != 0 && !dependent &&				\
-		    unlikely(!rtree_node_valid(node))) {		\
-			return NULL;					\
-		}							\
-		uintptr_t subkey = rtree_subkey(key, level);		\
-		if (level + 2 < RTREE_HEIGHT) {				\
-			node = init_missing ?				\
-			    rtree_child_node_read(tsdn, rtree,		\
-			    &node[subkey], level, dependent) :		\
-			    rtree_child_node_tryread(&node[subkey],	\
-			    dependent);					\
-		} else {						\
-			leaf = init_missing ?				\
-			    rtree_child_leaf_read(tsdn, rtree,		\
-			    &node[subkey], level, dependent) :		\
-			    rtree_child_leaf_tryread(&node[subkey],	\
-			    dependent);					\
-		}							\
-	}
-	/*
-	 * Cache replacement upon hard lookup (i.e. L1 & L2 rtree cache miss):
-	 * (1) evict last entry in L2 cache; (2) move the collision slot from L1
-	 * cache down to L2; and 3) fill L1.
-	 */
-#define RTREE_GET_LEAF(level) {						\
-		assert(level == RTREE_HEIGHT-1);			\
-		if (!dependent && unlikely(!rtree_leaf_valid(leaf))) {	\
-			return NULL;					\
-		}							\
-		if (RTREE_CTX_NCACHE_L2 > 1) {				\
-			memmove(&rtree_ctx->l2_cache[1],		\
-			    &rtree_ctx->l2_cache[0],			\
-			    sizeof(rtree_ctx_cache_elm_t) *		\
-			    (RTREE_CTX_NCACHE_L2 - 1));			\
-		}							\
-		size_t slot = rtree_cache_direct_map(key);		\
-		rtree_ctx->l2_cache[0].leafkey =			\
-		    rtree_ctx->cache[slot].leafkey;			\
-		rtree_ctx->l2_cache[0].leaf =				\
-		    rtree_ctx->cache[slot].leaf;			\
-		uintptr_t leafkey = rtree_leafkey(key);			\
-		rtree_ctx->cache[slot].leafkey = leafkey;		\
-		rtree_ctx->cache[slot].leaf = leaf;			\
-		uintptr_t subkey = rtree_subkey(key, level);		\
-		return &leaf[subkey];					\
-	}
-	if (RTREE_HEIGHT > 1) {
-		RTREE_GET_CHILD(0)
-	}
-	if (RTREE_HEIGHT > 2) {
-		RTREE_GET_CHILD(1)
-	}
-	if (RTREE_HEIGHT > 3) {
-		for (unsigned i = 2; i < RTREE_HEIGHT-1; i++) {
-			RTREE_GET_CHILD(i)
-		}
-	}
-	RTREE_GET_LEAF(RTREE_HEIGHT-1)
-#undef RTREE_GET_CHILD
-#undef RTREE_GET_LEAF
-	not_reached();
-}
+static rtree_leaf_elm_t * 
+rtree_child_leaf_tryread(rtree_node_elm_t *elm, bool dependent) { 
+	rtree_leaf_elm_t *leaf; 
 
-void
-rtree_ctx_data_init(rtree_ctx_t *ctx) {
-	for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) {
-		rtree_ctx_cache_elm_t *cache = &ctx->cache[i];
-		cache->leafkey = RTREE_LEAFKEY_INVALID;
-		cache->leaf = NULL;
-	}
-	for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) {
-		rtree_ctx_cache_elm_t *cache = &ctx->l2_cache[i];
-		cache->leafkey = RTREE_LEAFKEY_INVALID;
-		cache->leaf = NULL;
-	}
+	if (dependent) { 
+		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 
+		    ATOMIC_RELAXED); 
+	} else { 
+		leaf = (rtree_leaf_elm_t *)atomic_load_p(&elm->child, 
+		    ATOMIC_ACQUIRE); 
+	} 
+ 
+	assert(!dependent || leaf != NULL); 
+	return leaf; 
 }
+ 
+static rtree_leaf_elm_t * 
+rtree_child_leaf_read(tsdn_t *tsdn, rtree_t *rtree, rtree_node_elm_t *elm, 
+    unsigned level, bool dependent) { 
+	rtree_leaf_elm_t *leaf; 
+ 
+	leaf = rtree_child_leaf_tryread(elm, dependent); 
+	if (!dependent && unlikely(!rtree_leaf_valid(leaf))) { 
+		leaf = rtree_leaf_init(tsdn, rtree, &elm->child); 
+	} 
+	assert(!dependent || leaf != NULL); 
+	return leaf; 
+} 
+ 
+rtree_leaf_elm_t * 
+rtree_leaf_elm_lookup_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_ctx_t *rtree_ctx, 
+    uintptr_t key, bool dependent, bool init_missing) { 
+	rtree_node_elm_t *node; 
+	rtree_leaf_elm_t *leaf; 
+#if RTREE_HEIGHT > 1 
+	node = rtree->root; 
+#else 
+	leaf = rtree->root; 
+#endif 
+ 
+	if (config_debug) { 
+		uintptr_t leafkey = rtree_leafkey(key); 
+		for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 
+			assert(rtree_ctx->cache[i].leafkey != leafkey); 
+		} 
+		for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 
+			assert(rtree_ctx->l2_cache[i].leafkey != leafkey); 
+		} 
+	} 
+ 
+#define RTREE_GET_CHILD(level) {					\ 
+		assert(level < RTREE_HEIGHT-1);				\ 
+		if (level != 0 && !dependent &&				\ 
+		    unlikely(!rtree_node_valid(node))) {		\ 
+			return NULL;					\ 
+		}							\ 
+		uintptr_t subkey = rtree_subkey(key, level);		\ 
+		if (level + 2 < RTREE_HEIGHT) {				\ 
+			node = init_missing ?				\ 
+			    rtree_child_node_read(tsdn, rtree,		\ 
+			    &node[subkey], level, dependent) :		\ 
+			    rtree_child_node_tryread(&node[subkey],	\ 
+			    dependent);					\ 
+		} else {						\ 
+			leaf = init_missing ?				\ 
+			    rtree_child_leaf_read(tsdn, rtree,		\ 
+			    &node[subkey], level, dependent) :		\ 
+			    rtree_child_leaf_tryread(&node[subkey],	\ 
+			    dependent);					\ 
+		}							\ 
+	} 
+	/* 
+	 * Cache replacement upon hard lookup (i.e. L1 & L2 rtree cache miss): 
+	 * (1) evict last entry in L2 cache; (2) move the collision slot from L1 
+	 * cache down to L2; and 3) fill L1. 
+	 */ 
+#define RTREE_GET_LEAF(level) {						\ 
+		assert(level == RTREE_HEIGHT-1);			\ 
+		if (!dependent && unlikely(!rtree_leaf_valid(leaf))) {	\ 
+			return NULL;					\ 
+		}							\ 
+		if (RTREE_CTX_NCACHE_L2 > 1) {				\ 
+			memmove(&rtree_ctx->l2_cache[1],		\ 
+			    &rtree_ctx->l2_cache[0],			\ 
+			    sizeof(rtree_ctx_cache_elm_t) *		\ 
+			    (RTREE_CTX_NCACHE_L2 - 1));			\ 
+		}							\ 
+		size_t slot = rtree_cache_direct_map(key);		\ 
+		rtree_ctx->l2_cache[0].leafkey =			\ 
+		    rtree_ctx->cache[slot].leafkey;			\ 
+		rtree_ctx->l2_cache[0].leaf =				\ 
+		    rtree_ctx->cache[slot].leaf;			\ 
+		uintptr_t leafkey = rtree_leafkey(key);			\ 
+		rtree_ctx->cache[slot].leafkey = leafkey;		\ 
+		rtree_ctx->cache[slot].leaf = leaf;			\ 
+		uintptr_t subkey = rtree_subkey(key, level);		\ 
+		return &leaf[subkey];					\ 
+	} 
+	if (RTREE_HEIGHT > 1) { 
+		RTREE_GET_CHILD(0) 
+	} 
+	if (RTREE_HEIGHT > 2) { 
+		RTREE_GET_CHILD(1) 
+	} 
+	if (RTREE_HEIGHT > 3) { 
+		for (unsigned i = 2; i < RTREE_HEIGHT-1; i++) { 
+			RTREE_GET_CHILD(i) 
+		} 
+	} 
+	RTREE_GET_LEAF(RTREE_HEIGHT-1) 
+#undef RTREE_GET_CHILD 
+#undef RTREE_GET_LEAF 
+	not_reached(); 
+} 
+ 
+void 
+rtree_ctx_data_init(rtree_ctx_t *ctx) { 
+	for (unsigned i = 0; i < RTREE_CTX_NCACHE; i++) { 
+		rtree_ctx_cache_elm_t *cache = &ctx->cache[i]; 
+		cache->leafkey = RTREE_LEAFKEY_INVALID; 
+		cache->leaf = NULL; 
+	} 
+	for (unsigned i = 0; i < RTREE_CTX_NCACHE_L2; i++) { 
+		rtree_ctx_cache_elm_t *cache = &ctx->l2_cache[i]; 
+		cache->leafkey = RTREE_LEAFKEY_INVALID; 
+		cache->leaf = NULL; 
+	} 
+}