dbwrap_rbt

This is meant as a replacement for the internal tdb. To me it seems a bit silly
that for in-memory structures we do our own memory management. With this rbt
based approach we can make use of the system-supplied malloc.
(This used to be commit 54e5d4404619443caed32e2acff8921cdbff9ed1)

3 files changed, 388 insertions, 2 deletions

diff --git a/source3/Makefile.in b/source3/Makefile.in
index 01aa236130..e636a9119f 100644
--- a/source3/Makefile.in
+++ b/source3/Makefile.in
@@ -224,8 +224,8 @@ TDBBASE_OBJ = lib/tdb/common/tdb.o lib/tdb/common/dump.o lib/tdb/common/error.o
 	lib/tdb/common/open.o lib/tdb/common/transaction.o \
 	lib/tdb/common/traverse.o
 
-TDB_OBJ = $(TDBBASE_OBJ) lib/util_tdb.o\
-	lib/dbwrap.o lib/dbwrap_tdb.o lib/dbwrap_ctdb.o
+TDB_OBJ = $(TDBBASE_OBJ) lib/util_tdb.o \
+	lib/dbwrap.o lib/dbwrap_tdb.o lib/dbwrap_ctdb.o lib/dbwrap_rbt.o
 
 SMBLDAP_OBJ = @SMBLDAP@ @SMBLDAPUTIL@
 
diff --git a/source3/lib/dbwrap_rbt.c b/source3/lib/dbwrap_rbt.c
new file mode 100644
index 0000000000..df568a0410
--- /dev/null
+++ b/source3/lib/dbwrap_rbt.c
@@ -0,0 +1,303 @@
+/*
+   Unix SMB/CIFS implementation.
+   Database interface wrapper around red-black trees
+   Copyright (C) Volker Lendecke 2007
+
+   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
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "includes.h"
+#include "rbtree.h"
+
+struct db_rbt_ctx {
+	struct rb_root tree;
+};
+
+struct db_rbt_rec {
+	struct db_rbt_ctx *db_ctx;
+	struct db_rbt_node *node;
+};
+
+/* The structure that ends up in the tree */
+
+struct db_rbt_node {
+	struct rb_node rb_node;
+	size_t keysize, valuesize;
+
+	/*
+	 * key and value are appended implicitly, "data" is only here as a
+	 * target for offsetof()
+	 */
+
+	char data[];
+};
+
+/*
+ * dissect a db_rbt_node into its implicit key and value parts
+ */
+
+static void db_rbt_parse_node(struct db_rbt_node *node,
+			      TDB_DATA *key, TDB_DATA *value)
+{
+	key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
+	key->dsize = node->keysize;
+	value->dptr = key->dptr + node->keysize;
+	value->dsize = node->valuesize;
+}
+
+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_node *node;
+
+	struct rb_node ** p;
+	struct rb_node * parent;
+
+	TDB_DATA this_key, this_val;
+
+	if (rec_priv->node != NULL) {
+
+		/*
+		 * The record was around previously
+		 */
+
+		db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
+
+		SMB_ASSERT(this_key.dsize == rec->key.dsize);
+		SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
+				  this_key.dsize) == 0);
+
+		if (this_val.dsize >= data.dsize) {
+			/*
+			 * The new value fits into the old space
+			 */
+			memcpy(this_val.dptr, data.dptr, data.dsize);
+			rec_priv->node->valuesize = data.dsize;
+			return NT_STATUS_OK;
+		}
+
+		/*
+		 * We need to delete the key from the tree and start fresh,
+		 * there's not enough space in the existing record
+		 */
+
+		rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
+		SAFE_FREE(rec_priv->node);
+	}
+
+	node = (struct db_rbt_node *)SMB_MALLOC(
+		offsetof(struct db_rbt_node, data) + rec->key.dsize
+		+ data.dsize);
+
+	if (node == NULL) {
+		return NT_STATUS_NO_MEMORY;
+	}
+
+	ZERO_STRUCT(node->rb_node);
+
+	node->keysize = rec->key.dsize;
+	node->valuesize = data.dsize;
+
+	db_rbt_parse_node(node, &this_key, &this_val);
+
+	memcpy(this_key.dptr, rec->key.dptr, node->keysize);
+	memcpy(this_val.dptr, data.dptr, node->valuesize);
+
+	parent = NULL;
+	p = &rec_priv->db_ctx->tree.rb_node;
+
+	while (*p) {
+		struct db_rbt_node *r;
+		TDB_DATA search_key, search_val;
+		int res;
+
+		parent = (*p);
+
+		r = (struct db_rbt_node *)
+			((char *)(*p) - offsetof(struct db_rbt_node, rb_node));
+
+		db_rbt_parse_node(r, &search_key, &search_val);
+
+		res = memcmp(this_key.dptr, search_key.dptr,
+			     MIN(this_key.dsize, search_key.dsize));
+
+		if ((res < 0)
+		    || ((res == 0)
+			&& (this_key.dsize < search_key.dsize))) {
+			p = &(*p)->rb_left;
+		}
+		else if ((res > 0)
+			 || ((res == 0)
+			     && (this_key.dsize > search_key.dsize))) {
+			p = &(*p)->rb_right;
+		}
+		else {
+			smb_panic("someone messed with the tree");
+		}
+	}
+
+	rb_link_node(&node->rb_node, parent, p);
+	rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
+
+	return NT_STATUS_OK;
+}
+
+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);
+
+	if (rec_priv->node == NULL) {
+		return NT_STATUS_OK;
+	}
+
+	rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
+	SAFE_FREE(rec_priv->node);
+
+	return NT_STATUS_OK;
+}
+
+static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
+					     TALLOC_CTX *mem_ctx,
+					     TDB_DATA key)
+{
+	struct db_rbt_ctx *ctx = talloc_get_type_abort(
+		db_ctx->private_data, struct db_rbt_ctx);
+
+	struct db_rbt_rec *rec_priv;
+	struct db_record *result;
+	struct rb_node *n;
+
+	result = talloc(mem_ctx, struct db_record);
+
+	if (result == NULL) {
+		return NULL;
+	}
+
+	rec_priv = talloc(result, struct db_rbt_rec);
+
+	if (rec_priv == NULL) {
+		TALLOC_FREE(result);
+		return NULL;
+	}
+
+	rec_priv->db_ctx = ctx;
+
+	result->store = db_rbt_store;
+	result->delete_rec = db_rbt_delete;
+	result->private_data = rec_priv;
+
+	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));
+
+		db_rbt_parse_node(r, &search_key, &search_val);
+
+		res = memcmp(key.dptr, search_key.dptr,
+			     MIN(key.dsize, search_key.dsize));
+
+		if ((res < 0)
+		    || ((res == 0) && (key.dsize < search_key.dsize))) {
+			n = n->rb_left;
+		}
+		else if ((res > 0)
+			 || ((res == 0) && (key.dsize > search_key.dsize))) {
+			n = n->rb_right;
+		}
+		else {
+			rec_priv->node = r;
+			result->key = search_key;
+			result->value = search_val;
+			return result;
+		}
+	}
+
+	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;
+	}
+
+	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))) {
+		return -1;
+	}
+
+	data->dsize = rec->value.dsize;
+	data->dptr = (uint8 *)talloc_memdup(mem_ctx, rec->value.dptr,
+					    rec->value.dsize);
+	TALLOC_FREE(rec);
+	return 0;
+}
+
+
+static int db_rbt_traverse(struct db_context *db,
+			   int (*f)(struct db_record *db,
+				    void *private_data),
+			   void *private_data)
+{
+	return -1;
+}
+
+static int db_rbt_get_seqnum(struct db_context *db)
+{
+	return 0;
+}
+
+struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
+{
+	struct db_context *result;
+
+	result = talloc(mem_ctx, struct db_context);
+
+	if (result == NULL) {
+		return NULL;
+	}
+
+	result->private_data = TALLOC_ZERO_P(result, struct db_rbt_ctx);
+
+	if (result->private_data == NULL) {
+		TALLOC_FREE(result);
+		return NULL;
+	}
+
+	result->fetch_locked = db_rbt_fetch_locked;
+	result->fetch = db_rbt_fetch;
+	result->traverse = db_rbt_traverse;
+	result->traverse_read = db_rbt_traverse;
+	result->get_seqnum = db_rbt_get_seqnum;
+
+	return result;
+}
diff --git a/source3/torture/torture.c b/source3/torture/torture.c
index 48b7aa60c0..1e6865b754 100644
--- a/source3/torture/torture.c
+++ b/source3/torture/torture.c
@@ -4960,6 +4960,88 @@ static bool run_local_gencache(int dummy)
 	return True;
 }
 
+static bool rbt_testval(struct db_context *db, const char *key,
+			const char *value)
+{
+	struct db_record *rec;
+	TDB_DATA data = string_tdb_data(value);
+	bool ret = false;
+	NTSTATUS status;
+
+	rec = db->fetch_locked(db, db, string_tdb_data(key));
+	if (rec == NULL) {
+		d_fprintf(stderr, "fetch_locked failed\n");
+		goto done;
+	}
+	status = rec->store(rec, data, 0);
+	if (!NT_STATUS_IS_OK(status)) {
+		d_fprintf(stderr, "store failed: %s\n", nt_errstr(status));
+		goto done;
+	}
+	TALLOC_FREE(rec);
+
+	rec = db->fetch_locked(db, db, string_tdb_data(key));
+	if (rec == NULL) {
+		d_fprintf(stderr, "second fetch_locked failed\n");
+		goto done;
+	}
+	if ((rec->value.dsize != data.dsize)
+	    || (memcmp(rec->value.dptr, data.dptr, data.dsize) != 0)) {
+		d_fprintf(stderr, "Got wrong data back\n");
+		goto done;
+	}
+
+	ret = true;
+ done:
+	TALLOC_FREE(rec);
+	return ret;
+}
+
+static bool run_local_rbtree(int dummy)
+{
+	struct db_context *db;
+	bool ret = false;
+	int i;
+
+	db = db_open_rbt(NULL);
+
+	if (db == NULL) {
+		d_fprintf(stderr, "db_open_rbt failed\n");
+		return false;
+	}
+
+	for (i=0; i<1000; i++) {
+		char *key, *value;
+
+		asprintf(&key, "key%ld", random());
+		asprintf(&value, "value%ld", random());
+
+		if (!rbt_testval(db, key, value)) {
+			SAFE_FREE(key);
+			SAFE_FREE(value);
+			goto done;
+		}
+
+		SAFE_FREE(value);
+		asprintf(&value, "value%ld", random());
+
+		if (!rbt_testval(db, key, value)) {
+			SAFE_FREE(key);
+			SAFE_FREE(value);
+			goto done;
+		}
+
+		SAFE_FREE(key);
+		SAFE_FREE(value);
+	}
+
+	ret = true;
+
+ done:
+	TALLOC_FREE(db);
+	return ret;
+}
+
 static double create_procs(bool (*fn)(int), bool *result)
 {
 	int i, status;
@@ -5113,6 +5195,7 @@ static struct {
 	{ "SESSSETUP_BENCH", run_sesssetup_bench, 0},
 	{ "LOCAL-SUBSTITUTE", run_local_substitute, 0},
 	{ "LOCAL-GENCACHE", run_local_gencache, 0},
+	{ "LOCAL-RBTREE", run_local_rbtree, 0},
 	{NULL, NULL, 0}};