make a more recent snapshot of ldb available to interested

people. Note that I decided to make it LGPL.

ldb is not finished yet, but enough of it is there for people to get
an idea of what it does, and quite a few simple tests work
(This used to be commit dc6f41f9e777d37f883303ddef0d96840d80f78e)

36 files changed, 5656 insertions, 0 deletions

diff --git a/source4/lib/ldb/Makefile.ldb b/source4/lib/ldb/Makefile.ldb
new file mode 100644
index 0000000000..346c041666
--- /dev/null
+++ b/source4/lib/ldb/Makefile.ldb
@@ -0,0 +1,43 @@
+CFLAGS=-Wall -g -Iinclude -I. -DSTANDALONE=1 -DUSE_MMAP=1
+OPENLDAP=/home/tridge/samba/openldap/prefix
+
+LIB_FLAGS=-Llib -lldb -L$(OPENLDAP)/lib -lldap 
+
+TDB_OBJ=tdb/tdb.o tdb/spinlock.o
+
+LDB_TDB_OBJ=ldb_tdb/ldb_match.o ldb_tdb/ldb_tdb.o \
+	ldb_tdb/ldb_pack.o ldb_tdb/ldb_search.o ldb_tdb/ldb_index.o
+
+LDB_LDAP_OBJ=ldb_ldap/ldb_ldap.o
+
+COMMON_OBJ=common/ldb.o common/ldb_ldif.o common/util.o common/ldb_parse.o
+
+OBJS =  $(COMMON_OBJ) $(LDB_TDB_OBJ) $(TDB_OBJ) $(LDB_LDAP_OBJ)
+
+LDB_LIB = lib/libldb.a
+
+BINS = bin/ldbadd bin/ldbsearch bin/ldbdel
+
+LIBS = $(LDB_LIB)($(OBJS))
+
+all: $(BINS) $(LIBS)
+
+lib/libldb.a: $(OBJS)
+
+bin/ldbadd: tools/ldbadd.o $(LIBS)
+	$(CC) -o bin/ldbadd tools/ldbadd.o $(LIB_FLAGS)
+
+bin/ldbsearch: tools/ldbsearch.o $(LIBS)
+	$(CC) -o bin/ldbsearch tools/ldbsearch.o $(LIB_FLAGS)
+
+bin/ldbdel: tools/ldbdel.o $(LIBS)
+	$(CC) -o bin/ldbdel tools/ldbdel.o $(LIB_FLAGS)
+
+clean:
+	rm -f */*.o *~ */*~ $(BINS) $(LDB_LIB)
+
+proto:
+	mkproto.pl */*.c > include/proto.h
+
+etags:
+	etags */*.[ch]
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
new file mode 100644
index 0000000000..90b77e1e7f
--- /dev/null
+++ b/source4/lib/ldb/common/ldb.c
@@ -0,0 +1,129 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb core API
+ *
+ *  Description: core API routines interfacing to ldb backends
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+/* 
+ connect to a database. The URL can either be one of the following forms
+   ldb://path
+   ldapi://path
+
+   flags is made up of LDB_FLG_*
+
+   the options are passed uninterpreted to the backend, and are
+   backend specific
+*/
+struct ldb_context *ldb_connect(const char *url, unsigned int flags,
+				const char *options[])
+{
+
+	if (strncmp(url, "tdb:", 4) == 0) {
+		return ltdb_connect(url, flags, options);
+	}
+
+	if (strncmp(url, "ldap", 4) == 0) {
+		return lldb_connect(url, flags, options);
+	}
+
+	errno = EINVAL;
+	return NULL;
+}
+
+/*
+  close the connection to the database
+*/
+int ldb_close(struct ldb_context *ldb)
+{
+	return ldb->ops->close(ldb);
+}
+
+
+/*
+  search the database given a LDAP-like search expression
+
+  return the number of records found, or -1 on error
+*/
+int ldb_search(struct ldb_context *ldb, 
+	       const char *base,
+	       enum ldb_scope scope,
+	       const char *expression,
+	       const char *attrs[], struct ldb_message ***res)
+{
+	return ldb->ops->search(ldb, base, scope, expression, attrs, res);
+}
+
+/* 
+   free a set of messages returned by ldb_search
+*/
+int ldb_search_free(struct ldb_context *ldb, struct ldb_message **msgs)
+{
+	return ldb->ops->search_free(ldb, msgs);
+}
+
+
+/*
+  add a record to the database. Will fail if a record with the given class and key
+  already exists
+*/
+int ldb_add(struct ldb_context *ldb, 
+	    const struct ldb_message *message)
+{
+	return ldb->ops->add(ldb, message);
+}
+
+/*
+  modify the specified attributes of a record
+*/
+int ldb_modify(struct ldb_context *ldb, 
+	       const struct ldb_message *message)
+{
+	return ldb->ops->modify(ldb, message);
+}
+
+
+/*
+  delete a record from the database
+*/
+int ldb_delete(struct ldb_context *ldb, const char *dn)
+{
+	return ldb->ops->delete(ldb, dn);
+}
+
+/*
+  return extended error information 
+*/
+const char *ldb_errstring(struct ldb_context *ldb)
+{
+	return ldb->ops->errstring(ldb);
+}
diff --git a/source4/lib/ldb/common/ldb_ldif.c b/source4/lib/ldb/common/ldb_ldif.c
new file mode 100644
index 0000000000..198c984823
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_ldif.c
@@ -0,0 +1,476 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldif routines
+ *
+ *  Description: ldif pack/unpack routines
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+
+/*
+  this base64 decoder was taken from jitterbug (written by tridge).
+  we might need to replace it with a new version
+*/
+static int base64_decode(char *s)
+{
+	const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+	int bit_offset, byte_offset, idx, i, n;
+	unsigned char *d = (unsigned char *)s;
+	char *p;
+
+	n=i=0;
+
+	while (*s && (p=strchr(b64,*s))) {
+		idx = (int)(p - b64);
+		byte_offset = (i*6)/8;
+		bit_offset = (i*6)%8;
+		d[byte_offset] &= ~((1<<(8-bit_offset))-1);
+		if (bit_offset < 3) {
+			d[byte_offset] |= (idx << (2-bit_offset));
+			n = byte_offset+1;
+		} else {
+			d[byte_offset] |= (idx >> (bit_offset-2));
+			d[byte_offset+1] = 0;
+			d[byte_offset+1] |= (idx << (8-(bit_offset-2))) & 0xFF;
+			n = byte_offset+2;
+		}
+		s++; i++;
+	}
+
+	if (*s && !p) {
+		/* the only termination allowed */
+		if (*s != '=') {
+			return -1;
+		}
+	}
+
+	/* null terminate */
+	d[n] = 0;
+	return n;
+}
+
+
+/*
+  encode as base64
+  caller frees
+*/
+char *ldb_base64_encode(const char *buf, int len)
+{
+	const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+	int bit_offset, byte_offset, idx, i;
+	unsigned char *d = (unsigned char *)buf;
+	int bytes = (len*8 + 5)/6;
+	char *out;
+
+	out = malloc(bytes+2);
+	if (!out) return NULL;
+
+	for (i=0;i<bytes;i++) {
+		byte_offset = (i*6)/8;
+		bit_offset = (i*6)%8;
+		if (bit_offset < 3) {
+			idx = (d[byte_offset] >> (2-bit_offset)) & 0x3F;
+		} else {
+			idx = (d[byte_offset] << (bit_offset-2)) & 0x3F;
+			if (byte_offset+1 < len) {
+				idx |= (d[byte_offset+1] >> (8-(bit_offset-2)));
+			}
+		}
+		out[i] = b64[idx];
+	}
+
+	out[i++] = '=';
+	out[i] = 0;
+
+	return out;
+}
+
+/*
+  see if a buffer should be base64 encoded
+*/
+int ldb_should_b64_encode(const struct ldb_val *val)
+{
+	int i;
+	unsigned char *p = val->data;
+
+	if (val->length == 0 || p[0] == ' ' || p[0] == ':') {
+		return 1;
+	}
+
+	for (i=0; i<val->length; i++) {
+		if (!isprint(p[i]) || p[i] == '\n') {
+			return 1;
+		}
+	}
+	return 0;
+}
+
+/* this macro is used to handle the return checking on fprintf_fn() */
+#define CHECK_RET do { if (ret < 0) return ret; total += ret; } while (0)
+
+/*
+  write a line folded string onto a file
+*/
+static int fold_string(int (*fprintf_fn)(void *, const char *, ...), void *private,
+			const char *buf, size_t length, int start_pos)
+{
+	int i;
+	int total=0, ret;
+
+	for (i=0;i<length;i++) {
+		ret = fprintf_fn(private, "%c", buf[i]);
+		CHECK_RET;
+		if (i != (length-1) && (i + start_pos) % 77 == 0) {
+			ret = fprintf_fn(private, "\n ");
+			CHECK_RET;
+		}
+	}
+
+	return total;
+}
+
+/*
+  encode as base64 to a file
+*/
+static int base64_encode_f(int (*fprintf_fn)(void *, const char *, ...), void *private,
+			   const char *buf, int len, int start_pos)
+{
+	char *b = ldb_base64_encode(buf, len);
+	int ret;
+
+	if (!b) {
+		return -1;
+	}
+
+	ret = fold_string(fprintf_fn, private, b, strlen(b), start_pos);
+
+	free(b);
+	return ret;
+}
+
+/*
+  write to ldif, using a caller supplied write method
+*/
+int ldif_write(int (*fprintf_fn)(void *, const char *, ...), 
+	       void *private,
+	       const struct ldb_message *msg)
+{
+	int i;
+	int total=0, ret;
+
+	ret = fprintf_fn(private, "dn: %s\n", msg->dn);
+	CHECK_RET;
+
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_should_b64_encode(&msg->elements[i].value)) {
+			ret = fprintf_fn(private, "%s:: ", msg->elements[i].name);
+			CHECK_RET;
+			ret = base64_encode_f(fprintf_fn, private, 
+					      msg->elements[i].value.data, 
+					      msg->elements[i].value.length,
+					      strlen(msg->elements[i].name)+3);
+			CHECK_RET;
+			ret = fprintf_fn(private, "\n");
+			CHECK_RET;
+		} else {
+			ret = fprintf_fn(private, "%s: ", msg->elements[i].name);
+			CHECK_RET;
+			ret = fold_string(fprintf_fn, private,
+					  msg->elements[i].value.data,
+					  msg->elements[i].value.length,
+					  strlen(msg->elements[i].name)+2);
+			CHECK_RET;
+			ret = fprintf_fn(private, "\n");
+			CHECK_RET;
+		}
+	}
+	ret = fprintf_fn(private,"\n");
+	CHECK_RET;
+
+	return total;
+}
+
+#undef CHECK_RET
+
+
+/*
+  pull a ldif chunk, which is defined as a piece of data ending in \n\n or EOF
+  this routine removes any RFC2849 continuations and comments
+
+  caller frees
+*/
+static char *next_chunk(int (*fgetc_fn)(void *), void *private)
+{
+	size_t alloc_size=0, chunk_size = 0;
+	char *chunk = NULL;
+	int c;
+	int in_comment = 0;
+
+	while ((c = fgetc_fn(private)) != EOF) {
+		if (chunk_size == alloc_size) {
+			char *c2;
+			alloc_size += 1024;
+			c2 = realloc_p(chunk, char, alloc_size);
+			if (!c2) {
+				free(chunk);
+				errno = ENOMEM;
+				return NULL;
+			}
+			chunk = c2;
+		}
+
+		if (in_comment) {
+			if (c == '\n') {
+				in_comment = 0;
+			}
+			continue;			
+		}
+		
+		/* handle continuation lines - see RFC2849 */
+		if (c == ' ' && chunk_size > 1 && chunk[chunk_size-1] == '\n') {
+			chunk_size--;
+			continue;
+		}
+		
+		/* chunks are terminated by a double line-feed */
+		if (c == '\n' && chunk_size > 0 && chunk[chunk_size-1] == '\n') {
+			chunk[chunk_size-1] = 0;
+			return chunk;
+		}
+
+		if (c == '#' && (chunk_size == 0 || chunk[chunk_size-1] == '\n')) {
+			in_comment = 1;
+			continue;
+		}
+
+		/* ignore leading blank lines */
+		if (chunk_size == 0 && c == '\n') {
+			continue;
+		}
+
+		chunk[chunk_size++] = c;
+	}
+
+	return chunk;
+}
+
+
+/* simple ldif attribute parser */
+static int next_attr(char **s, char **attr, struct ldb_val *value)
+{
+	char *p;
+	int base64_encoded = 0;
+
+	p = strchr(*s, ':');
+	if (!p) {
+		return -1;
+	}
+
+	*p++ = 0;
+
+	if (*p == ':') {
+		base64_encoded = 1;
+		p++;
+	}
+
+	*attr = *s;
+
+	while (isspace(*p)) {
+		p++;
+	}
+
+	value->data = p;
+
+	p = strchr(p, '\n');
+
+	if (!p) {
+		value->length = strlen((char *)value->data);
+		*s = ((char *)value->data) + value->length;
+	} else {
+		value->length = p - (char *)value->data;
+		*s = p+1;
+		*p = 0;
+	}
+
+	if (base64_encoded) {
+		int len = base64_decode(value->data);
+		if (len == -1) {
+			/* it wasn't valid base64 data */
+			return -1;
+		}
+		value->length = len;
+	}
+
+	return 0;
+}
+
+
+/*
+  free a message from a ldif_read
+*/
+void ldif_read_free(struct ldb_message *msg)
+{
+	if (msg->elements) free(msg->elements);
+	if (msg->private) free(msg->private);
+	free(msg);
+}
+
+/*
+ read from a LDIF source, creating a ldb_message
+*/
+struct ldb_message *ldif_read(int (*fgetc_fn)(void *), void *private)
+{
+	struct ldb_message *msg;
+	char *attr=NULL, *chunk=NULL, *s;
+	struct ldb_val value;
+
+	value.data = NULL;
+
+	msg = malloc_p(struct ldb_message);
+	if (!msg) return NULL;
+
+	msg->dn = NULL;
+	msg->elements = NULL;
+	msg->num_elements = 0;
+	msg->private = NULL;
+
+	chunk = next_chunk(fgetc_fn, private);
+	if (!chunk) {
+		goto failed;
+	}
+
+	msg->private = chunk;
+	s = chunk;
+
+	if (next_attr(&s, &attr, &value) != 0) {
+		goto failed;
+	}
+	
+	/* first line must be a dn */
+	if (strcmp(attr, "dn") != 0) {
+		fprintf(stderr, "First line must be a dn not '%s'\n", attr);
+		goto failed;
+	}
+
+	msg->dn = value.data;
+
+	while (next_attr(&s, &attr, &value) == 0) {
+		msg->elements = realloc_p(msg->elements, 
+					  struct ldb_message_element, 
+					  msg->num_elements+1);
+		if (!msg->elements) {
+			goto failed;
+		}
+		msg->elements[msg->num_elements].flags = 0;
+		msg->elements[msg->num_elements].name = attr;
+		msg->elements[msg->num_elements].value = value;
+		msg->num_elements++;
+	}
+
+	return msg;
+
+failed:
+	if (msg) ldif_read_free(msg);
+	return NULL;
+}
+
+
+
+/*
+  a wrapper around ldif_read() for reading from FILE*
+*/
+struct ldif_read_file_state {
+	FILE *f;
+};
+
+static int fgetc_file(void *private)
+{
+	struct ldif_read_file_state *state = private;
+	return fgetc(state->f);
+}
+
+struct ldb_message *ldif_read_file(FILE *f)
+{
+	struct ldif_read_file_state state;
+	state.f = f;
+	return ldif_read(fgetc_file, &state);
+}
+
+
+/*
+  a wrapper around ldif_read() for reading from const char*
+*/
+struct ldif_read_string_state {
+	const char *s;
+};
+
+static int fgetc_string(void *private)
+{
+	struct ldif_read_string_state *state = private;
+	if (state->s[0] != 0) {
+		return *state->s++;
+	}
+	return EOF;
+}
+
+struct ldb_message *ldif_read_string(const char *s)
+{
+	struct ldif_read_string_state state;
+	state.s = s;
+	return ldif_read(fgetc_string, &state);
+}
+
+
+/*
+  wrapper around ldif_write() for a file
+*/
+struct ldif_write_file_state {
+	FILE *f;
+};
+
+static int fprintf_file(void *private, const char *fmt, ...)
+{
+	struct ldif_write_file_state *state = private;
+	int ret;
+	va_list ap;
+
+	va_start(ap, fmt);
+	ret = vfprintf(state->f, fmt, ap);
+	va_end(ap);
+	return ret;
+}
+
+int ldif_write_file(FILE *f, const struct ldb_message *msg)
+{
+	struct ldif_write_file_state state;
+	state.f = f;
+	return ldif_write(fprintf_file, &state, msg);
+}
diff --git a/source4/lib/ldb/common/ldb_parse.c b/source4/lib/ldb/common/ldb_parse.c
new file mode 100644
index 0000000000..4f8d469e6c
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_parse.c
@@ -0,0 +1,460 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb expression parsing
+ *
+ *  Description: parse LDAP-like search expressions
+ *
+ *  Author: Andrew Tridgell
+ */
+
+/*
+  TODO:
+      - add RFC2254 binary string handling
+      - possibly add ~=, <= and >= handling
+      - expand the test suite
+      - add better parse error handling
+
+*/
+
+#include "includes.h"
+
+
+/*
+a filter is defined by:
+               <filter> ::= '(' <filtercomp> ')'
+               <filtercomp> ::= <and> | <or> | <not> | <simple>
+               <and> ::= '&' <filterlist>
+               <or> ::= '|' <filterlist>
+               <not> ::= '!' <filter>
+               <filterlist> ::= <filter> | <filter> <filterlist>
+               <simple> ::= <attributetype> <filtertype> <attributevalue>
+               <filtertype> ::= '=' | '~=' | '<=' | '>='
+*/
+
+/*
+  return next token element. Caller frees
+*/
+static char *ldb_parse_lex(const char **s)
+{
+	const char *p = *s;
+	char *ret;
+
+	while (isspace(*p)) {
+		p++;
+	}
+	*s = p;
+
+	if (*p == 0) {
+		return NULL;
+	}
+
+	if (strchr("()&|=!", *p)) {
+		(*s) = p+1;
+		ret = strndup(p, 1);
+		if (!ret) {
+			errno = ENOMEM;
+		}
+		return ret;
+	}
+
+	while (*p && (isalnum(*p) || !strchr("()&|=!", *p))) {
+		p++;
+	}
+
+	if (p == *s) {
+		return NULL;
+	}
+
+	ret = strndup(*s, p - *s);
+	if (!ret) {
+		errno = ENOMEM;
+	}
+
+	*s = p;
+
+	return ret;
+}
+
+/*
+  find a matching close brace in a string
+*/
+static const char *match_brace(const char *s)
+{
+	unsigned int count = 0;
+	while (*s && (count != 0 || *s != ')')) {
+		if (*s == '(') {
+			count++;
+		}
+		if (*s == ')') {
+			count--;
+		}
+		s++;
+	}
+	if (! *s) {
+		return NULL;
+	}
+	return s;
+}
+
+
+static struct ldb_parse_tree *ldb_parse_filter(const char **s);
+
+/*
+  <simple> ::= <attributetype> <filtertype> <attributevalue>
+*/
+static struct ldb_parse_tree *ldb_parse_simple(const char *s)
+{
+	char *eq, *val, *l;
+	struct ldb_parse_tree *ret;
+
+	l = ldb_parse_lex(&s);
+	if (!l) {
+		fprintf(stderr, "Unexpected end of expression\n");
+		return NULL;
+	}
+
+	if (strchr("()&|=", *l)) {
+		fprintf(stderr, "Unexpected token '%s'\n", l);
+		free(l);
+		return NULL;
+	}
+
+	eq = ldb_parse_lex(&s);
+	if (!eq || strcmp(eq, "=") != 0) {
+		fprintf(stderr, "Expected '='\n");
+		free(l);
+		if (eq) free(eq);
+		return NULL;
+	}
+	free(eq);
+
+	val = ldb_parse_lex(&s);
+	if (val && strchr("()&|=", *val)) {
+		fprintf(stderr, "Unexpected token '%s'\n", val);
+		free(l);
+		if (val) free(val);
+		return NULL;
+	}
+	
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = LDB_OP_SIMPLE;
+	ret->u.simple.attr = l;
+	ret->u.simple.value.data = val;
+	ret->u.simple.value.length = val?strlen(val):0;
+
+	return ret;
+}
+
+
+/*
+  parse a filterlist
+  <and> ::= '&' <filterlist>
+  <or> ::= '|' <filterlist>
+  <filterlist> ::= <filter> | <filter> <filterlist>
+*/
+static struct ldb_parse_tree *ldb_parse_filterlist(enum ldb_parse_op op, const char *s)
+{
+	struct ldb_parse_tree *ret, *next;
+
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = op;
+	ret->u.list.num_elements = 1;
+	ret->u.list.elements = malloc_p(struct ldb_parse_tree *);
+	if (!ret->u.list.elements) {
+		errno = ENOMEM;
+		free(ret);
+		return NULL;
+	}
+
+	ret->u.list.elements[0] = ldb_parse_filter(&s);
+	if (!ret->u.list.elements[0]) {
+		free(ret->u.list.elements);
+		free(ret);
+		return NULL;
+	}
+
+	while (isspace(*s)) s++;
+
+	while (*s && (next = ldb_parse_filter(&s))) {
+		struct ldb_parse_tree **e;
+		e = realloc_p(ret->u.list.elements, 
+			      struct ldb_parse_tree *, 
+			      ret->u.list.num_elements+1);
+		if (!e) {
+			errno = ENOMEM;
+			ldb_parse_tree_free(next);
+			ldb_parse_tree_free(ret);
+			return NULL;
+		}
+		ret->u.list.elements = e;
+		ret->u.list.elements[ret->u.list.num_elements] = next;
+		ret->u.list.num_elements++;
+		while (isspace(*s)) s++;
+	}
+
+	return ret;
+}
+
+
+/*
+  <not> ::= '!' <filter>
+*/
+static struct ldb_parse_tree *ldb_parse_not(const char *s)
+{
+	struct ldb_parse_tree *ret;
+
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = LDB_OP_NOT;
+	ret->u.not.child = ldb_parse_filter(&s);
+	if (!ret->u.not.child) {
+		free(ret);
+		return NULL;
+	}
+
+	return ret;
+}
+
+/*
+  parse a filtercomp
+  <filtercomp> ::= <and> | <or> | <not> | <simple>
+*/
+static struct ldb_parse_tree *ldb_parse_filtercomp(const char *s)
+{
+	while (isspace(*s)) s++;
+
+	switch (*s) {
+	case '&':
+		return ldb_parse_filterlist(LDB_OP_AND, s+1);
+
+	case '|':
+		return ldb_parse_filterlist(LDB_OP_OR, s+1);
+
+	case '!':
+		return ldb_parse_not(s+1);
+
+	case '(':
+	case ')':
+		fprintf(stderr, "Unexpected token '%c'\n", *s);
+		return NULL;
+	}
+
+	return ldb_parse_simple(s);
+}
+
+
+/*
+  <filter> ::= '(' <filtercomp> ')'
+*/
+static struct ldb_parse_tree *ldb_parse_filter(const char **s)
+{
+	char *l, *s2;
+	const char *p, *p2;
+	struct ldb_parse_tree *ret;
+
+	l = ldb_parse_lex(s);
+	if (!l) {
+		fprintf(stderr, "Unexpected end of expression\n");
+		return NULL;
+	}
+
+	if (strcmp(l, "(") != 0) {
+		free(l);
+		fprintf(stderr, "Expected '('\n");
+		return NULL;
+	}
+	free(l);
+
+	p = match_brace(*s);
+	if (!p) {
+		fprintf(stderr, "Parse error - mismatched braces\n");
+		return NULL;
+	}
+	p2 = p + 1;
+
+	s2 = strndup(*s, p - *s);
+	if (!s2) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret = ldb_parse_filtercomp(s2);
+	free(s2);
+
+	*s = p2;
+
+	return ret;
+}
+
+
+/*
+  main parser entry point. Takes a search string and returns a parse tree
+
+  expression ::= <simple> | <filter>
+*/
+struct ldb_parse_tree *ldb_parse_tree(const char *s)
+{
+	while (isspace(*s)) s++;
+
+	if (*s == '(') {
+		return ldb_parse_filter(&s);
+	}
+
+	return ldb_parse_simple(s);
+}
+
+/*
+  free a parse tree returned from ldb_parse_tree()
+*/
+void ldb_parse_tree_free(struct ldb_parse_tree *tree)
+{
+	int i;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		free(tree->u.simple.attr);
+		if (tree->u.simple.value.data) free(tree->u.simple.value.data);
+		break;
+
+	case LDB_OP_AND:
+	case LDB_OP_OR:
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			ldb_parse_tree_free(tree->u.list.elements[i]);
+		}
+		if (tree->u.list.elements) free(tree->u.list.elements);
+		break;
+
+	case LDB_OP_NOT:
+		ldb_parse_tree_free(tree->u.not.child);
+		break;
+	}
+
+	free(tree);
+}
+
+#if TEST_PROGRAM
+/*
+  return a string representation of a parse tree
+  used for debugging
+*/
+static char *tree_string(struct ldb_parse_tree *tree)
+{
+	char *s = NULL;
+	char *s1, *s2;
+	int i;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		asprintf(&s, "( %s = \"%s\" )", tree->u.simple.attr, 
+			 (char *)tree->u.simple.value.data);
+		break;
+
+	case LDB_OP_AND:
+	case LDB_OP_OR:
+		asprintf(&s, "( %c", tree->operation==LDB_OP_AND?'&':'|');
+		if (!s) return NULL;
+
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			s1 = tree_string(tree->u.list.elements[i]);
+			if (!s1) {
+				free(s);
+				return NULL;
+			}
+			asprintf(&s2, "%s %s", s, s1);
+			free(s);
+			free(s1);
+			s = s2;
+		}
+		if (!s) {
+			return NULL;
+		}
+		asprintf(&s2, "%s )", s);
+		free(s);
+		s = s2;
+		break;
+
+	case LDB_OP_NOT:
+		s1 = tree_string(tree->u.not.child);
+		asprintf(&s, "( ! %s )", s1);
+		free(s1);
+		break;
+	}
+	return s;
+}
+
+
+/*
+  print a tree
+ */
+static void print_tree(struct ldb_parse_tree *tree)
+{
+	char *s = tree_string(tree);
+	printf("%s\n", s);
+	free(s);
+}
+
+
+ int main(void)
+{
+	char line[1000];
+	int ret = 0;
+
+	while (fgets(line, sizeof(line)-1, stdin)) {
+		struct ldb_parse_tree *tree;
+
+		if (line[strlen(line)-1] == '\n') {
+			line[strlen(line)-1] = 0;
+		}
+		tree = ldb_parse_tree(line);
+		if (!tree) {
+			fprintf(stderr, "Failed to parse\n");
+			ret = 1;
+			continue;
+		}
+		print_tree(tree);
+		ldb_parse_tree_free(tree);
+	}
+	
+	return ret;
+}
+#endif /* TEST_PROGRAM */
+
diff --git a/source4/lib/ldb/common/util.c b/source4/lib/ldb/common/util.c
new file mode 100644
index 0000000000..d198a1ad92
--- /dev/null
+++ b/source4/lib/ldb/common/util.c
@@ -0,0 +1,102 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb utility functions
+ *
+ *  Description: miscellanous utility functions for ldb
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+
+#define MAX_MALLOC_SIZE 0x7fffffff
+
+/*
+  realloc an array, checking for integer overflow in the array size
+*/
+void *realloc_array(void *ptr, size_t el_size, unsigned count)
+{
+	if (count == 0 ||
+	    count >= MAX_MALLOC_SIZE/el_size) {
+		return NULL;
+	}
+	if (!ptr) {
+		return malloc(el_size * count);
+	}
+	return realloc(ptr, el_size * count);
+}
+
+
+/*
+  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
+*/
+int list_find(const void *needle, 
+	      const void *base, size_t nmemb, size_t size, comparison_fn_t comp_fn)
+{
+	const char *base_p = 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) {
+		size_t test_t;
+		int r;
+
+		test_i = (min_i + max_i) / 2;
+		r = comp_fn(needle, *(void **)(base_p + (size * test_i)));
+		if (r == 0) {
+			/* scan back for first element */
+			while (test_t > 0 &&
+			       comp_fn(needle, *(void **)(base_p + (size * (test_i-1)))) == 0) {
+				test_i--;
+			}
+			return test_i;
+		}
+		if (r == -1) {
+			max_i = test_i - 1;
+		}
+		if (r == 1) {
+			min_i = test_i + 1;
+		}
+	}
+
+	if (comp_fn(needle, *(void **)(base_p + (size * min_i))) == 0) {
+		return min_i;
+	}
+
+	return -1;
+}
diff --git a/source4/lib/ldb/docs/design.txt b/source4/lib/ldb/docs/design.txt
new file mode 100644
index 0000000000..0bb278b5b4
--- /dev/null
+++ b/source4/lib/ldb/docs/design.txt
@@ -0,0 +1,41 @@
+The list of indexed fields
+--------------------------
+
+dn=@INDEXLIST
+	list of field names that are indexed
+
+	contains fields of type @IDXATTR which contain attriute names
+	of indexed fields
+
+
+Data records
+------------
+
+for each user record in the db there is:
+    main record
+	 key: DN=dn
+	 data: packed attribute/value list
+
+    a index record for each indexed field in the record
+
+
+Index Records
+-------------
+
+The index records contain the list of dn's that contain records
+matching the index key
+
+All index records are of the form:
+      dn=@INDEX:field:value
+
+and contain fields of type @IDX which are the dns of the records
+that have that value for some attribute
+
+
+Search Expressions
+------------------
+
+Very similar to LDAP search expressions, but does not allow ~=, <= or >=
+
+	attrib0 := (field=value)
+	attrib := attrib0 | (attrib&&attrib) | (attrib||attrib) | !attrib
diff --git a/source4/lib/ldb/include/includes.h b/source4/lib/ldb/include/includes.h
new file mode 100644
index 0000000000..ea8540d330
--- /dev/null
+++ b/source4/lib/ldb/include/includes.h
@@ -0,0 +1,22 @@
+/*
+  a temporary includes file until I work on the ldb build system
+*/
+
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <ctype.h>
+#include <fcntl.h>
+#include <stdarg.h>
+#include <signal.h>
+#include "ldb.h"
+#include "ldb_parse.h"
+
+#define malloc_p(type) (type *)malloc(sizeof(type))
+#define malloc_array_p(type, count) (type *)realloc_array(NULL, sizeof(type), count)
+#define realloc_p(p, type, count) (type *)realloc_array(p, sizeof(type), count)
+
+#include "tdb/tdb.h"
+#include "proto.h"
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
new file mode 100644
index 0000000000..35474d23c5
--- /dev/null
+++ b/source4/lib/ldb/include/ldb.h
@@ -0,0 +1,204 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb header
+ *
+ *  Description: defines for base ldb API
+ *
+ *  Author: Andrew Tridgell
+ */
+
+/*
+  major restrictions as compared to normal LDAP:
+
+     - no async calls.
+     - each record must have a unique key field
+     - the key must be representable as a NULL terminated C string and may not 
+       contain a comma or braces
+
+  major restrictions as compared to tdb:
+
+     - no explicit locking calls
+
+*/
+
+
+/*
+  an individual lump of data in a result comes in this format. The
+  pointer will usually be to a UTF-8 string if the application is
+  sensible, but it can be to anything you like, including binary data
+  blobs of arbitrary size.
+*/
+struct ldb_val {
+	unsigned int length;
+	void *data;
+};
+
+/* these flags are used in ldd_message_element.flags fields. The
+   LDA_FLAGS_MOD_* flags are used in ldap_modify() calls to specify
+   whether attributes are being added, deleted or modified */
+#define LDB_FLAG_MOD_MASK  0x3
+#define LDB_FLAG_MOD_ADD     1
+#define LDB_FLAG_MOD_REPLACE 2
+#define LDB_FLAG_MOD_DELETE  3
+
+
+/*
+  results are given back as arrays of ldb_message_element
+*/
+struct ldb_message_element {
+	unsigned int flags;
+	char *name;
+	struct ldb_val value;
+};
+
+
+/*
+  a ldb_message represents all or part of a record. It can contain an arbitrary
+  number of elements. 
+*/
+struct ldb_message {
+	char *dn;
+	unsigned int num_elements;
+	struct ldb_message_element *elements;
+	void *private; /* private to the backend */
+};
+
+
+enum ldb_scope {LDB_SCOPE_DEFAULT=-1, 
+		LDB_SCOPE_BASE=0, 
+		LDB_SCOPE_ONELEVEL=1,
+		LDB_SCOPE_SUBTREE=2};
+
+struct ldb_context;
+
+/*
+  the fuction type for the callback used in traversing the database
+*/
+typedef int (*ldb_traverse_fn)(struct ldb_context *, const struct ldb_message *);
+
+
+/* 
+   these function pointers define the operations that a ldb backend must perform
+   they correspond exactly to the ldb_*() interface 
+*/
+struct ldb_backend_ops {
+	int (*close)(struct ldb_context *);
+	int (*search)(struct ldb_context *, const char *, enum ldb_scope,
+		      const char *, const char *[], struct ldb_message ***);
+	int (*search_free)(struct ldb_context *, struct ldb_message **);
+	int (*add)(struct ldb_context *, const struct ldb_message *);
+	int (*modify)(struct ldb_context *, const struct ldb_message *);
+	int (*delete)(struct ldb_context *, const char *);
+	const char * (*errstring)(struct ldb_context *);
+};
+
+/*
+  every ldb connection is started by establishing a ldb_context
+*/
+struct ldb_context {
+	/* a private pointer for the backend to use */
+	void *private;
+
+	/* the operations provided by the backend */
+	const struct ldb_backend_ops *ops;
+};
+
+
+#define LDB_FLG_RDONLY 1
+
+/* 
+ connect to a database. The URL can either be one of the following forms
+   ldb://path
+   ldapi://path
+
+   flags is made up of LDB_FLG_*
+
+   the options are passed uninterpreted to the backend, and are
+   backend specific
+*/
+struct ldb_context *ldb_connect(const char *url, unsigned int flags,
+				const char *options[]);
+
+/*
+  close the connection to the database
+*/
+int ldb_close(struct ldb_context *ldb);
+
+
+/*
+  search the database given a LDAP-like search expression
+
+  return the number of records found, or -1 on error
+*/
+int ldb_search(struct ldb_context *ldb, 
+	       const char *base,
+	       enum ldb_scope scope,
+	       const char *expression,
+	       const char *attrs[], struct ldb_message ***res);
+
+/* 
+   free a set of messages returned by ldb_search
+*/
+int ldb_search_free(struct ldb_context *ldb, struct ldb_message **msgs);
+
+
+/*
+  add a record to the database. Will fail if a record with the given class and key
+  already exists
+*/
+int ldb_add(struct ldb_context *ldb, 
+	    const struct ldb_message *message);
+
+/*
+  modify the specified attributes of a record
+*/
+int ldb_modify(struct ldb_context *ldb, 
+	       const struct ldb_message *message);
+
+/*
+  delete a record from the database
+*/
+int ldb_delete(struct ldb_context *ldb, const char *dn);
+
+
+/*
+  return extended error information from the last call
+*/
+const char *ldb_errstring(struct ldb_context *ldb);
+
+/*
+  ldif manipulation functions
+*/
+int ldif_write(int (*fprintf_fn)(void *, const char *, ...), 
+	       void *private,
+	       const struct ldb_message *msg);
+void ldif_read_free(struct ldb_message *msg);
+struct ldb_message *ldif_read(int (*fgetc_fn)(void *), void *private);
+struct ldb_message *ldif_read_file(FILE *f);
+struct ldb_message *ldif_read_string(const char *s);
+int ldif_write_file(FILE *f, const struct ldb_message *msg);
diff --git a/source4/lib/ldb/include/ldb_parse.h b/source4/lib/ldb/include/ldb_parse.h
new file mode 100644
index 0000000000..c0d5806cc9
--- /dev/null
+++ b/source4/lib/ldb/include/ldb_parse.h
@@ -0,0 +1,53 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb expression parse header
+ *
+ *  Description: structure for expression parsing
+ *
+ *  Author: Andrew Tridgell
+ */
+
+
+enum ldb_parse_op {LDB_OP_SIMPLE, LDB_OP_AND, LDB_OP_OR, LDB_OP_NOT};
+
+struct ldb_parse_tree {
+	enum ldb_parse_op operation;
+	union {
+		struct {
+			char *attr;
+			struct ldb_val value;
+		} simple;
+		struct {
+			unsigned int num_elements;
+			struct ldb_parse_tree **elements;
+		} list;
+		struct {
+			struct ldb_parse_tree *child;
+		} not;
+	} u;
+};
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.c b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
new file mode 100644
index 0000000000..b2f7688497
--- /dev/null
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
@@ -0,0 +1,524 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb ldap backend
+ *
+ *  Description: core files for LDAP backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include "ldb_ldap/ldb_ldap.h"
+
+#if 0
+/*
+  we don't need this right now, but will once we add more backend 
+  options
+*/
+
+/*
+  find an option in an option list (a null terminated list of strings)
+
+  this assumes the list is short. If it ever gets long then we really
+  should do this in some smarter way
+ */
+static const char *lldb_option_find(const struct lldb_private *lldb, const char *name)
+{
+	int i;
+	size_t len = strlen(name);
+
+	if (!lldb->options) return NULL;
+
+	for (i=0;lldb->options[i];i++) {		
+		if (strncmp(lldb->options[i], name, len) == 0 &&
+		    lldb->options[i][len] == '=') {
+			return &lldb->options[i][len+1];
+		}
+	}
+
+	return NULL;
+}
+#endif
+
+/*
+  close/free the connection
+*/
+static int lldb_close(struct ldb_context *ldb)
+{
+	int i, ret = 0;
+	struct lldb_private *lldb = ldb->private;
+
+	if (ldap_unbind(lldb->ldap) != LDAP_SUCCESS) {
+		ret = -1;
+	}
+
+	if (lldb->options) {
+		for (i=0;lldb->options[i];i++) {
+			free(lldb->options[i]);
+		}
+		free(lldb->options);
+	}
+	free(lldb);
+	free(ldb);
+
+	return ret;
+}
+
+/*
+  delete a record
+*/
+static int lldb_delete(struct ldb_context *ldb, const char *dn)
+{
+	struct lldb_private *lldb = ldb->private;
+	int ret = 0;
+	
+	lldb->last_rc = ldap_delete_s(lldb->ldap, dn);
+	if (lldb->last_rc != LDAP_SUCCESS) {
+		ret = -1;
+	}
+
+	return ret;
+}
+
+/*
+  free a search message
+*/
+static int lldb_msg_free(struct ldb_context *ldb, struct ldb_message *msg)
+{
+	int i;
+	free(msg->dn);
+	for (i=0;i<msg->num_elements;i++) {
+		free(msg->elements[i].name);
+		if (msg->elements[i].value.data) {
+			free(msg->elements[i].value.data);
+		}
+	}
+	if (msg->elements) free(msg->elements);
+	free(msg);
+	return 0;
+}
+
+/*
+  free a search result
+*/
+static int lldb_search_free(struct ldb_context *ldb, struct ldb_message **res)
+{
+	int i;
+	for (i=0;res[i];i++) {
+		if (lldb_msg_free(ldb, res[i]) != 0) {
+			return -1;
+		}
+	}
+	free(res);
+	return 0;
+}
+
+
+/*
+  add a single set of ldap message values to a ldb_message
+*/
+static int lldb_add_msg_attr(struct ldb_message *msg, 
+			     const char *attr, struct berval **bval)
+{
+	int count, i;
+	struct ldb_message_element *el;
+
+	count = ldap_count_values_len(bval);
+
+	if (count <= 0) {
+		return -1;
+	}
+
+	el = realloc_p(msg->elements, struct ldb_message_element, 
+		       msg->num_elements + count);
+	if (!el) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	msg->elements = el;
+
+	for (i=0;i<count;i++) {
+		msg->elements[msg->num_elements].name = strdup(attr);
+		if (!msg->elements[msg->num_elements].name) {
+			return -1;
+		}
+		msg->elements[msg->num_elements].value.data = malloc(bval[i]->bv_len);
+		if (!msg->elements[msg->num_elements].value.data) {
+			free(msg->elements[msg->num_elements].name);
+			return -1;
+		}
+		memcpy(msg->elements[msg->num_elements].value.data, 
+		       bval[i]->bv_val, bval[i]->bv_len);
+		msg->elements[msg->num_elements].value.length = bval[i]->bv_len;
+		msg->num_elements++;
+	}
+
+	return 0;
+}
+
+/*
+  search for matching records
+*/
+static int lldb_search(struct ldb_context *ldb, const char *base,
+		       enum ldb_scope scope, const char *expression,
+		       const char **attrs, struct ldb_message ***res)
+{
+	struct lldb_private *lldb = ldb->private;
+	int count, msg_count;
+	LDAPMessage *ldapres, *msg;
+
+	lldb->last_rc = ldap_search_s(lldb->ldap, base, (int)scope, 
+				      expression, attrs, 0, &ldapres);
+	if (lldb->last_rc != LDAP_SUCCESS) {
+		return -1;
+	}
+
+	count = ldap_count_entries(lldb->ldap, ldapres);
+	if (count == -1 || count == 0) {
+		ldap_msgfree(ldapres);
+		return count;
+	}
+
+	(*res) = malloc_array_p(struct ldb_message *, count+1);
+	if (! *res) {
+		ldap_msgfree(ldapres);
+		errno = ENOMEM;
+		return -1;
+	}
+
+	(*res)[0] = NULL;
+
+	msg_count = 0;
+
+	/* loop over all messages */
+	for (msg=ldap_first_entry(lldb->ldap, ldapres); 
+	     msg; 
+	     msg=ldap_next_entry(lldb->ldap, msg)) {
+		BerElement *berptr = NULL;
+		char *attr, *dn;
+
+		if (msg_count == count) {
+			/* hmm, got too many? */
+			fprintf(stderr,"Too many messages?!\n");
+			break;
+		}
+
+		(*res)[msg_count] = malloc_p(struct ldb_message);
+		if (!(*res)[msg_count]) {
+			goto failed;
+		}
+		(*res)[msg_count+1] = NULL;
+
+		dn = ldap_get_dn(lldb->ldap, msg);
+		if (!dn) {
+			goto failed;
+		}
+
+		(*res)[msg_count]->dn = strdup(dn);
+		ldap_memfree(dn);
+		if (!(*res)[msg_count]->dn) {
+			goto failed;
+		}
+
+
+		(*res)[msg_count]->num_elements = 0;
+		(*res)[msg_count]->elements = NULL;
+		(*res)[msg_count]->private = NULL;
+
+		/* loop over all attributes */
+		for (attr=ldap_first_attribute(lldb->ldap, msg, &berptr);
+		     attr;
+		     attr=ldap_next_attribute(lldb->ldap, msg, berptr)) {
+			struct berval **bval;
+			bval = ldap_get_values_len(lldb->ldap, msg, attr);
+
+			if (bval) {
+				lldb_add_msg_attr((*res)[msg_count], attr, bval);
+				ldap_value_free_len(bval);
+			}					  
+			
+			ldap_memfree(attr);
+		}
+		if (berptr) ber_free(berptr, 0);
+
+		msg_count++;
+	}
+
+	ldap_msgfree(ldapres);
+
+	return msg_count;
+
+failed:
+	if (*res) lldb_search_free(ldb, *res);
+	return -1;
+}
+
+
+/*
+  free a set of mods from lldb_msg_to_mods()
+*/
+static void lldb_mods_free(LDAPMod **mods)
+{
+	int i, j;
+
+	if (!mods) return;
+
+	for (i=0;mods[i];i++) {
+		if (mods[i]->mod_vals.modv_bvals) {
+			for (j=0;mods[i]->mod_vals.modv_bvals[j];j++) {
+				free(mods[i]->mod_vals.modv_bvals[j]);
+			}
+			free(mods[i]->mod_vals.modv_bvals);
+		}
+		free(mods[i]);
+	}
+	free(mods);
+}
+
+
+/*
+  convert a ldb_message structure to a list of LDAPMod structures
+  ready for ldap_add() or ldap_modify()
+*/
+static LDAPMod **lldb_msg_to_mods(const struct ldb_message *msg, int use_flags)
+{
+	LDAPMod **mods;
+	int i, num_vals, num_mods = 0;
+
+	/* allocate maximum number of elements needed */
+	mods = malloc_array_p(LDAPMod *, msg->num_elements+1);
+	if (!mods) {
+		errno = ENOMEM;
+		return NULL;
+	}
+	mods[0] = NULL;
+
+	for (i=0;i<msg->num_elements;i++) {
+
+		if (i > 0 && 
+		    (!use_flags || 
+		     (msg->elements[i].flags == msg->elements[i-1].flags)) &&
+		    strcmp(msg->elements[i].name, msg->elements[i-1].name) == 0) {
+			struct berval **b;
+			/* when attributes are repeated we need to extend the
+			   existing bvals array */
+			b = realloc_p(mods[num_mods-1]->mod_vals.modv_bvals, 
+				      struct berval *, num_vals+2);
+			if (!b) {
+				goto failed;
+			}
+			mods[num_mods-1]->mod_vals.modv_bvals = b;
+			b[num_vals+1] = NULL;
+			b[num_vals] = malloc_p(struct berval);
+			if (!b[num_vals]) goto failed;
+			b[num_vals]->bv_val = msg->elements[i].value.data;
+			b[num_vals]->bv_len = msg->elements[i].value.length;
+			num_vals++;
+			continue;
+		}
+
+		num_vals = 1;
+
+		mods[num_mods] = malloc_p(LDAPMod);
+		if (!mods[num_mods]) {
+			goto failed;
+		}
+		mods[num_mods+1] = NULL;
+		mods[num_mods]->mod_op = LDAP_MOD_BVALUES;
+		if (use_flags) {
+			switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
+			case LDB_FLAG_MOD_ADD:
+				mods[num_mods]->mod_op |= LDAP_MOD_ADD;
+				break;
+			case LDB_FLAG_MOD_DELETE:
+				mods[num_mods]->mod_op |= LDAP_MOD_DELETE;
+				break;
+			case LDB_FLAG_MOD_REPLACE:
+				mods[num_mods]->mod_op |= LDAP_MOD_REPLACE;
+				break;
+			}
+		}
+		mods[num_mods]->mod_type = msg->elements[i].name;
+		mods[num_mods]->mod_vals.modv_bvals = malloc_array_p(struct berval *, 2);
+		if (!mods[num_mods]->mod_vals.modv_bvals) {
+			goto failed;
+		}
+		mods[num_mods]->mod_vals.modv_bvals[0] = malloc_p(struct berval);
+		if (!mods[num_mods]->mod_vals.modv_bvals[0]) {
+			goto failed;
+		}
+		mods[num_mods]->mod_vals.modv_bvals[0]->bv_val = msg->elements[i].value.data;
+		mods[num_mods]->mod_vals.modv_bvals[0]->bv_len = msg->elements[i].value.length;
+		mods[num_mods]->mod_vals.modv_bvals[1] = NULL;
+		num_mods++;
+	}
+
+	return mods;
+
+failed:
+	lldb_mods_free(mods);
+	return NULL;
+}
+
+
+/*
+  add a record
+*/
+static int lldb_add(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	struct lldb_private *lldb = ldb->private;
+	LDAPMod **mods;
+	int ret = 0;
+
+	mods = lldb_msg_to_mods(msg, 0);
+
+	lldb->last_rc = ldap_add_s(lldb->ldap, msg->dn, mods);
+	if (lldb->last_rc != LDAP_SUCCESS) {
+		ret = -1;
+	}
+
+	lldb_mods_free(mods);
+
+	return ret;
+}
+
+
+/*
+  modify a record
+*/
+static int lldb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	struct lldb_private *lldb = ldb->private;
+	LDAPMod **mods;
+	int ret = 0;
+
+	mods = lldb_msg_to_mods(msg, 1);
+
+	lldb->last_rc = ldap_modify_s(lldb->ldap, msg->dn, mods);
+	if (lldb->last_rc != LDAP_SUCCESS) {
+		ret = -1;
+	}
+
+	lldb_mods_free(mods);
+
+	return ret;
+}
+
+
+/*
+  return extended error information
+*/
+static const char *lldb_errstring(struct ldb_context *ldb)
+{
+	struct lldb_private *lldb = ldb->private;
+	return ldap_err2string(lldb->last_rc);
+}
+
+
+static const struct ldb_backend_ops lldb_ops = {
+	lldb_close, 
+	lldb_search,
+	lldb_search_free,
+	lldb_add,
+	lldb_modify,
+	lldb_delete,
+	lldb_errstring
+};
+
+
+/*
+  connect to the database
+*/
+struct ldb_context *lldb_connect(const char *url, 
+				 unsigned int flags, 
+				 const char *options[])
+{
+	struct ldb_context *ldb = NULL;
+	struct lldb_private *lldb = NULL;
+	int i;
+
+	ldb = malloc_p(struct ldb_context);
+	if (!ldb) {
+		errno = ENOMEM;
+		goto failed;
+	}
+
+	lldb = malloc_p(struct lldb_private);
+	if (!lldb) {
+		free(ldb);
+		errno = ENOMEM;
+		goto failed;
+	}
+
+	lldb->ldap = NULL;
+	lldb->options = NULL;
+
+	lldb->last_rc = ldap_initialize(&lldb->ldap, url);
+	if (lldb->last_rc != LDAP_SUCCESS) {
+		goto failed;
+	}
+
+	ldb->ops = &lldb_ops;
+	ldb->private = lldb;
+
+	if (options) {
+		/* take a copy of the options array, so we don't have to rely
+		   on the caller keeping it around (it might be dynamic) */
+		for (i=0;options[i];i++) ;
+
+		lldb->options = malloc_array_p(char *, i+1);
+		if (!lldb->options) {
+			goto failed;
+		}
+		
+		for (i=0;options[i];i++) {
+			lldb->options[i+1] = NULL;
+			lldb->options[i] = strdup(options[i]);
+			if (!lldb->options[i]) {
+				goto failed;
+			}
+		}
+	}
+
+	return ldb;
+
+failed:
+	if (lldb && lldb->options) {
+		for (i=0;lldb->options[i];i++) {
+			free(lldb->options[i]);
+		}
+		free(lldb->options);
+	}
+	if (lldb && lldb->ldap) {
+		ldap_unbind(lldb->ldap);
+	}
+	if (lldb) free(lldb);
+	if (ldb) free(ldb);
+	return NULL;
+}
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.h b/source4/lib/ldb/ldb_ldap/ldb_ldap.h
new file mode 100644
index 0000000000..ba68283abd
--- /dev/null
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.h
@@ -0,0 +1,8 @@
+#include <ldap.h>
+
+struct lldb_private {
+	char **options;
+	const char *basedn;
+	LDAP *ldap;
+	int last_rc;
+};
diff --git a/source4/lib/ldb/ldb_tdb/.cvsignore b/source4/lib/ldb/ldb_tdb/.cvsignore
new file mode 100644
index 0000000000..8f968d06f4
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/.cvsignore
@@ -0,0 +1,7 @@
+ldbadd
+ldbsearch
+ldbdel
+test.ldb
+TAGS
+.*~
+*.o
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
new file mode 100644
index 0000000000..dda80a6b2a
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -0,0 +1,641 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb backend - indexing
+ *
+ *  Description: indexing routines for ldb tdb backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+struct dn_list {
+	unsigned int count;
+	char **dn;
+};
+
+/*
+  free a struct dn_list
+*/
+static void dn_list_free(struct dn_list *list)
+{
+	int i;
+	for (i=0;i<list->count;i++) {
+		free(list->dn[i]);
+	}
+	if (list->dn) free(list->dn);
+}
+
+/*
+  return the dn key to be used for an index
+  caller frees
+*/
+static char *ldb_dn_key(const char *attr, const struct ldb_val *value)
+{
+	char *ret = NULL;
+
+	if (ldb_should_b64_encode(value)) {
+		char *vstr = ldb_base64_encode(value->data, value->length);
+		if (!vstr) return NULL;
+		asprintf(&ret, "@INDEX:%s::%s", attr, vstr);
+		free(vstr);
+		return ret;
+	}
+
+	asprintf(&ret, "@INDEX:%s:%s", attr, (char *)value->data);
+	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)
+{
+	int i;
+	for (i=0;i<msg->num_elements;i++) {
+		if (strcmp(msg->elements[i].name, "@IDXATTR") == 0 &&
+		    strcmp((char *)msg->elements[i].value.data, attr) == 0) {
+			return i;
+		}
+	}
+	return -1;
+}
+
+/*
+  return a list of dn's that might match a simple indexed search or
+ */
+static int ltdb_index_dn_simple(struct ldb_context *ldb, 
+				struct ldb_parse_tree *tree,
+				const struct ldb_message *index_list,
+				struct dn_list *list)
+{
+	char *dn = NULL;
+	int ret, i;
+	struct ldb_message msg;
+
+	list->count = 0;
+	list->dn = NULL;
+
+	/*
+	  if the value is a wildcard then we can't do a match via indexing
+	*/
+	if (ltdb_has_wildcard(&tree->u.simple.value)) {
+		return -1;
+	}
+
+	/* 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.simple.attr) == -1) {
+		return -1;
+	}
+
+	/* the attribute is indexed. Pull the list of DNs that match the 
+	   search criterion */
+	dn = ldb_dn_key(tree->u.simple.attr, &tree->u.simple.value);
+	if (!dn) return -1;
+
+	ret = ltdb_search_dn1(ldb, dn, &msg);
+	free(dn);
+	if (ret == 0 || ret == -1) {
+		return ret;
+	}
+
+	list->dn = malloc_array_p(char *, msg.num_elements);
+	if (!list->dn) {
+		ltdb_search_dn1_free(ldb, &msg);
+	}
+
+	for (i=0;i<msg.num_elements;i++) {
+		if (strcmp(msg.elements[i].name, "@IDX") != 0) {
+			continue;
+		}
+		list->dn[list->count] = 
+			strdup((char *)msg.elements[i].value.data);
+		if (!list->dn[list->count]) {
+			dn_list_free(list);
+			ltdb_search_dn1_free(ldb, &msg);
+			return -1;
+		}
+		list->count++;
+	}
+
+	ltdb_search_dn1_free(ldb, &msg);
+
+	qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t) strcmp);
+
+	return 1;
+}
+
+/*
+  list intersection
+  list = list & list2
+  relies on the lists being sorted
+*/
+static int list_intersect(struct dn_list *list, const struct dn_list *list2)
+{
+	struct dn_list list3;
+	int i;
+
+	if (list->count == 0 || list2->count == 0) {
+		/* 0 & X == 0 */
+		dn_list_free(list);
+		return 0;
+	}
+
+	list3.dn = malloc_array_p(char *, list->count);
+	if (!list3.dn) {
+		dn_list_free(list);
+		return -1;
+	}
+	list3.count = 0;
+
+	for (i=0;i<list->count;i++) {
+		if (list_find(list->dn[i], list2->dn, list2->count, 
+			      sizeof(char *), (comparison_fn_t)strcmp) != -1) {
+			list3.dn[list3.count] = list->dn[i];
+			list3.count++;
+		} else {
+			free(list->dn[i]);
+		}		
+	}
+
+	free(list->dn);
+	list->dn = list3.dn;
+	list->count = list3.count;
+
+	return 0;
+}
+
+
+/*
+  list union
+  list = list | list2
+  relies on the lists being sorted
+*/
+static int list_union(struct dn_list *list, const struct dn_list *list2)
+{
+	int i;
+	char **d;
+	unsigned int count = list->count;
+
+	if (list->count == 0 && list2->count == 0) {
+		/* 0 | 0 == 0 */
+		dn_list_free(list);
+		return 0;
+	}
+
+	d = realloc_p(list->dn, char *, list->count + list2->count);
+	if (!d) {
+		dn_list_free(list);
+		return -1;
+	}
+	list->dn = d;
+
+	for (i=0;i<list2->count;i++) {
+		if (list_find(list2->dn[i], list->dn, count, 
+			      sizeof(char *), (comparison_fn_t)strcmp) == -1) {
+			list->dn[list->count] = strdup(list2->dn[i]);
+			if (!list->dn[list->count]) {
+				dn_list_free(list);
+				return -1;
+			}
+			list->count++;
+		}		
+	}
+
+	if (list->count != count) {
+		qsort(list->dn, list->count, sizeof(char *), (comparison_fn_t)strcmp);
+	}
+
+	return 0;
+}
+
+static int ltdb_index_dn(struct ldb_context *ldb, 
+			 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_context *ldb, 
+			    struct ldb_parse_tree *tree,
+			    const struct ldb_message *index_list,
+			    struct dn_list *list)
+{
+	int ret, i;
+	
+	ret = -1;
+	list->dn = NULL;
+	list->count = 0;
+
+	for (i=0;i<tree->u.list.num_elements;i++) {
+		struct dn_list list2;
+		int v;
+		v = ltdb_index_dn(ldb, tree->u.list.elements[i], index_list, &list2);
+
+		if (v == 0) {
+			/* 0 || X == X */
+			if (ret == -1) {
+				ret = 0;
+			}
+			continue;
+		}
+
+		if (v == -1) {
+			/* 1 || X == 1 */
+			dn_list_free(list);
+			return -1;
+		}
+
+		if (ret == -1) {
+			ret = 1;
+			*list = list2;
+		} else {
+			if (list_union(list, &list2) == -1) {
+				dn_list_free(&list2);
+				return -1;
+			}
+			dn_list_free(&list2);
+		}
+	}
+
+	if (list->count == 0) {
+		dn_list_free(list);
+		return 0;
+	}
+
+	return ret;
+}
+
+
+/*
+  NOT an index results
+ */
+static int ltdb_index_dn_not(struct ldb_context *ldb, 
+			     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 -1;
+}
+
+/*
+  AND two index results
+ */
+static int ltdb_index_dn_and(struct ldb_context *ldb, 
+			     struct ldb_parse_tree *tree,
+			     const struct ldb_message *index_list,
+			     struct dn_list *list)
+{
+	int ret, i;
+	
+	ret = -1;
+	list->dn = NULL;
+	list->count = 0;
+
+	for (i=0;i<tree->u.list.num_elements;i++) {
+		struct dn_list list2;
+		int v;
+		v = ltdb_index_dn(ldb, tree->u.list.elements[i], index_list, &list2);
+
+		if (v == 0) {
+			/* 0 && X == 0 */
+			dn_list_free(list);
+			return 0;
+		}
+
+		if (v == -1) {
+			continue;
+		}
+
+		if (ret == -1) {
+			ret = 1;
+			*list = list2;
+		} else {
+			if (list_intersect(list, &list2) == -1) {
+				dn_list_free(&list2);
+				return -1;
+			}
+			dn_list_free(&list2);
+		}
+
+		if (list->count == 0) {
+			if (list->dn) free(list->dn);
+			return 0;
+		}
+	}
+
+	return ret;
+}
+
+/*
+  return a list of dn's that might match a indexed search or
+  -1 if an error. return 0 for no matches, or 1 for matches
+ */
+static int ltdb_index_dn(struct ldb_context *ldb, 
+			 struct ldb_parse_tree *tree,
+			 const struct ldb_message *index_list,
+			 struct dn_list *list)
+{
+	int ret;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		ret = ltdb_index_dn_simple(ldb, tree, index_list, list);
+		break;
+
+	case LDB_OP_AND:
+		ret = ltdb_index_dn_and(ldb, tree, index_list, list);
+		break;
+
+	case LDB_OP_OR:
+		ret = ltdb_index_dn_or(ldb, tree, index_list, list);
+		break;
+
+	case LDB_OP_NOT:
+		ret = ltdb_index_dn_not(ldb, tree, index_list, list);
+		break;
+	}
+
+	return ret;
+}
+
+/*
+  filter a candidate dn_list from an indexed search into a set of results
+  extracting just the given attributes
+*/
+static int ldb_index_filter(struct ldb_context *ldb, struct ldb_parse_tree *tree,
+			    const char *base,
+			    enum ldb_scope scope,
+			    const struct dn_list *dn_list, 
+			    const char *attrs[], struct ldb_message ***res)
+{
+	int i;
+	unsigned int count = 0;
+
+	for (i=0;i<dn_list->count;i++) {
+		struct ldb_message msg;
+		int ret;
+		ret = ltdb_search_dn1(ldb, dn_list->dn[i], &msg);
+		if (ret == 0) {
+			/* the record has disappeared? yes, this can happen */
+			continue;
+		}
+
+		if (ret == -1) {
+			/* an internal error */
+			return -1;
+		}
+
+		if (ldb_message_match(ldb, &msg, tree, base, scope) == 1) {
+			ret = ltdb_add_attr_results(ldb, &msg, attrs, &count, res);
+		}
+		ltdb_search_dn1_free(ldb, &msg);
+		if (ret != 0) {
+			return -1;
+		}
+	}
+
+	return count;
+}
+
+/*
+  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_context *ldb, 
+			const char *base,
+			enum ldb_scope scope,
+			struct ldb_parse_tree *tree,
+			const char *attrs[], struct ldb_message ***res)
+{
+	struct ldb_message index_list;
+	struct dn_list dn_list;
+	int ret;
+
+	/* find the list of indexed fields */	
+	ret = ltdb_search_dn1(ldb, "@INDEXLIST", &index_list);
+	if (ret != 1) {
+		/* no index list? must do full search */
+		return -1;
+	}
+
+	ret = ltdb_index_dn(ldb, tree, &index_list, &dn_list);
+	ltdb_search_dn1_free(ldb, &index_list);
+
+	if (ret == 1) {
+		/* we've got a candidate list - now filter by the full tree
+		   and extract the needed attributes */
+		ret = ldb_index_filter(ldb, tree, base, scope, &dn_list, 
+				       attrs, res);
+		dn_list_free(&dn_list);
+	}
+
+	return ret;
+}
+
+/*
+  add an index entry for one message element
+*/
+static int ltdb_index_add1(struct ldb_context *ldb, const char *dn, 
+			   struct ldb_message_element *el)
+{
+	struct ldb_message msg;
+	char *dn_key;
+	int ret;
+	struct ldb_message_element *el2;
+
+	dn_key = ldb_dn_key(el->name, &el->value);
+	if (!dn_key) {
+		return -1;
+	}
+
+	ret = ltdb_search_dn1(ldb, dn_key, &msg);
+	if (ret == -1) {
+		free(dn_key);
+		return -1;
+	}
+
+	if (ret == 0) {
+		msg.dn = dn_key;
+		msg.num_elements = 0;
+		msg.elements = NULL;
+		msg.private = NULL;
+	}
+
+	/* add another entry */
+	el2 = realloc_p(msg.elements, struct ldb_message_element, msg.num_elements+1);
+	if (!el2) {
+		if (ret == 1) {
+			ltdb_search_dn1_free(ldb, &msg);
+		}
+		free(dn_key);
+		return -1;
+	}
+
+	msg.elements = el2;
+	msg.elements[msg.num_elements].name = "@IDX";
+	msg.elements[msg.num_elements].value.length = strlen(dn);
+	msg.elements[msg.num_elements].value.data = dn;
+	msg.num_elements++;
+
+	ret = ltdb_store(ldb, &msg, TDB_REPLACE);
+
+	if (msg.num_elements == 1) {
+		free(msg.elements);
+	} else {
+		ltdb_search_dn1_free(ldb, &msg);
+	}
+
+	return ret;
+}
+
+/*
+  add the index entries for a new record
+  return -1 on failure
+*/
+int ltdb_index_add(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	int ret, i;
+	struct ldb_message index_list;
+
+	/* find the list of indexed fields */	
+	ret = ltdb_search_dn1(ldb, "@INDEXLIST", &index_list);
+	if (ret != 1) {
+		/* no indexed fields or an error */
+		return ret;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		ret = ldb_msg_find_idx(&index_list, msg->elements[i].name);
+		if (ret == -1) {
+			continue;
+		}
+		ret = ltdb_index_add1(ldb, msg->dn, &msg->elements[i]);
+		if (ret == -1) {
+			ltdb_search_dn1_free(ldb, &index_list);
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+  delete an index entry for one message element
+*/
+static int ltdb_index_del1(struct ldb_context *ldb, const char *dn, 
+			   struct ldb_message_element *el)
+{
+	struct ldb_message msg;
+	char *dn_key;
+	int ret, i;
+
+	dn_key = ldb_dn_key(el->name, &el->value);
+	if (!dn_key) {
+		return -1;
+	}
+
+	ret = ltdb_search_dn1(ldb, dn_key, &msg);
+	if (ret == -1) {
+		free(dn_key);
+		return -1;
+	}
+
+	if (ret == 0) {
+		/* it wasn't indexed. Did we have an earlier error? If we did then
+		   its gone now */
+		ltdb_search_dn1_free(ldb, &msg);
+		return 0;
+	}
+
+	i = ldb_msg_find_idx(&msg, dn);
+	if (i == -1) {
+		/* it ain't there. hmmm */
+		ltdb_search_dn1_free(ldb, &msg);
+		return 0;
+	}
+
+	if (i != msg.num_elements - 1) {
+		memmove(&msg.elements[i], &msg.elements[i+1], sizeof(msg.elements[i]));
+	}
+	msg.num_elements--;
+
+	if (msg.num_elements == 0) {
+		ret = ltdb_delete_noindex(ldb, dn_key);
+	} else {
+		ret = ltdb_store(ldb, &msg, TDB_REPLACE);
+	}
+
+	ltdb_search_dn1_free(ldb, &msg);
+
+	return ret;
+}
+
+/*
+  delete the index entries for a record
+  return -1 on failure
+*/
+int ltdb_index_del(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	int ret, i;
+	struct ldb_message index_list;
+
+	/* find the list of indexed fields */	
+	ret = ltdb_search_dn1(ldb, "@INDEXLIST", &index_list);
+	if (ret != 1) {
+		/* no indexed fields or an error */
+		return ret;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		ret = ldb_msg_find_idx(&index_list, msg->elements[i].name);
+		if (ret == -1) {
+			continue;
+		}
+		ret = ltdb_index_del1(ldb, msg->dn, &msg->elements[i]);
+		if (ret == -1) {
+			ltdb_search_dn1_free(ldb, &index_list);
+			return -1;
+		}
+	}
+
+	return 0;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_ldif.c b/source4/lib/ldb/ldb_tdb/ldb_ldif.c
new file mode 100644
index 0000000000..170685cc03
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_ldif.c
@@ -0,0 +1,366 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   ldif utilities for ldb
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+
+
+/*
+  this base64 decoder was taken from jitterbug (written by tridge).
+  we might need to replace it with a new version
+*/
+static int base64_decode(char *s)
+{
+	const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+	int bit_offset, byte_offset, idx, i, n;
+	unsigned char *d = (unsigned char *)s;
+	char *p;
+
+	n=i=0;
+
+	while (*s && (p=strchr(b64,*s))) {
+		idx = (int)(p - b64);
+		byte_offset = (i*6)/8;
+		bit_offset = (i*6)%8;
+		d[byte_offset] &= ~((1<<(8-bit_offset))-1);
+		if (bit_offset < 3) {
+			d[byte_offset] |= (idx << (2-bit_offset));
+			n = byte_offset+1;
+		} else {
+			d[byte_offset] |= (idx >> (bit_offset-2));
+			d[byte_offset+1] = 0;
+			d[byte_offset+1] |= (idx << (8-(bit_offset-2))) & 0xFF;
+			n = byte_offset+2;
+		}
+		s++; i++;
+	}
+
+	if (*s && !p) {
+		/* the only termination allowed */
+		if (*s != '=') {
+			return -1;
+		}
+	}
+
+	/* null terminate */
+	d[n] = 0;
+	return n;
+}
+
+
+/*
+  encode as base64
+  caller frees
+*/
+char *ldb_base64_encode(const char *buf, int len)
+{
+	const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+	int bit_offset, byte_offset, idx, i;
+	unsigned char *d = (unsigned char *)buf;
+	int bytes = (len*8 + 5)/6;
+	char *out;
+
+	out = malloc(bytes+2);
+	if (!out) return NULL;
+
+	for (i=0;i<bytes;i++) {
+		byte_offset = (i*6)/8;
+		bit_offset = (i*6)%8;
+		if (bit_offset < 3) {
+			idx = (d[byte_offset] >> (2-bit_offset)) & 0x3F;
+		} else {
+			idx = (d[byte_offset] << (bit_offset-2)) & 0x3F;
+			if (byte_offset+1 < len) {
+				idx |= (d[byte_offset+1] >> (8-(bit_offset-2)));
+			}
+		}
+		out[i] = b64[idx];
+	}
+
+	out[i++] = '=';
+	out[i] = 0;
+
+	return out;
+}
+
+/*
+  see if a buffer should be base64 encoded
+*/
+int ldb_should_b64_encode(const struct ldb_val *val)
+{
+	int i;
+	unsigned char *p = val->data;
+
+	if (val->length == 0 || p[0] == ' ' || p[0] == ':') {
+		return 1;
+	}
+
+	for (i=0; i<val->length; i++) {
+		if (!isprint(p[i]) || p[i] == '\n') {
+			return 1;
+		}
+	}
+	return 0;
+}
+
+
+/*
+  encode as base64 to a file
+*/
+static int base64_encode_f(FILE *f, const char *buf, int len, int start_pos)
+{
+	int i;
+	char *b = ldb_base64_encode(buf, len);
+
+	if (!b) {
+		return -1;
+	}
+
+	for (i=0;b[i];i++) {
+		fputc(b[i], f);
+		if (b[i+1] && (i + start_pos) % 77 == 0) {
+			fputc('\n', f);
+			fputc(' ', f);
+		}
+	}
+	free(b);
+	return 0;
+}
+
+/*
+  write a line folded string onto a file
+*/
+static void fold_string(FILE *f, const char *buf, size_t length, int start_pos)
+{
+	int i;
+
+	for (i=0;i<length;i++) {
+		fputc(buf[i], f);
+		if (i != (length-1) && (i + start_pos) % 77 == 0) {
+			fputc('\n', f);
+			fputc(' ', f);
+		}
+	}
+}
+
+
+/*
+  pull a ldif chunk, which is defined as a piece of data ending in \n\n or EOF
+  this routine removes any RFC2849 continuations and comments
+
+  caller frees
+*/
+static char *next_chunk(FILE *f)
+{
+	size_t alloc_size=0, chunk_size = 0;
+	char *chunk = NULL;
+	int c;
+	int in_comment = 0;
+
+	while ((c = fgetc(f)) != EOF) {
+		if (chunk_size == alloc_size) {
+			char *c2;
+			alloc_size += 1024;
+			c2 = realloc_p(chunk, char, alloc_size);
+			if (!c2) {
+				free(chunk);
+				errno = ENOMEM;
+				return NULL;
+			}
+			chunk = c2;
+		}
+
+		if (in_comment) {
+			if (c == '\n') {
+				in_comment = 0;
+			}
+			continue;			
+		}
+		
+		/* handle continuation lines - see RFC2849 */
+		if (c == ' ' && chunk_size > 1 && chunk[chunk_size-1] == '\n') {
+			chunk_size--;
+			continue;
+		}
+		
+		/* chunks are terminated by a double line-feed */
+		if (c == '\n' && chunk_size > 0 && chunk[chunk_size-1] == '\n') {
+			chunk[chunk_size-1] = 0;
+			return chunk;
+		}
+
+		if (c == '#' && (chunk_size == 0 || chunk[chunk_size-1] == '\n')) {
+			in_comment = 1;
+			continue;
+		}
+
+		chunk[chunk_size++] = c;
+	}
+
+	return chunk;
+}
+
+
+/* simple ldif attribute parser */
+static int next_attr(char **s, char **attr, struct ldb_val *value)
+{
+	char *p;
+	int base64_encoded = 0;
+
+	p = strchr(*s, ':');
+	if (!p) {
+		return -1;
+	}
+
+	*p++ = 0;
+
+	if (*p == ':') {
+		base64_encoded = 1;
+		p++;
+	}
+
+	*attr = *s;
+
+	while (isspace(*p)) {
+		p++;
+	}
+
+	value->data = p;
+
+	p = strchr(p, '\n');
+
+	if (!p) {
+		value->length = strlen((char *)value->data);
+		*s = ((char *)value->data) + value->length;
+	} else {
+		value->length = p - (char *)value->data;
+		*s = p+1;
+		*p = 0;
+	}
+
+	if (base64_encoded) {
+		int len = base64_decode(value->data);
+		if (len == -1) {
+			/* it wasn't valid base64 data */
+			return -1;
+		}
+		value->length = len;
+	}
+
+	return 0;
+}
+
+
+/*
+  free a message from a ldif_read
+*/
+void ldif_read_free(struct ldb_message *msg)
+{
+	if (msg->elements) free(msg->elements);
+	if (msg->private) free(msg->private);
+	free(msg);
+}
+
+/*
+ read from a LDIF file, creating a ldb_message
+*/
+struct ldb_message *ldif_read(FILE *f)
+{
+	struct ldb_message *msg;
+	char *attr=NULL, *chunk=NULL, *s;
+	struct ldb_val value;
+
+	value.data = NULL;
+
+	msg = malloc_p(struct ldb_message);
+	if (!msg) return NULL;
+
+	msg->dn = NULL;
+	msg->elements = NULL;
+	msg->num_elements = 0;
+	msg->private = NULL;
+
+	chunk = next_chunk(f);
+	if (!chunk) {
+		goto failed;
+	}
+
+	msg->private = chunk;
+	s = chunk;
+
+	if (next_attr(&s, &attr, &value) != 0) {
+		goto failed;
+	}
+	
+	/* first line must be a dn */
+	if (strcmp(attr, "dn") != 0) {
+		fprintf(stderr, "First line must be a dn not '%s'\n", attr);
+		goto failed;
+	}
+
+	msg->dn = value.data;
+
+	while (next_attr(&s, &attr, &value) == 0) {
+		msg->elements = realloc_p(msg->elements, 
+					  struct ldb_message_element, 
+					  msg->num_elements+1);
+		if (!msg->elements) {
+			goto failed;
+		}
+		msg->elements[msg->num_elements].flags = 0;
+		msg->elements[msg->num_elements].name = attr;
+		msg->elements[msg->num_elements].value = value;
+		msg->num_elements++;
+	}
+
+	return msg;
+
+failed:
+	if (msg) ldif_read_free(msg);
+	return NULL;
+}
+
+
+/*
+  write to a ldif file 
+*/
+void ldif_write(FILE *f, const struct ldb_message *msg)
+{
+	int i;
+	fprintf(f, "dn: %s\n", msg->dn);
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_should_b64_encode(&msg->elements[i].value)) {
+			fprintf(f, "%s:: ", msg->elements[i].name);
+			base64_encode_f(f, 
+					msg->elements[i].value.data, 
+					msg->elements[i].value.length,
+					strlen(msg->elements[i].name)+3);
+			fprintf(f, "\n");
+		} else {
+			fprintf(f, "%s: ", msg->elements[i].name);
+			fold_string(f, msg->elements[i].value.data,				    
+				    msg->elements[i].value.length,
+				    strlen(msg->elements[i].name)+2);
+			fprintf(f, "\n");
+		}
+	}
+	fprintf(f,"\n");
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_match.c b/source4/lib/ldb/ldb_tdb/ldb_match.c
new file mode 100644
index 0000000000..89d204f56a
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_match.c
@@ -0,0 +1,176 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb expression matching
+ *
+ *  Description: ldb expression matching for tdb backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+
+/*
+  see if two ldb_val structures contain the same data
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal(struct ldb_val *v1, struct ldb_val *v2)
+{
+	if (v1->length != v2->length) return 0;
+
+	if (v1->length == 0) return 1;
+
+	if (memcmp(v1->data, v2->data, v1->length) == 0) {
+		return 1;
+	}
+
+	return 0;
+}
+
+/*
+  check if the scope matches in a search result
+*/
+static int scope_match(const char *dn, const char *base, enum ldb_scope scope)
+{
+	size_t dn_len, base_len;
+
+	if (base == NULL) {
+		return 1;
+	}
+
+	base_len = strlen(base);
+	dn_len = strlen(dn);
+
+	if (strcmp(dn, base) == 0) {
+		return 1;
+	}
+
+	if (base_len+1 >= dn_len) {
+		return 0;
+	}
+
+	switch (scope) {
+	case LDB_SCOPE_BASE:
+		break;
+
+	case LDB_SCOPE_ONELEVEL:
+		if (strcmp(dn + (dn_len - base_len), base) == 0 &&
+		    dn[dn_len - base_len - 1] == ',' &&
+		    strchr(dn, ',') == &dn[dn_len - base_len - 1]) {
+			return 1;
+		}
+		break;
+		
+	case LDB_SCOPE_SUBTREE:
+	default:
+		if (strcmp(dn + (dn_len - base_len), base) == 0 &&
+		    dn[dn_len - base_len - 1] == ',') {
+			return 1;
+		}
+		break;
+	}
+
+	return 0;
+}
+
+
+/*
+  match a leaf node
+*/
+static int match_leaf(struct ldb_context *ldb, 
+		      struct ldb_message *msg,
+		      struct ldb_parse_tree *tree,
+		      const char *base,
+		      enum ldb_scope scope)
+{
+	int i;
+
+	if (!scope_match(msg->dn, base, scope)) {
+		return 0;
+	}
+
+	if (strcmp(tree->u.simple.attr, "dn") == 0) {
+		if (strcmp(tree->u.simple.value.data, "*") == 0) {
+			return 1;
+		}
+		return strcmp(msg->dn, tree->u.simple.value.data) == 0;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		if (strcmp(msg->elements[i].name, tree->u.simple.attr) == 0 &&
+		    (strcmp(tree->u.simple.value.data, "*") == 0 ||
+		     ldb_val_equal(&msg->elements[i].value, &tree->u.simple.value))) {
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+/*
+  return 0 if the given parse tree matches the given message. Assumes
+  the message is in sorted order
+
+  return 1 if it matches, and 0 if it doesn't match
+
+  this is a recursive function, and does short-circuit evaluation
+ */
+int ldb_message_match(struct ldb_context *ldb, 
+		      struct ldb_message *msg,
+		      struct ldb_parse_tree *tree,
+		      const char *base,
+		      enum ldb_scope scope)
+{
+	int v, i;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		break;
+
+	case LDB_OP_NOT:
+		return ! ldb_message_match(ldb, msg, tree->u.not.child, base, scope);
+
+	case LDB_OP_AND:
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			v = ldb_message_match(ldb, msg, tree->u.list.elements[i],
+					      base, scope);
+			if (!v) return 0;
+		}
+		return 1;
+
+	case LDB_OP_OR:
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			v = ldb_message_match(ldb, msg, tree->u.list.elements[i],
+					      base, scope);
+			if (v) return 1;
+		}
+		return 0;
+	}
+
+	return match_leaf(ldb, msg, tree, base, scope);
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_pack.c b/source4/lib/ldb/ldb_tdb/ldb_pack.c
new file mode 100644
index 0000000000..b0c825e8e2
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_pack.c
@@ -0,0 +1,174 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb pack/unpack
+ *
+ *  Description: pack/unpack routines for ldb messages as key/value blobs
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include "ldb_tdb/ldb_tdb.h"
+
+/* change this if the data format ever changes */
+#define LTDB_PACKING_FORMAT 0x26011966
+
+/*
+  pack a ldb message into a linear buffer in a TDB_DATA
+
+  caller frees the data buffer after use
+*/
+int ltdb_pack_data(struct ldb_context *ctx,
+		   const struct ldb_message *message,
+		   struct TDB_DATA *data)
+{
+	int i;
+	size_t size;
+	char *p;
+
+	/* work out how big it needs to be */
+	size = 8;
+
+	for (i=0;i<message->num_elements;i++) {
+		size += 1 + strlen(message->elements[i].name);
+		size += 4 + message->elements[i].value.length + 1;
+	}
+
+	/* allocate it */
+	data->dptr = malloc(size);
+	if (!data->dptr) {
+		errno = ENOMEM;
+		return -1;
+	}
+	data->dsize = size;
+
+	p = data->dptr;
+	SIVAL(p, 0, LTDB_PACKING_FORMAT); 
+	SIVAL(p, 4, message->num_elements); 
+	p += 8;
+	
+	for (i=0;i<message->num_elements;i++) {
+		size_t len = strlen(message->elements[i].name);
+		memcpy(p, message->elements[i].name, len+1);
+		p += len + 1;
+		SIVAL(p, 0, message->elements[i].value.length);
+		memcpy(p+4, message->elements[i].value.data, 
+		       message->elements[i].value.length);
+		p[4+message->elements[i].value.length] = 0;
+		p += 4 + message->elements[i].value.length + 1;
+	}
+
+	return 0;
+}
+
+
+/*
+  unpack a ldb message from a linear buffer in TDB_DATA
+
+  note that this does not fill in the class and key elements
+
+  caller frees. Memory for the elements[] array is malloced, 
+  but the memory for the elements is re-used from the TDB_DATA
+  data. This means the caller only has to free the elements array
+*/
+int ltdb_unpack_data(struct ldb_context *ctx,
+		     const struct TDB_DATA *data,
+		     struct ldb_message *message)
+{
+	char *p;
+	unsigned int remaining;
+	int i;
+
+	message->elements = NULL;
+
+	p = data->dptr;
+	if (data->dsize < 4) {
+		errno = EIO;
+		goto failed;
+	}
+
+	if (IVAL(p, 0) != LTDB_PACKING_FORMAT) {
+		/* this is where we will cope with upgrading the
+		   format if/when the format is ever changed */
+		errno = EIO;
+		goto failed;
+	}
+
+	message->num_elements = IVAL(p, 4);
+	p += 8;
+
+	if (message->num_elements == 0) {
+		message->elements = NULL;
+		return 0;
+	}
+	
+	/* basic sanity check */
+	remaining = data->dsize - 8;
+
+	if (message->num_elements > remaining / 6) {
+		errno = EIO;
+		goto failed;
+	}
+
+	message->elements = malloc_array_p(struct ldb_message_element,
+					   message->num_elements);
+				     
+	if (!message->elements) {
+		errno = ENOMEM;
+		goto failed;
+	}
+
+	for (i=0;i<message->num_elements;i++) {
+		size_t len;
+		if (remaining < 6) {
+			errno = EIO;
+			goto failed;
+		}
+		len = strnlen(p, remaining-6);
+		message->elements[i].name = p;
+		remaining -= len + 1;
+		p += len + 1;
+		len = IVAL(p, 0);
+		if (len > remaining-5) {
+			errno = EIO;
+			goto failed;
+		}
+		message->elements[i].value.length = len;
+		message->elements[i].value.data = p+4;
+		remaining -= len+4+1;
+		p += len+4+1;
+	}
+
+	return 0;
+
+failed:
+	if (message->elements) {
+		free(message->elements);
+	}
+	return -1;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_parse.c b/source4/lib/ldb/ldb_tdb/ldb_parse.c
new file mode 100644
index 0000000000..44cfc5b4ff
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_parse.c
@@ -0,0 +1,448 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   parse a LDAP-like expression
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+/*
+  TODO:
+      - add RFC2254 binary string handling
+      - possibly add ~=, <= and >= handling
+      - expand the test suite
+      - add better parse error handling
+
+*/
+
+#include "includes.h"
+
+
+/*
+a filter is defined by:
+               <filter> ::= '(' <filtercomp> ')'
+               <filtercomp> ::= <and> | <or> | <not> | <simple>
+               <and> ::= '&' <filterlist>
+               <or> ::= '|' <filterlist>
+               <not> ::= '!' <filter>
+               <filterlist> ::= <filter> | <filter> <filterlist>
+               <simple> ::= <attributetype> <filtertype> <attributevalue>
+               <filtertype> ::= '=' | '~=' | '<=' | '>='
+*/
+
+/*
+  return next token element. Caller frees
+*/
+static char *ldb_parse_lex(const char **s)
+{
+	const char *p = *s;
+	char *ret;
+
+	while (isspace(*p)) {
+		p++;
+	}
+	*s = p;
+
+	if (*p == 0) {
+		return NULL;
+	}
+
+	if (strchr("()&|=!", *p)) {
+		(*s) = p+1;
+		ret = strndup(p, 1);
+		if (!ret) {
+			errno = ENOMEM;
+		}
+		return ret;
+	}
+
+	while (*p && (isalnum(*p) || !strchr("()&|=!", *p))) {
+		p++;
+	}
+
+	if (p == *s) {
+		return NULL;
+	}
+
+	ret = strndup(*s, p - *s);
+	if (!ret) {
+		errno = ENOMEM;
+	}
+
+	*s = p;
+
+	return ret;
+}
+
+/*
+  find a matching close brace in a string
+*/
+static const char *match_brace(const char *s)
+{
+	unsigned int count = 0;
+	while (*s && (count != 0 || *s != ')')) {
+		if (*s == '(') {
+			count++;
+		}
+		if (*s == ')') {
+			count--;
+		}
+		s++;
+	}
+	if (! *s) {
+		return NULL;
+	}
+	return s;
+}
+
+
+static struct ldb_parse_tree *ldb_parse_filter(const char **s);
+
+/*
+  <simple> ::= <attributetype> <filtertype> <attributevalue>
+*/
+static struct ldb_parse_tree *ldb_parse_simple(const char *s)
+{
+	char *eq, *val, *l;
+	struct ldb_parse_tree *ret;
+
+	l = ldb_parse_lex(&s);
+	if (!l) {
+		fprintf(stderr, "Unexpected end of expression\n");
+		return NULL;
+	}
+
+	if (strchr("()&|=", *l)) {
+		fprintf(stderr, "Unexpected token '%s'\n", l);
+		free(l);
+		return NULL;
+	}
+
+	eq = ldb_parse_lex(&s);
+	if (!eq || strcmp(eq, "=") != 0) {
+		fprintf(stderr, "Expected '='\n");
+		free(l);
+		if (eq) free(eq);
+		return NULL;
+	}
+	free(eq);
+
+	val = ldb_parse_lex(&s);
+	if (val && strchr("()&|=", *val)) {
+		fprintf(stderr, "Unexpected token '%s'\n", val);
+		free(l);
+		if (val) free(val);
+		return NULL;
+	}
+	
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = LDB_OP_SIMPLE;
+	ret->u.simple.attr = l;
+	ret->u.simple.value.data = val;
+	ret->u.simple.value.length = val?strlen(val):0;
+
+	return ret;
+}
+
+
+/*
+  parse a filterlist
+  <and> ::= '&' <filterlist>
+  <or> ::= '|' <filterlist>
+  <filterlist> ::= <filter> | <filter> <filterlist>
+*/
+static struct ldb_parse_tree *ldb_parse_filterlist(enum ldb_parse_op op, const char *s)
+{
+	struct ldb_parse_tree *ret, *next;
+
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = op;
+	ret->u.list.num_elements = 1;
+	ret->u.list.elements = malloc_p(struct ldb_parse_tree *);
+	if (!ret->u.list.elements) {
+		errno = ENOMEM;
+		free(ret);
+		return NULL;
+	}
+
+	ret->u.list.elements[0] = ldb_parse_filter(&s);
+	if (!ret->u.list.elements[0]) {
+		free(ret->u.list.elements);
+		free(ret);
+		return NULL;
+	}
+
+	while (isspace(*s)) s++;
+
+	while (*s && (next = ldb_parse_filter(&s))) {
+		struct ldb_parse_tree **e;
+		e = realloc_p(ret->u.list.elements, 
+			      struct ldb_parse_tree *, 
+			      ret->u.list.num_elements+1);
+		if (!e) {
+			errno = ENOMEM;
+			ldb_parse_tree_free(next);
+			ldb_parse_tree_free(ret);
+			return NULL;
+		}
+		ret->u.list.elements = e;
+		ret->u.list.elements[ret->u.list.num_elements] = next;
+		ret->u.list.num_elements++;
+		while (isspace(*s)) s++;
+	}
+
+	return ret;
+}
+
+
+/*
+  <not> ::= '!' <filter>
+*/
+static struct ldb_parse_tree *ldb_parse_not(const char *s)
+{
+	struct ldb_parse_tree *ret;
+
+	ret = malloc_p(struct ldb_parse_tree);
+	if (!ret) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret->operation = LDB_OP_NOT;
+	ret->u.not.child = ldb_parse_filter(&s);
+	if (!ret->u.not.child) {
+		free(ret);
+		return NULL;
+	}
+
+	return ret;
+}
+
+/*
+  parse a filtercomp
+  <filtercomp> ::= <and> | <or> | <not> | <simple>
+*/
+static struct ldb_parse_tree *ldb_parse_filtercomp(const char *s)
+{
+	while (isspace(*s)) s++;
+
+	switch (*s) {
+	case '&':
+		return ldb_parse_filterlist(LDB_OP_AND, s+1);
+
+	case '|':
+		return ldb_parse_filterlist(LDB_OP_OR, s+1);
+
+	case '!':
+		return ldb_parse_not(s+1);
+
+	case '(':
+	case ')':
+		fprintf(stderr, "Unexpected token '%c'\n", *s);
+		return NULL;
+	}
+
+	return ldb_parse_simple(s);
+}
+
+
+/*
+  <filter> ::= '(' <filtercomp> ')'
+*/
+static struct ldb_parse_tree *ldb_parse_filter(const char **s)
+{
+	char *l, *s2;
+	const char *p, *p2;
+	struct ldb_parse_tree *ret;
+
+	l = ldb_parse_lex(s);
+	if (!l) {
+		fprintf(stderr, "Unexpected end of expression\n");
+		return NULL;
+	}
+
+	if (strcmp(l, "(") != 0) {
+		free(l);
+		fprintf(stderr, "Expected '('\n");
+		return NULL;
+	}
+	free(l);
+
+	p = match_brace(*s);
+	if (!p) {
+		fprintf(stderr, "Parse error - mismatched braces\n");
+		return NULL;
+	}
+	p2 = p + 1;
+
+	s2 = strndup(*s, p - *s);
+	if (!s2) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ret = ldb_parse_filtercomp(s2);
+	free(s2);
+
+	*s = p2;
+
+	return ret;
+}
+
+
+/*
+  main parser entry point. Takes a search string and returns a parse tree
+
+  expression ::= <simple> | <filter>
+*/
+struct ldb_parse_tree *ldb_parse_tree(const char *s)
+{
+	while (isspace(*s)) s++;
+
+	if (*s == '(') {
+		return ldb_parse_filter(&s);
+	}
+
+	return ldb_parse_simple(s);
+}
+
+/*
+  free a parse tree returned from ldb_parse_tree()
+*/
+void ldb_parse_tree_free(struct ldb_parse_tree *tree)
+{
+	int i;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		free(tree->u.simple.attr);
+		if (tree->u.simple.value.data) free(tree->u.simple.value.data);
+		break;
+
+	case LDB_OP_AND:
+	case LDB_OP_OR:
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			ldb_parse_tree_free(tree->u.list.elements[i]);
+		}
+		if (tree->u.list.elements) free(tree->u.list.elements);
+		break;
+
+	case LDB_OP_NOT:
+		ldb_parse_tree_free(tree->u.not.child);
+		break;
+	}
+
+	free(tree);
+}
+
+#if TEST_PROGRAM
+/*
+  return a string representation of a parse tree
+  used for debugging
+*/
+static char *tree_string(struct ldb_parse_tree *tree)
+{
+	char *s = NULL;
+	char *s1, *s2;
+	int i;
+
+	switch (tree->operation) {
+	case LDB_OP_SIMPLE:
+		asprintf(&s, "( %s = \"%s\" )", tree->u.simple.attr, 
+			 (char *)tree->u.simple.value.data);
+		break;
+
+	case LDB_OP_AND:
+	case LDB_OP_OR:
+		asprintf(&s, "( %c", tree->operation==LDB_OP_AND?'&':'|');
+		if (!s) return NULL;
+
+		for (i=0;i<tree->u.list.num_elements;i++) {
+			s1 = tree_string(tree->u.list.elements[i]);
+			if (!s1) {
+				free(s);
+				return NULL;
+			}
+			asprintf(&s2, "%s %s", s, s1);
+			free(s);
+			free(s1);
+			s = s2;
+		}
+		if (!s) {
+			return NULL;
+		}
+		asprintf(&s2, "%s )", s);
+		free(s);
+		s = s2;
+		break;
+
+	case LDB_OP_NOT:
+		s1 = tree_string(tree->u.not.child);
+		asprintf(&s, "( ! %s )", s1);
+		free(s1);
+		break;
+	}
+	return s;
+}
+
+
+/*
+  print a tree
+ */
+static void print_tree(struct ldb_parse_tree *tree)
+{
+	char *s = tree_string(tree);
+	printf("%s\n", s);
+	free(s);
+}
+
+
+ int main(void)
+{
+	char line[1000];
+	int ret = 0;
+
+	while (fgets(line, sizeof(line)-1, stdin)) {
+		struct ldb_parse_tree *tree;
+
+		if (line[strlen(line)-1] == '\n') {
+			line[strlen(line)-1] = 0;
+		}
+		tree = ldb_parse_tree(line);
+		if (!tree) {
+			fprintf(stderr, "Failed to parse\n");
+			ret = 1;
+			continue;
+		}
+		print_tree(tree);
+		ldb_parse_tree_free(tree);
+	}
+	
+	return ret;
+}
+#endif /* TEST_PROGRAM */
+
diff --git a/source4/lib/ldb/ldb_tdb/ldb_parse.h b/source4/lib/ldb/ldb_tdb/ldb_parse.h
new file mode 100644
index 0000000000..995e0e04ff
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_parse.h
@@ -0,0 +1,40 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   parse a LDAP-like expression - header
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+enum ldb_parse_op {LDB_OP_SIMPLE, LDB_OP_AND, LDB_OP_OR, LDB_OP_NOT};
+
+struct ldb_parse_tree {
+	enum ldb_parse_op operation;
+	union {
+		struct {
+			char *attr;
+			struct ldb_val value;
+		} simple;
+		struct {
+			unsigned int num_elements;
+			struct ldb_parse_tree **elements;
+		} list;
+		struct {
+			struct ldb_parse_tree *child;
+		} not;
+	} u;
+};
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
new file mode 100644
index 0000000000..952053c920
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -0,0 +1,482 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb search functions
+ *
+ *  Description: functions to search ldb+tdb databases
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include "ldb_tdb/ldb_tdb.h"
+
+/*
+  free a message that has all parts separately allocated
+*/
+static void msg_free_all_parts(struct ldb_message *msg)
+{
+	int i;
+	if (msg->dn) free(msg->dn);
+	for (i=0;i<msg->num_elements;i++) {
+		if (msg->elements[i].name) free(msg->elements[i].name);
+		if (msg->elements[i].value.data) free(msg->elements[i].value.data);
+	}
+	free(msg->elements);
+	free(msg);
+}
+
+
+/*
+  TODO: this should take advantage of the sorted nature of the message
+  return index of the attribute, or -1 if not found
+*/
+int ldb_msg_find_attr(const struct ldb_message *msg, const char *attr)
+{
+	int i;
+	for (i=0;i<msg->num_elements;i++) {
+		if (strcmp(msg->elements[i].name, attr) == 0) {
+			return i;
+		}
+	}
+	return -1;
+}
+
+/*
+  duplicate a ldb_val structure
+*/
+static struct ldb_val ldb_val_dup(const struct ldb_val *v)
+{
+	struct ldb_val v2;
+	v2.length = v->length;
+	if (v->length == 0) {
+		v2.data = NULL;
+		return v2;
+	}
+
+	/* the +1 is to cope with buggy C library routines like strndup
+	   that look one byte beyond */
+	v2.data = malloc(v->length+1);
+	if (!v2.data) {
+		v2.length = 0;
+		return v2;
+	}
+
+	memcpy(v2.data, v->data, v->length);
+	((char *)v2.data)[v->length] = 0;
+	return v2;
+}
+
+
+
+/*
+  add one element to a message
+*/
+static int msg_add_element(struct ldb_message *ret, const struct ldb_message_element *el)
+{
+	struct ldb_message_element *e2;
+
+	e2 = realloc_p(ret->elements, struct ldb_message_element, ret->num_elements+1);
+	if (!e2) {
+		return -1;
+	}
+	ret->elements = e2;
+	
+	e2[ret->num_elements].name = strdup(el->name);
+	if (!e2[ret->num_elements].name) {
+		return -1;
+	}
+	e2[ret->num_elements].value = ldb_val_dup(&el->value);
+	if (e2[ret->num_elements].value.length != el->value.length) {
+		return -1;
+	}
+
+	ret->num_elements++;
+
+	return 0;
+}
+
+/*
+  add all elements from one message into another
+ */
+static int msg_add_all_elements(struct ldb_message *ret,
+				const struct ldb_message *msg)
+{
+	int i;
+	for (i=0;i<msg->num_elements;i++) {
+		if (msg_add_element(ret, &msg->elements[i]) != 0) {
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+  pull the specified list of attributes from a message
+ */
+static struct ldb_message *ltdb_pull_attrs(struct ldb_context *ldb, 
+					   const struct ldb_message *msg, 
+					   const char **attrs)
+{
+	struct ldb_message *ret;
+	int i;
+
+	ret = malloc_p(struct ldb_message);
+	if (!ret) {
+		return NULL;
+	}
+
+	ret->dn = strdup(msg->dn);
+	if (!ret->dn) {
+		free(ret);
+		return NULL;
+	}
+
+	ret->num_elements = 0;
+	ret->elements = NULL;
+	ret->private = NULL;
+
+	if (!attrs) {
+		if (msg_add_all_elements(ret, msg) != 0) {
+			msg_free_all_parts(ret);
+			return NULL;
+		}
+		return ret;
+	}
+
+	for (i=0;attrs[i];i++) {
+		int j;
+
+		if (strcmp(attrs[i], "*") == 0) {
+			if (msg_add_all_elements(ret, msg) != 0) {
+				msg_free_all_parts(ret);
+				return NULL;
+			}
+			continue;
+		}
+		j = ldb_msg_find_attr(msg, attrs[i]);
+		if (j == -1) {
+			continue;
+		}
+		do {
+			if (msg_add_element(ret, &msg->elements[j]) != 0) {
+				msg_free_all_parts(ret);
+				return NULL;				
+			}
+		} while (++j < msg->num_elements && 
+			 strcmp(attrs[i], msg->elements[j].name) == 0);
+	}
+
+	return ret;
+}
+
+
+
+/*
+  see if a ldb_val is a wildcard
+*/
+int ltdb_has_wildcard(const struct ldb_val *val)
+{
+	if (val->length == 1 && ((char *)val->data)[0] == '*') {
+		return 1;
+	}
+	return 0;
+}
+
+
+/*
+  free the results of a ltdb_search_dn1 search
+*/
+void ltdb_search_dn1_free(struct ldb_context *ldb, struct ldb_message *msg)
+{
+	free(msg->dn);
+	free(msg->private);
+	if (msg->elements) free(msg->elements);
+}
+
+
+/*
+  search the database for a single simple dn, returning all attributes
+  in a single message
+
+  return 1 on success, 0 on record-not-found and -1 on error
+*/
+int ltdb_search_dn1(struct ldb_context *ldb, const char *dn, struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	int ret;
+	TDB_DATA tdb_key, tdb_data;
+
+	/* form the key */
+	tdb_key = ltdb_key(dn);
+	if (!tdb_key.dptr) {
+		return -1;
+	}
+
+	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
+	free(tdb_key.dptr);
+	if (!tdb_data.dptr) {
+		return 0;
+	}
+
+	msg->dn = strdup(dn);
+	if (!msg->dn) {
+		free(tdb_data.dptr);
+		return -1;
+	}
+	msg->private = tdb_data.dptr;
+	msg->num_elements = 0;
+	msg->elements = NULL;
+
+	ret = ltdb_unpack_data(ldb, &tdb_data, msg);
+	if (ret == -1) {
+		free(tdb_data.dptr);
+		return -1;		
+	}
+
+	return 1;
+}
+
+
+/*
+  search the database for a single simple dn
+*/
+int ltdb_search_dn(struct ldb_context *ldb, char *dn,
+		   const char *attrs[], struct ldb_message ***res)
+{
+	int ret;
+	struct ldb_message msg, *msg2;
+
+	ret = ltdb_search_dn1(ldb, dn, &msg);
+	if (ret != 1) {
+		return ret;
+	}
+
+	msg2 = ltdb_pull_attrs(ldb, &msg, attrs);
+
+	ltdb_search_dn1_free(ldb, &msg);
+
+	if (!msg2) {
+		return -1;		
+	}
+
+	*res = malloc_array_p(struct ldb_message *, 2);
+	if (! *res) {
+		msg_free_all_parts(msg2);
+		return -1;		
+	}
+
+	(*res)[0] = msg2;
+	(*res)[1] = NULL;
+
+	return 1;
+}
+
+
+/*
+  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_context *ldb, struct ldb_message *msg,
+			  const char *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(ldb, msg, attrs);
+	if (!msg2) {
+		return -1;
+	}
+
+	/* add to the results list */
+	res2 = realloc_p(*res, struct ldb_message *, (*count)+2);
+	if (!res2) {
+		msg_free_all_parts(msg2);
+		return -1;
+	}
+
+	(*res) = res2;
+
+	(*res)[*count] = msg2;
+	(*res)[(*count)+1] = NULL;
+	(*count)++;
+
+	return 0;
+}
+
+
+/*
+  internal search state during a full db search
+*/
+struct ltdb_search_info {
+	struct ldb_context *ldb;
+	struct ldb_parse_tree *tree;
+	const char *base;
+	enum ldb_scope scope;
+	const char **attrs;
+	struct ldb_message **msgs;
+	int failures;
+	int count;
+};
+
+
+/*
+  search function for a non-indexed search
+ */
+static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ltdb_search_info *sinfo = state;
+	struct ldb_message msg;
+	int ret;
+
+	if (key.dsize < 4 || 
+	    strncmp(key.dptr, "DN=", 3) != 0) {
+		return 0;
+	}
+
+	msg.dn = key.dptr + 3;
+
+	/* unpack the record */
+	ret = ltdb_unpack_data(sinfo->ldb, &data, &msg);
+	if (ret == -1) {
+		sinfo->failures++;
+		return 0;
+	}
+
+	/* see if it matches the given expression */
+	if (!ldb_message_match(sinfo->ldb, &msg, sinfo->tree, 
+			       sinfo->base, sinfo->scope)) {
+		if (msg.elements) free(msg.elements);
+		return 0;
+	}
+
+	ret = ltdb_add_attr_results(sinfo->ldb, &msg, sinfo->attrs, &sinfo->count, &sinfo->msgs);
+
+	if (ret == -1) {
+		sinfo->failures++;
+	}
+
+	if (msg.elements) free(msg.elements);
+
+	return ret;
+}
+
+
+/*
+  free a set of search results
+*/
+int ltdb_search_free(struct ldb_context *ldb, struct ldb_message **msgs)
+{
+	int i;
+
+	if (!msgs) return 0;
+
+	for (i=0;msgs[i];i++) {
+		msg_free_all_parts(msgs[i]);
+	}
+
+	free(msgs);
+
+	return 0;
+}
+
+/*
+  search the database with a LDAP-like expression.
+  this is the "full search" non-indexed varient
+*/
+static int ltdb_search_full(struct ldb_context *ldb, 
+			    const char *base,
+			    enum ldb_scope scope,
+			    struct ldb_parse_tree *tree,
+			    const char *attrs[], struct ldb_message ***res)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	int ret;
+	struct ltdb_search_info sinfo;
+
+	sinfo.tree = tree;
+	sinfo.ldb = ldb;
+	sinfo.scope = scope;
+	sinfo.base = base;
+	sinfo.attrs = attrs;
+	sinfo.msgs = NULL;
+	sinfo.count = 0;
+	sinfo.failures = 0;
+
+	ret = tdb_traverse(ltdb->tdb, search_func, &sinfo);
+
+	if (ret == -1) {
+		ltdb_search_free(ldb, sinfo.msgs);
+		return -1;
+	}
+
+	*res = sinfo.msgs;
+	return sinfo.count;
+}
+
+
+/*
+  search the database with a LDAP-like expression.
+  choses a search method
+*/
+int ltdb_search(struct ldb_context *ldb, const char *base,
+		enum ldb_scope scope, const char *expression,
+		const char *attrs[], struct ldb_message ***res)
+{
+	struct ldb_parse_tree *tree;
+	int ret;
+
+	*res = NULL;
+
+	/* form a parse tree for the expression */
+	tree = ldb_parse_tree(expression);
+	if (!tree) {
+		return -1;
+	}
+
+	if (tree->operation == LDB_OP_SIMPLE && 
+	    strcmp(tree->u.simple.attr, "dn") == 0 &&
+	    !ltdb_has_wildcard(&tree->u.simple.value)) {
+		/* yay! its a nice simple one */
+		ret = ltdb_search_dn(ldb, tree->u.simple.value.data, attrs, res);
+	} else {
+		ret = ltdb_search_indexed(ldb, base, scope, tree, attrs, res);
+		if (ret == -1) {
+			ret = ltdb_search_full(ldb, base, scope, tree, attrs, res);
+		}
+	}
+
+	ldb_parse_tree_free(tree);
+
+	return ret;
+}
+
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
new file mode 100644
index 0000000000..17931352f7
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -0,0 +1,303 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb backend
+ *
+ *  Description: core functions for tdb backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include "ldb_tdb/ldb_tdb.h"
+
+/*
+  form a TDB_DATA for a record key
+  caller frees
+*/
+struct TDB_DATA ltdb_key(const char *dn)
+{
+	TDB_DATA key;
+	char *key_str = NULL;
+
+	asprintf(&key_str, "DN=%s", dn);
+	if (!key_str) {
+		errno = ENOMEM;
+		key.dptr = NULL;
+		key.dsize = 0;
+		return key;
+	}
+
+	key.dptr = key_str;
+	key.dsize = strlen(key_str)+1;
+
+	return key;
+}
+
+
+/*
+  store a record into the db
+*/
+int ltdb_store(struct ldb_context *ldb, const struct ldb_message *msg, int flgs)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	TDB_DATA tdb_key, tdb_data;
+	int ret;
+
+	tdb_key = ltdb_key(msg->dn);
+	if (!tdb_key.dptr) {
+		return -1;
+	}
+
+	ret = ltdb_pack_data(ldb, msg, &tdb_data);
+	if (ret == -1) {
+		free(tdb_key.dptr);
+		return -1;
+	}
+
+	ret = tdb_store(ltdb->tdb, tdb_key, tdb_data, flgs);
+	if (ret == -1) {
+		goto done;
+	}
+	
+	ret = ltdb_index_add(ldb, msg);
+	if (ret == -1) {
+		tdb_delete(ltdb->tdb, tdb_key);
+	}
+
+done:
+	free(tdb_key.dptr);
+	free(tdb_data.dptr);
+
+	return ret;
+}
+
+
+/*
+  add a record to the database
+*/
+static int ltdb_add(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	return ltdb_store(ldb, msg, TDB_INSERT);
+}
+
+
+/*
+  delete a record from the database, not updating indexes (used for deleting
+  index records)
+*/
+int ltdb_delete_noindex(struct ldb_context *ldb, const char *dn)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	TDB_DATA tdb_key;
+	int ret;
+
+	tdb_key = ltdb_key(dn);
+	if (!tdb_key.dptr) {
+		return -1;
+	}
+
+	ret = tdb_delete(ltdb->tdb, tdb_key);
+	free(tdb_key.dptr);
+
+	return ret;
+}
+
+/*
+  delete a record from the database
+*/
+static int ltdb_delete(struct ldb_context *ldb, const char *dn)
+{
+	int ret;
+	struct ldb_message msg;
+
+	/* in case any attribute of the message was indexed, we need
+	   to fetch the old record */
+	ret = ltdb_search_dn1(ldb, dn, &msg);
+	if (ret != 1) {
+		/* not finding the old record is an error */
+		return -1;
+	}
+
+	ret = ltdb_delete_noindex(ldb, dn);
+	if (ret == -1) {
+		ltdb_search_dn1_free(ldb, &msg);
+		return -1;
+	}
+
+	/* remove any indexed attributes */
+	ret = ltdb_index_del(ldb, &msg);
+
+	ltdb_search_dn1_free(ldb, &msg);
+
+	return ret;
+}
+
+
+/*
+  modify a record
+*/
+static int ltdb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	TDB_DATA tdb_key, tdb_data;
+	struct ldb_message msg2;
+	int ret;
+
+	tdb_key = ltdb_key(msg->dn);
+	if (!tdb_key.dptr) {
+		return -1;
+	}
+
+	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
+	if (!tdb_data.dptr) {
+		free(tdb_key.dptr);
+		return -1;
+	}
+
+	ret = ltdb_unpack_data(ldb, &tdb_data, &msg2);
+	if (ret == -1) {
+		free(tdb_key.dptr);
+		free(tdb_data.dptr);
+		return -1;
+	}
+
+#if 0
+	for (i=0;i<msg->num_elements;i++) {
+		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
+		case LDB_FLAG_MOD_ADD:
+			ret = find_element(&msg2, msg->elements[i].name);
+			if (ret != -1) {
+				errno = EEXIST;
+				goto failed;
+			}
+			
+		}
+	}
+
+failed:
+#endif
+
+	free(tdb_key.dptr);
+	free(tdb_data.dptr);
+	if (msg2.elements) free(msg2.elements);
+	
+	return -1;
+}
+
+/*
+  close database
+*/
+static int ltdb_close(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	int ret;
+	ret = tdb_close(ltdb->tdb);
+	free(ltdb);
+	free(ldb);
+	return ret;
+}
+		      
+
+/*
+  return extended error information
+*/
+static const char *ltdb_errstring(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private;
+	return tdb_errorstr(ltdb->tdb);
+}
+
+
+static const struct ldb_backend_ops ltdb_ops = {
+	ltdb_close, 
+	ltdb_search,
+	ltdb_search_free,
+	ltdb_add,
+	ltdb_modify,
+	ltdb_delete,
+	ltdb_errstring
+};
+
+
+/*
+  connect to the database
+*/
+struct ldb_context *ltdb_connect(const char *url, 
+				 unsigned int flags, 
+				 const char *options[])
+{
+	const char *path;
+	int tdb_flags, open_flags;
+	struct ltdb_private *ltdb;
+	TDB_CONTEXT *tdb;
+	struct ldb_context *ldb;
+
+	/* parse the url */
+	if (strncmp(url, "tdb://", 6) != 0) {
+		errno = EINVAL;
+		return NULL;
+	}
+
+	path = url+6;
+
+	tdb_flags = TDB_DEFAULT;
+
+	if (flags & LDB_FLG_RDONLY) {
+		open_flags = O_RDONLY;
+	} else {
+		open_flags = O_CREAT | O_RDWR;
+	}
+
+	tdb = tdb_open(path, 0, tdb_flags, open_flags, 0666);
+	if (!tdb) {
+		return NULL;
+	}
+
+	ltdb = malloc_p(struct ltdb_private);
+	if (!ltdb) {
+		tdb_close(tdb);
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ltdb->tdb = tdb;
+	
+
+	ldb = malloc_p(struct ldb_context);
+	if (!ldb) {
+		tdb_close(tdb);
+		free(ltdb);
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	ldb->private = ltdb;
+	ldb->ops = &ltdb_ops;
+
+	return ldb;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.h b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
new file mode 100644
index 0000000000..edf525f895
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -0,0 +1,11 @@
+/* this private structure is used by the ltdb backend in the
+   ldb_context */
+struct ltdb_private {
+	TDB_CONTEXT *tdb;
+	unsigned int connect_flags;
+};
+
+
+#define IVAL(p, ofs) (((unsigned *)((char *)(p) + (ofs)))[0])
+#define SIVAL(p, ofs, v) do { IVAL(p, ofs) = (v); } while (0)
+
diff --git a/source4/lib/ldb/ldb_tdb/ldbadd.c b/source4/lib/ldb/ldb_tdb/ldbadd.c
new file mode 100644
index 0000000000..3959a17525
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldbadd.c
@@ -0,0 +1,55 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   a utility to add elements to a ldb
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+
+ int main(void)
+{
+	static struct ldb_context *ldb;
+	struct ldb_message *msg;
+	int ret;
+	int count=0, failures=0;
+
+	ldb = ltdb_connect("tdb://test.ldb", 0, NULL);
+
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	while ((msg = ldif_read(stdin))) {
+		ret = ldb->ops->add(ldb, msg);
+		if (ret != 0) {
+			fprintf(stderr, "Failed to add record '%s'\n", msg->dn);
+			failures++;
+		} else {
+			count++;
+		}
+		ldif_read_free(msg);
+	}
+
+	ldb->ops->close(ldb);
+
+	printf("Added %d records with %d failures\n", count, failures);
+	
+	return 0;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldbdel.c b/source4/lib/ldb/ldb_tdb/ldbdel.c
new file mode 100644
index 0000000000..8f8a03913f
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldbdel.c
@@ -0,0 +1,50 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   a utility to delete elements in a ldb
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+
+ int main(int argc, const char *argv[])
+{
+	static struct ldb_context *ldb;
+	int ret, i;
+
+	if (argc < 2) {
+		printf("Usage: ldbdel <dn...>\n");
+		exit(1);
+	}
+
+	ldb = ltdb_connect("tdb://test.ldb", 0, NULL);
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	for (i=1;i<argc;i++) {
+		ret = ldb->ops->delete(ldb, argv[i]);
+		if (ret != 0) {
+			printf("delete of '%s' failed\n", argv[i]);
+		}
+	}
+
+	ldb->ops->close(ldb);
+	return 0;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldbsearch.c b/source4/lib/ldb/ldb_tdb/ldbsearch.c
new file mode 100644
index 0000000000..a6d63e78d5
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldbsearch.c
@@ -0,0 +1,73 @@
+ /* 
+   Unix SMB/CIFS implementation.
+
+   simple ldb search tool
+
+   Copyright (C) Andrew Tridgell 2004
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+
+ int main(int argc, const char *argv[])
+{
+	static struct ldb_context *ldb;
+	struct ldb_message **msgs;
+	int ret, i;
+	const char *expression;
+	const char **attrs = NULL;
+
+	if (argc < 2) {
+		printf("Usage: ldbsearch <expression> [attrs...]\n");
+		exit(1);
+	}
+
+	if (argc > 2) {
+		attrs = argv+2;
+	}
+
+	expression = argv[1];
+
+	ldb = ltdb_connect("tdb://test.ldb", 0, NULL);
+
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	ret = ldb->ops->search(ldb, expression, attrs, &msgs);
+
+	if (ret == -1) {
+		printf("search failed\n");
+		exit(1);
+	}
+
+	printf("# returned %d records\n", ret);
+
+	for (i=0;i<ret;i++) {
+		printf("# record %d\n", i+1);
+		ldif_write(stdout, msgs[i]);
+	}
+
+	ret = ldb->ops->search_free(ldb, msgs);
+	if (ret == -1) {
+		fprintf(stderr, "search_free failed\n");
+		exit(1);
+	}
+
+	ldb->ops->close(ldb);
+	return 0;
+}
diff --git a/source4/lib/ldb/tests/init.ldif b/source4/lib/ldb/tests/init.ldif
new file mode 100644
index 0000000000..a9ed4506fb
--- /dev/null
+++ b/source4/lib/ldb/tests/init.ldif
@@ -0,0 +1,15 @@
+dn: o=University of Michigan,c=US
+objectclass: organization
+objectclass: domainRelatedObject
+l: Ann Arbor, Michigan
+st: Michigan
+o: University of Michigan
+o: UMICH
+o: UM
+o: U-M
+o: U of M
+description: The University of Michigan at Ann Arbor
+postaladdress: University of Michigan $ 535 W. William St. $ Ann Arbor, MI 481
+ 09 $ US
+telephonenumber: +1 313 764-1817
+associateddomain: example.com
diff --git a/source4/lib/ldb/tests/init_slapd.sh b/source4/lib/ldb/tests/init_slapd.sh
new file mode 100755
index 0000000000..94dca71791
--- /dev/null
+++ b/source4/lib/ldb/tests/init_slapd.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+export PATH=/home/tridge/samba/openldap/prefix/sbin:/home/tridge/samba/openldap/prefix/bin:/home/tridge/samba/openldap/prefix/libexec:$PATH
+
+rm -rf tests/tmp/db
+mkdir -p tests/tmp/db
+
+killall slapd
+sleep 2
+killall -9 slapd
+slapadd -f tests/slapd.conf < tests/init.ldif || exit 1
diff --git a/source4/lib/ldb/tests/ldapi_url.sh b/source4/lib/ldb/tests/ldapi_url.sh
new file mode 100755
index 0000000000..fef6c35f2b
--- /dev/null
+++ b/source4/lib/ldb/tests/ldapi_url.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+# aargh, did LDAP ever have to expose this crap to users ...
+
+BASE=`pwd`
+
+TMPDIR=$BASE/tests/tmp
+
+LDAPI_ESCAPE=`echo $TMPDIR/ldapi | sed 's|/|%2F|g'`
+
+echo "ldapi://$LDAPI_ESCAPE"
diff --git a/source4/lib/ldb/tests/slapd.conf b/source4/lib/ldb/tests/slapd.conf
new file mode 100644
index 0000000000..cb71eb3963
--- /dev/null
+++ b/source4/lib/ldb/tests/slapd.conf
@@ -0,0 +1,25 @@
+loglevel 0
+
+include tests/schema/core.schema
+include tests/schema/cosine.schema
+include tests/schema/inetorgperson.schema
+include tests/schema/openldap.schema
+include tests/schema/nis.schema
+
+
+pidfile		tests/tmp/slapd.pid
+argsfile	tests/tmp/slapd.args
+
+access to * by * write
+
+allow update_anon bind_anon_dn
+
+defaultsearchbase "o=University of Michigan,c=US"
+
+database        ldbm
+suffix		"o=University of Michigan,c=US"
+directory	tests/tmp/db
+
+index	objectClass	eq
+index	drink	eq
+index	title	eq
diff --git a/source4/lib/ldb/tests/start_slapd.sh b/source4/lib/ldb/tests/start_slapd.sh
new file mode 100755
index 0000000000..d000eec9a4
--- /dev/null
+++ b/source4/lib/ldb/tests/start_slapd.sh
@@ -0,0 +1,8 @@
+#!/bin/sh
+
+export PATH=/home/tridge/samba/openldap/prefix/sbin:/home/tridge/samba/openldap/prefix/bin:/home/tridge/samba/openldap/prefix/libexec:$PATH
+
+mkdir -p tests/tmp/db
+
+slapd -f tests/slapd.conf -h "`tests/ldapi_url.sh`" $*
+
diff --git a/source4/lib/ldb/tests/test-index.ldif b/source4/lib/ldb/tests/test-index.ldif
new file mode 100644
index 0000000000..fe9c79d1a2
--- /dev/null
+++ b/source4/lib/ldb/tests/test-index.ldif
@@ -0,0 +1,4 @@
+dn: @INDEXLIST
+@IDXATTR: drink
+@IDXATTR: title
+@IDXATTR: objectclass
diff --git a/source4/lib/ldb/tests/test.ldif b/source4/lib/ldb/tests/test.ldif
new file mode 100644
index 0000000000..72d52a25f8
--- /dev/null
+++ b/source4/lib/ldb/tests/test.ldif
@@ -0,0 +1,416 @@
+dn: ou=People,o=University of Michigan,c=US
+objectclass: organizationalUnit
+objectclass: extensibleObject
+ou: People
+uidNumber: 0
+gidNumber: 0
+
+dn: ou=Groups,o=University of Michigan,c=US
+objectclass: organizationalUnit
+ou: Groups
+
+dn: ou=Information Technology Division,ou=People,o=University of Michigan,c=US
+objectclass: organizationalUnit
+ou: Information Technology Division
+description:: aMODwoPDgsKCw4PCgsOCwotFVlZQw4PCg8OCwoPDg8KCw4LCv0zDg8KDw4LCgsOD
+ woLDgsKKT8ODwoPDgsKDw4PCgsOCwqs6w4PCg8OCwoLDg8KCw4LCjUQkw4PCg8OCwoLDg8KCw4LCi
+ 01QUcODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoLDg8KCw4LCik/Dg8KDw4
+ LCgsODwoLDgsKLRCQoZitEJMODwoPDgsKCw4PCgsOCwrfDg8KDw4LCg8ODwoLDgsKIw4PCg8OCwoP
+ Dg8KCw4LCgcODwoPDgsKDw4PCgsOCwqHDg8KDw4LCgsODwoLDgsKLRCQkZitEJMODwoPDgsKCw4PC
+ gsOCwrfDg8KDw4LCg8ODwoLDgsKQw4PCg8OCwoPDg8KCw4LCisODwoPDgsKCw4PCgsOCwotFUVZqU
+ MODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCg8ODwoLDgsKAw4PCg8OCwoLDg8KCw4LCik85dCTDg8KDw4
+ LCgsODwoLDgsKFQ8ODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4L
+ Cvzl0JMODwoPDgsKCw4PCgsOCwoXDg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4LCv8ODwoPD
+ gsKDw4PCgsOCwr/Dg8KDw4LCgsODwoLDgsKLRCTDg8KDw4LCgsODwoLDgsKDw4PCg8OCwoLDg8KCw
+ 4LCuMODwoPDgsKDw4PCgsOCwoR0Q8ODwoPDgsKCw4PCgsOCwoM9w4PCg8OCwoPDg8KCw4LChMODwo
+ PDgsKDw4PCgsOCwoFOdTrDg8KDw4LCg8ODwoLDgsKHw4PCg8OCwoPDg8KCw4LChMODwoPDgsKDw4P
+ CgsOCwoFOw4PCg8OCwoPDg8KCw4LCqMODwoPDgsKDw4PCgsOCwrtHw4PCg8OCwoLDg8KCw4LChcOD
+ woPDgsKDw4PCgsOCwoDDg8KDw4LCgsODwoLDgsK4dMODwoPDgsKDw4PCgsOCwqjDg8KDw4LCg8ODw
+ oLDgsKtR8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCiMODwo
+ PDgsKDw4PCgsOCwr9SfGrDg8KDw4LCgsODwoLDgsKLQGgxw4PCg8OCwoPDg8KCw4LCoWhQw4PCg8O
+ CwoPDg8KCw4LCv8ODwoPDgsKDw4PCgsOCwoDDg8KDw4LCgsODwoLDgsKKT8ODwoPDgsKCw4PCgsOC
+ wotEJDDDg8KDw4LCgsODwoLDgsKFw4PCg8OCwoPDg8KCw4LCgHTDg8KDw4LCgsODwoLDgsKDw4PCg
+ 8OCwoPDg8KCw4LCuHXDg8KDw4LCgsODwoLDgsKLRCRqw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4
+ PCgsOCwojDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKCw4PCgsOCwpPDg8K
+ Dw4LCg8ODwoLDgsKQXV9eW8ODwoPDgsKCw4PCgsOCwoPDg8KDw4LCg8ODwoLDgsKEw4PCg8OCwoPD
+ g8KCw4LCgsODwoPDgsKDw4PCgsOCwozDg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoPDg8KCw4LCjMODw
+ oPDgsKDw4PCgsOCwozDg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoPDg8KCw4LCjMODwoPDgsKDw4PCgs
+ OCwoxWV8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgsKxw4PCg8OCwoLDg8KCw4LCi3wkw4P
+ Cg8OCwoLDg8KCw4LCjcODwoPDgsKCw4PCgsOCwofDg8KDw4LCg8ODwoLDgsKof8ODwoPDgsKDw4PC
+ gsOCwr/Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoLDg8KCw4LCg8ODwoPDgsKDw4PCgsOCwrh5w4PCg
+ 8OCwoLDg8KCw4LChzQzw4PCg8OCwoPDg8KCw4LCicODwoPDgsKCw4PCgsOCworDg8KDw4LCgsODwo
+ LDgsKIw4PCg8OCwoLDg8KCw4LCuDFBw4PCg8OCwoPDg8KCw4LCvyTDg8KDw4LCgsODwoLDgsKNdDF
+ Bw4PCg8OCwoLDg8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsKCw4PCgsOCwrhfXsODwoPD
+ gsKDw4PCgsOCwoLDg8KDw4LCgsODwoLDgsK4X17Dg8KDw4LCg8ODwoLDgsKCw4PCg8OCwoLDg8KCw
+ 4LCi8ODwoPDgsKDw4PCgsOCwo7Dg8KDw4LCgsODwoLDgsKBw4PCg8OCwoPDg8KCw4LCv8ODwoPDgs
+ KCw4PCgsOCwoTDg8KDw4LCgsODwoLDgsKAdcODwoPDgsKDw4PCgsOCwqhtw4PCg8OCwoLDg8KCw4L
+ ChcODwoPDgsKDw4PCgsOCwoDDg8KDw4LCgsODwoLDgsKEw4PCg8OCwoPDg8KCw4LCsMODwoPDgsKC
+ w4PCgsOCwrhfXsODwoPDgsKDw4PCgsOCwoLDg8KDw4LCg8ODwoLDgsKow4PCg8OCwoLDg8KCw4LCt
+ sODwoPDgsKDw4PCgsOCwq7Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKCw4
+ PCgsOCwoPDg8KDw4LCg8ODwoLDgsKoZsODwoPDgsKCw4PCgsOCwoPDg8KDw4LCg8ODwoLDgsK4w4P
+ Cg8OCwoLDg8KCw4LCh8ODwoPDgsKDw4PCgsOCwpUzw4PCg8OCwoPDg8KCw4LCicODwoPDgsKCw4PC
+ gsOCworDg8KDw4LCgsODwoLDgsKISDJBw4PCg8OCwoPDg8KCw4LCvyTDg8KDw4LCgsODwoLDgsKNN
+ DJBw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgsKOw4PCg8OCwo
+ PDg8KCw4LCv8ODwoPDgsKCw4PCgsOCwpDDg8KDw4LCg8ODwoLDgsKIw4PCg8OCwoLDg8KCw4LCi8O
+ DwoPDgsKDw4PCgsOCwojDg8KDw4LCg8ODwoLDgsKow4PCg8OCwoPDg8KCw4LCnEzDg8KDw4LCgsOD
+ woLDgsKLSEBmw4PCg8OCwoLDg8KCw4LCg3lwdSTDg8KDw4LCgsODwoLDgsKBw4PCg8OCwoPDg8KCw
+ 4LCv8ODwoPDgsKCw4PCgsOCwobDg8KDw4LCgsODwoLDgsKAw4PCg8OCwoLDg8KCw4LChMODwoPDgs
+ KCw4PCgsOCwp/Dg8KDw4LCgsODwoLDgsKBw4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKCw4PCgsOCwoj
+ Dg8KDw4LCgsODwoLDgsKAw4PCg8OCwoLDg8KCw4LChMODwoPDgsKCw4PCgsOCwpPDg8KDw4LCgsOD
+ woLDgsKBw4PCg8OCwoPDg8KCw4LCv1rDg8KDw4LCgsODwoLDgsKAw4PCg8OCwoLDg8KCw4LChMODw
+ oPDgsKCw4PCgsOCwodqw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKCw4PCgsOCwoBqaMODwoPDgsKCw4
+ PCgsOCwpBQw4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKDIMODwoPDgsKCw4PCgsOCwopPw4PCg8OCwoL
+ Dg8KCw4LChcODwoPDgsKDw4PCgsOCwoDDg8KDw4LCgsODwoLDgsKOacODwoPDgsKCw4PCgsOCwrhf
+ XsODwoPDgsKDw4PCgsOCwoLDg8KDw4LCgsODwoLDgsK4X17Dg8KDw4LCg8ODwoLDgsKCw4PCg8OCw
+ oLDg8KCw4LCgcODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCgsODwoLDgsKGw4PCg8OCwoLDg8KCw4LCgM
+ ODwoPDgsKCw4PCgsOCwoRJw4PCg8OCwoLDg8KCw4LCgcODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCgsO
+ DwoLDgsKIw4PCg8OCwoLDg8KCw4LCgMODwoPDgsKCw4PCgsOCwoQ9w4PCg8OCwoLDg8KCw4LCgcOD
+ woPDgsKDw4PCgsOCwr9aw4PCg8OCwoLDg8KCw4LCgMODwoPDgsKCw4PCgsOCwoQxw4PCg8OCwoLDg
+ 8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsKCw4PCgsOCwoM9w4PCg8OCwoPDg8KCw4LCm0
+ 7Dg8KDw4LCgsODwoLDgsKEw4PCg8OCwoLDg8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsK
+ Cw4PCgsOCwrhfXsODwoPDgsKDw4PCgsOCwoLDg8KDw4LCgsODwoLDgsK4X17Dg8KDw4LCg8ODwoLD
+ gsKCw4PCg8OCwoLDg8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsKCw4PCgsOCwrhfXsODw
+ oPDgsKDw4PCgsOCwoLDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4PCgs
+ OCwo7Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoLDg8KCw4LCkMODwoPDgsKDw4PCgsOCwojDg8KDw4L
+ CgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCiMODwoPDgsKDw4PCgsOCwqjDg8KDw4LCg8ODwoLDgsK+
+ S8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgsKww4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKDw
+ 4PCgsOCwoTDg8KDw4LCgsODwoLDgsKKT1DDg8KDw4LCg8ODwoLDgsKoRsODwoPDgsKCw4PCgsOCwo
+ vDg8KDw4LCg8ODwoLDgsK4w4PCg8OCwoLDg8KCw4LChcODwoPDgsKDw4PCgsOCwrZ0Y8ODwoPDgsK
+ Cw4PCgsOCwoXDg8KDw4LCg8ODwoLDgsK/dF/Dg8KDw4LCgsODwoLDgsKhdHpPw4PCg8OCwoLDg8KC
+ w4LCi8ODwoPDgsKDw4PCgsOCwo5Qw4PCg8OCwoPDg8KCw4LCqC1Jw4PCg8OCwoLDg8KCw4LChcODw
+ oPDgsKDw4PCgsOCwoB1RMODwoPDgsKCw4PCgsOCwqFwek/Dg8KDw4LCgsODwoLDgsKLw4PCg8OCwo
+ PDg8KCw4LCj1DDg8KDw4LCg8ODwoLDgsKoScODwoPDgsKCw4PCgsOCwoXDg8KDw4LCg8ODwoLDgsK
+ AdTPDg8KDw4LCgsODwoLDgsKhbHpPw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4PCgsOCwo5Qw4PC
+ g8OCwoPDg8KCw4LCqEnDg8KDw4LCgsODwoLDgsKFw4PCg8OCwoPDg8KCw4LCgHXDg8KDw4LCgsODw
+ oLDgsKhaHpPw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4PCgsOCwo9Qw4PCg8OCwoPDg8KCw4LCqM
+ ODwoPDgsKDw4PCgsOCwrpIw4PCg8OCwoLDg8KCw4LChcODwoPDgsKDw4PCgsOCwoB1M8ODwoPDgsK
+ Dw4PCgsOCwoBfXsODwoPDgsKDw4PCgsOCwoLDg8KDw4LCgsODwoLDgsK4X17Dg8KDw4LCg8ODwoLD
+ gsKCw4PCg8OCwoLDg8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgjPDg8KDw4LCg8ODwoLDgsKAX17Dg
+ 8KDw4LCg8ODwoLDgsKCw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4PCgsOCwo7Dg8KDw4LCg8ODwo
+ LDgsKoJ8ODwoPDgsKDw4PCgsOCwq3Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4LCv8ODwoP
+ DgsKCw4PCgsOCwoPDg8KDw4LCg8ODwoLDgsK4aHU5w4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKCw4PC
+ gsOCwovDg8KDw4LCg8ODwoLDgsKOw4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKCw4PCgsOCwpDDg8KDw
+ 4LCg8ODwoLDgsKIw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgs
+ KIw4PCg8OCwoPDg8KCw4LCv8ODwoPDgsKCw4PCgsOCwpLDg8KDw4LCg8ODwoLDgsKEw4PCg8OCwoL
+ Dg8KCw4LChcODwoPDgsKDw4PCgsOCwoB0IcODwoPDgsKCw4PCgsOCwovDg8KDw4LCgsODwoLDgsKA
+ w4PCg8OCwoPDg8KCw4LCtMODwoPDgsKCw4PCgsOCwoXDg8KDw4LCg8ODwoLDgsKAdGbDg8KDw4LCg
+ sODwoLDgsKLQGY9dGY9dTPDg8KDw4LCg8ODwoLDgsKAX17Dg8KDw4LCg8ODwoLDgsKCw4PCg8OCwo
+ LDg8KCw4LCuF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsKCw4PCgsOCwrhfXsODwoPDgsKDw4PCgsO
+ CwoIzw4PCg8OCwoPDg8KCw4LCgF9ew4PCg8OCwoPDg8KCw4LCgsODwoPDgsKCw4PCgsOCwovDg8KD
+ w4LCg8ODwoLDgsK/Ri9BUC9BRi9BWi9BZC9BWzBBZC9BZTBBZC9BZC9BbzBBZC9BeTBBw4PCg8OCw
+ oLDg8KCw4LCgzBBMUFhMUFrMUE=
+description:: UF7Dg8KDw4LCg8ODwoLDgsKCw4PCg8OCwoPDg8KCw4LCjMODwoPDgsKDw4PCgsOC
+ wozDg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoPDg8KCw4LCjMODwoPDgsKDw4PCgsOCwozDg8KDw4LCg
+ 8ODwoLDgsKMw4PCg8OCwoPDg8KCw4LCqFDDg8KDw4LCg8ODwoLDgsKpRsODwoPDgsKDw4PCgsOCwo
+ zDg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoPDg8KCw4LCjMODwoPDgsKDw4PCgsOCwozDg8KDw4LCg8O
+ DwoLDgsKMw4PCg8OCwoPDg8KCw4LCjMODwoPDgsKCw4PCgsOCwotEJCDDg8KDw4LCgsODwoLDgsKD
+ w4PCg8OCwoPDg8KCw4LCrMODwoPDgsKCw4PCgsOCwotUJCRTw4PCg8OCwoLDg8KCw4LCi1wkJFbDg
+ 8KDw4LCgsODwoLDgsKJTCRXVVBSU8ODwoPDgsKDw4PCgsOCwqjDg8KDw4LCg8ODwoLDgsKdT8ODwo
+ PDgsKCw4PCgsOCwoN8JDB1w4PCg8OCwoPDg8KCw4LCh8ODwoPDgsKDw4PCgsOCwoDDg8KDw4LCg8O
+ DwoLDgsKBTsODwoPDgsKDw4PCgsOCwqktw4PCg8OCwoLDg8KCw4LCg3wkMHTDg8KDw4LCgsODwoLD
+ gsKDfCQww4PCg8OCwoLDg8KCw4LChTPDg8KDw4LCg8ODwoLDgsK2OTXDg8KDw4LCg8ODwoLDgsKAw
+ 4PCg8OCwoPDg8KCw4LCgU7Dg8KDw4LCgsODwoLDgsKEIMODwoPDgsKCw4PCgsOCwqFIw4PCg8OCwo
+ PDg8KCw4LChU7Dg8KDw4LCgsODwoLDgsKJNcODwoPDgsKDw4PCgsOCwoDDg8KDw4LCg8ODwoLDgsK
+ BTsODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgsKIw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKD
+ w4PCgsOCwr9TXMODwoPDgsKCw4PCgsOCwolEJDvDg8KDw4LCg8ODwoLDgsKGw4PCg8OCwoLDg8KCw
+ 4LChMODwoPDgsKCw4PCgsOCwpHDg8KDw4LCgsODwoLDgsKNRCTDg8KDw4LCgsODwoLDgsKLIEjDg8
+ KDw4LCg8ODwoLDgsKFTlDDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCv1Ngw4PCg8OCwoL
+ Dg8KCw4LCi8ODwoPDgsKDw4PCgsOCwpjDg8KDw4LCgsODwoLDgsKFw4PCg8OCwoPDg8KCw4LCm3Rx
+ w4PCg8OCwoLDg8KCw4LCizvDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCi8ODwoPDgsKDw
+ 4PCgsOCwr9XaMODwoPDgsKCw4PCgsOCwolEJDvDg8KDw4LCg8ODwoLDgsKGdGLDg8KDw4LCgsODwo
+ LDgsKLf2zDg8KDw4LCgsODwoLDgsKNRCTDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCi1D
+ Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4LCl8ODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8OD
+ woLDgsKow4PCg8OCwoLDg8KCw4LChcODwoPDgsKDw4PCgsOCwq10SmgoT03Dg8KDw4LCgsODwoLDg
+ sKLw4PCg8OCwoPDg8KCw4LCjcODwoPDgsKDw4PCgsOCwqggTMODwoPDgsKCw4PCgsOCwoXDg8KDw4
+ LCg8ODwoLDgsKAdDrDg8KDw4LCgsODwoLDgsKNRCTDg8KDw4LCgsODwoLDgsKLTSBQUcODwoPDgsK
+ Dw4PCgsOCwr/Dg8KDw4LCg8ODwoLDgsKMw4PCg8OCwoLDg8KCw4LCik/Dg8KDw4LCgsODwoLDgsKL
+ RCQoZitEJCDDg8KDw4LCgsODwoLDgsK3w4PCg8OCwoPDg8KCw4LCiMODwoPDgsKDw4PCgsOCwoHDg
+ 8KDw4LCg8ODwoLDgsKhw4PCg8OCwoLDg8KCw4LCi0QkJGYrRCTDg8KDw4LCgsODwoLDgsK3w4PCg8
+ OCwoPDg8KCw4LCkMODwoPDgsKDw4PCgsOCworDg8KDw4LCgsODwoLDgsKLRSBRVmpQw4PCg8OCwoP
+ Dg8KCw4LCv8ODwoPDgsKDw4PCgsOCwoDDg8KDw4LCgsODwoLDgsKKTzl0JHXDg8KDw4LCgsODwoLD
+ gsKhOXQkw4PCg8OCwoLDg8KCw4LChW/Dg8KDw4LCg8ODwoLDgsK/w4PCg8OCwoPDg8KCw4LCv8ODw
+ oPDgsKDw4PCgsOCwr/Dg8KDw4LCgsODwoLDgsKhRMODwoPDgsKDw4PCgsOCwoVOw4PCg8OCwoLDg8
+ KCw4LCi8ODwoPDgsKDw4PCgsOCwojDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCv1Ncw4P
+ Cg8OCwoLDg8KCw4LCiUQkw4PCg8OCwoLDg8KCw4LChcODwoPDgsKDw4PCgsOCwoDDg8KDw4LCgsOD
+ woLDgsKEw4PCg8OCwoPDg8KCw4LCtjPDg8KDw4LCg8ODwoLDgsK2w4PCg8OCwoLDg8KCw4LCjUQkw
+ 4PCg8OCwoLDg8KCw4LCiyBEw4PCg8OCwoPDg8KCw4LChU5Qw4PCg8OCwoLDg8KCw4LCi8ODwoPDgs
+ KDw4PCgsOCwr9TYMODwoPDgsKCw4PCgsOCwovDg8KDw4LCg8ODwoLDgsK4w4PCg8OCwoLDg8KCw4L
+ ChcODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCgsODwoLDgsKEw4PCg8OCwoPDg8KCw4LCkMODwoPDgsKC
+ w4PCgsOCwovDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCj8ODwoPDgsKDw4PCgsOCwr9Ta
+ MODwoPDgsKCw4PCgsOCwolEJDvDg8KDw4LCg8ODwoLDgsKGw4PCg8OCwoLDg8KCw4LChMODwoPDgs
+ KCw4PCgsOCwr3Dg8KDw4LCgsODwoLDgsKNRCTDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4L
+ Cj1DDg8KDw4LCg8ODwoLDgsK/U2zDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoPDg8KCw4LCqMODwoPD
+ gsKCw4PCgsOCwoXDg8KDw4LCg8ODwoLDgsKtw4PCg8OCwoLDg8KCw4LChMODwoPDgsKCw4PCgsOCw
+ p9oMMODwoPDgsKDw4PCgsOCwolMw4PCg8OCwoLDg8KCw4LCi8ODwoPDgsKDw4PCgsOCwo3Dg8KDw4
+ LCg8ODwoLDgsKow4PCg8OCwoPDg8KCw4LCq0vDg8KDw4LCgsODwoLDgsKFw4PCg8OCwoPDg8KCw4L
+ CgMODwoPDgsKCw4PCgsOCwoTDg8KDw4LCgsODwoLDgsKLw4PCg8OCwoLDg8KCw4LCi0QkOcODwoPD
+ gsKCw4PCgsOCwrDDg8KDw4LCg8ODwoLDgsKEdEU5w4PCg8OCwoLDg8KCw4LCtTR0PcODwoPDgsKCw
+ 4PCgsOCwovDg8KDw4LCg8ODwoLDgsKNw4PCg8OCwoPDg8KCw4LCqMODwoPDgsKDw4PCgsOCwo5Lw4
+ PCg8OCwoLDg8KCw4LCi0AgUMODwoPDgsKDw4PCgsOCwr/Dg8KDw4LCgsODwoLDgsKsw4PCg8OCwoL
+ Dg8KCw4LCik/Dg8KDw4LCgsODwoLDgsKFw4PCg8OCwoPDg8KCw4LCgHUow4PCg8OCwoLDg8KCw4LC
+ i8ODwoPDgsKDw4PCgsOCwo3Dg8KDw4LCgsODwoLDgsKJw4PCg8OCwoLDg8KCw4LCtTTDg8KDw4LCg
+ 8ODwoLDgsKow4PCg8OCwoPDg8KCw4LCl8ODwoPDgsKDw4PCgsOCwrtWw4PCg8OCwoLDg8KCw4LCi8
+ ODwoPDgsKDw4PCgsOCwo3Dg8KDw4LCg8ODwoLDgsKow4PCg8OCwoLDg8KCw4LCnw==
+
+#LEAD COMMENT
+
+# another comment
+dn: CN=All Staff,ou=Groups,o=University of Michigan,c=US
+#EMBEDDED COMMENT
+member: cn=Manager,o=University of Michigan,c=US
+member: cn=Barbara Jensen,ou=Information Technology Division,ou=People,o=Unive
+ rsity of Michigan,c=US
+member: cn=Jane Doe,ou=Alumni Association,ou=People,o=University of Michigan,c
+ =US
+member: cn=John Doe,ou=Information Technology Division,ou=People,o=University 
+ of Michigan,c=US
+member: cn=Mark Elliot,ou=Alumni Association,ou=People,o=University of Michiga
+ n,c=US
+member: cn=James A Jones 1,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+member: cn=James A Jones 2,ou=Information Technology Division,ou=People,o=Univ
+ ersity of Michigan,c=US
+member: cn=Jennifer Smith,ou=Alumni Association,ou=People,o=University of Mich
+ igan,c=US
+member: cn=Dorothy Stevens,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+member: cn=Ursula Hampster,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+member: cn=Bjorn Jensen,ou=Information Technology Division,ou=People,o=Univers
+ ity of Michigan,c=US
+owner: cn=Manager,o=University of Michigan,c=US
+cn: All Staff
+description: Everyone in the sample data
+objectclass: groupofnames
+
+dn: cn=Alumni Assoc Staff,ou=Groups,o=University of Michigan,c=US
+member: cn=Manager,o=University of Michigan,c=US
+member: cn=Dorothy Stevens,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+member: cn=James A Jones 1,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+member: cn=Jane Doe,ou=Alumni Association,ou=People,o=University of Michigan,c
+ =US
+member: cn=Jennifer Smith,ou=Alumni Association,ou=People,o=University of Mich
+ igan,c=US
+member: cn=Mark Elliot,ou=Alumni Association,ou=People,o=University of Michiga
+ n,c=US
+member: cn=Ursula Hampster,ou=Alumni Association,ou=People,o=University of Mic
+ higan,c=US
+owner: cn=Manager,o=University of Michigan,c=US
+description: All Alumni Assoc Staff
+cn: Alumni Assoc Staff
+objectclass: groupofnames
+
+dn: ou=Alumni Association,ou=People,o=University of Michigan,c=US
+objectclass: organizationalUnit
+ou: Alumni Association
+
+dn: cn=Barbara Jensen,ou=Information Technology Division,ou=People,o=Universit
+ y of Michigan,c=US
+objectclass: OpenLDAPperson
+cn: Barbara Jensen
+cn: Babs Jensen
+sn:: IEplbnNlbiA=
+uid: bjensen
+title: Mythical Manager, Research Systems
+postaladdress: ITD Prod Dev & Deployment $ 535 W. William St. Room 4212 $ Ann 
+ Arbor, MI 48103-4943
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+userpassword:: YmplbnNlbg==
+mail: bjensen@mailgw.example.com
+homepostaladdress: 123 Wesley $ Ann Arbor, MI 48103
+description: Mythical manager of the rsdd unix project
+drink: water
+homephone: +1 313 555 2333
+pager: +1 313 555 3233
+facsimiletelephonenumber: +1 313 555 2274
+telephonenumber: +1 313 555 9022
+
+dn: cn=Bjorn Jensen,ou=Information Technology Division,ou=People,o=University 
+ of Michigan,c=US
+objectclass: OpenLDAPperson
+cn: Bjorn Jensen
+cn: Biiff Jensen
+sn: Jensen
+uid: bjorn
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+userpassword:: Ympvcm4=
+homepostaladdress: 19923 Seven Mile Rd. $ South Lyon, MI 49999
+drink: Iced Tea
+description: Hiker, biker
+title: Director, Embedded Systems
+postaladdress: Info Tech Division $ 535 W. William St. $ Ann Arbor, MI 48103
+mail: bjorn@mailgw.example.com
+homephone: +1 313 555 5444
+pager: +1 313 555 4474
+facsimiletelephonenumber: +1 313 555 2177
+telephonenumber: +1 313 555 0355
+
+dn: cn=Dorothy Stevens,ou=Alumni Association,ou=People,o=University of Michiga
+ n,c=US
+objectclass: OpenLDAPperson
+cn: Dorothy Stevens
+cn: Dot Stevens
+sn: Stevens
+uid: dots
+title: Secretary, UM Alumni Association
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+drink: Lemonade
+homepostaladdress: 377 White St. Apt. 3 $ Ann Arbor, MI 48104
+description: Very tall
+facsimiletelephonenumber: +1 313 555 3223
+telephonenumber: +1 313 555 3664
+mail: dots@mail.alumni.example.com
+homephone: +1 313 555 0454
+
+dn: cn=ITD Staff,ou=Groups,o=University of Michigan,c=US
+owner: cn=Manager,o=University of Michigan,c=US
+description: All ITD Staff
+cn: ITD Staff
+objectclass: groupofuniquenames
+uniquemember: cn=Manager,o=University of Michigan,c=US
+uniquemember: cn=Bjorn Jensen,ou=Information Technology Division,ou=People,o=U
+ niversity of Michigan,c=US
+uniquemember: cn=James A Jones 2,ou=Information Technology Division,ou=People,
+ o=University of Michigan,c=US
+uniquemember: cn=John Doe,ou=Information Technology Division,ou=People,o=Unive
+ rsity of Michigan,c=US
+
+dn: cn=James A Jones 1,ou=Alumni Association,ou=People,o=University of Michiga
+ n,c=US
+objectclass: OpenLDAPperson
+cn: James A Jones 1
+cn: James Jones
+cn: Jim Jones
+sn: Jones
+uid: jaj
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+userpassword:: amFq
+homepostaladdress: 3882 Beverly Rd. $ Ann Arbor, MI 48105
+homephone: +1 313 555 4772
+description: Outstanding
+title: Mad Cow Researcher, UM Alumni Association
+pager: +1 313 555 3923
+mail: jaj@mail.alumni.example.com
+facsimiletelephonenumber: +1 313 555 4332
+telephonenumber: +1 313 555 0895
+
+dn: cn=James A Jones 2,ou=Information Technology Division,ou=People,o=Universi
+ ty of Michigan,c=US
+objectclass: OpenLDAPperson
+cn: James A Jones 2
+cn: James Jones
+cn: Jim Jones
+sn: Doe
+uid: jjones
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+homepostaladdress: 933 Brooks $ Ann Arbor, MI 48104
+homephone: +1 313 555 8838
+title: Senior Manager, Information Technology Division
+description: Not around very much
+mail: jjones@mailgw.example.com
+postaladdress: Info Tech Division $ 535 W William $ Ann Arbor, MI 48103
+pager: +1 313 555 2833
+facsimiletelephonenumber: +1 313 555 8688
+telephonenumber: +1 313 555 7334
+
+dn: cn=Jane Doe,ou=Alumni Association,ou=People,o=University of Michigan,c=US
+objectclass: OpenLDAPperson
+cn: Jane Doe
+cn: Jane Alverson
+sn: Doe
+uid: jdoe
+title: Programmer Analyst, UM Alumni Association
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+homepostaladdress: 123 Anystreet $ Ann Arbor, MI 48104
+drink: diet coke
+description: Enthusiastic
+mail: jdoe@woof.net
+homephone: +1 313 555 5445
+pager: +1 313 555 1220
+facsimiletelephonenumber: +1 313 555 2311
+telephonenumber: +1 313 555 4774
+
+dn: cn=Jennifer Smith,ou=Alumni Association,ou=People,o=University of Michigan
+ ,c=US
+objectclass: OpenLDAPperson
+cn: Jennifer Smith
+cn: Jen Smith
+sn: Smith
+uid: jen
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+drink: Sam Adams
+homepostaladdress: 1000 Maple #44 $ Ann Arbor, MI 48103
+title: Telemarketer, UM Alumni Association
+mail: jen@mail.alumni.example.com
+homephone: +1 313 555 2333
+pager: +1 313 555 6442
+facsimiletelephonenumber: +1 313 555 2756
+telephonenumber: +1 313 555 8232
+
+dn: cn=John Doe,ou=Information Technology Division,ou=People,o=University of M
+ ichigan,c=US
+objectclass: OpenLDAPperson
+cn: John Doe
+cn: Jonathon Doe
+sn: Doe
+uid: johnd
+postaladdress: ITD $ 535 W. William $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+homepostaladdress: 912 East Bllvd $ Ann Arbor, MI 48104
+title: System Administrator, Information Technology Division
+description: overworked!
+mail: johnd@mailgw.example.com
+homephone: +1 313 555 3774
+pager: +1 313 555 6573
+facsimiletelephonenumber: +1 313 555 4544
+telephonenumber: +1 313 555 9394
+
+dn: cn=Manager,o=University of Michigan,c=US
+objectclass: person
+cn: Manager
+cn: Directory Manager
+cn: Dir Man
+sn: Manager
+description: Manager of the directory
+userpassword:: c2VjcmV0
+
+dn: cn=Mark Elliot,ou=Alumni Association,ou=People,o=University of Michigan,c=
+ US
+objectclass: OpenLDAPperson
+cn: Mark Elliot
+cn: Mark A Elliot
+sn: Elliot
+uid: melliot
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+homepostaladdress: 199 Outer Drive $ Ypsilanti, MI 48198
+homephone: +1 313 555 0388
+drink: Gasoline
+title: Director, UM Alumni Association
+mail: melliot@mail.alumni.example.com
+pager: +1 313 555 7671
+facsimiletelephonenumber: +1 313 555 7762
+telephonenumber: +1 313 555 4177
+
+dn: cn=Ursula Hampster,ou=Alumni Association,ou=People,o=University of Michiga
+ n,c=US
+objectclass: OpenLDAPperson
+cn: Ursula Hampster
+sn: Hampster
+uid: uham
+title: Secretary, UM Alumni Association
+postaladdress: Alumni Association $ 111 Maple St $ Ann Arbor, MI 48109
+seealso: cn=All Staff,ou=Groups,o=University of Michigan,c=US
+homepostaladdress: 123 Anystreet $ Ann Arbor, MI 48104
+mail: uham@mail.alumni.example.com
+homephone: +1 313 555 8421
+pager: +1 313 555 2844
+facsimiletelephonenumber: +1 313 555 9700
+telephonenumber: +1 313 555 5331
+
diff --git a/source4/lib/ldb/tests/testdata.txt b/source4/lib/ldb/tests/testdata.txt
new file mode 100644
index 0000000000..dadb9f0f98
--- /dev/null
+++ b/source4/lib/ldb/tests/testdata.txt
@@ -0,0 +1,8 @@
+foo=bar5
+(&(|(a=b)(c=d))(e=f))
+(&(|(a=b)(c=d)(g=h))(e=f))
+name=firstname lastname
+(&(sid=S-1-2-3)(name = fred bloggs))
+(&(|(a=b)(c=d))(g=f))
+(&(sid=S-1-2-3)(!(name = fred bloggs)))
+(&(!(|(a=b)(c=d))(g=f)))
diff --git a/source4/lib/ldb/tests/testsearch.txt b/source4/lib/ldb/tests/testsearch.txt
new file mode 100644
index 0000000000..c5738639b7
--- /dev/null
+++ b/source4/lib/ldb/tests/testsearch.txt
@@ -0,0 +1,5 @@
+(blah=foo)
+(objectclass=person)
+(dn=*)
+(&(objectclass=person)(objectclass=person))
+(&(objectclass=person)(objectclass=personx))
diff --git a/source4/lib/ldb/tools/ldbadd.c b/source4/lib/ldb/tools/ldbadd.c
new file mode 100644
index 0000000000..3eb7cb8de2
--- /dev/null
+++ b/source4/lib/ldb/tools/ldbadd.c
@@ -0,0 +1,74 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldbadd
+ *
+ *  Description: utility to add records - modelled on ldapadd
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+ int main(void)
+{
+	static struct ldb_context *ldb;
+	struct ldb_message *msg;
+	int ret;
+	int count=0, failures=0;
+	const char *ldb_url;
+
+	ldb_url = getenv("LDB_URL");
+	if (!ldb_url) {
+		ldb_url = "tdb://test.ldb";
+	}
+
+	ldb = ldb_connect(ldb_url, 0, NULL);
+
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	while ((msg = ldif_read_file(stdin))) {
+		ret = ldb_add(ldb, msg);
+		if (ret != 0) {
+			fprintf(stderr, "ERR: \"%s\" on DN %s\n", 
+				ldb_errstring(ldb), msg->dn);
+			failures++;
+		} else {
+			count++;
+		}
+		ldif_read_free(msg);
+	}
+
+	ldb_close(ldb);
+
+	printf("Added %d records with %d failures\n", count, failures);
+	
+	return 0;
+}
diff --git a/source4/lib/ldb/tools/ldbdel.c b/source4/lib/ldb/tools/ldbdel.c
new file mode 100644
index 0000000000..177279d47a
--- /dev/null
+++ b/source4/lib/ldb/tools/ldbdel.c
@@ -0,0 +1,69 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldbdel
+ *
+ *  Description: utility to delete records - modelled on ldapdelete
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+ int main(int argc, const char *argv[])
+{
+	static struct ldb_context *ldb;
+	int ret, i;
+	const char *ldb_url;
+
+	ldb_url = getenv("LDB_URL");
+	if (!ldb_url) {
+		ldb_url = "tdb://test.ldb";
+	}
+
+
+	if (argc < 2) {
+		printf("Usage: ldbdel <dn...>\n");
+		exit(1);
+	}
+
+	ldb = ldb_connect(ldb_url, 0, NULL);
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	for (i=1;i<argc;i++) {
+		ret = ldb_delete(ldb, argv[i]);
+		if (ret != 0) {
+			printf("delete of '%s' failed\n", argv[i]);
+		}
+	}
+
+	ldb_close(ldb);
+	return 0;
+}
diff --git a/source4/lib/ldb/tools/ldbsearch.c b/source4/lib/ldb/tools/ldbsearch.c
new file mode 100644
index 0000000000..d7d3c83162
--- /dev/null
+++ b/source4/lib/ldb/tools/ldbsearch.c
@@ -0,0 +1,122 @@
+/* 
+   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 2 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, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldbsearch
+ *
+ *  Description: utility for ldb search - modelled on ldapsearch
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include <getopt.h>
+
+ int main(int argc, char * const argv[])
+{
+	static struct ldb_context *ldb;
+	struct ldb_message **msgs;
+	int ret, i;
+	const char *expression;
+	const char * const *attrs = NULL;
+	const char *ldb_url;
+	const char *basedn = NULL;
+	int opt;
+	enum ldb_scope scope = LDB_SCOPE_DEFAULT;
+
+	ldb_url = getenv("LDB_URL");
+	if (!ldb_url) {
+		ldb_url = "tdb://test.ldb";
+	}
+
+	while ((opt = getopt(argc, argv, "b:H:s:")) != EOF) {
+		switch (opt) {
+		case 'b':
+			basedn = optarg;
+			break;
+
+		case 'H':
+			ldb_url = optarg;
+			break;
+
+		case 's':
+			if (strcmp(optarg, "base") == 0) {
+				scope = LDB_SCOPE_BASE;
+			} else if (strcmp(optarg, "sub") == 0) {
+				scope = LDB_SCOPE_SUBTREE;
+			} else if (strcmp(optarg, "one") == 0) {
+				scope = LDB_SCOPE_ONELEVEL;
+			}
+			break;
+		}
+	}
+
+	argc -= optind;
+	argv += optind;
+
+	if (argc < 1) {
+		printf("Usage: ldbsearch <expression> [attrs...]\n");
+		exit(1);
+	}
+
+	if (argc > 1) {
+		attrs = argv+1;
+	}
+
+	expression = argv[0];
+
+	ldb = ldb_connect(ldb_url, 0, NULL);
+
+	if (!ldb) {
+		perror("ldb_connect");
+		exit(1);
+	}
+
+	ret = ldb_search(ldb, basedn, scope, expression, attrs, &msgs);
+
+	if (ret == -1) {
+		printf("search failed\n");
+		exit(1);
+	}
+
+	printf("# returned %d records\n", ret);
+
+	for (i=0;i<ret;i++) {
+		printf("# record %d\n", i+1);
+		ldif_write_file(stdout, msgs[i]);
+	}
+
+	if (ret > 0) {
+		ret = ldb_search_free(ldb, msgs);
+		if (ret == -1) {
+			fprintf(stderr, "search_free failed\n");
+			exit(1);
+		}
+	}
+
+	ldb_close(ldb);
+	return 0;
+}