Restructure dbwrap_rbt

In this low-level code, play tricks to reduce the number of allocations to the
possible minimum. I would not recommend this for higher-level code, but here it
pays off.
(This used to be commit 71b1e6ff1595fbaa8dd49b996c45541531c7e98c)

1 files changed, 127 insertions, 59 deletions

diff --git a/source3/lib/dbwrap_rbt.c b/source3/lib/dbwrap_rbt.c
index 93d73f29d1..633b695b52 100644
--- a/source3/lib/dbwrap_rbt.c
+++ b/source3/lib/dbwrap_rbt.c
@@ -1,7 +1,7 @@
 /*
    Unix SMB/CIFS implementation.
    Database interface wrapper around red-black trees
-   Copyright (C) Volker Lendecke 2007
+   Copyright (C) Volker Lendecke 2007, 2008
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -20,6 +20,8 @@
 #include "includes.h"
 #include "rbtree.h"
 
+#define ALIGN(_size_) (((_size_)+15)&~15)
+
 struct db_rbt_ctx {
 	struct rb_root tree;
 };
@@ -44,6 +46,35 @@ struct db_rbt_node {
 };
 
 /*
+ * Hide the ugly pointer calculations in a function
+ */
+
+static struct db_rbt_node *db_rbt2node(struct rb_node *node)
+{
+	return (struct db_rbt_node *)
+		((char *)node - offsetof(struct db_rbt_node, rb_node));
+}
+
+/*
+ * Compare two keys
+ */
+
+static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
+{
+	int res;
+
+	res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
+
+	if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
+		return -1;
+	}
+	if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
+		return 1;
+	}
+	return 0;
+}
+
+/*
  * dissect a db_rbt_node into its implicit key and value parts
  */
 
@@ -58,9 +89,7 @@ static void db_rbt_parse_node(struct db_rbt_node *node,
 
 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 {
-	struct db_rbt_rec *rec_priv = talloc_get_type_abort(
-		rec->private_data, struct db_rbt_rec);
-
+	struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 	struct db_rbt_node *node;
 
 	struct rb_node ** p;
@@ -133,22 +162,16 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 
 		parent = (*p);
 
-		r = (struct db_rbt_node *)
-			((char *)(*p) - offsetof(struct db_rbt_node, rb_node));
+		r = db_rbt2node(*p);
 
 		db_rbt_parse_node(r, &search_key, &search_val);
 
-		res = memcmp(this_key.dptr, search_key.dptr,
-			     MIN(this_key.dsize, search_key.dsize));
+		res = db_rbt_compare(this_key, search_key);
 
-		if ((res < 0)
-		    || ((res == 0)
-			&& (this_key.dsize < search_key.dsize))) {
+		if (res == -1) {
 			p = &(*p)->rb_left;
 		}
-		else if ((res > 0)
-			 || ((res == 0)
-			     && (this_key.dsize > search_key.dsize))) {
+		else if (res == 1) {
 			p = &(*p)->rb_right;
 		}
 		else {
@@ -164,8 +187,7 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
 
 static NTSTATUS db_rbt_delete(struct db_record *rec)
 {
-	struct db_rbt_rec *rec_priv = talloc_get_type_abort(
-		rec->private_data, struct db_rbt_rec);
+	struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
 
 	if (rec_priv->node == NULL) {
 		return NT_STATUS_OK;
@@ -187,85 +209,128 @@ static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
 	struct db_rbt_rec *rec_priv;
 	struct db_record *result;
 	struct rb_node *n;
+	size_t size;
+	bool found = false;
+	struct db_rbt_node *r = NULL;
+	TDB_DATA search_key = tdb_null, search_val = tdb_null;
 
-	result = talloc(mem_ctx, struct db_record);
+	n = ctx->tree.rb_node;
 
-	if (result == NULL) {
-		return NULL;
+	while (n != NULL) {
+		int res;
+
+		r = db_rbt2node(n);
+
+		db_rbt_parse_node(r, &search_key, &search_val);
+
+		res = db_rbt_compare(key, search_key);
+
+		if (res == -1) {
+			n = n->rb_left;
+		}
+		else if (res == 1) {
+			n = n->rb_right;
+		}
+		else {
+			found = true;
+			break;
+		}
 	}
 
-	rec_priv = talloc(result, struct db_rbt_rec);
+	/*
+	 * In this low-level routine, play tricks to reduce the number of
+	 * tallocs to one. Not recommened for general use, but here it pays
+	 * off.
+	 */
 
-	if (rec_priv == NULL) {
-		TALLOC_FREE(result);
+	size = ALIGN(sizeof(struct db_record)) + sizeof(struct db_rbt_rec);
+
+	if (!found) {
+		/*
+		 * We need to keep the key around for later store
+		 */
+		size += key.dsize;
+	}
+
+	result = (struct db_record *)talloc_size(mem_ctx, size);
+	if (result == NULL) {
 		return NULL;
 	}
 
+	rec_priv = (struct db_rbt_rec *)
+		((char *)result + ALIGN(sizeof(struct db_record)));
 	rec_priv->db_ctx = ctx;
 
 	result->store = db_rbt_store;
 	result->delete_rec = db_rbt_delete;
 	result->private_data = rec_priv;
 
+	if (found) {
+		rec_priv->node = r;
+		result->key = search_key;
+		result->value = search_val;
+	}
+	else {
+		rec_priv->node = NULL;
+		result->key.dptr = (uint8 *)
+			((char *)rec_priv + sizeof(*rec_priv));
+		result->key.dsize = key.dsize;
+		memcpy(result->key.dptr, key.dptr, key.dsize);
+
+		result->value = tdb_null;
+	}
+
+	return result;
+}
+
+static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
+			TDB_DATA key, TDB_DATA *data)
+{
+	struct db_rbt_ctx *ctx = talloc_get_type_abort(
+		db->private_data, struct db_rbt_ctx);
+
+	struct rb_node *n;
+	bool found = false;
+	struct db_rbt_node *r = NULL;
+	TDB_DATA search_key, search_val;
+	uint8_t *result;
+
 	n = ctx->tree.rb_node;
 
 	while (n != NULL) {
-		struct db_rbt_node *r;
-		TDB_DATA search_key, search_val;
 		int res;
 
-		r = (struct db_rbt_node *)
-			((char *)n - offsetof(struct db_rbt_node, rb_node));
+		r = db_rbt2node(n);
 
 		db_rbt_parse_node(r, &search_key, &search_val);
 
-		res = memcmp(key.dptr, search_key.dptr,
-			     MIN(key.dsize, search_key.dsize));
+		res = db_rbt_compare(key, search_key);
 
-		if ((res < 0)
-		    || ((res == 0) && (key.dsize < search_key.dsize))) {
+		if (res == -1) {
 			n = n->rb_left;
 		}
-		else if ((res > 0)
-			 || ((res == 0) && (key.dsize > search_key.dsize))) {
+		else if (res == 1) {
 			n = n->rb_right;
 		}
 		else {
-			rec_priv->node = r;
-			result->key = search_key;
-			result->value = search_val;
-			return result;
+			found = true;
+			break;
 		}
 	}
 
-	result->key.dsize = key.dsize;
-	result->key.dptr = (uint8_t *)talloc_memdup(
-		result, key.dptr, key.dsize);
-
-	if (result->key.dptr == NULL) {
-		TALLOC_FREE(result);
-		return NULL;
+	if (!found) {
+		*data = tdb_null;
+		return 0;
 	}
 
-	rec_priv->node = NULL;
-	result->value.dsize = 0;
-	result->value.dptr = NULL;
-	return result;
-}
-
-static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
-			TDB_DATA key, TDB_DATA *data)
-{
-	struct db_record *rec;
-
-	if (!(rec = db->fetch_locked(db, mem_ctx, key))) {
+	result = (uint8 *)talloc_memdup(mem_ctx, search_val.dptr,
+					search_val.dsize);
+	if (result == NULL) {
 		return -1;
 	}
 
-	data->dsize = rec->value.dsize;
-	data->dptr = (uint8 *)talloc_memdup(mem_ctx, rec->value.dptr,
-					    rec->value.dsize);
-	TALLOC_FREE(rec);
+	data->dptr = result;
+	data->dsize = search_val.dsize;
 	return 0;
 }
 
@@ -275,6 +340,9 @@ static int db_rbt_traverse(struct db_context *db,
 				    void *private_data),
 			   void *private_data)
 {
+	/*
+	 * Nobody uses this so far, and unused code is broken code :-)
+	 */
 	return -1;
 }