[RFC] [PATCH] talloc: Look up parents in O(1) time instead of O(n).

[Kenneth Graunke]

Previously, only parent->child (the head of the list of children)
pointed to its parent; the others had a parent pointer of NULL.  This
meant that one had to traverse the list in reverse to find a parent.

The tradeoff is that talloc_realloc now must update all children's
parent pointers.
---
 lib/talloc/talloc.c |   30 ++++++++++--------------------
 1 files changed, 10 insertions(+), 20 deletions(-)

diff --git a/lib/talloc/talloc.c b/lib/talloc/talloc.c
index bd364ed..ea8809d 100644
--- a/lib/talloc/talloc.c
+++ b/lib/talloc/talloc.c
@@ -286,7 +286,6 @@ static inline struct talloc_chunk *talloc_parent_chunk(const void *ptr)
 	}
 
 	tc = talloc_chunk_from_ptr(ptr);
-	while (tc->prev) tc=tc->prev;
 
 	return tc->parent;
 }
@@ -418,7 +417,6 @@ static inline void *__talloc(const void *context, size_t size)
 		struct talloc_chunk *parent = talloc_chunk_from_ptr(context);
 
 		if (parent->child) {
-			parent->child->parent = NULL;
 			tc->next = parent->child;
 			tc->next->prev = tc;
 		} else {
@@ -722,7 +720,6 @@ static void *_talloc_steal_internal(const void *new_ctx, const void *ptr)
 	}
 
 	tc->parent = new_tc;
-	if (new_tc->child) new_tc->child->parent = NULL;
 	_TLIST_ADD(new_tc->child, tc);
 
 	return discard_const_p(void, ptr);
@@ -1157,6 +1154,8 @@ _PUBLIC_ int _talloc_free(void *ptr, const char *location)
 _PUBLIC_ void *_talloc_realloc(const void *context, void *ptr, size_t size, const char *name)
 {
 	struct talloc_chunk *tc;
+	struct talloc_chunk *old_tc;
+	struct talloc_chunk *child;
 	void *new_ptr;
 	bool malloced = false;
 
@@ -1175,7 +1174,7 @@ _PUBLIC_ void *_talloc_realloc(const void *context, void *ptr, size_t size, cons
 		return _talloc_named_const(context, size, name);
 	}
 
-	tc = talloc_chunk_from_ptr(ptr);
+	tc = old_tc = talloc_chunk_from_ptr(ptr);
 
 	/* don't allow realloc on referenced pointers */
 	if (unlikely(tc->refs)) {
@@ -1232,11 +1231,11 @@ _PUBLIC_ void *_talloc_realloc(const void *context, void *ptr, size_t size, cons
 	if (malloced) {
 		tc->flags &= ~TALLOC_FLAG_POOLMEM;
 	}
-	if (tc->parent) {
+	if (tc->parent && tc->parent->child == old_tc) {
 		tc->parent->child = tc;
 	}
-	if (tc->child) {
-		tc->child->parent = tc;
+	for (child = tc->child; child; child = child->next) {
+		child->parent = tc;
 	}
 
 	if (tc->prev) {
@@ -1954,10 +1953,7 @@ _PUBLIC_ void *talloc_find_parent_byname(const void *context, const char *name)
 		if (tc->name && strcmp(tc->name, name) == 0) {
 			return TC_PTR_FROM_CHUNK(tc);
 		}
-		while (tc && tc->prev) tc = tc->prev;
-		if (tc) {
-			tc = tc->parent;
-		}
+		tc = tc->parent;
 	}
 	return NULL;
 }
@@ -1978,10 +1974,7 @@ _PUBLIC_ void talloc_show_parents(const void *context, FILE *file)
 	fprintf(file, "talloc parents of '%s'\n", talloc_get_name(context));
 	while (tc) {
 		fprintf(file, "\t'%s'\n", talloc_get_name(TC_PTR_FROM_CHUNK(tc)));
-		while (tc && tc->prev) tc = tc->prev;
-		if (tc) {
-			tc = tc->parent;
-		}
+		tc = tc->parent;
 	}
 	fflush(file);
 }
@@ -2000,11 +1993,8 @@ static int _talloc_is_parent(const void *context, const void *ptr, int depth)
 	tc = talloc_chunk_from_ptr(context);
 	while (tc && depth > 0) {
 		if (TC_PTR_FROM_CHUNK(tc) == ptr) return 1;
-		while (tc && tc->prev) tc = tc->prev;
-		if (tc) {
-			tc = tc->parent;
-			depth--;
-		}
+		tc = tc->parent;
+		depth--;
 	}
 	return 0;
 }
-- 
1.7.1