Initial Import

7 files changed, 4059 insertions, 0 deletions

diff --git a/ldb/ldb_tdb/ldb_cache.c b/ldb/ldb_tdb/ldb_cache.c
new file mode 100644
index 000000000..2576e2c7b
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_cache.c
@@ -0,0 +1,458 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb cache functions
+ *
+ *  Description: cache special records in a ldb/tdb
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_includes.h"
+
+#include "ldb_tdb.h"
+
+#define LTDB_FLAG_CASE_INSENSITIVE (1<<0)
+#define LTDB_FLAG_INTEGER          (1<<1)
+#define LTDB_FLAG_HIDDEN           (1<<2)
+
+/* valid attribute flags */
+static const struct {
+	const char *name;
+	int value;
+} ltdb_valid_attr_flags[] = {
+	{ "CASE_INSENSITIVE", LTDB_FLAG_CASE_INSENSITIVE },
+	{ "INTEGER", LTDB_FLAG_INTEGER },
+	{ "HIDDEN", LTDB_FLAG_HIDDEN },
+	{ "NONE", 0 },
+	{ NULL, 0 }
+};
+
+
+/*
+  de-register any special handlers for @ATTRIBUTES
+*/
+static void ltdb_attributes_unload(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_message *msg;
+	int i;
+
+	if (ltdb->cache->attributes == NULL) {
+		/* no previously loaded attributes */
+		return;
+	}
+
+	msg = ltdb->cache->attributes;
+	for (i=0;i<msg->num_elements;i++) {
+		ldb_schema_attribute_remove(module->ldb, msg->elements[i].name);
+	}
+
+	talloc_free(ltdb->cache->attributes);
+	ltdb->cache->attributes = NULL;
+}
+
+/*
+  add up the attrib flags for a @ATTRIBUTES element
+*/
+static int ltdb_attributes_flags(struct ldb_message_element *el, unsigned *v)
+{
+	int i;
+	unsigned value = 0;
+	for (i=0;i<el->num_values;i++) {
+		int j;
+		for (j=0;ltdb_valid_attr_flags[j].name;j++) {
+			if (strcmp(ltdb_valid_attr_flags[j].name, 
+				   (char *)el->values[i].data) == 0) {
+				value |= ltdb_valid_attr_flags[j].value;
+				break;
+			}
+		}
+		if (ltdb_valid_attr_flags[j].name == NULL) {
+			return -1;
+		}
+	}
+	*v = value;
+	return 0;
+}
+
+/*
+  register any special handlers from @ATTRIBUTES
+*/
+static int ltdb_attributes_load(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_message *msg = ltdb->cache->attributes;
+	struct ldb_dn *dn;
+	int i, r;
+
+	dn = ldb_dn_new(module, module->ldb, LTDB_ATTRIBUTES);
+	if (dn == NULL) goto failed;
+
+	r = ltdb_search_dn1(module, dn, msg);
+	talloc_free(dn);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	if (r == LDB_ERR_NO_SUCH_OBJECT) {
+		return 0;
+	}
+	/* mapping these flags onto ldap 'syntaxes' isn't strictly correct,
+	   but its close enough for now */
+	for (i=0;i<msg->num_elements;i++) {
+		unsigned flags;
+		const char *syntax;
+		const struct ldb_schema_syntax *s;
+
+		if (ltdb_attributes_flags(&msg->elements[i], &flags) != 0) {
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid @ATTRIBUTES element for '%s'\n", msg->elements[i].name);
+			goto failed;
+		}
+		switch (flags & ~LTDB_FLAG_HIDDEN) {
+		case 0:
+			syntax = LDB_SYNTAX_OCTET_STRING;
+			break;
+		case LTDB_FLAG_CASE_INSENSITIVE:
+			syntax = LDB_SYNTAX_DIRECTORY_STRING;
+			break;
+		case LTDB_FLAG_INTEGER:
+			syntax = LDB_SYNTAX_INTEGER;
+			break;
+		default:
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, 
+				  "Invalid flag combination 0x%x for '%s' in @ATTRIBUTES\n",
+				  flags, msg->elements[i].name);
+			goto failed;
+		}
+
+		s = ldb_standard_syntax_by_name(module->ldb, syntax);
+		if (s == NULL) {
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, 
+				  "Invalid attribute syntax '%s' for '%s' in @ATTRIBUTES\n",
+				  syntax, msg->elements[i].name);
+			goto failed;
+		}
+
+		flags |= LDB_ATTR_FLAG_ALLOCATED;
+		if (ldb_schema_attribute_add_with_syntax(module->ldb, msg->elements[i].name, flags, s) != 0) {
+			goto failed;
+		}
+	}
+
+	return 0;
+failed:
+	return -1;
+}
+
+
+/*
+  initialise the baseinfo record
+*/
+static int ltdb_baseinfo_init(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_message *msg;
+	struct ldb_message_element el;
+	struct ldb_val val;
+	int ret;
+	/* the initial sequence number must be different from the one
+	   set in ltdb_cache_free(). Thanks to Jon for pointing this
+	   out. */
+	const char *initial_sequence_number = "1";
+
+	ltdb->sequence_number = atof(initial_sequence_number);
+
+	msg = talloc(ltdb, struct ldb_message);
+	if (msg == NULL) {
+		goto failed;
+	}
+
+	msg->num_elements = 1;
+	msg->elements = &el;
+	msg->dn = ldb_dn_new(msg, module->ldb, LTDB_BASEINFO);
+	if (!msg->dn) {
+		goto failed;
+	}
+	el.name = talloc_strdup(msg, LTDB_SEQUENCE_NUMBER);
+	if (!el.name) {
+		goto failed;
+	}
+	el.values = &val;
+	el.num_values = 1;
+	el.flags = 0;
+	val.data = (uint8_t *)talloc_strdup(msg, initial_sequence_number);
+	if (!val.data) {
+		goto failed;
+	}
+	val.length = 1;
+	
+	ret = ltdb_store(module, msg, TDB_INSERT);
+
+	talloc_free(msg);
+
+	return ret;
+
+failed:
+	talloc_free(msg);
+	errno = ENOMEM;
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/*
+  free any cache records
+ */
+static void ltdb_cache_free(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+
+	ltdb->sequence_number = 0;
+	talloc_free(ltdb->cache);
+	ltdb->cache = NULL;
+}
+
+/*
+  force a cache reload
+*/
+int ltdb_cache_reload(struct ldb_module *module)
+{
+	ltdb_attributes_unload(module);
+	ltdb_cache_free(module);
+	return ltdb_cache_load(module);
+}
+
+/*
+  load the cache records
+*/
+int ltdb_cache_load(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_dn *baseinfo_dn = NULL, *options_dn = NULL;
+	struct ldb_dn *indexlist_dn = NULL;
+	uint64_t seq;
+	struct ldb_message *baseinfo = NULL, *options = NULL;
+	int r;
+
+	/* a very fast check to avoid extra database reads */
+	if (ltdb->cache != NULL && 
+	    tdb_get_seqnum(ltdb->tdb) == ltdb->tdb_seqnum) {
+		return 0;
+	}
+
+	if (ltdb->cache == NULL) {
+		ltdb->cache = talloc_zero(ltdb, struct ltdb_cache);
+		if (ltdb->cache == NULL) goto failed;
+		ltdb->cache->indexlist = talloc_zero(ltdb->cache, struct ldb_message);
+		ltdb->cache->attributes = talloc_zero(ltdb->cache, struct ldb_message);
+		if (ltdb->cache->indexlist == NULL ||
+		    ltdb->cache->attributes == NULL) {
+			goto failed;
+		}
+	}
+
+	baseinfo = talloc(ltdb->cache, struct ldb_message);
+	if (baseinfo == NULL) goto failed;
+
+	baseinfo_dn = ldb_dn_new(module, module->ldb, LTDB_BASEINFO);
+	if (baseinfo_dn == NULL) goto failed;
+
+	r= ltdb_search_dn1(module, baseinfo_dn, baseinfo);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	
+	/* possibly initialise the baseinfo */
+	if (r == LDB_ERR_NO_SUCH_OBJECT) {
+		if (ltdb_baseinfo_init(module) != LDB_SUCCESS) {
+			goto failed;
+		}
+		if (ltdb_search_dn1(module, baseinfo_dn, baseinfo) != LDB_SUCCESS) {
+			goto failed;
+		}
+	}
+
+	ltdb->tdb_seqnum = tdb_get_seqnum(ltdb->tdb);
+
+	/* if the current internal sequence number is the same as the one
+	   in the database then assume the rest of the cache is OK */
+	seq = ldb_msg_find_attr_as_uint64(baseinfo, LTDB_SEQUENCE_NUMBER, 0);
+	if (seq == ltdb->sequence_number) {
+		goto done;
+	}
+	ltdb->sequence_number = seq;
+
+	/* Read an interpret database options */
+	options = talloc(ltdb->cache, struct ldb_message);
+	if (options == NULL) goto failed;
+
+	options_dn = ldb_dn_new(options, module->ldb, LTDB_OPTIONS);
+	if (options_dn == NULL) goto failed;
+
+	r= ltdb_search_dn1(module, options_dn, options);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	
+	/* set flag for checking base DN on searches */
+	if (r == LDB_SUCCESS) {
+		ltdb->check_base = ldb_msg_find_attr_as_bool(options, LTDB_CHECK_BASE, false);
+	} else {
+		ltdb->check_base = false;
+	}
+
+	talloc_free(ltdb->cache->last_attribute.name);
+	memset(&ltdb->cache->last_attribute, 0, sizeof(ltdb->cache->last_attribute));
+
+	ltdb_attributes_unload(module);
+
+	talloc_free(ltdb->cache->indexlist);
+
+	ltdb->cache->indexlist = talloc_zero(ltdb->cache, struct ldb_message);
+	ltdb->cache->attributes = talloc_zero(ltdb->cache, struct ldb_message);
+	if (ltdb->cache->indexlist == NULL ||
+	    ltdb->cache->attributes == NULL) {
+		goto failed;
+	}
+	    
+	indexlist_dn = ldb_dn_new(module, module->ldb, LTDB_INDEXLIST);
+	if (indexlist_dn == NULL) goto failed;
+
+	r = ltdb_search_dn1(module, indexlist_dn, ltdb->cache->indexlist);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+
+	if (ltdb_attributes_load(module) == -1) {
+		goto failed;
+	}
+
+done:
+	talloc_free(options);
+	talloc_free(baseinfo);
+	talloc_free(baseinfo_dn);
+	talloc_free(indexlist_dn);
+	return 0;
+
+failed:
+	talloc_free(options);
+	talloc_free(baseinfo);
+	talloc_free(baseinfo_dn);
+	talloc_free(indexlist_dn);
+	return -1;
+}
+
+
+/*
+  increase the sequence number to indicate a database change
+*/
+int ltdb_increase_sequence_number(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_message *msg;
+	struct ldb_message_element el[2];
+	struct ldb_val val;
+	struct ldb_val val_time;
+	time_t t = time(NULL);
+	char *s = NULL;
+	int ret;
+
+	msg = talloc(ltdb, struct ldb_message);
+	if (msg == NULL) {
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	s = talloc_asprintf(msg, "%llu", ltdb->sequence_number+1);
+	if (!s) {
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg->num_elements = ARRAY_SIZE(el);
+	msg->elements = el;
+	msg->dn = ldb_dn_new(msg, module->ldb, LTDB_BASEINFO);
+	if (msg->dn == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[0].name = talloc_strdup(msg, LTDB_SEQUENCE_NUMBER);
+	if (el[0].name == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[0].values = &val;
+	el[0].num_values = 1;
+	el[0].flags = LDB_FLAG_MOD_REPLACE;
+	val.data = (uint8_t *)s;
+	val.length = strlen(s);
+
+	el[1].name = talloc_strdup(msg, LTDB_MOD_TIMESTAMP);
+	if (el[1].name == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[1].values = &val_time;
+	el[1].num_values = 1;
+	el[1].flags = LDB_FLAG_MOD_REPLACE;
+
+	s = ldb_timestring(msg, t);
+	if (s == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val_time.data = (uint8_t *)s;
+	val_time.length = strlen(s);
+
+	ret = ltdb_modify_internal(module, msg);
+
+	talloc_free(msg);
+
+	if (ret == LDB_SUCCESS) {
+		ltdb->sequence_number += 1;
+	}
+
+	/* updating the tdb_seqnum here avoids us reloading the cache
+	   records due to our own modification */
+	ltdb->tdb_seqnum = tdb_get_seqnum(ltdb->tdb);
+
+	return ret;
+}
+
+int ltdb_check_at_attributes_values(const struct ldb_val *value)
+{
+	int i;
+
+	for (i = 0; ltdb_valid_attr_flags[i].name != NULL; i++) {
+		if ((strcmp(ltdb_valid_attr_flags[i].name, (char *)value->data) == 0)) {
+			return 0;
+		}
+	}
+
+	return -1;
+}
+
diff --git a/ldb/ldb_tdb/ldb_index.c b/ldb/ldb_tdb/ldb_index.c
new file mode 100644
index 000000000..269305a46
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_index.c
@@ -0,0 +1,1273 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb backend - indexing
+ *
+ *  Description: indexing routines for ldb tdb backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_includes.h"
+
+#include "ldb_tdb.h"
+
+/*
+  find an element in a list, using the given comparison function and
+  assuming that the list is already sorted using comp_fn
+
+  return -1 if not found, or the index of the first occurance of needle if found
+*/
+static int ldb_list_find(const void *needle, 
+			 const void *base, size_t nmemb, size_t size, 
+			 comparison_fn_t comp_fn)
+{
+	const char *base_p = (const char *)base;
+	size_t min_i, max_i, test_i;
+
+	if (nmemb == 0) {
+		return -1;
+	}
+
+	min_i = 0;
+	max_i = nmemb-1;
+
+	while (min_i < max_i) {
+		int r;
+
+		test_i = (min_i + max_i) / 2;
+		/* the following cast looks strange, but is
+		 correct. The key to understanding it is that base_p
+		 is a pointer to an array of pointers, so we have to
+		 dereference it after casting to void **. The strange
+		 const in the middle gives us the right type of pointer
+		 after the dereference  (tridge) */
+		r = comp_fn(needle, *(void * const *)(base_p + (size * test_i)));
+		if (r == 0) {
+			/* scan back for first element */
+			while (test_i > 0 &&
+			       comp_fn(needle, *(void * const *)(base_p + (size * (test_i-1)))) == 0) {
+				test_i--;
+			}
+			return test_i;
+		}
+		if (r < 0) {
+			if (test_i == 0) {
+				return -1;
+			}
+			max_i = test_i - 1;
+		}
+		if (r > 0) {
+			min_i = test_i + 1;
+		}
+	}
+
+	if (comp_fn(needle, *(void * const *)(base_p + (size * min_i))) == 0) {
+		return min_i;
+	}
+
+	return -1;
+}
+
+struct dn_list {
+	unsigned int count;
+	char **dn;
+};
+
+/*
+  return the dn key to be used for an index
+  caller frees
+*/
+static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
+				     const char *attr, const struct ldb_val *value)
+{
+	struct ldb_dn *ret;
+	struct ldb_val v;
+	const struct ldb_schema_attribute *a;
+	char *attr_folded;
+	int r;
+
+	attr_folded = ldb_attr_casefold(ldb, attr);
+	if (!attr_folded) {
+		return NULL;
+	}
+
+	a = ldb_schema_attribute_by_name(ldb, attr);
+	r = a->syntax->canonicalise_fn(ldb, ldb, value, &v);
+	if (r != LDB_SUCCESS) {
+		const char *errstr = ldb_errstring(ldb);
+		/* canonicalisation can be refused. For example, 
+		   a attribute that takes wildcards will refuse to canonicalise
+		   if the value contains a wildcard */
+		ldb_asprintf_errstring(ldb, "Failed to create index key for attribute '%s':%s%s%s",
+				       attr, ldb_strerror(r), (errstr?":":""), (errstr?errstr:""));
+		talloc_free(attr_folded);
+		return NULL;
+	}
+	if (ldb_should_b64_encode(&v)) {
+		char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
+		if (!vstr) return NULL;
+		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
+		talloc_free(vstr);
+	} else {
+		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
+	}
+
+	if (v.data != value->data) {
+		talloc_free(v.data);
+	}
+	talloc_free(attr_folded);
+
+	return ret;
+}
+
+/*
+  see if a attribute value is in the list of indexed attributes
+*/
+static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
+			    unsigned int *v_idx, const char *key)
+{
+	unsigned int i, j;
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_attr_cmp(msg->elements[i].name, key) == 0) {
+			const struct ldb_message_element *el = &msg->elements[i];
+
+			if (attr == NULL) {
+				/* in this case we are just looking to see if key is present,
+ 				   we are not spearching for a specific index */
+				return 0;
+			}
+
+			for (j=0;j<el->num_values;j++) {
+				if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
+					if (v_idx) {
+						*v_idx = j;
+					}
+					return i;
+				}
+			}
+		}
+	}
+	return -1;
+}
+
+/* used in sorting dn lists */
+static int list_cmp(const char **s1, const char **s2)
+{
+	return strcmp(*s1, *s2);
+}
+
+/*
+  return a list of dn's that might match a simple indexed search or
+ */
+static int ltdb_index_dn_simple(struct ldb_module *module, 
+				const struct ldb_parse_tree *tree,
+				const struct ldb_message *index_list,
+				struct dn_list *list)
+{
+	struct ldb_context *ldb = module->ldb;
+	struct ldb_dn *dn;
+	int ret;
+	unsigned int i, j;
+	struct ldb_message *msg;
+
+	list->count = 0;
+	list->dn = NULL;
+
+	/* if the attribute isn't in the list of indexed attributes then
+	   this node needs a full search */
+	if (ldb_msg_find_idx(index_list, tree->u.equality.attr, NULL, LTDB_IDXATTR) == -1) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* the attribute is indexed. Pull the list of DNs that match the 
+	   search criterion */
+	dn = ltdb_index_key(ldb, tree->u.equality.attr, &tree->u.equality.value);
+	if (!dn) return LDB_ERR_OPERATIONS_ERROR;
+
+	msg = talloc(list, struct ldb_message);
+	if (msg == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_search_dn1(module, dn, msg);
+	talloc_free(dn);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		struct ldb_message_element *el;
+
+		if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
+			continue;
+		}
+
+		el = &msg->elements[i];
+
+		list->dn = talloc_array(list, char *, el->num_values);
+		if (!list->dn) {
+			talloc_free(msg);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		for (j=0;j<el->num_values;j++) {
+			list->dn[list->count] = 
+				talloc_strdup(list->dn, (char *)el->values[j].data);
+			if (!list->dn[list->count]) {
+				talloc_free(msg);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			list->count++;
+		}
+	}
+
+	talloc_free(msg);
+
+	if (list->count > 1) {
+		qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) list_cmp);
+	}
+
+	return LDB_SUCCESS;
+}
+
+
+static int list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
+
+/*
+  return a list of dn's that might match a leaf indexed search
+ */
+static int ltdb_index_dn_leaf(struct ldb_module *module, 
+			      const struct ldb_parse_tree *tree,
+			      const struct ldb_message *index_list,
+			      struct dn_list *list)
+{
+	if (ldb_attr_dn(tree->u.equality.attr) == 0) {
+		list->dn = talloc_array(list, char *, 1);
+		if (list->dn == NULL) {
+			ldb_oom(module->ldb);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		list->dn[0] = talloc_strdup(list->dn, (char *)tree->u.equality.value.data);
+		if (list->dn[0] == NULL) {
+			ldb_oom(module->ldb);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		list->count = 1;
+		return LDB_SUCCESS;
+	}
+	return ltdb_index_dn_simple(module, tree, index_list, list);
+}
+
+
+/*
+  list intersection
+  list = list & list2
+  relies on the lists being sorted
+*/
+static int list_intersect(struct ldb_context *ldb,
+			  struct dn_list *list, const struct dn_list *list2)
+{
+	struct dn_list *list3;
+	unsigned int i;
+
+	if (list->count == 0 || list2->count == 0) {
+		/* 0 & X == 0 */
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	list3 = talloc(ldb, struct dn_list);
+	if (list3 == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	list3->dn = talloc_array(list3, char *, list->count);
+	if (!list3->dn) {
+		talloc_free(list3);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	list3->count = 0;
+
+	for (i=0;i<list->count;i++) {
+		if (ldb_list_find(list->dn[i], list2->dn, list2->count, 
+			      sizeof(char *), (comparison_fn_t)strcmp) != -1) {
+			list3->dn[list3->count] = talloc_move(list3->dn, &list->dn[i]);
+			list3->count++;
+		} else {
+			talloc_free(list->dn[i]);
+		}		
+	}
+
+	talloc_free(list->dn);
+	list->dn = talloc_move(list, &list3->dn);
+	list->count = list3->count;
+	talloc_free(list3);
+
+	return LDB_ERR_NO_SUCH_OBJECT;
+}
+
+
+/*
+  list union
+  list = list | list2
+  relies on the lists being sorted
+*/
+static int list_union(struct ldb_context *ldb, 
+		      struct dn_list *list, const struct dn_list *list2)
+{
+	unsigned int i;
+	char **d;
+	unsigned int count = list->count;
+
+	if (list->count == 0 && list2->count == 0) {
+		/* 0 | 0 == 0 */
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	d = talloc_realloc(list, list->dn, char *, list->count + list2->count);
+	if (!d) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	list->dn = d;
+
+	for (i=0;i<list2->count;i++) {
+		if (ldb_list_find(list2->dn[i], list->dn, count, 
+			      sizeof(char *), (comparison_fn_t)strcmp) == -1) {
+			list->dn[list->count] = talloc_strdup(list->dn, list2->dn[i]);
+			if (!list->dn[list->count]) {
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			list->count++;
+		}		
+	}
+
+	if (list->count != count) {
+		qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)list_cmp);
+	}
+
+	return LDB_ERR_NO_SUCH_OBJECT;
+}
+
+static int ltdb_index_dn(struct ldb_module *module, 
+			 const struct ldb_parse_tree *tree,
+			 const struct ldb_message *index_list,
+			 struct dn_list *list);
+
+
+/*
+  OR two index results
+ */
+static int ltdb_index_dn_or(struct ldb_module *module, 
+			    const struct ldb_parse_tree *tree,
+			    const struct ldb_message *index_list,
+			    struct dn_list *list)
+{
+	struct ldb_context *ldb = module->ldb;
+	unsigned int i;
+	int ret;
+	
+	ret = LDB_ERR_OPERATIONS_ERROR;
+	list->dn = NULL;
+	list->count = 0;
+
+	for (i=0;i<tree->u.list.num_elements;i++) {
+		struct dn_list *list2;
+		int v;
+
+		list2 = talloc(module, struct dn_list);
+		if (list2 == NULL) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
+
+		if (v == LDB_ERR_NO_SUCH_OBJECT) {
+			/* 0 || X == X */
+			if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+				ret = v;
+			}
+			talloc_free(list2);
+			continue;
+		}
+
+		if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
+			/* 1 || X == 1 */
+			talloc_free(list->dn);
+			talloc_free(list2);
+			return v;
+		}
+
+		if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+			ret = LDB_SUCCESS;
+			list->dn = talloc_move(list, &list2->dn);
+			list->count = list2->count;
+		} else {
+			if (list_union(ldb, list, list2) == -1) {
+				talloc_free(list2);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			ret = LDB_SUCCESS;
+		}
+		talloc_free(list2);
+	}
+
+	if (list->count == 0) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	return ret;
+}
+
+
+/*
+  NOT an index results
+ */
+static int ltdb_index_dn_not(struct ldb_module *module, 
+			     const struct ldb_parse_tree *tree,
+			     const struct ldb_message *index_list,
+			     struct dn_list *list)
+{
+	/* the only way to do an indexed not would be if we could
+	   negate the not via another not or if we knew the total
+	   number of database elements so we could know that the
+	   existing expression covered the whole database. 
+	   
+	   instead, we just give up, and rely on a full index scan
+	   (unless an outer & manages to reduce the list)
+	*/
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/*
+  AND two index results
+ */
+static int ltdb_index_dn_and(struct ldb_module *module, 
+			     const struct ldb_parse_tree *tree,
+			     const struct ldb_message *index_list,
+			     struct dn_list *list)
+{
+	struct ldb_context *ldb = module->ldb;
+	unsigned int i;
+	int ret;
+	
+	ret = LDB_ERR_OPERATIONS_ERROR;
+	list->dn = NULL;
+	list->count = 0;
+
+	for (i=0;i<tree->u.list.num_elements;i++) {
+		struct dn_list *list2;
+		int v;
+
+		list2 = talloc(module, struct dn_list);
+		if (list2 == NULL) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		v = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
+
+		if (v == LDB_ERR_NO_SUCH_OBJECT) {
+			/* 0 && X == 0 */
+			talloc_free(list->dn);
+			talloc_free(list2);
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+
+		if (v != LDB_SUCCESS && v != LDB_ERR_NO_SUCH_OBJECT) {
+			talloc_free(list2);
+			continue;
+		}
+
+		if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+			ret = LDB_SUCCESS;
+			talloc_free(list->dn);
+			list->dn = talloc_move(list, &list2->dn);
+			list->count = list2->count;
+		} else {
+			if (list_intersect(ldb, list, list2) == -1) {
+				talloc_free(list2);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+		}
+
+		talloc_free(list2);
+
+		if (list->count == 0) {
+			talloc_free(list->dn);
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+	}
+
+	return ret;
+}
+
+/*
+  AND index results and ONE level special index
+ */
+static int ltdb_index_dn_one(struct ldb_module *module, 
+			     struct ldb_dn *parent_dn,
+			     struct dn_list *list)
+{
+	struct ldb_context *ldb = module->ldb;
+	struct dn_list *list2;
+	struct ldb_message *msg;
+	struct ldb_dn *key;
+	struct ldb_val val;
+	unsigned int i, j;
+	int ret;
+	
+	list2 = talloc_zero(module, struct dn_list);
+	if (list2 == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* the attribute is indexed. Pull the list of DNs that match the 
+	   search criterion */
+	val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn));
+	val.length = strlen((char *)val.data);
+	key = ltdb_index_key(ldb, LTDB_IDXONE, &val);
+	if (!key) {
+		talloc_free(list2);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg = talloc(list2, struct ldb_message);
+	if (msg == NULL) {
+		talloc_free(list2);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_search_dn1(module, key, msg);
+	talloc_free(key);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	for (i = 0; i < msg->num_elements; i++) {
+		struct ldb_message_element *el;
+
+		if (strcmp(msg->elements[i].name, LTDB_IDX) != 0) {
+			continue;
+		}
+
+		el = &msg->elements[i];
+
+		list2->dn = talloc_array(list2, char *, el->num_values);
+		if (!list2->dn) {
+			talloc_free(list2);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		for (j = 0; j < el->num_values; j++) {
+			list2->dn[list2->count] = talloc_strdup(list2->dn, (char *)el->values[j].data);
+			if (!list2->dn[list2->count]) {
+				talloc_free(list2);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			list2->count++;
+		}
+	}
+
+	if (list2->count == 0) {
+		talloc_free(list2);
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	if (list2->count > 1) {
+		qsort(list2->dn, list2->count, sizeof(char *), (comparison_fn_t) list_cmp);
+	}
+
+	if (list->count > 0) {
+		if (list_intersect(ldb, list, list2) == -1) {
+			talloc_free(list2);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		if (list->count == 0) {
+			talloc_free(list->dn);
+			talloc_free(list2);
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+	} else {
+		list->dn = talloc_move(list, &list2->dn);
+		list->count = list2->count;
+	}
+
+	talloc_free(list2);
+
+	return LDB_SUCCESS;
+}
+
+/*
+  return a list of dn's that might match a indexed search or
+  an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
+ */
+static int ltdb_index_dn(struct ldb_module *module, 
+			 const struct ldb_parse_tree *tree,
+			 const struct ldb_message *index_list,
+			 struct dn_list *list)
+{
+	int ret = LDB_ERR_OPERATIONS_ERROR;
+
+	switch (tree->operation) {
+	case LDB_OP_AND:
+		ret = ltdb_index_dn_and(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_OR:
+		ret = ltdb_index_dn_or(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_NOT:
+		ret = ltdb_index_dn_not(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_EQUALITY:
+		ret = ltdb_index_dn_leaf(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_SUBSTRING:
+	case LDB_OP_GREATER:
+	case LDB_OP_LESS:
+	case LDB_OP_PRESENT:
+	case LDB_OP_APPROX:
+	case LDB_OP_EXTENDED:
+		/* we can't index with fancy bitops yet */
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		break;
+	}
+
+	return ret;
+}
+
+/*
+  filter a candidate dn_list from an indexed search into a set of results
+  extracting just the given attributes
+*/
+static int ltdb_index_filter(const struct dn_list *dn_list, 
+			     struct ldb_handle *handle)
+{
+	struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
+	struct ldb_reply *ares = NULL;
+	unsigned int i;
+
+	for (i = 0; i < dn_list->count; i++) {
+		struct ldb_dn *dn;
+		int ret;
+
+		ares = talloc_zero(ac, struct ldb_reply);
+		if (!ares) {
+			handle->status = LDB_ERR_OPERATIONS_ERROR;
+			handle->state = LDB_ASYNC_DONE;
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ares->message = ldb_msg_new(ares);
+		if (!ares->message) {
+			handle->status = LDB_ERR_OPERATIONS_ERROR;
+			handle->state = LDB_ASYNC_DONE;
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+
+		dn = ldb_dn_new(ares->message, ac->module->ldb, dn_list->dn[i]);
+		if (dn == NULL) {
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ret = ltdb_search_dn1(ac->module, dn, ares->message);
+		talloc_free(dn);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* the record has disappeared? yes, this can happen */
+			talloc_free(ares);
+			continue;
+		}
+
+		if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+			/* an internal error */
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		if (!ldb_match_msg(ac->module->ldb, ares->message, ac->tree, ac->base, ac->scope)) {
+			talloc_free(ares);
+			continue;
+		}
+
+		/* filter the attributes that the user wants */
+		ret = ltdb_filter_attrs(ares->message, ac->attrs);
+
+		if (ret == -1) {
+			handle->status = LDB_ERR_OPERATIONS_ERROR;
+			handle->state = LDB_ASYNC_DONE;
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ares->type = LDB_REPLY_ENTRY;
+        	handle->state = LDB_ASYNC_PENDING;
+		handle->status = ac->callback(ac->module->ldb, ac->context, ares);
+
+		if (handle->status != LDB_SUCCESS) {
+			handle->state = LDB_ASYNC_DONE;
+			return handle->status;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  search the database with a LDAP-like expression using indexes
+  returns -1 if an indexed search is not possible, in which
+  case the caller should call ltdb_search_full() 
+*/
+int ltdb_search_indexed(struct ldb_handle *handle)
+{
+	struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
+	struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
+	struct dn_list *dn_list;
+	int ret, idxattr, idxone;
+
+	idxattr = idxone = 0;
+	ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXATTR);
+	if (ret == 0 ) {
+		idxattr = 1;
+	}
+
+	/* We do one level indexing only if requested */
+	ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
+	if (ret == 0 ) {
+		idxone = 1;
+	}
+
+	if ((ac->scope == LDB_SCOPE_ONELEVEL && (idxattr+idxone == 0)) ||
+	    (ac->scope == LDB_SCOPE_SUBTREE && idxattr == 0)) {
+		/* no indexes? must do full search */
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = LDB_ERR_OPERATIONS_ERROR;
+
+	dn_list = talloc_zero(handle, struct dn_list);
+	if (dn_list == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (ac->scope == LDB_SCOPE_BASE) {
+		/* with BASE searches only one DN can match */
+		dn_list->dn = talloc_array(dn_list, char *, 1);
+		if (dn_list->dn == NULL) {
+			ldb_oom(ac->module->ldb);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		dn_list->dn[0] = ldb_dn_alloc_linearized(dn_list, ac->base);
+		if (dn_list->dn[0] == NULL) {
+			ldb_oom(ac->module->ldb);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		dn_list->count = 1;
+		ret = LDB_SUCCESS;
+	}
+
+	if (ac->scope != LDB_SCOPE_BASE && idxattr == 1) {
+		ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
+
+		if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+			talloc_free(dn_list);
+			return ret;
+		}
+	}
+
+	if (ac->scope == LDB_SCOPE_ONELEVEL && idxone == 1) {
+		ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
+	}
+
+	if (ret == LDB_SUCCESS) {
+		/* we've got a candidate list - now filter by the full tree
+		   and extract the needed attributes */
+		ret = ltdb_index_filter(dn_list, handle);
+		handle->status = ret;
+		handle->state = LDB_ASYNC_DONE;
+	}
+
+	talloc_free(dn_list);
+
+	return ret;
+}
+
+/*
+  add a index element where this is the first indexed DN for this value
+*/
+static int ltdb_index_add1_new(struct ldb_context *ldb, 
+			       struct ldb_message *msg,
+			       const char *dn)
+{
+	struct ldb_message_element *el;
+
+	/* add another entry */
+	el = talloc_realloc(msg, msg->elements, 
+			       struct ldb_message_element, msg->num_elements+1);
+	if (!el) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg->elements = el;
+	msg->elements[msg->num_elements].name = talloc_strdup(msg->elements, LTDB_IDX);
+	if (!msg->elements[msg->num_elements].name) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	msg->elements[msg->num_elements].num_values = 0;
+	msg->elements[msg->num_elements].values = talloc(msg->elements, struct ldb_val);
+	if (!msg->elements[msg->num_elements].values) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	msg->elements[msg->num_elements].values[0].length = strlen(dn);
+	msg->elements[msg->num_elements].values[0].data = discard_const_p(uint8_t, dn);
+	msg->elements[msg->num_elements].num_values = 1;
+	msg->num_elements++;
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  add a index element where this is not the first indexed DN for this
+  value
+*/
+static int ltdb_index_add1_add(struct ldb_context *ldb, 
+			       struct ldb_message *msg,
+			       int idx,
+			       const char *dn)
+{
+	struct ldb_val *v2;
+	unsigned int i;
+
+	/* for multi-valued attributes we can end up with repeats */
+	for (i=0;i<msg->elements[idx].num_values;i++) {
+		if (strcmp(dn, (char *)msg->elements[idx].values[i].data) == 0) {
+			return LDB_SUCCESS;
+		}
+	}
+
+	v2 = talloc_realloc(msg->elements, msg->elements[idx].values,
+			      struct ldb_val, 
+			      msg->elements[idx].num_values+1);
+	if (!v2) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	msg->elements[idx].values = v2;
+
+	msg->elements[idx].values[msg->elements[idx].num_values].length = strlen(dn);
+	msg->elements[idx].values[msg->elements[idx].num_values].data = discard_const_p(uint8_t, dn);
+	msg->elements[idx].num_values++;
+
+	return LDB_SUCCESS;
+}
+
+/*
+  add an index entry for one message element
+*/
+static int ltdb_index_add1(struct ldb_module *module, const char *dn, 
+			   struct ldb_message_element *el, int v_idx)
+{
+	struct ldb_context *ldb = module->ldb;
+	struct ldb_message *msg;
+	struct ldb_dn *dn_key;
+	int ret;
+	unsigned int i;
+
+	msg = talloc(module, struct ldb_message);
+	if (msg == NULL) {
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
+	if (!dn_key) {
+		talloc_free(msg);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	talloc_steal(msg, dn_key);
+
+	ret = ltdb_search_dn1(module, dn_key, msg);
+	if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+		talloc_free(msg);
+		return ret;
+	}
+
+	if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+		msg->dn = dn_key;
+		msg->num_elements = 0;
+		msg->elements = NULL;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		if (strcmp(LTDB_IDX, msg->elements[i].name) == 0) {
+			break;
+		}
+	}
+
+	if (i == msg->num_elements) {
+		ret = ltdb_index_add1_new(ldb, msg, dn);
+	} else {
+		ret = ltdb_index_add1_add(ldb, msg, i, dn);
+	}
+
+	if (ret == LDB_SUCCESS) {
+		ret = ltdb_store(module, msg, TDB_REPLACE);
+	}
+
+	talloc_free(msg);
+
+	return ret;
+}
+
+static int ltdb_index_add0(struct ldb_module *module, const char *dn,
+			   struct ldb_message_element *elements, int num_el)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	int ret;
+	unsigned int i, j;
+
+	if (dn[0] == '@') {
+		return LDB_SUCCESS;
+	}
+
+	if (ltdb->cache->indexlist->num_elements == 0) {
+		/* no indexed fields */
+		return LDB_SUCCESS;
+	}
+
+	for (i = 0; i < num_el; i++) {
+		ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name, 
+				       NULL, LTDB_IDXATTR);
+		if (ret == -1) {
+			continue;
+		}
+		for (j = 0; j < elements[i].num_values; j++) {
+			ret = ltdb_index_add1(module, dn, &elements[i], j);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  add the index entries for a new record
+*/
+int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
+{
+	const char *dn;
+	int ret;
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
+
+	return ret;
+}
+
+
+/*
+  delete an index entry for one message element
+*/
+int ltdb_index_del_value(struct ldb_module *module, const char *dn, 
+			 struct ldb_message_element *el, int v_idx)
+{
+	struct ldb_context *ldb = module->ldb;
+	struct ldb_message *msg;
+	struct ldb_dn *dn_key;
+	int ret, i;
+	unsigned int j;
+
+	if (dn[0] == '@') {
+		return LDB_SUCCESS;
+	}
+
+	dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx]);
+	if (!dn_key) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg = talloc(dn_key, struct ldb_message);
+	if (msg == NULL) {
+		talloc_free(dn_key);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_search_dn1(module, dn_key, msg);
+	if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+		talloc_free(dn_key);
+		return ret;
+	}
+
+	if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+		/* it wasn't indexed. Did we have an earlier error? If we did then
+		   its gone now */
+		talloc_free(dn_key);
+		return LDB_SUCCESS;
+	}
+
+	i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
+	if (i == -1) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR,
+				"ERROR: dn %s not found in %s\n", dn,
+				ldb_dn_get_linearized(dn_key));
+		/* it ain't there. hmmm */
+		talloc_free(dn_key);
+		return LDB_SUCCESS;
+	}
+
+	if (j != msg->elements[i].num_values - 1) {
+		memmove(&msg->elements[i].values[j], 
+			&msg->elements[i].values[j+1], 
+			(msg->elements[i].num_values-(j+1)) * 
+			sizeof(msg->elements[i].values[0]));
+	}
+	msg->elements[i].num_values--;
+
+	if (msg->elements[i].num_values == 0) {
+		ret = ltdb_delete_noindex(module, dn_key);
+	} else {
+		ret = ltdb_store(module, msg, TDB_REPLACE);
+	}
+
+	talloc_free(dn_key);
+
+	return ret;
+}
+
+/*
+  delete the index entries for a record
+  return -1 on failure
+*/
+int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	int ret;
+	const char *dn;
+	unsigned int i, j;
+
+	/* find the list of indexed fields */	
+	if (ltdb->cache->indexlist->num_elements == 0) {
+		/* no indexed fields */
+		return LDB_SUCCESS;
+	}
+
+	if (ldb_dn_is_special(msg->dn)) {
+		return LDB_SUCCESS;
+	}
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	for (i = 0; i < msg->num_elements; i++) {
+		ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name, 
+				       NULL, LTDB_IDXATTR);
+		if (ret == -1) {
+			continue;
+		}
+		for (j = 0; j < msg->elements[i].num_values; j++) {
+			ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+/* 
+  handle special index for one level searches
+*/
+int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	struct ldb_message_element el;
+	struct ldb_val val;
+	struct ldb_dn *pdn;
+	const char *dn;
+	int ret;
+
+	/* We index for ONE Level only if requested */
+	ret = ldb_msg_find_idx(ltdb->cache->indexlist, NULL, NULL, LTDB_IDXONE);
+	if (ret != 0) {
+		return LDB_SUCCESS;
+	}
+
+	pdn = ldb_dn_get_parent(module, msg->dn);
+	if (pdn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		talloc_free(pdn);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn));
+	if (val.data == NULL) {
+		talloc_free(pdn);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val.length = strlen((char *)val.data);
+	el.name = LTDB_IDXONE;
+	el.values = &val;
+	el.num_values = 1;
+
+	if (add) {
+		ret = ltdb_index_add1(module, dn, &el, 0);
+	} else { /* delete */
+		ret = ltdb_index_del_value(module, dn, &el, 0);
+	}
+
+	talloc_free(pdn);
+
+	return ret;
+}
+
+
+/*
+  traversal function that deletes all @INDEX records
+*/
+static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	const char *dn = "DN=" LTDB_INDEX ":";
+	if (strncmp((char *)key.dptr, dn, strlen(dn)) == 0) {
+		return tdb_delete(tdb, key);
+	}
+	return 0;
+}
+
+/*
+  traversal function that adds @INDEX records during a re index
+*/
+static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_module *module = (struct ldb_module *)state;
+	struct ldb_message *msg;
+	const char *dn = NULL;
+	int ret;
+	TDB_DATA key2;
+
+	if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
+	    strncmp((char *)key.dptr, "DN=", 3) != 0) {
+		return 0;
+	}
+
+	msg = talloc(module, struct ldb_message);
+	if (msg == NULL) {
+		return -1;
+	}
+
+	ret = ltdb_unpack_data(module, &data, msg);
+	if (ret != 0) {
+		talloc_free(msg);
+		return -1;
+	}
+
+	/* check if the DN key has changed, perhaps due to the 
+	   case insensitivity of an element changing */
+	key2 = ltdb_key(module, msg->dn);
+	if (key2.dptr == NULL) {
+		/* probably a corrupt record ... darn */
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
+							ldb_dn_get_linearized(msg->dn));
+		talloc_free(msg);
+		return 0;
+	}
+	if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
+		tdb_delete(tdb, key);
+		tdb_store(tdb, key2, data, 0);
+	}
+	talloc_free(key2.dptr);
+
+	if (msg->dn == NULL) {
+		dn = (char *)key.dptr + 3;
+	} else {
+		dn = ldb_dn_get_linearized(msg->dn);
+	}
+
+	ret = ltdb_index_one(module, msg, 1);
+	if (ret == LDB_SUCCESS) {
+		ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
+	} else {
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR,
+			"Adding special ONE LEVEL index failed (%s)!\n",
+			ldb_dn_get_linearized(msg->dn));
+	}
+
+	talloc_free(msg);
+
+	if (ret != LDB_SUCCESS) return -1;
+
+	return 0;
+}
+
+/*
+  force a complete reindex of the database
+*/
+int ltdb_reindex(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	int ret;
+
+	if (ltdb_cache_reload(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* first traverse the database deleting any @INDEX records */
+	ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
+	if (ret == -1) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* if we don't have indexes we have nothing todo */
+	if (ltdb->cache->indexlist->num_elements == 0) {
+		return LDB_SUCCESS;
+	}
+
+	/* now traverse adding any indexes for normal LDB records */
+	ret = tdb_traverse(ltdb->tdb, re_index, module);
+	if (ret == -1) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	return LDB_SUCCESS;
+}
diff --git a/ldb/ldb_tdb/ldb_pack.c b/ldb/ldb_tdb/ldb_pack.c
new file mode 100644
index 000000000..afb07dcbc
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_pack.c
@@ -0,0 +1,289 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb pack/unpack
+ *
+ *  Description: pack/unpack routines for ldb messages as key/value blobs
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_includes.h"
+#include "ldb_tdb.h"
+
+/* change this if the data format ever changes */
+#define LTDB_PACKING_FORMAT 0x26011967
+
+/* old packing formats */
+#define LTDB_PACKING_FORMAT_NODN 0x26011966
+
+/* use a portable integer format */
+static void put_uint32(uint8_t *p, int ofs, unsigned int val)
+{
+	p += ofs;
+	p[0] = val&0xFF;
+	p[1] = (val>>8)  & 0xFF;
+	p[2] = (val>>16) & 0xFF;
+	p[3] = (val>>24) & 0xFF;
+}
+
+static unsigned int pull_uint32(uint8_t *p, int ofs)
+{
+	p += ofs;
+	return p[0] | (p[1]<<8) | (p[2]<<16) | (p[3]<<24);
+}
+
+static int attribute_storable_values(const struct ldb_message_element *el)
+{
+	if (el->num_values == 0) return 0;
+
+	if (ldb_attr_cmp(el->name, "dn") == 0) return 0;
+
+	if (ldb_attr_cmp(el->name, "distinguishedName") == 0) return 0;
+
+	return el->num_values;
+}
+
+/*
+  pack a ldb message into a linear buffer in a TDB_DATA
+
+  note that this routine avoids saving elements with zero values,
+  as these are equivalent to having no element
+
+  caller frees the data buffer after use
+*/
+int ltdb_pack_data(struct ldb_module *module,
+		   const struct ldb_message *message,
+		   struct TDB_DATA *data)
+{
+	struct ldb_context *ldb = module->ldb;
+	unsigned int i, j, real_elements=0;
+	size_t size;
+	const char *dn;
+	uint8_t *p;
+	size_t len;
+
+	dn = ldb_dn_get_linearized(message->dn);
+	if (dn == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	/* work out how big it needs to be */
+	size = 8;
+
+	size += 1 + strlen(dn);
+
+	for (i=0;i<message->num_elements;i++) {
+		if (attribute_storable_values(&message->elements[i]) == 0) {
+			continue;
+		}
+
+		real_elements++;
+
+		size += 1 + strlen(message->elements[i].name) + 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			size += 4 + message->elements[i].values[j].length + 1;
+		}
+	}
+
+	/* allocate it */
+	data->dptr = talloc_array(ldb, uint8_t, size);
+	if (!data->dptr) {
+		errno = ENOMEM;
+		return -1;
+	}
+	data->dsize = size;
+
+	p = data->dptr;
+	put_uint32(p, 0, LTDB_PACKING_FORMAT); 
+	put_uint32(p, 4, real_elements); 
+	p += 8;
+
+	/* the dn needs to be packed so we can be case preserving
+	   while hashing on a case folded dn */
+	len = strlen(dn);
+	memcpy(p, dn, len+1);
+	p += len + 1;
+	
+	for (i=0;i<message->num_elements;i++) {
+		if (attribute_storable_values(&message->elements[i]) == 0) {
+			continue;
+		}
+		len = strlen(message->elements[i].name);
+		memcpy(p, message->elements[i].name, len+1);
+		p += len + 1;
+		put_uint32(p, 0, message->elements[i].num_values);
+		p += 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			put_uint32(p, 0, message->elements[i].values[j].length);
+			memcpy(p+4, message->elements[i].values[j].data, 
+			       message->elements[i].values[j].length);
+			p[4+message->elements[i].values[j].length] = 0;
+			p += 4 + message->elements[i].values[j].length + 1;
+		}
+	}
+
+	return 0;
+}
+
+/*
+  unpack a ldb message from a linear buffer in TDB_DATA
+
+  Free with ltdb_unpack_data_free()
+*/
+int ltdb_unpack_data(struct ldb_module *module,
+		     const struct TDB_DATA *data,
+		     struct ldb_message *message)
+{
+	struct ldb_context *ldb = module->ldb;
+	uint8_t *p;
+	unsigned int remaining;
+	unsigned int i, j;
+	unsigned format;
+	size_t len;
+
+	message->elements = NULL;
+
+	p = data->dptr;
+	if (data->dsize < 8) {
+		errno = EIO;
+		goto failed;
+	}
+
+	format = pull_uint32(p, 0);
+	message->num_elements = pull_uint32(p, 4);
+	p += 8;
+
+	remaining = data->dsize - 8;
+
+	switch (format) {
+	case LTDB_PACKING_FORMAT_NODN:
+		message->dn = NULL;
+		break;
+
+	case LTDB_PACKING_FORMAT:
+		len = strnlen((char *)p, remaining);
+		if (len == remaining) {
+			errno = EIO;
+			goto failed;
+		}
+		message->dn = ldb_dn_new(message, ldb, (char *)p);
+		if (message->dn == NULL) {
+			errno = ENOMEM;
+			goto failed;
+		}
+		remaining -= len + 1;
+		p += len + 1;
+		break;
+
+	default:
+		errno = EIO;
+		goto failed;
+	}
+
+	if (message->num_elements == 0) {
+		message->elements = NULL;
+		return 0;
+	}
+	
+	if (message->num_elements > remaining / 6) {
+		errno = EIO;
+		goto failed;
+	}
+
+	message->elements = talloc_array(message, struct ldb_message_element, message->num_elements);
+	if (!message->elements) {
+		errno = ENOMEM;
+		goto failed;
+	}
+
+	memset(message->elements, 0, 
+	       message->num_elements * sizeof(struct ldb_message_element));
+
+	for (i=0;i<message->num_elements;i++) {
+		if (remaining < 10) {
+			errno = EIO;
+			goto failed;
+		}
+		len = strnlen((char *)p, remaining-6);
+		if (len == remaining-6) {
+			errno = EIO;
+			goto failed;
+		}
+		message->elements[i].flags = 0;
+		message->elements[i].name = talloc_strndup(message->elements, (char *)p, len);
+		if (message->elements[i].name == NULL) {
+			errno = ENOMEM;
+			goto failed;
+		}
+		remaining -= len + 1;
+		p += len + 1;
+		message->elements[i].num_values = pull_uint32(p, 0);
+		message->elements[i].values = NULL;
+		if (message->elements[i].num_values != 0) {
+			message->elements[i].values = talloc_array(message->elements,
+								     struct ldb_val, 
+								     message->elements[i].num_values);
+			if (!message->elements[i].values) {
+				errno = ENOMEM;
+				goto failed;
+			}
+		}
+		p += 4;
+		remaining -= 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			len = pull_uint32(p, 0);
+			if (len > remaining-5) {
+				errno = EIO;
+				goto failed;
+			}
+
+			message->elements[i].values[j].length = len;
+			message->elements[i].values[j].data = talloc_size(message->elements[i].values, len+1);
+			if (message->elements[i].values[j].data == NULL) {
+				errno = ENOMEM;
+				goto failed;
+			}
+			memcpy(message->elements[i].values[j].data, p+4, len);
+			message->elements[i].values[j].data[len] = 0;
+	
+			remaining -= len+4+1;
+			p += len+4+1;
+		}
+	}
+
+	if (remaining != 0) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR, 
+			  "Error: %d bytes unread in ltdb_unpack_data\n", remaining);
+	}
+
+	return 0;
+
+failed:
+	talloc_free(message->elements);
+	return -1;
+}
diff --git a/ldb/ldb_tdb/ldb_search.c b/ldb/ldb_tdb/ldb_search.c
new file mode 100644
index 000000000..da899c361
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_search.c
@@ -0,0 +1,616 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb search functions
+ *
+ *  Description: functions to search ldb+tdb databases
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_includes.h"
+
+#include "ldb_tdb.h"
+
+/*
+  add one element to a message
+*/
+static int msg_add_element(struct ldb_message *ret, 
+			   const struct ldb_message_element *el,
+			   int check_duplicates)
+{
+	unsigned int i;
+	struct ldb_message_element *e2, *elnew;
+
+	if (check_duplicates && ldb_msg_find_element(ret, el->name)) {
+		/* its already there */
+		return 0;
+	}
+
+	e2 = talloc_realloc(ret, ret->elements, struct ldb_message_element, ret->num_elements+1);
+	if (!e2) {
+		return -1;
+	}
+	ret->elements = e2;
+	
+	elnew = &e2[ret->num_elements];
+
+	elnew->name = talloc_strdup(ret->elements, el->name);
+	if (!elnew->name) {
+		return -1;
+	}
+
+	if (el->num_values) {
+		elnew->values = talloc_array(ret->elements, struct ldb_val, el->num_values);
+		if (!elnew->values) {
+			return -1;
+		}
+	} else {
+		elnew->values = NULL;
+	}
+
+	for (i=0;i<el->num_values;i++) {
+		elnew->values[i] = ldb_val_dup(elnew->values, &el->values[i]);
+		if (elnew->values[i].length != el->values[i].length) {
+			return -1;
+		}
+	}
+
+	elnew->num_values = el->num_values;
+
+	ret->num_elements++;
+
+	return 0;
+}
+
+/*
+  add the special distinguishedName element
+*/
+static int msg_add_distinguished_name(struct ldb_message *msg)
+{
+	struct ldb_message_element el;
+	struct ldb_val val;
+	int ret;
+
+	el.flags = 0;
+	el.name = "distinguishedName";
+	el.num_values = 1;
+	el.values = &val;
+	val.data = (uint8_t *)ldb_dn_alloc_linearized(msg, msg->dn);
+	val.length = strlen((char *)val.data);
+	
+	ret = msg_add_element(msg, &el, 1);
+	return ret;
+}
+
+/*
+  add all elements from one message into another
+ */
+static int msg_add_all_elements(struct ldb_module *module, struct ldb_message *ret,
+				const struct ldb_message *msg)
+{
+	struct ldb_context *ldb = module->ldb;
+	unsigned int i;
+	int check_duplicates = (ret->num_elements != 0);
+
+	if (msg_add_distinguished_name(ret) != 0) {
+		return -1;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		const struct ldb_schema_attribute *a;
+		a = ldb_schema_attribute_by_name(ldb, msg->elements[i].name);
+		if (a->flags & LDB_ATTR_FLAG_HIDDEN) {
+			continue;
+		}
+		if (msg_add_element(ret, &msg->elements[i],
+				    check_duplicates) != 0) {
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+  pull the specified list of attributes from a message
+ */
+static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module, 
+					   TALLOC_CTX *mem_ctx, 
+					   const struct ldb_message *msg, 
+					   const char * const *attrs)
+{
+	struct ldb_message *ret;
+	int i;
+
+	ret = talloc(mem_ctx, struct ldb_message);
+	if (!ret) {
+		return NULL;
+	}
+
+	ret->dn = ldb_dn_copy(ret, msg->dn);
+	if (!ret->dn) {
+		talloc_free(ret);
+		return NULL;
+	}
+
+	ret->num_elements = 0;
+	ret->elements = NULL;
+
+	if (!attrs) {
+		if (msg_add_all_elements(module, ret, msg) != 0) {
+			talloc_free(ret);
+			return NULL;
+		}
+		return ret;
+	}
+
+	for (i=0;attrs[i];i++) {
+		struct ldb_message_element *el;
+
+		if (strcmp(attrs[i], "*") == 0) {
+			if (msg_add_all_elements(module, ret, msg) != 0) {
+				talloc_free(ret);
+				return NULL;
+			}
+			continue;
+		}
+
+		if (ldb_attr_cmp(attrs[i], "distinguishedName") == 0) {
+			if (msg_add_distinguished_name(ret) != 0) {
+				return NULL;
+			}
+			continue;
+		}
+
+		el = ldb_msg_find_element(msg, attrs[i]);
+		if (!el) {
+			continue;
+		}
+		if (msg_add_element(ret, el, 1) != 0) {
+			talloc_free(ret);
+			return NULL;				
+		}
+	}
+
+	return ret;
+}
+
+/*
+  search the database for a single simple dn.
+  return LDB_ERR_NO_SUCH_OBJECT on record-not-found
+  and LDB_SUCCESS on success
+*/
+int ltdb_search_base(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	TDB_DATA tdb_key, tdb_data;
+
+	if (ldb_dn_is_null(dn)) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	/* form the key */
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+	if (!tdb_data.dptr) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+	
+	free(tdb_data.dptr);
+	return LDB_SUCCESS;
+}
+
+/*
+  search the database for a single simple dn, returning all attributes
+  in a single message
+
+  return LDB_ERR_NO_SUCH_OBJECT on record-not-found
+  and LDB_SUCCESS on success
+*/
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	int ret;
+	TDB_DATA tdb_key, tdb_data;
+
+	memset(msg, 0, sizeof(*msg));
+
+	/* form the key */
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+	if (!tdb_data.dptr) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+	
+	msg->num_elements = 0;
+	msg->elements = NULL;
+
+	ret = ltdb_unpack_data(module, &tdb_data, msg);
+	free(tdb_data.dptr);
+	if (ret == -1) {
+		return LDB_ERR_OPERATIONS_ERROR;		
+	}
+
+	if (!msg->dn) {
+		msg->dn = ldb_dn_copy(msg, dn);
+	}
+	if (!msg->dn) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  lock the database for read - use by ltdb_search
+*/
+static int ltdb_lock_read(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	if (ltdb->in_transaction == 0) {
+		return tdb_lockall_read(ltdb->tdb);
+	}
+	return 0;
+}
+
+/*
+  unlock the database after a ltdb_lock_read()
+*/
+static int ltdb_unlock_read(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = (struct ltdb_private *)module->private_data;
+	if (ltdb->in_transaction == 0) {
+		return tdb_unlockall_read(ltdb->tdb);
+	}
+	return 0;
+}
+
+/*
+  add a set of attributes from a record to a set of results
+  return 0 on success, -1 on failure
+*/
+int ltdb_add_attr_results(struct ldb_module *module, 
+			  TALLOC_CTX *mem_ctx, 
+			  struct ldb_message *msg,
+			  const char * const attrs[], 
+			  unsigned int *count, 
+			  struct ldb_message ***res)
+{
+	struct ldb_message *msg2;
+	struct ldb_message **res2;
+
+	/* pull the attributes that the user wants */
+	msg2 = ltdb_pull_attrs(module, mem_ctx, msg, attrs);
+	if (!msg2) {
+		return -1;
+	}
+
+	/* add to the results list */
+	res2 = talloc_realloc(mem_ctx, *res, struct ldb_message *, (*count)+2);
+	if (!res2) {
+		talloc_free(msg2);
+		return -1;
+	}
+
+	(*res) = res2;
+
+	(*res)[*count] = talloc_move(*res, &msg2);
+	(*res)[(*count)+1] = NULL;
+	(*count)++;
+
+	return 0;
+}
+
+
+
+/*
+  filter the specified list of attributes from a message
+  removing not requested attrs.
+ */
+int ltdb_filter_attrs(struct ldb_message *msg, const char * const *attrs)
+{
+	int i, keep_all = 0;
+
+	if (attrs) {
+		/* check for special attrs */
+		for (i = 0; attrs[i]; i++) {
+			if (strcmp(attrs[i], "*") == 0) {
+				keep_all = 1;
+				break;
+			}
+
+			if (ldb_attr_cmp(attrs[i], "distinguishedName") == 0) {
+				if (msg_add_distinguished_name(msg) != 0) {
+					return -1;
+				}
+			}
+		}
+	} else {
+		keep_all = 1;
+	}
+	
+	if (keep_all) {
+		if (msg_add_distinguished_name(msg) != 0) {
+			return -1;
+		}
+		return 0;
+	}
+
+	for (i = 0; i < msg->num_elements; i++) {
+		int j, found;
+		
+		for (j = 0, found = 0; attrs[j]; j++) {
+			if (ldb_attr_cmp(msg->elements[i].name, attrs[j]) == 0) {
+				found = 1;
+				break;
+			}
+		}
+
+		if (!found) {
+			ldb_msg_remove_attr(msg, msg->elements[i].name);
+			i--;
+		}
+	}
+
+	return 0;
+}
+
+/*
+  search function for a non-indexed search
+ */
+static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_handle *handle = talloc_get_type(state, struct ldb_handle);
+	struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
+	struct ldb_reply *ares = NULL;
+	int ret;
+
+	if (key.dsize < 4 || 
+	    strncmp((char *)key.dptr, "DN=", 3) != 0) {
+		return 0;
+	}
+
+	ares = talloc_zero(ac, struct ldb_reply);
+	if (!ares) {
+		handle->status = LDB_ERR_OPERATIONS_ERROR;
+		handle->state = LDB_ASYNC_DONE;
+		return -1;
+	}
+
+	ares->message = ldb_msg_new(ares);
+	if (!ares->message) {
+		handle->status = LDB_ERR_OPERATIONS_ERROR;
+		handle->state = LDB_ASYNC_DONE;
+		talloc_free(ares);
+		return -1;
+	}
+
+	/* unpack the record */
+	ret = ltdb_unpack_data(ac->module, &data, ares->message);
+	if (ret == -1) {
+		talloc_free(ares);
+		return -1;
+	}
+
+	if (!ares->message->dn) {
+		ares->message->dn = ldb_dn_new(ares->message, ac->module->ldb, (char *)key.dptr + 3);
+		if (ares->message->dn == NULL) {
+			handle->status = LDB_ERR_OPERATIONS_ERROR;
+			handle->state = LDB_ASYNC_DONE;
+			talloc_free(ares);
+			return -1;
+		}
+	}
+
+	/* see if it matches the given expression */
+	if (!ldb_match_msg(ac->module->ldb, ares->message, ac->tree, 
+			       ac->base, ac->scope)) {
+		talloc_free(ares);
+		return 0;
+	}
+
+	/* filter the attributes that the user wants */
+	ret = ltdb_filter_attrs(ares->message, ac->attrs);
+
+	if (ret == -1) {
+		handle->status = LDB_ERR_OPERATIONS_ERROR;
+		handle->state = LDB_ASYNC_DONE;
+		talloc_free(ares);
+		return -1;
+	}
+
+	ares->type = LDB_REPLY_ENTRY;
+        handle->state = LDB_ASYNC_PENDING;
+	handle->status = ac->callback(ac->module->ldb, ac->context, ares);
+
+	if (handle->status != LDB_SUCCESS) {
+		/* don't try to free ares here, the callback is in charge of that */
+		return -1;
+	}	
+
+	return 0;
+}
+
+
+/*
+  search the database with a LDAP-like expression.
+  this is the "full search" non-indexed variant
+*/
+static int ltdb_search_full(struct ldb_handle *handle)
+{
+	struct ltdb_context *ac = talloc_get_type(handle->private_data, struct ltdb_context);
+	struct ltdb_private *ltdb = talloc_get_type(ac->module->private_data, struct ltdb_private);
+	int ret;
+
+	if (ltdb->in_transaction != 0) {
+		ret = tdb_traverse(ltdb->tdb, search_func, handle);
+	} else {
+		ret = tdb_traverse_read(ltdb->tdb, search_func, handle);
+	}
+
+	if (ret == -1) {
+		handle->status = LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	handle->state = LDB_ASYNC_DONE;
+	return LDB_SUCCESS;
+}
+
+/*
+  search the database with a LDAP-like expression.
+  choses a search method
+*/
+int ltdb_search(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ltdb_private *ltdb = talloc_get_type(module->private_data, struct ltdb_private);
+	struct ltdb_context *ltdb_ac;
+	struct ldb_reply *ares;
+	int ret;
+
+	if (ltdb_lock_read(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (ltdb_cache_load(module) != 0) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (req->op.search.tree == NULL) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->handle = init_ltdb_handle(ltdb, module, req);
+	if (req->handle == NULL) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if ((req->op.search.base == NULL) || (ldb_dn_is_null(req->op.search.base) == true)) {
+
+		/* Check what we should do with a NULL dn */
+		switch (req->op.search.scope) {
+		case LDB_SCOPE_BASE:
+			ldb_asprintf_errstring(module->ldb, 
+					       "NULL Base DN invalid for a base search");
+			ret = LDB_ERR_INVALID_DN_SYNTAX;
+			break;
+		case LDB_SCOPE_ONELEVEL:
+			ldb_asprintf_errstring(module->ldb, 
+					       "NULL Base DN invalid for a one-level search");
+			ret = LDB_ERR_INVALID_DN_SYNTAX;	
+			break;
+		case LDB_SCOPE_SUBTREE:
+		default:
+			/* We accept subtree searches from a NULL base DN, ie over the whole DB */
+			ret = LDB_SUCCESS;
+		}
+	} else if (ldb_dn_is_valid(req->op.search.base) == false) {
+
+		/* We don't want invalid base DNs here */
+		ldb_asprintf_errstring(module->ldb, 
+				       "Invalid Base DN: %s", 
+				       ldb_dn_get_linearized(req->op.search.base));
+		ret = LDB_ERR_INVALID_DN_SYNTAX;
+
+	} else if (ltdb->check_base) {
+		/* This database has been marked as 'checkBaseOnSearch', so do a spot check of the base dn */
+		ret = ltdb_search_base(module, req->op.search.base);
+		
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			ldb_asprintf_errstring(module->ldb, 
+					       "No such Base DN: %s", 
+					       ldb_dn_get_linearized(req->op.search.base));
+		}
+			
+	} else {
+		/* If we are not checking the base DN life is easy */
+		ret = LDB_SUCCESS;
+	}
+
+	ltdb_ac = talloc_get_type(req->handle->private_data, struct ltdb_context);
+
+	ltdb_ac->tree = req->op.search.tree;
+	ltdb_ac->scope = req->op.search.scope;
+	ltdb_ac->base = req->op.search.base;
+	ltdb_ac->attrs = req->op.search.attrs;
+
+
+	if (ret == LDB_SUCCESS) {
+		ret = ltdb_search_indexed(req->handle);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* Not in the index, therefore OK! */
+			ret = LDB_SUCCESS;
+			
+		} else if (ret == LDB_ERR_OPERATIONS_ERROR) {
+			/* Not indexed, so we need to do a full scan */
+			ret = ltdb_search_full(req->handle);
+			if (ret != LDB_SUCCESS) {
+				ldb_set_errstring(module->ldb, "Indexed and full searches both failed!\n");
+			}
+		}
+	}
+
+	if (ret != LDB_SUCCESS) {
+		req->handle->state = LDB_ASYNC_DONE;
+		req->handle->status = ret;
+	}
+
+	/* Finally send an LDB_REPLY_DONE packet when searching is finished */
+
+	ares = talloc_zero(req, struct ldb_reply);
+	if (!ares) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->handle->state = LDB_ASYNC_DONE;
+
+	if (ret == LDB_SUCCESS) {
+		ares->type = LDB_REPLY_DONE;
+		
+		ret = req->callback(module->ldb, req->context, ares);
+		req->handle->status = ret;
+	}
+
+	ltdb_unlock_read(module);
+
+	return LDB_SUCCESS;
+}
+
diff --git a/ldb/ldb_tdb/ldb_tdb.c b/ldb/ldb_tdb/ldb_tdb.c
new file mode 100644
index 000000000..01d570c89
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_tdb.c
@@ -0,0 +1,1140 @@
+/*
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+   Copyright (C) Stefan Metzmacher  2004
+   Copyright (C) Simo Sorce       2006
+
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb_tdb
+ *
+ *  Component: ldb tdb backend
+ *
+ *  Description: core functions for tdb backend
+ *
+ *  Author: Andrew Tridgell
+ *  Author: Stefan Metzmacher
+ *
+ *  Modifications:
+ *
+ *  - description: make the module use asyncronous calls
+ *    date: Feb 2006
+ *    Author: Simo Sorce
+ */
+
+#include "ldb_includes.h"
+
+#include "ldb_tdb.h"
+
+
+/*
+  map a tdb error code to a ldb error code
+*/
+static int ltdb_err_map(enum TDB_ERROR tdb_code)
+{
+	switch (tdb_code) {
+	case TDB_SUCCESS:
+		return LDB_SUCCESS;
+	case TDB_ERR_CORRUPT:
+	case TDB_ERR_OOM:
+	case TDB_ERR_EINVAL:
+		return LDB_ERR_OPERATIONS_ERROR;
+	case TDB_ERR_IO:
+		return LDB_ERR_PROTOCOL_ERROR;
+	case TDB_ERR_LOCK:
+	case TDB_ERR_NOLOCK:
+		return LDB_ERR_BUSY;
+	case TDB_ERR_LOCK_TIMEOUT:
+		return LDB_ERR_TIME_LIMIT_EXCEEDED;
+	case TDB_ERR_EXISTS:
+		return LDB_ERR_ENTRY_ALREADY_EXISTS;
+	case TDB_ERR_NOEXIST:
+		return LDB_ERR_NO_SUCH_OBJECT;
+	case TDB_ERR_RDONLY:
+		return LDB_ERR_INSUFFICIENT_ACCESS_RIGHTS;
+	}
+	return LDB_ERR_OTHER;
+}
+
+
+struct ldb_handle *init_ltdb_handle(struct ltdb_private *ltdb,
+				    struct ldb_module *module,
+				    struct ldb_request *req)
+{
+	struct ltdb_context *ac;
+	struct ldb_handle *h;
+
+	h = talloc_zero(req, struct ldb_handle);
+	if (h == NULL) {
+		ldb_set_errstring(module->ldb, "Out of Memory");
+		return NULL;
+	}
+
+	h->module = module;
+
+	ac = talloc_zero(h, struct ltdb_context);
+	if (ac == NULL) {
+		ldb_set_errstring(module->ldb, "Out of Memory");
+		talloc_free(h);
+		return NULL;
+	}
+
+	h->private_data = (void *)ac;
+
+	h->state = LDB_ASYNC_INIT;
+	h->status = LDB_SUCCESS;
+
+	ac->module = module;
+	ac->context = req->context;
+	ac->callback = req->callback;
+
+	return h;
+}
+
+/*
+  form a TDB_DATA for a record key
+  caller frees
+
+  note that the key for a record can depend on whether the
+  dn refers to a case sensitive index record or not
+*/
+struct TDB_DATA ltdb_key(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ldb_context *ldb = module->ldb;
+	TDB_DATA key;
+	char *key_str = NULL;
+	const char *dn_folded = NULL;
+
+	/*
+	  most DNs are case insensitive. The exception is index DNs for
+	  case sensitive attributes
+
+	  there are 3 cases dealt with in this code:
+
+	  1) if the dn doesn't start with @ then uppercase the attribute
+             names and the attributes values of case insensitive attributes
+	  2) if the dn starts with @ then leave it alone -
+	     the indexing code handles the rest
+	*/
+
+	dn_folded = ldb_dn_get_casefold(dn);
+	if (!dn_folded) {
+		goto failed;
+	}
+
+	key_str = talloc_strdup(ldb, "DN=");
+	if (!key_str) {
+		goto failed;
+	}
+
+	key_str = talloc_strdup_append_buffer(key_str, dn_folded);
+	if (!key_str) {
+		goto failed;
+	}
+
+	key.dptr = (uint8_t *)key_str;
+	key.dsize = strlen(key_str) + 1;
+
+	return key;
+
+failed:
+	errno = ENOMEM;
+	key.dptr = NULL;
+	key.dsize = 0;
+	return key;
+}
+
+/*
+  check special dn's have valid attributes
+  currently only @ATTRIBUTES is checked
+*/
+int ltdb_check_special_dn(struct ldb_module *module,
+			  const struct ldb_message *msg)
+{
+	int i, j;
+
+	if (! ldb_dn_is_special(msg->dn) ||
+	    ! ldb_dn_check_special(msg->dn, LTDB_ATTRIBUTES)) {
+		return 0;
+	}
+
+	/* we have @ATTRIBUTES, let's check attributes are fine */
+	/* should we check that we deny multivalued attributes ? */
+	for (i = 0; i < msg->num_elements; i++) {
+		for (j = 0; j < msg->elements[i].num_values; j++) {
+			if (ltdb_check_at_attributes_values(&msg->elements[i].values[j]) != 0) {
+				ldb_set_errstring(module->ldb, "Invalid attribute value in an @ATTRIBUTES entry");
+				return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
+			}
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+  we've made a modification to a dn - possibly reindex and
+  update sequence number
+*/
+static int ltdb_modified(struct ldb_module *module, struct ldb_dn *dn)
+{
+	int ret = LDB_SUCCESS;
+
+	if (ldb_dn_is_special(dn) &&
+	    (ldb_dn_check_special(dn, LTDB_INDEXLIST) ||
+	     ldb_dn_check_special(dn, LTDB_ATTRIBUTES)) ) {
+		ret = ltdb_reindex(module);
+	}
+
+	if (ret == LDB_SUCCESS &&
+	    !(ldb_dn_is_special(dn) &&
+	      ldb_dn_check_special(dn, LTDB_BASEINFO)) ) {
+		ret = ltdb_increase_sequence_number(module);
+	}
+
+	return ret;
+}
+
+/*
+  store a record into the db
+*/
+int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs)
+{
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+	TDB_DATA tdb_key, tdb_data;
+	int ret;
+
+	tdb_key = ltdb_key(module, msg->dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OTHER;
+	}
+
+	ret = ltdb_pack_data(module, msg, &tdb_data);
+	if (ret == -1) {
+		talloc_free(tdb_key.dptr);
+		return LDB_ERR_OTHER;
+	}
+
+	ret = tdb_store(ltdb->tdb, tdb_key, tdb_data, flgs);
+	if (ret == -1) {
+		ret = ltdb_err_map(tdb_error(ltdb->tdb));
+		goto done;
+	}
+
+	ret = ltdb_index_add(module, msg);
+	if (ret != LDB_SUCCESS) {
+		tdb_delete(ltdb->tdb, tdb_key);
+	}
+
+done:
+	talloc_free(tdb_key.dptr);
+	talloc_free(tdb_data.dptr);
+
+	return ret;
+}
+
+
+static int ltdb_add_internal(struct ldb_module *module,
+			     const struct ldb_message *msg)
+{
+	int ret;
+
+	ret = ltdb_check_special_dn(module, msg);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_store(module, msg, TDB_INSERT);
+
+	if (ret == LDB_ERR_ENTRY_ALREADY_EXISTS) {
+		ldb_asprintf_errstring(module->ldb,
+					"Entry %s already exists",
+					ldb_dn_get_linearized(msg->dn));
+		return ret;
+	}
+
+	if (ret == LDB_SUCCESS) {
+		ret = ltdb_index_one(module, msg, 1);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+
+		ret = ltdb_modified(module, msg->dn);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	return ret;
+}
+
+/*
+  add a record to the database
+*/
+static int ltdb_add(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ltdb_private *ltdb;
+	struct ltdb_context *ltdb_ac;
+	int tret, ret = LDB_SUCCESS;
+
+	ltdb = talloc_get_type(module->private_data, struct ltdb_private);
+
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	req->handle = init_ltdb_handle(ltdb, module, req);
+	if (req->handle == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ltdb_ac = talloc_get_type(req->handle->private_data, struct ltdb_context);
+
+	tret = ltdb_add_internal(module, req->op.add.message);
+	if (tret != LDB_SUCCESS) {
+		req->handle->status = tret;
+		goto done;
+	}
+
+	if (ltdb_ac->callback) {
+		ret = ltdb_ac->callback(module->ldb, ltdb_ac->context, NULL);
+	}
+done:
+	req->handle->state = LDB_ASYNC_DONE;
+	return ret;
+}
+
+/*
+  delete a record from the database, not updating indexes (used for deleting
+  index records)
+*/
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+	TDB_DATA tdb_key;
+	int ret;
+
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OTHER;
+	}
+
+	ret = tdb_delete(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+
+	if (ret != 0) {
+		ret = ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	return ret;
+}
+
+static int ltdb_delete_internal(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ldb_message *msg;
+	int ret;
+
+	msg = talloc(module, struct ldb_message);
+	if (msg == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* in case any attribute of the message was indexed, we need
+	   to fetch the old record */
+	ret = ltdb_search_dn1(module, dn, msg);
+	if (ret != LDB_SUCCESS) {
+		/* not finding the old record is an error */
+		goto done;
+	}
+
+	ret = ltdb_delete_noindex(module, dn);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	/* remove one level attribute */
+	ret = ltdb_index_one(module, msg, 0);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	/* remove any indexed attributes */
+	ret = ltdb_index_del(module, msg);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	ret = ltdb_modified(module, dn);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+done:
+	talloc_free(msg);
+	return ret;
+}
+
+/*
+  delete a record from the database
+*/
+static int ltdb_delete(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ltdb_private *ltdb;
+	struct ltdb_context *ltdb_ac;
+	int tret, ret = LDB_SUCCESS;
+
+	ltdb = talloc_get_type(module->private_data, struct ltdb_private);
+
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	req->handle = NULL;
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->handle = init_ltdb_handle(ltdb, module, req);
+	if (req->handle == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ltdb_ac = talloc_get_type(req->handle->private_data, struct ltdb_context);
+
+	tret = ltdb_delete_internal(module, req->op.del.dn);
+	if (tret != LDB_SUCCESS) {
+		req->handle->status = tret;
+		goto done;
+	}
+
+	if (ltdb_ac->callback) {
+		ret = ltdb_ac->callback(module->ldb, ltdb_ac->context, NULL);
+	}
+done:
+	req->handle->state = LDB_ASYNC_DONE;
+	return ret;
+}
+
+/*
+  find an element by attribute name. At the moment this does a linear search,
+  it should be re-coded to use a binary search once all places that modify
+  records guarantee sorted order
+
+  return the index of the first matching element if found, otherwise -1
+*/
+static int find_element(const struct ldb_message *msg, const char *name)
+{
+	unsigned int i;
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
+			return i;
+		}
+	}
+	return -1;
+}
+
+
+/*
+  add an element to an existing record. Assumes a elements array that we
+  can call re-alloc on, and assumed that we can re-use the data pointers from
+  the passed in additional values. Use with care!
+
+  returns 0 on success, -1 on failure (and sets errno)
+*/
+static int msg_add_element(struct ldb_context *ldb,
+			   struct ldb_message *msg,
+			   struct ldb_message_element *el)
+{
+	struct ldb_message_element *e2;
+	unsigned int i;
+
+	e2 = talloc_realloc(msg, msg->elements, struct ldb_message_element,
+			      msg->num_elements+1);
+	if (!e2) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	msg->elements = e2;
+
+	e2 = &msg->elements[msg->num_elements];
+
+	e2->name = el->name;
+	e2->flags = el->flags;
+	e2->values = NULL;
+	if (el->num_values != 0) {
+		e2->values = talloc_array(msg->elements,
+					  struct ldb_val, el->num_values);
+		if (!e2->values) {
+			errno = ENOMEM;
+			return -1;
+		}
+	}
+	for (i=0;i<el->num_values;i++) {
+		e2->values[i] = el->values[i];
+	}
+	e2->num_values = el->num_values;
+
+	msg->num_elements++;
+
+	return 0;
+}
+
+/*
+  delete all elements having a specified attribute name
+*/
+static int msg_delete_attribute(struct ldb_module *module,
+				struct ldb_context *ldb,
+				struct ldb_message *msg, const char *name)
+{
+	const char *dn;
+	unsigned int i, j;
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		return -1;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
+			for (j=0;j<msg->elements[i].num_values;j++) {
+				ltdb_index_del_value(module, dn,
+						     &msg->elements[i], j);
+			}
+			talloc_free(msg->elements[i].values);
+			if (msg->num_elements > (i+1)) {
+				memmove(&msg->elements[i],
+					&msg->elements[i+1],
+					sizeof(struct ldb_message_element)*
+					(msg->num_elements - (i+1)));
+			}
+			msg->num_elements--;
+			i--;
+			msg->elements = talloc_realloc(msg, msg->elements,
+							struct ldb_message_element,
+							msg->num_elements);
+		}
+	}
+
+	return 0;
+}
+
+/*
+  delete all elements matching an attribute name/value
+
+  return 0 on success, -1 on failure
+*/
+static int msg_delete_element(struct ldb_module *module,
+			      struct ldb_message *msg,
+			      const char *name,
+			      const struct ldb_val *val)
+{
+	struct ldb_context *ldb = module->ldb;
+	unsigned int i;
+	int found;
+	struct ldb_message_element *el;
+	const struct ldb_schema_attribute *a;
+
+	found = find_element(msg, name);
+	if (found == -1) {
+		return -1;
+	}
+
+	el = &msg->elements[found];
+
+	a = ldb_schema_attribute_by_name(ldb, el->name);
+
+	for (i=0;i<el->num_values;i++) {
+		if (a->syntax->comparison_fn(ldb, ldb,
+						&el->values[i], val) == 0) {
+			if (i<el->num_values-1) {
+				memmove(&el->values[i], &el->values[i+1],
+					sizeof(el->values[i])*
+						(el->num_values-(i+1)));
+			}
+			el->num_values--;
+			if (el->num_values == 0) {
+				return msg_delete_attribute(module, ldb,
+							    msg, name);
+			}
+			return 0;
+		}
+	}
+
+	return -1;
+}
+
+
+/*
+  modify a record - internal interface
+
+  yuck - this is O(n^2). Luckily n is usually small so we probably
+  get away with it, but if we ever have really large attribute lists
+  then we'll need to look at this again
+*/
+int ltdb_modify_internal(struct ldb_module *module,
+			 const struct ldb_message *msg)
+{
+	struct ldb_context *ldb = module->ldb;
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+	TDB_DATA tdb_key, tdb_data;
+	struct ldb_message *msg2;
+	unsigned i, j;
+	int ret, idx;
+
+	tdb_key = ltdb_key(module, msg->dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OTHER;
+	}
+
+	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
+	if (!tdb_data.dptr) {
+		talloc_free(tdb_key.dptr);
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	msg2 = talloc(tdb_key.dptr, struct ldb_message);
+	if (msg2 == NULL) {
+		talloc_free(tdb_key.dptr);
+		return LDB_ERR_OTHER;
+	}
+
+	ret = ltdb_unpack_data(module, &tdb_data, msg2);
+	if (ret == -1) {
+		ret = LDB_ERR_OTHER;
+		goto failed;
+	}
+
+	if (!msg2->dn) {
+		msg2->dn = msg->dn;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		struct ldb_message_element *el = &msg->elements[i];
+		struct ldb_message_element *el2;
+		struct ldb_val *vals;
+		const char *dn;
+
+		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
+
+		case LDB_FLAG_MOD_ADD:
+			/* add this element to the message. fail if it
+			   already exists */
+			idx = find_element(msg2, el->name);
+
+			if (idx == -1) {
+				if (msg_add_element(ldb, msg2, el) != 0) {
+					ret = LDB_ERR_OTHER;
+					goto failed;
+				}
+				continue;
+			}
+
+			el2 = &msg2->elements[idx];
+
+			/* An attribute with this name already exists,
+			 * add all values if they don't already exist
+			 * (check both the other elements to be added,
+			 * and those already in the db). */
+
+			for (j=0;j<el->num_values;j++) {
+				if (ldb_msg_find_val(el2, &el->values[j])) {
+					ldb_asprintf_errstring(module->ldb, "%s: value #%d already exists", el->name, j);
+					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+					goto failed;
+				}
+				if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
+					ldb_asprintf_errstring(module->ldb, "%s: value #%d provided more than once", el->name, j);
+					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+					goto failed;
+				}
+			}
+
+		        vals = talloc_realloc(msg2->elements, el2->values, struct ldb_val,
+						el2->num_values + el->num_values);
+
+			if (vals == NULL) {
+				ret = LDB_ERR_OTHER;
+				goto failed;
+			}
+
+			for (j=0;j<el->num_values;j++) {
+				vals[el2->num_values + j] =
+					ldb_val_dup(vals, &el->values[j]);
+			}
+
+			el2->values = vals;
+			el2->num_values += el->num_values;
+
+			break;
+
+		case LDB_FLAG_MOD_REPLACE:
+			/* replace all elements of this attribute name with the elements
+			   listed. The attribute not existing is not an error */
+			msg_delete_attribute(module, ldb, msg2, el->name);
+
+			for (j=0;j<el->num_values;j++) {
+				if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
+					ldb_asprintf_errstring(module->ldb, "%s: value #%d provided more than once", el->name, j);
+					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+					goto failed;
+				}
+			}
+
+			/* add the replacement element, if not empty */
+			if (el->num_values != 0 &&
+			    msg_add_element(ldb, msg2, el) != 0) {
+				ret = LDB_ERR_OTHER;
+				goto failed;
+			}
+			break;
+
+		case LDB_FLAG_MOD_DELETE:
+
+			dn = ldb_dn_get_linearized(msg->dn);
+			if (dn == NULL) {
+				ret = LDB_ERR_OTHER;
+				goto failed;
+			}
+
+			/* we could be being asked to delete all
+			   values or just some values */
+			if (msg->elements[i].num_values == 0) {
+				if (msg_delete_attribute(module, ldb, msg2, 
+							 msg->elements[i].name) != 0) {
+					ldb_asprintf_errstring(module->ldb, "No such attribute: %s for delete on %s", msg->elements[i].name, dn);
+					ret = LDB_ERR_NO_SUCH_ATTRIBUTE;
+					goto failed;
+				}
+				break;
+			}
+			for (j=0;j<msg->elements[i].num_values;j++) {
+				if (msg_delete_element(module,
+						       msg2, 
+						       msg->elements[i].name,
+						       &msg->elements[i].values[j]) != 0) {
+					ldb_asprintf_errstring(module->ldb, "No matching attribute value when deleting attribute: %s on %s", msg->elements[i].name, dn);
+					ret = LDB_ERR_NO_SUCH_ATTRIBUTE;
+					goto failed;
+				}
+				ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
+				if (ret != LDB_SUCCESS) {
+					goto failed;
+				}
+			}
+			break;
+		default:
+			ldb_asprintf_errstring(module->ldb,
+				"Invalid ldb_modify flags on %s: 0x%x",
+				msg->elements[i].name,
+				msg->elements[i].flags & LDB_FLAG_MOD_MASK);
+			ret = LDB_ERR_PROTOCOL_ERROR;
+			goto failed;
+		}
+	}
+
+	/* we've made all the mods
+	 * save the modified record back into the database */
+	ret = ltdb_store(module, msg2, TDB_MODIFY);
+	if (ret != LDB_SUCCESS) {
+		goto failed;
+	}
+
+	ret = ltdb_modified(module, msg->dn);
+	if (ret != LDB_SUCCESS) {
+		goto failed;
+	}
+
+	talloc_free(tdb_key.dptr);
+	free(tdb_data.dptr);
+	return ret;
+
+failed:
+	talloc_free(tdb_key.dptr);
+	free(tdb_data.dptr);
+	return ret;
+}
+
+/*
+  modify a record
+*/
+static int ltdb_modify(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ltdb_private *ltdb;
+	struct ltdb_context *ltdb_ac;
+	int tret, ret = LDB_SUCCESS;
+
+	ltdb = talloc_get_type(module->private_data, struct ltdb_private);
+
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	req->handle = NULL;
+
+	req->handle = init_ltdb_handle(ltdb, module, req);
+	if (req->handle == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ltdb_ac = talloc_get_type(req->handle->private_data, struct ltdb_context);
+
+	tret = ltdb_check_special_dn(module, req->op.mod.message);
+	if (tret != LDB_SUCCESS) {
+		req->handle->status = tret;
+		goto done;
+	}
+
+	if (ltdb_cache_load(module) != 0) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	tret = ltdb_modify_internal(module, req->op.mod.message);
+	if (tret != LDB_SUCCESS) {
+		req->handle->status = tret;
+		goto done;
+	}
+
+	if (ltdb_ac->callback) {
+		ret = ltdb_ac->callback(module->ldb, ltdb_ac->context, NULL);
+	}
+done:
+	req->handle->state = LDB_ASYNC_DONE;
+	return ret;
+}
+
+/*
+  rename a record
+*/
+static int ltdb_rename(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ltdb_private *ltdb;
+	struct ltdb_context *ltdb_ac;
+	struct ldb_message *msg;
+	int tret, ret = LDB_SUCCESS;
+
+	ltdb = talloc_get_type(module->private_data, struct ltdb_private);
+
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	req->handle = NULL;
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->handle = init_ltdb_handle(ltdb, module, req);
+	if (req->handle == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ltdb_ac = talloc_get_type(req->handle->private_data, struct ltdb_context);
+
+	msg = talloc(ltdb_ac, struct ldb_message);
+	if (msg == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	/* in case any attribute of the message was indexed, we need
+	   to fetch the old record */
+	tret = ltdb_search_dn1(module, req->op.rename.olddn, msg);
+	if (tret != LDB_SUCCESS) {
+		/* not finding the old record is an error */
+		req->handle->status = tret;
+		goto done;
+	}
+
+	msg->dn = ldb_dn_copy(msg, req->op.rename.newdn);
+	if (!msg->dn) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	if (ldb_dn_compare(req->op.rename.olddn, req->op.rename.newdn) == 0) {
+		/* The rename operation is apparently only changing case -
+		   the DNs are the same.  Delete the old DN before adding
+		   the new one to avoid a TDB_ERR_EXISTS error.
+
+		   The only drawback to this is that if the delete
+		   succeeds but the add fails, we rely on the
+		   transaction to roll this all back. */
+		ret = ltdb_delete_internal(module, req->op.rename.olddn);
+		if (ret != LDB_SUCCESS) {
+			goto done;
+		}
+
+		ret = ltdb_add_internal(module, msg);
+		if (ret != LDB_SUCCESS) {
+			goto done;
+		}
+	} else {
+		/* The rename operation is changing DNs.  Try to add the new
+		   DN first to avoid clobbering another DN not related to
+		   this rename operation. */
+		ret = ltdb_add_internal(module, msg);
+		if (ret != LDB_SUCCESS) {
+			goto done;
+		}
+
+		tret = ltdb_delete_internal(module, req->op.rename.olddn);
+		if (tret != LDB_SUCCESS) {
+			ltdb_delete_internal(module, req->op.rename.newdn);
+			ret = LDB_ERR_OPERATIONS_ERROR;
+			goto done;
+		}
+	}
+
+	if (ltdb_ac->callback) {
+		ret = ltdb_ac->callback(module->ldb, ltdb_ac->context, NULL);
+	}
+done:
+	req->handle->state = LDB_ASYNC_DONE;
+	return ret;
+}
+
+static int ltdb_start_trans(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+
+	if (tdb_transaction_start(ltdb->tdb) != 0) {
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	ltdb->in_transaction++;
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_end_trans(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+
+	ltdb->in_transaction--;
+
+	if (tdb_transaction_commit(ltdb->tdb) != 0) {
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_del_trans(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb =
+		talloc_get_type(module->private_data, struct ltdb_private);
+
+	ltdb->in_transaction--;
+
+	if (tdb_transaction_cancel(ltdb->tdb) != 0) {
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_wait(struct ldb_handle *handle, enum ldb_wait_type type)
+{
+	return handle->status;
+}
+
+static int ltdb_request(struct ldb_module *module, struct ldb_request *req)
+{
+	/* check for oustanding critical controls
+	 * and return an error if found */
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	/* search, add, modify, delete, rename are handled by their own,
+	 * no other op supported */
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/*
+  return sequenceNumber from @BASEINFO
+*/
+static int ltdb_sequence_number(struct ldb_module *module,
+				struct ldb_request *req)
+{
+	TALLOC_CTX *tmp_ctx;
+	struct ldb_message *msg = NULL;
+	struct ldb_dn *dn;
+	const char *date;
+	int tret;
+
+	tmp_ctx = talloc_new(req);
+	if (tmp_ctx == NULL) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn = ldb_dn_new(tmp_ctx, module->ldb, LTDB_BASEINFO);
+
+	msg = talloc(tmp_ctx, struct ldb_message);
+	if (msg == NULL) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->op.seq_num.flags = 0;
+
+	tret = ltdb_search_dn1(module, dn, msg);
+	if (tret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		/* zero is as good as anything when we don't know */
+		req->op.seq_num.seq_num = 0;
+		return LDB_SUCCESS;
+	}
+
+	switch (req->op.seq_num.type) {
+	case LDB_SEQ_HIGHEST_SEQ:
+		req->op.seq_num.seq_num = ldb_msg_find_attr_as_uint64(msg, LTDB_SEQUENCE_NUMBER, 0);
+		break;
+	case LDB_SEQ_NEXT:
+		req->op.seq_num.seq_num = ldb_msg_find_attr_as_uint64(msg, LTDB_SEQUENCE_NUMBER, 0);
+		req->op.seq_num.seq_num++;
+		break;
+	case LDB_SEQ_HIGHEST_TIMESTAMP:
+		date = ldb_msg_find_attr_as_string(msg, LTDB_MOD_TIMESTAMP, NULL);
+		if (date) {
+			req->op.seq_num.seq_num = ldb_string_to_time(date);
+		} else {
+			req->op.seq_num.seq_num = 0;
+			/* zero is as good as anything when we don't know */
+		}
+		break;
+	}
+	talloc_free(tmp_ctx);
+	return LDB_SUCCESS;
+}
+
+static const struct ldb_module_ops ltdb_ops = {
+	.name              = "tdb",
+	.search            = ltdb_search,
+	.add               = ltdb_add,
+	.modify            = ltdb_modify,
+	.del               = ltdb_delete,
+	.rename            = ltdb_rename,
+	.request           = ltdb_request,
+	.start_transaction = ltdb_start_trans,
+	.end_transaction   = ltdb_end_trans,
+	.del_transaction   = ltdb_del_trans,
+	.wait              = ltdb_wait,
+	.sequence_number   = ltdb_sequence_number
+};
+
+/*
+  connect to the database
+*/
+static int ltdb_connect(struct ldb_context *ldb, const char *url,
+			unsigned int flags, const char *options[],
+			struct ldb_module **module)
+{
+	const char *path;
+	int tdb_flags, open_flags;
+	struct ltdb_private *ltdb;
+
+	/* parse the url */
+	if (strchr(url, ':')) {
+		if (strncmp(url, "tdb://", 6) != 0) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR,
+				  "Invalid tdb URL '%s'", url);
+			return -1;
+		}
+		path = url+6;
+	} else {
+		path = url;
+	}
+
+	tdb_flags = TDB_DEFAULT | TDB_SEQNUM;
+
+	/* check for the 'nosync' option */
+	if (flags & LDB_FLG_NOSYNC) {
+		tdb_flags |= TDB_NOSYNC;
+	}
+
+	/* and nommap option */
+	if (flags & LDB_FLG_NOMMAP) {
+		tdb_flags |= TDB_NOMMAP;
+	}
+
+	if (flags & LDB_FLG_RDONLY) {
+		open_flags = O_RDONLY;
+	} else {
+		open_flags = O_CREAT | O_RDWR;
+	}
+
+	ltdb = talloc_zero(ldb, struct ltdb_private);
+	if (!ltdb) {
+		ldb_oom(ldb);
+		return -1;
+	}
+
+	/* note that we use quite a large default hash size */
+	ltdb->tdb = ltdb_wrap_open(ltdb, path, 10000,
+				   tdb_flags, open_flags,
+				   ldb->create_perms, ldb);
+	if (!ltdb->tdb) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR,
+			  "Unable to open tdb '%s'\n", path);
+		talloc_free(ltdb);
+		return -1;
+	}
+
+	ltdb->sequence_number = 0;
+
+	*module = talloc(ldb, struct ldb_module);
+	if (!module) {
+		ldb_oom(ldb);
+		talloc_free(ltdb);
+		return -1;
+	}
+	talloc_set_name_const(*module, "ldb_tdb backend");
+	(*module)->ldb = ldb;
+	(*module)->prev = (*module)->next = NULL;
+	(*module)->private_data = ltdb;
+	(*module)->ops = &ltdb_ops;
+
+	if (ltdb_cache_load(*module) != 0) {
+		talloc_free(*module);
+		talloc_free(ltdb);
+		return -1;
+	}
+
+	return 0;
+}
+
+const struct ldb_backend_ops ldb_tdb_backend_ops = {
+	.name = "tdb",
+	.connect_fn = ltdb_connect
+};
diff --git a/ldb/ldb_tdb/ldb_tdb.h b/ldb/ldb_tdb/ldb_tdb.h
new file mode 100644
index 000000000..4beced30e
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_tdb.h
@@ -0,0 +1,130 @@
+#if (_SAMBA_BUILD_ == 3)
+#include "tdb/include/tdb.h"
+#else
+#include "replace.h"
+#include "system/wait.h"
+#include "tdb.h"
+#endif
+
+/* this private structure is used by the ltdb backend in the
+   ldb_context */
+struct ltdb_private {
+	TDB_CONTEXT *tdb;
+	unsigned int connect_flags;
+	
+	/* a double is used for portability and ease of string
+	   handling. It has plenty of digits of precision */
+	unsigned long long sequence_number;
+
+	/* the low level tdb seqnum - used to avoid loading BASEINFO when
+	   possible */
+	int tdb_seqnum;
+
+	struct ltdb_cache {
+		struct ldb_message *indexlist;
+		struct ldb_message *attributes;
+
+		struct {
+			char *name;
+			int flags;
+		} last_attribute;
+	} *cache;
+
+	int in_transaction;
+
+	bool check_base;
+};
+
+/*
+  the async local context
+  holds also internal search state during a full db search
+*/
+struct ltdb_context {
+	struct ldb_module *module;
+
+	/* search stuff */
+	const struct ldb_parse_tree *tree;
+	struct ldb_dn *base;
+	enum ldb_scope scope;
+	const char * const *attrs;
+
+	/* async stuff */
+	void *context;
+	int (*callback)(struct ldb_context *, void *, struct ldb_reply *);
+};
+
+/* special record types */
+#define LTDB_INDEX      "@INDEX"
+#define LTDB_INDEXLIST  "@INDEXLIST"
+#define LTDB_IDX        "@IDX"
+#define LTDB_IDXATTR    "@IDXATTR"
+#define LTDB_IDXONE     "@IDXONE"
+#define LTDB_BASEINFO   "@BASEINFO"
+#define LTDB_OPTIONS    "@OPTIONS"
+#define LTDB_ATTRIBUTES "@ATTRIBUTES"
+
+/* special attribute types */
+#define LTDB_SEQUENCE_NUMBER "sequenceNumber"
+#define LTDB_CHECK_BASE "checkBaseOnSearch"
+#define LTDB_MOD_TIMESTAMP "whenChanged"
+#define LTDB_OBJECTCLASS "objectClass"
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_cache.c  */
+
+int ltdb_cache_reload(struct ldb_module *module);
+int ltdb_cache_load(struct ldb_module *module);
+int ltdb_increase_sequence_number(struct ldb_module *module);
+int ltdb_check_at_attributes_values(const struct ldb_val *value);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_index.c  */
+
+struct ldb_parse_tree;
+
+int ltdb_search_indexed(struct ldb_handle *handle);
+int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg);
+int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg);
+int ltdb_index_one(struct ldb_module *module, const struct ldb_message *msg, int add);
+int ltdb_reindex(struct ldb_module *module);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_pack.c  */
+
+int ltdb_pack_data(struct ldb_module *module,
+		   const struct ldb_message *message,
+		   struct TDB_DATA *data);
+void ltdb_unpack_data_free(struct ldb_module *module,
+			   struct ldb_message *message);
+int ltdb_unpack_data(struct ldb_module *module,
+		     const struct TDB_DATA *data,
+		     struct ldb_message *message);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_search.c  */
+
+int ltdb_has_wildcard(struct ldb_module *module, const char *attr_name, 
+		      const struct ldb_val *val);
+void ltdb_search_dn1_free(struct ldb_module *module, struct ldb_message *msg);
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg);
+int ltdb_add_attr_results(struct ldb_module *module,
+ 			  TALLOC_CTX *mem_ctx, 
+			  struct ldb_message *msg,
+			  const char * const attrs[], 
+			  unsigned int *count, 
+			  struct ldb_message ***res);
+int ltdb_filter_attrs(struct ldb_message *msg, const char * const *attrs);
+int ltdb_search(struct ldb_module *module, struct ldb_request *req);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_tdb.c  */
+struct ldb_handle *init_ltdb_handle(struct ltdb_private *ltdb, struct ldb_module *module,
+				    struct ldb_request *req);
+struct TDB_DATA ltdb_key(struct ldb_module *module, struct ldb_dn *dn);
+int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs);
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn);
+int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *msg);
+
+int ltdb_index_del_value(struct ldb_module *module, const char *dn, 
+			 struct ldb_message_element *el, int v_idx);
+
+struct tdb_context *ltdb_wrap_open(TALLOC_CTX *mem_ctx,
+				   const char *path, int hash_size, int tdb_flags,
+				   int open_flags, mode_t mode,
+				   struct ldb_context *ldb);
+
diff --git a/ldb/ldb_tdb/ldb_tdb_wrap.c b/ldb/ldb_tdb/ldb_tdb_wrap.c
new file mode 100644
index 000000000..654574cd2
--- /dev/null
+++ b/ldb/ldb_tdb/ldb_tdb_wrap.c
@@ -0,0 +1,153 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2005
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "ldb_includes.h"
+
+#include "ldb_tdb.h"
+
+/*
+  the purpose of this code is to work around the braindead posix locking
+  rules, to allow us to have a ldb open more than once while allowing 
+  locking to work
+*/
+
+struct ltdb_wrap {
+	struct ltdb_wrap *next, *prev;
+	struct tdb_context *tdb;
+	dev_t device;
+	ino_t inode;
+};
+
+static struct ltdb_wrap *tdb_list;
+
+/* destroy the last connection to a tdb */
+static int ltdb_wrap_destructor(struct ltdb_wrap *w)
+{
+	tdb_close(w->tdb);
+	if (w->next) {
+		w->next->prev = w->prev;
+	}
+	if (w->prev) {
+		w->prev->next = w->next;
+	}
+	if (w == tdb_list) {
+		tdb_list = w->next;
+	}
+	return 0;
+}				 
+
+static void ltdb_log_fn(struct tdb_context *tdb, enum tdb_debug_level level, const char *fmt, ...) PRINTF_ATTRIBUTE(3, 4);
+static void ltdb_log_fn(struct tdb_context *tdb, enum tdb_debug_level level, const char *fmt, ...)
+{
+	va_list ap;
+	const char *name = tdb_name(tdb);
+	struct ldb_context *ldb = talloc_get_type(tdb_get_logging_private(tdb), struct ldb_context);
+	enum ldb_debug_level ldb_level;
+	char *message; 
+	va_start(ap, fmt);
+	message = talloc_vasprintf(ldb, fmt, ap);
+	va_end(ap);
+
+	switch (level) {
+	case TDB_DEBUG_FATAL:
+		ldb_level = LDB_DEBUG_FATAL;
+		break;
+	case TDB_DEBUG_ERROR:
+		ldb_level = LDB_DEBUG_ERROR;
+		break;
+	case TDB_DEBUG_WARNING:
+		ldb_level = LDB_DEBUG_WARNING;
+		break;
+	case TDB_DEBUG_TRACE:
+		ldb_level = LDB_DEBUG_TRACE;
+		break;
+	default:
+		ldb_level = LDB_DEBUG_FATAL;
+	}
+
+	ldb_debug(ldb, ldb_level, "ltdb: tdb(%s): %s", name, message);
+	talloc_free(message);
+}
+
+/*
+  wrapped connection to a tdb database. The caller should _not_ free
+  this as it is not a talloc structure (as tdb does not use talloc
+  yet). It will auto-close when the caller frees the mem_ctx that is
+  passed to this call
+ */
+struct tdb_context *ltdb_wrap_open(TALLOC_CTX *mem_ctx,
+				   const char *path, int hash_size, 
+				   int tdb_flags,
+				   int open_flags, mode_t mode, 
+				   struct ldb_context *ldb)
+{
+	struct ltdb_wrap *w;
+	struct stat st;
+	struct tdb_logging_context log_ctx;
+
+	log_ctx.log_fn = ltdb_log_fn;
+	log_ctx.log_private = ldb;
+
+	if (stat(path, &st) == 0) {
+		for (w=tdb_list;w;w=w->next) {
+			if (st.st_dev == w->device && st.st_ino == w->inode) {
+				if (!talloc_reference(mem_ctx, w)) {
+					return NULL;
+				}
+				return w->tdb;
+			}
+		}
+	}
+
+	w = talloc(mem_ctx, struct ltdb_wrap);
+	if (w == NULL) {
+		return NULL;
+	}
+
+	w->tdb = tdb_open_ex(path, hash_size, tdb_flags, open_flags, mode, &log_ctx, NULL);
+	if (w->tdb == NULL) {
+		talloc_free(w);
+		return NULL;
+	}
+
+	if (fstat(tdb_fd(w->tdb), &st) != 0) {
+		tdb_close(w->tdb);
+		talloc_free(w);
+		return NULL;
+	}
+
+	w->device = st.st_dev;
+	w->inode  = st.st_ino;
+
+	talloc_set_destructor(w, ltdb_wrap_destructor);
+
+	w->next = tdb_list;
+	w->prev = NULL;
+	if (tdb_list) {
+		tdb_list->prev = w;
+	}
+	tdb_list = w;
+	
+	return w->tdb;
+}
+