r435: a major upgrade for ldb

 - added the ability to mark record attributes as being CASE_INSENSITIVE, WILDCARD or INTEGER.

 - added the ability to support objectclass subclasses, and to search by a parent class

 - added internal support for case insensitive versus case sensitive
   indexing (not UTF8 compliant yet)

 - cleaned up a number of const warnings

 - added a number of helper functions for fetching integers, strings and doubles

 - added a in-memory cache for important database properties, supported by a
   database sequence number

 - changed some variable names to avoid conflicts with C++
(This used to be commit f2bf06f25c2e6c744817711c7bedbd1d3b52f994)

18 files changed, 904 insertions, 142 deletions

diff --git a/source4/lib/ldb/Makefile.ldb b/source4/lib/ldb/Makefile.ldb
index 6ff1bcf78e..ba8c040f9c 100644
--- a/source4/lib/ldb/Makefile.ldb
+++ b/source4/lib/ldb/Makefile.ldb
@@ -17,11 +17,12 @@ LIB_FLAGS=-Llib -lldb $(LDAP_LIBS)
 TDB_OBJ=$(TDBDIR)/tdb.o $(TDBDIR)/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_tdb/ldb_pack.o ldb_tdb/ldb_search.o ldb_tdb/ldb_index.o \
+	ldb_tdb/ldb_cache.o
 
 
 COMMON_OBJ=common/ldb.o common/ldb_ldif.o common/util.o \
-	   common/ldb_parse.o common/ldb_msg.o
+	   common/ldb_parse.o common/ldb_msg.o common/ldb_utf8.o
 
 OBJS =  $(COMMON_OBJ) $(LDB_TDB_OBJ) $(TDB_OBJ) $(LDB_LDAP_OBJ)
 
@@ -66,3 +67,6 @@ proto:
 
 etags:
 	etags */*.[ch]
+
+test:
+	tests/test-tdb.sh
diff --git a/source4/lib/ldb/common/ldb_ldif.c b/source4/lib/ldb/common/ldb_ldif.c
index fcf0150557..1ca585ca80 100644
--- a/source4/lib/ldb/common/ldb_ldif.c
+++ b/source4/lib/ldb/common/ldb_ldif.c
@@ -407,6 +407,7 @@ void ldif_read_free(struct ldb_ldif *ldif)
 	struct ldb_message *msg = &ldif->msg;
 	int i;
 	for (i=0;i<msg->num_elements;i++) {
+		if (msg->elements[i].name) free(msg->elements[i].name);
 		if (msg->elements[i].values) free(msg->elements[i].values);
 	}
 	if (msg->elements) free(msg->elements);
@@ -431,11 +432,16 @@ static int msg_add_empty(struct ldb_message *msg, const char *name, unsigned fla
 
 	el = &msg->elements[msg->num_elements];
 	
-	el->name = name;
+	el->name = strdup(name);
 	el->num_values = 0;
 	el->values = NULL;
 	el->flags = flags;
 
+	if (!el->name) {
+		errno = ENOMEM;
+		return -1;
+	}
+
 	msg->num_elements++;
 
 	return 0;
@@ -478,7 +484,7 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data)
 	}
 	
 	/* first line must be a dn */
-	if (strcmp(attr, "dn") != 0) {
+	if (ldb_attr_cmp(attr, "dn") != 0) {
 		fprintf(stderr, "First line must be a dn not '%s'\n", attr);
 		goto failed;
 	}
@@ -489,10 +495,10 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data)
 		struct ldb_message_element *el;
 		int empty = 0;
 
-		if (strcmp(attr, "changetype") == 0) {
+		if (ldb_attr_cmp(attr, "changetype") == 0) {
 			int i;
 			for (i=0;ldb_changetypes[i].name;i++) {
-				if (strcmp((char *)value.data, ldb_changetypes[i].name) == 0) {
+				if (ldb_attr_cmp((char *)value.data, ldb_changetypes[i].name) == 0) {
 					ldif->changetype = ldb_changetypes[i].changetype;
 					break;
 				}
@@ -505,19 +511,19 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data)
 			continue;
 		}
 
-		if (strcmp(attr, "add") == 0) {
+		if (ldb_attr_cmp(attr, "add") == 0) {
 			flags = LDB_FLAG_MOD_ADD;
 			empty = 1;
 		}
-		if (strcmp(attr, "delete") == 0) {
+		if (ldb_attr_cmp(attr, "delete") == 0) {
 			flags = LDB_FLAG_MOD_DELETE;
 			empty = 1;
 		}
-		if (strcmp(attr, "replace") == 0) {
+		if (ldb_attr_cmp(attr, "replace") == 0) {
 			flags = LDB_FLAG_MOD_REPLACE;
 			empty = 1;
 		}
-		if (strcmp(attr, "-") == 0) {
+		if (ldb_attr_cmp(attr, "-") == 0) {
 			flags = 0;
 			continue;
 		}
@@ -531,7 +537,7 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data)
 		
 		el = &msg->elements[msg->num_elements-1];
 
-		if (msg->num_elements > 0 && strcmp(attr, el->name) == 0 &&
+		if (msg->num_elements > 0 && ldb_attr_cmp(attr, el->name) == 0 &&
 		    flags == el->flags) {
 			/* its a continuation */
 			el->values = 
@@ -549,11 +555,11 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data)
 			if (!msg->elements) {
 				goto failed;
 			}
-			msg->elements[msg->num_elements].flags = flags;
-			msg->elements[msg->num_elements].name = attr;
 			el = &msg->elements[msg->num_elements];
+			el->flags = flags;
+			el->name = strdup(attr);
 			el->values = malloc_p(struct ldb_val);
-			if (!el->values) {
+			if (!el->values || !el->name) {
 				goto failed;
 			}
 			el->num_values = 1;
diff --git a/source4/lib/ldb/common/ldb_msg.c b/source4/lib/ldb/common/ldb_msg.c
index 633cc91f2c..8eb8a8c5ef 100644
--- a/source4/lib/ldb/common/ldb_msg.c
+++ b/source4/lib/ldb/common/ldb_msg.c
@@ -43,23 +43,40 @@ struct ldb_message_element *ldb_msg_find_element(const struct ldb_message *msg,
 {
 	int i;
 	for (i=0;i<msg->num_elements;i++) {
-		if (strcmp(msg->elements[i].name, attr_name) == 0) {
+		if (ldb_attr_cmp(msg->elements[i].name, attr_name) == 0) {
 			return &msg->elements[i];
 		}
 	}
 	return NULL;
 }
 
+/*
+  see if two ldb_val structures contain exactly the same data
+  return 1 for a match, 0 for a mis-match
+*/
+int ldb_val_equal_exact(const struct ldb_val *v1, const 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;
+}
 
 /*
   find a value in an element
+  assumes case sensitive comparison
 */
 struct ldb_val *ldb_msg_find_val(const struct ldb_message_element *el, 
 				 struct ldb_val *val)
 {
 	int i;
 	for (i=0;i<el->num_values;i++) {
-		if (ldb_val_equal(val, &el->values[i])) {
+		if (ldb_val_equal_exact(val, &el->values[i])) {
 			return &el->values[i];
 		}
 	}
@@ -113,6 +130,7 @@ int ldb_msg_add(struct ldb_message *msg,
 
 /*
   compare two ldb_message_element structures
+  assumes case senistive comparison
 */
 int ldb_msg_element_compare(struct ldb_message_element *el1, 
 			    struct ldb_message_element *el2)
@@ -131,3 +149,52 @@ int ldb_msg_element_compare(struct ldb_message_element *el1,
 
 	return 0;
 }
+
+
+/*
+  convenience functions to return common types from a message
+  these return the first value if the attribute is multi-valued
+*/
+int ldb_msg_find_int(const struct ldb_message *msg, 
+		     const char *attr_name,
+		     int default_value)
+{
+	struct ldb_message_element *el = ldb_msg_find_element(msg, attr_name);
+	if (!el || el->num_values == 0) {
+		return default_value;
+	}
+	return strtol(el->values[0].data, NULL, 0);
+}
+
+unsigned int ldb_msg_find_uint(const struct ldb_message *msg, 
+			       const char *attr_name,
+			       int default_value)
+{
+	struct ldb_message_element *el = ldb_msg_find_element(msg, attr_name);
+	if (!el || el->num_values == 0) {
+		return default_value;
+	}
+	return strtoul(el->values[0].data, NULL, 0);
+}
+
+double ldb_msg_find_double(const struct ldb_message *msg, 
+			   const char *attr_name,
+			   double default_value)
+{
+	struct ldb_message_element *el = ldb_msg_find_element(msg, attr_name);
+	if (!el || el->num_values == 0) {
+		return default_value;
+	}
+	return strtod(el->values[0].data, NULL);
+}
+
+const char *ldb_msg_find_string(const struct ldb_message *msg, 
+				const char *attr_name,
+				const char *default_value)
+{
+	struct ldb_message_element *el = ldb_msg_find_element(msg, attr_name);
+	if (!el || el->num_values == 0) {
+		return default_value;
+	}
+	return el->values[0].data;
+}
diff --git a/source4/lib/ldb/common/ldb_utf8.c b/source4/lib/ldb/common/ldb_utf8.c
new file mode 100644
index 0000000000..7767b0955e
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_utf8.c
@@ -0,0 +1,87 @@
+/* 
+   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 utf8 handling
+ *
+ *  Description: case folding and case comparison for UTF8 strings
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+/*
+  TODO:
+  a simple case folding function - will be replaced by a UTF8 aware function later
+*/
+char *ldb_casefold(const char *s)
+{
+	int i;
+	char *ret = strdup(s);
+	if (!s) {
+		errno = ENOMEM;
+		return NULL;
+	}
+	for (i=0;ret[i];i++) {
+		ret[i] = toupper(ret[i]);
+	}
+	return ret;
+}
+
+/*
+  a caseless compare, optimised for 7 bit
+  TODO: doesn't yet handle UTF8
+*/
+static int ldb_caseless_cmp(const char *s1, const char *s2)
+{
+	int i;
+	for (i=0;s1[i] != 0;i++) {
+		int c1 = toupper(s1[i]), c2 = toupper(s2[i]);
+		if (c1 != c2) {
+			return c1 - c2;
+		}
+	}
+	return s2[i];
+}
+
+/*
+  compare two basedn fields
+  return 0 for match
+*/
+int ldb_dn_cmp(const char *dn1, const char *dn2)
+{
+	return ldb_caseless_cmp(dn1, dn2);
+}
+
+/*
+  compare two attributes
+  return 0 for match
+*/
+int ldb_attr_cmp(const char *dn1, const char *dn2)
+{
+	return ldb_caseless_cmp(dn1, dn2);
+}
diff --git a/source4/lib/ldb/config.m4 b/source4/lib/ldb/config.m4
index 737ff8b6f6..444e65bfab 100644
--- a/source4/lib/ldb/config.m4
+++ b/source4/lib/ldb/config.m4
@@ -7,11 +7,13 @@ SMB_SUBSYSTEM(LIBLDB,[lib/ldb/common/ldb.o],
 		lib/ldb/common/ldb_parse.o \
 		lib/ldb/common/ldb_msg.o \
 		lib/ldb/common/util.o \
+		lib/ldb/common/ldb_utf8.o \
 		lib/ldb/ldb_tdb/ldb_search.o \
 		lib/ldb/ldb_tdb/ldb_tdb.o \
 		lib/ldb/ldb_tdb/ldb_pack.o \
 		lib/ldb/ldb_tdb/ldb_index.o \
 		lib/ldb/ldb_tdb/ldb_match.o \
+		lib/ldb/ldb_tdb/ldb_cache.o \
 	        \$(LIBLDB_LDAP_OBJS)],
 		lib/ldb/include/ldb.h)
 
diff --git a/source4/lib/ldb/include/includes.h b/source4/lib/ldb/include/includes.h
index 70ad1f3588..485d7157b8 100644
--- a/source4/lib/ldb/include/includes.h
+++ b/source4/lib/ldb/include/includes.h
@@ -14,6 +14,7 @@
 #include <stdarg.h>
 #include <signal.h>
 #include <unistd.h>
+#include <fnmatch.h>
 #include "ldb.h"
 #include "ldb_parse.h"
 
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index 6369ab683a..215671c98a 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -124,7 +124,7 @@ typedef int (*ldb_traverse_fn)(struct ldb_context *, const struct ldb_message *)
 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 ***);
+		      const char *, char * const [], struct ldb_message ***);
 	int (*search_free)(struct ldb_context *, struct ldb_message **);
 	int (*add_record)(struct ldb_context *, const struct ldb_message *);
 	int (*modify_record)(struct ldb_context *, const struct ldb_message *);
@@ -207,6 +207,11 @@ int ldb_delete(struct ldb_context *ldb, const char *dn);
 const char *ldb_errstring(struct ldb_context *ldb);
 
 /*
+  casefold a string (should be UTF8, but at the moment it isn't)
+*/
+char *ldb_casefold(const char *s);
+
+/*
   ldif manipulation functions
 */
 int ldif_write(int (*fprintf_fn)(void *, const char *, ...), 
@@ -217,3 +222,4 @@ struct ldb_ldif *ldif_read(int (*fgetc_fn)(void *), void *private_data);
 struct ldb_ldif *ldif_read_file(FILE *f);
 struct ldb_ldif *ldif_read_string(const char *s);
 int ldif_write_file(FILE *f, const struct ldb_ldif *msg);
+
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.c b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
index 55c083b44c..8723beeadc 100644
--- a/source4/lib/ldb/ldb_ldap/ldb_ldap.c
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
@@ -96,6 +96,11 @@ static int lldb_delete(struct ldb_context *ldb, const char *dn)
 {
 	struct lldb_private *lldb = ldb->private_data;
 	int ret = 0;
+
+	/* ignore ltdb specials */
+	if (dn[0] == '@') {
+		return 0;
+	}
 	
 	lldb->last_rc = ldap_delete_s(lldb->ldap, dn);
 	if (lldb->last_rc != LDAP_SUCCESS) {
@@ -202,7 +207,7 @@ static int lldb_add_msg_attr(struct ldb_message *msg,
 */
 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)
+		       char * const *attrs, struct ldb_message ***res)
 {
 	struct lldb_private *lldb = ldb->private_data;
 	int count, msg_count;
@@ -392,6 +397,11 @@ static int lldb_add(struct ldb_context *ldb, const struct ldb_message *msg)
 	LDAPMod **mods;
 	int ret = 0;
 
+	/* ignore ltdb specials */
+	if (msg->dn[0] == '@') {
+		return 0;
+	}
+
 	mods = lldb_msg_to_mods(msg, 0);
 
 	lldb->last_rc = ldap_add_s(lldb->ldap, msg->dn, mods);
@@ -414,6 +424,11 @@ static int lldb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
 	LDAPMod **mods;
 	int ret = 0;
 
+	/* ignore ltdb specials */
+	if (msg->dn[0] == '@') {
+		return 0;
+	}
+
 	mods = lldb_msg_to_mods(msg, 1);
 
 	lldb->last_rc = ldap_modify_s(lldb->ldap, msg->dn, mods);
diff --git a/source4/lib/ldb/ldb_tdb/ldb_cache.c b/source4/lib/ldb/ldb_tdb/ldb_cache.c
new file mode 100644
index 0000000000..5d61fd35b3
--- /dev/null
+++ b/source4/lib/ldb/ldb_tdb/ldb_cache.c
@@ -0,0 +1,229 @@
+/* 
+   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 cache functions
+ *
+ *  Description: cache special records in a ldb/tdb
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+#include "ldb/ldb_tdb/ldb_tdb.h"
+
+/*
+  initialise the baseinfo record
+*/
+static int ltdb_baseinfo_init(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+	struct ldb_message msg;
+	struct ldb_message_element el;
+	struct ldb_val val;
+
+	ltdb->sequence_number = 0;
+
+	msg.num_elements = 1;
+	msg.elements = &el;
+	msg.dn = LTDB_BASEINFO;
+	el.name = LTDB_SEQUENCE_NUMBER;
+	el.values = &val;
+	el.num_values = 1;
+	el.flags = 0;
+	val.data = "0";
+	val.length = 1;
+	
+	return ltdb_store(ldb, &msg, TDB_INSERT);
+}
+
+/*
+  free any cache records
+ */
+void ltdb_cache_free(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+
+	ltdb->sequence_number = 0;
+	ltdb_search_dn1_free(ldb, &ltdb->cache.baseinfo);
+	ltdb_search_dn1_free(ldb, &ltdb->cache.indexlist);
+	ltdb_search_dn1_free(ldb, &ltdb->cache.subclasses);
+	ltdb_search_dn1_free(ldb, &ltdb->cache.attributes);
+
+	if (ltdb->cache.last_attribute.name) free(ltdb->cache.last_attribute.name);
+	memset(&ltdb->cache, 0, sizeof(ltdb->cache));
+}
+
+/*
+  load the cache records
+*/
+int ltdb_cache_load(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+	double seq;
+
+	ltdb_search_dn1_free(ldb, &ltdb->cache.baseinfo);
+	
+	if (ltdb_search_dn1(ldb, LTDB_BASEINFO, &ltdb->cache.baseinfo) == -1) {
+		return -1;
+	}
+	
+	/* possibly initialise the baseinfo */
+	if (!ltdb->cache.baseinfo.dn) {
+		if (ltdb_baseinfo_init(ldb) != 0) {
+			return -1;
+		}
+		if (ltdb_search_dn1(ldb, LTDB_BASEINFO, &ltdb->cache.baseinfo) != 1) {
+			return -1;
+		}
+	}
+
+	/* if the current internal sequence number is the same as the one
+	   in the database then assume the rest of the cache is OK */
+	seq = ldb_msg_find_double(&ltdb->cache.baseinfo, LTDB_SEQUENCE_NUMBER, 0);
+	if (seq == ltdb->sequence_number) {
+		return 0;
+	}
+	ltdb->sequence_number = seq;
+
+	if (ltdb->cache.last_attribute.name) free(ltdb->cache.last_attribute.name);
+	memset(&ltdb->cache.last_attribute, 0, sizeof(ltdb->cache.last_attribute));
+
+	ltdb_search_dn1_free(ldb, &ltdb->cache.indexlist);
+	ltdb_search_dn1_free(ldb, &ltdb->cache.subclasses);
+	ltdb_search_dn1_free(ldb, &ltdb->cache.attributes);
+
+	if (ltdb_search_dn1(ldb, LTDB_INDEXLIST, &ltdb->cache.indexlist) == -1) {
+		return -1;
+	}
+	if (ltdb_search_dn1(ldb, LTDB_SUBCLASSES, &ltdb->cache.subclasses) == -1) {
+		return -1;
+	}
+	if (ltdb_search_dn1(ldb, LTDB_ATTRIBUTES, &ltdb->cache.attributes) == -1) {
+		return -1;
+	}
+
+	return 0;
+}
+
+
+/*
+  increase the sequence number to indicate a database change
+*/
+int ltdb_increase_sequence_number(struct ldb_context *ldb)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+	struct ldb_message msg;
+	struct ldb_message_element el;
+	struct ldb_val val;
+	char *s = NULL;
+	int ret;
+
+	asprintf(&s, "%.0f", ltdb->sequence_number+1);
+	if (!s) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	msg.num_elements = 1;
+	msg.elements = &el;
+	msg.dn = LTDB_BASEINFO;
+	el.name = LTDB_SEQUENCE_NUMBER;
+	el.values = &val;
+	el.num_values = 1;
+	el.flags = LDB_FLAG_MOD_REPLACE;
+	val.data = s;
+	val.length = strlen(s);
+
+	ret = ltdb_modify_internal(ldb, &msg);
+
+	free(s);
+
+	if (ret == 0) {
+		ltdb->sequence_number += 1;
+	}
+
+	return ret;
+}
+
+
+/*
+  return the attribute flags from the @ATTRIBUTES record 
+  for the given attribute
+*/
+int ltdb_attribute_flags(struct ldb_context *ldb, const char *attr_name)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+	const char *attrs;
+	const struct {
+		const char *name;
+		int value;
+	} names[] = {
+		{ "CASE_INSENSITIVE", LTDB_FLAG_CASE_INSENSITIVE },
+		{ "INTEGER", LTDB_FLAG_INTEGER },
+		{ "WILDCARD", LTDB_FLAG_WILDCARD },
+		{ NULL, 0}
+	};
+	size_t len;
+	int i, ret=0;
+
+	if (ltdb->cache.last_attribute.name &&
+	    ldb_attr_cmp(ltdb->cache.last_attribute.name, attr_name) == 0) {
+		return ltdb->cache.last_attribute.flags;
+	}
+
+	/* objectclass is a special default case */
+	if (ldb_attr_cmp(attr_name, LTDB_OBJECTCLASS) == 0) {
+		ret = LTDB_FLAG_OBJECTCLASS | LTDB_FLAG_CASE_INSENSITIVE;
+	}
+
+	attrs = ldb_msg_find_string(&ltdb->cache.attributes, attr_name, NULL);
+
+	if (!attrs) {
+		return ret;
+	}
+
+	/* we avoid using strtok and friends due to their nasty
+	   interface. This is a little trickier, but much nicer
+	   from a C interface point of view */
+	while ((len = strcspn(attrs, " ,")) > 0) {
+		for (i=0;names[i].name;i++) {
+			if (strncmp(names[i].name, attrs, len) == 0 &&
+			    names[i].name[len] == 0) {
+				ret |= names[i].value;
+			}
+		}
+		attrs += len;
+		attrs += strspn(attrs, " ,");
+	}
+
+	if (ltdb->cache.last_attribute.name) free(ltdb->cache.last_attribute.name);
+
+	ltdb->cache.last_attribute.name = strdup(attr_name);
+	ltdb->cache.last_attribute.flags = ret;
+	
+	return ret;
+}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index a23fc2d525..c4243e9b40 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -63,12 +63,12 @@ static char *ldb_dn_key(const char *attr, const struct ldb_val *value)
 	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);
+		asprintf(&ret, "%s:%s::%s", LTDB_INDEX, attr, vstr);
 		free(vstr);
 		return ret;
 	}
 
-	asprintf(&ret, "@INDEX:%s:%s", attr, (char *)value->data);
+	asprintf(&ret, "%s:%s:%s", LTDB_INDEX, attr, (char *)value->data);
 	return ret;
 }
 
@@ -80,11 +80,11 @@ static int ldb_msg_find_idx(const struct ldb_message *msg, const char *attr,
 {
 	int i, j;
 	for (i=0;i<msg->num_elements;i++) {
-		if (strcmp(msg->elements[i].name, "@IDXATTR") == 0) {
+		if (ldb_attr_cmp(msg->elements[i].name, LTDB_IDXATTR) == 0) {
 			const struct ldb_message_element *el = 
 				&msg->elements[i];
 			for (j=0;j<el->num_values;j++) {
-				if (strcmp((char *)el->values[j].data, attr) == 0) {
+				if (ldb_attr_cmp((char *)el->values[j].data, attr) == 0) {
 					if (v_idx) {
 						*v_idx = j;
 					}
@@ -114,7 +114,7 @@ static int ltdb_index_dn_simple(struct ldb_context *ldb,
 	/*
 	  if the value is a wildcard then we can't do a match via indexing
 	*/
-	if (ltdb_has_wildcard(&tree->u.simple.value)) {
+	if (ltdb_has_wildcard(ldb, tree->u.simple.attr, &tree->u.simple.value)) {
 		return -1;
 	}
 
@@ -138,7 +138,7 @@ static int ltdb_index_dn_simple(struct ldb_context *ldb,
 	for (i=0;i<msg.num_elements;i++) {
 		struct ldb_message_element *el;
 
-		if (strcmp(msg.elements[i].name, "@IDX") != 0) {
+		if (strcmp(msg.elements[i].name, LTDB_IDX) != 0) {
 			continue;
 		}
 
@@ -420,7 +420,7 @@ 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)
+			    char * const attrs[], struct ldb_message ***res)
 {
 	int i;
 	unsigned int count = 0;
@@ -460,21 +460,18 @@ 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)
+			char * const attrs[], struct ldb_message ***res)
 {
-	struct ldb_message index_list;
+	struct ltdb_private *ltdb = ldb->private_data;
 	struct dn_list dn_list;
 	int ret;
 
-	/* find the list of indexed fields */	
-	ret = ltdb_search_dn1(ldb, "@INDEXLIST", &index_list);
-	if (ret != 1) {
+	if (ltdb->cache.indexlist.num_elements == 0) {
 		/* 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);
+	ret = ltdb_index_dn(ldb, tree, &ltdb->cache.indexlist, &dn_list);
 
 	if (ret == 1) {
 		/* we've got a candidate list - now filter by the full tree
@@ -493,7 +490,7 @@ int ltdb_search_indexed(struct ldb_context *ldb,
 static int ltdb_index_add1_new(struct ldb_context *ldb, 
 			       struct ldb_message *msg,
 			       struct ldb_message_element *el,
-			       const char *dn)
+			       char *dn)
 {
 	struct ldb_message_element *el2;
 
@@ -504,7 +501,7 @@ static int ltdb_index_add1_new(struct ldb_context *ldb,
 	}
 
 	msg->elements = el2;
-	msg->elements[msg->num_elements].name = "@IDX";
+	msg->elements[msg->num_elements].name = LTDB_IDX;
 	msg->elements[msg->num_elements].num_values = 0;
 	msg->elements[msg->num_elements].values = malloc_p(struct ldb_val);
 	if (!msg->elements[msg->num_elements].values) {
@@ -527,7 +524,7 @@ static int ltdb_index_add1_add(struct ldb_context *ldb,
 			       struct ldb_message *msg,
 			       struct ldb_message_element *el,
 			       int idx,
-			       const char *dn)
+			       char *dn)
 {
 	struct ldb_val *v2;
 
@@ -549,7 +546,7 @@ static int ltdb_index_add1_add(struct ldb_context *ldb,
 /*
   add an index entry for one message element
 */
-static int ltdb_index_add1(struct ldb_context *ldb, const char *dn, 
+static int ltdb_index_add1(struct ldb_context *ldb, char *dn, 
 			   struct ldb_message_element *el, int v_idx)
 {
 	struct ldb_message msg;
@@ -582,7 +579,7 @@ static int ltdb_index_add1(struct ldb_context *ldb, const char *dn,
 	free(dn_key);
 
 	for (i=0;i<msg.num_elements;i++) {
-		if (strcmp("@IDX", msg.elements[i].name) == 0) {
+		if (strcmp(LTDB_IDX, msg.elements[i].name) == 0) {
 			break;
 		}
 	}
@@ -608,32 +605,27 @@ static int ltdb_index_add1(struct ldb_context *ldb, const char *dn,
 */
 int ltdb_index_add(struct ldb_context *ldb, const struct ldb_message *msg)
 {
+	struct ltdb_private *ltdb = ldb->private_data;
 	int ret, i, j;
-	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;
+	if (ltdb->cache.indexlist.num_elements == 0) {
+		/* no indexed fields */
+		return 0;
 	}
 
 	for (i=0;i<msg->num_elements;i++) {
-		ret = ldb_msg_find_idx(&index_list, msg->elements[i].name, NULL);
+		ret = ldb_msg_find_idx(&ltdb->cache.indexlist, msg->elements[i].name, NULL);
 		if (ret == -1) {
 			continue;
 		}
 		for (j=0;j<msg->elements[i].num_values;j++) {
 			ret = ltdb_index_add1(ldb, msg->dn, &msg->elements[i], j);
 			if (ret == -1) {
-				ltdb_search_dn1_free(ldb, &index_list);
 				return -1;
 			}
 		}
 	}
 
-	ltdb_search_dn1_free(ldb, &index_list);
-
 	return 0;
 }
 
@@ -698,25 +690,23 @@ static int ltdb_index_del1(struct ldb_context *ldb, const char *dn,
 */
 int ltdb_index_del(struct ldb_context *ldb, const struct ldb_message *msg)
 {
+	struct ltdb_private *ltdb = ldb->private_data;
 	int ret, i, j;
-	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;
+	if (ltdb->cache.indexlist.num_elements == 0) {
+		/* no indexed fields */
+		return 0;
 	}
 
 	for (i=0;i<msg->num_elements;i++) {
-		ret = ldb_msg_find_idx(&index_list, msg->elements[i].name, NULL);
+		ret = ldb_msg_find_idx(&ltdb->cache.indexlist, msg->elements[i].name, NULL);
 		if (ret == -1) {
 			continue;
 		}
 		for (j=0;j<msg->elements[i].num_values;j++) {
 			ret = ltdb_index_del1(ldb, msg->dn, &msg->elements[i], j);
 			if (ret == -1) {
-				ltdb_search_dn1_free(ldb, &index_list);
 				return -1;
 			}
 		}
@@ -731,7 +721,8 @@ int ltdb_index_del(struct ldb_context *ldb, const struct ldb_message *msg)
 */
 static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
 {
-	if (strncmp(key.dptr, "DN=@INDEX:", 10) == 0) {
+	const char *dn = "DN=" LTDB_INDEX ":";
+	if (strncmp(key.dptr, dn, strlen(dn)) == 0) {
 		return tdb_delete(tdb, key);
 	}
 	return 0;
@@ -756,7 +747,9 @@ static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *
 		return -1;
 	}
 
-	msg.dn = key.dptr+3;
+	if (!msg.dn) {
+		msg.dn = key.dptr+3;
+	}
 
 	ret = ltdb_index_add(ldb, &msg);
 
@@ -773,6 +766,12 @@ int ltdb_reindex(struct ldb_context *ldb)
 	struct ltdb_private *ltdb = ldb->private_data;
 	int ret;
 
+	ltdb_cache_free(ldb);
+
+	if (ltdb_cache_load(ldb) != 0) {
+		return -1;
+	}
+
 	/* first traverse the database deleting any @INDEX records */
 	ret = tdb_traverse(ltdb->tdb, delete_index, NULL);
 	if (ret == -1) {
diff --git a/source4/lib/ldb/ldb_tdb/ldb_match.c b/source4/lib/ldb/ldb_tdb/ldb_match.c
index 6f29726ee7..26e0eebfe7 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_match.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_match.c
@@ -33,14 +33,162 @@
  */
 
 #include "includes.h"
+#include "ldb/ldb_tdb/ldb_tdb.h"
 
 
 /*
+  see if two ldb_val structures contain the same data as integers
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal_integer(const struct ldb_val *v1, const struct ldb_val *v2)
+{
+	int i1, i2;
+
+	i1 = strtol(v1->data, NULL, 0);
+	i2 = strtol(v2->data, NULL, 0);
+
+	return i1 == i2;
+}
+
+/*
+  see if two ldb_val structures contain the same data as case insensitive strings
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal_case_insensitive(const struct ldb_val *v1, 
+					  const struct ldb_val *v2)
+{
+	if (v1->length != v2->length) {
+		return 0;
+	}
+	if (strncasecmp(v1->data, v2->data, v1->length) == 0) {
+		return 1;
+	}
+	return 0;
+}
+
+/*
+  see if two ldb_val structures contain the same data with wildcards 
+  and case insensitive
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal_wildcard_ci(const struct ldb_val *v1, 
+				     const struct ldb_val *v2)
+{
+	char *s1, *s2;
+	int ret;
+
+	if (!v1->data || !v2->data) {
+		return v1->data == v2->data;
+	}
+
+	s1 = ldb_casefold(v1->data);
+	if (!s1) {
+		return -1;
+	}
+
+	s2 = ldb_casefold(v2->data);
+	if (!s2) {
+		return -1;
+	}
+
+	ret = fnmatch(s2, s1, 0);
+
+	free(s1);
+	free(s2);
+
+	if (ret == 0) {
+		return 1;
+	}
+
+	return 0;
+}
+
+/*
+  see if two ldb_val structures contain the same data with wildcards
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal_wildcard(const struct ldb_val *v1, 
+				  const struct ldb_val *v2,
+				  int flags)
+{
+	if (flags & LTDB_FLAG_CASE_INSENSITIVE) {
+		return ldb_val_equal_wildcard_ci(v1, v2);
+	}
+	if (!v1->data || !v2->data) {
+		return v1->data == v2->data;
+	}
+	if (fnmatch(v2->data, v1->data, 0) == 0) {
+		return 1;
+	}
+	return 0;
+}
+
+
+/*
+  see if two objectclasses are considered equal. This handles
+  the subclass attributes
+
+  v1 contains the in-database value, v2 contains the value
+  that the user gave
+
+  return 1 for a match, 0 for a mis-match
+*/
+static int ldb_val_equal_objectclass(struct ldb_context *ldb, 
+				     const struct ldb_val *v1, const struct ldb_val *v2)
+{
+	struct ltdb_private *ltdb = ldb->private_data;
+	int i;
+
+	if (ldb_val_equal_case_insensitive(v1, v2) == 1) {
+		return 1;
+	}
+
+	for (i=0;i<ltdb->cache.subclasses.num_elements;i++) {
+		struct ldb_message_element *el = &ltdb->cache.subclasses.elements[i];
+		if (ldb_attr_cmp(el->name, v2->data) == 0) {
+			int j;
+			for (j=0;j<el->num_values;j++) {
+				if (ldb_val_equal_objectclass(ldb, v1, &el->values[j])) {
+					return 1;
+				}
+			}
+		}
+	}
+
+	return 0;
+}
+				     
+
+/*
   see if two ldb_val structures contain the same data
+  
+  v1 contains the in-database value, v2 contains the value
+  that the user gave
+  
   return 1 for a match, 0 for a mis-match
 */
-int ldb_val_equal(const struct ldb_val *v1, const struct ldb_val *v2)
+int ldb_val_equal(struct ldb_context *ldb,
+		  const char *attr_name,
+		  const struct ldb_val *v1, const struct ldb_val *v2)
 {
+	int flags = ltdb_attribute_flags(ldb, attr_name);
+
+	if (flags & LTDB_FLAG_OBJECTCLASS) {
+		return ldb_val_equal_objectclass(ldb, v1, v2);
+	}
+
+	if (flags & LTDB_FLAG_INTEGER) {
+		return ldb_val_equal_integer(v1, v2);
+	}
+
+	if (flags & LTDB_FLAG_WILDCARD) {
+		return ldb_val_equal_wildcard(v1, v2, flags);
+	}
+
+	if (flags & LTDB_FLAG_CASE_INSENSITIVE) {
+		return ldb_val_equal_case_insensitive(v1, v2);
+	}
+
 	if (v1->length != v2->length) return 0;
 
 	if (v1->length == 0) return 1;
@@ -66,7 +214,7 @@ static int scope_match(const char *dn, const char *base, enum ldb_scope scope)
 	base_len = strlen(base);
 	dn_len = strlen(dn);
 
-	if (strcmp(dn, base) == 0) {
+	if (ldb_dn_cmp(dn, base) == 0) {
 		return 1;
 	}
 
@@ -79,7 +227,7 @@ static int scope_match(const char *dn, const char *base, enum ldb_scope scope)
 		break;
 
 	case LDB_SCOPE_ONELEVEL:
-		if (strcmp(dn + (dn_len - base_len), base) == 0 &&
+		if (ldb_dn_cmp(dn + (dn_len - base_len), base) == 0 &&
 		    dn[dn_len - base_len - 1] == ',' &&
 		    strchr(dn, ',') == &dn[dn_len - base_len - 1]) {
 			return 1;
@@ -88,7 +236,7 @@ static int scope_match(const char *dn, const char *base, enum ldb_scope scope)
 		
 	case LDB_SCOPE_SUBTREE:
 	default:
-		if (strcmp(dn + (dn_len - base_len), base) == 0 &&
+		if (ldb_dn_cmp(dn + (dn_len - base_len), base) == 0 &&
 		    dn[dn_len - base_len - 1] == ',') {
 			return 1;
 		}
@@ -114,20 +262,21 @@ static int match_leaf(struct ldb_context *ldb,
 		return 0;
 	}
 
-	if (strcmp(tree->u.simple.attr, "dn") == 0) {
+	if (ldb_attr_cmp(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;
+		return ldb_dn_cmp(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) {
+		if (ldb_attr_cmp(msg->elements[i].name, tree->u.simple.attr) == 0) {
 			if (strcmp(tree->u.simple.value.data, "*") == 0) {
 				return 1;
 			}
 			for (j=0;j<msg->elements[i].num_values;j++) {
-				if (ldb_val_equal(&msg->elements[i].values[j], 
+				if (ldb_val_equal(ldb, msg->elements[i].name,
+						  &msg->elements[i].values[j], 
 						  &tree->u.simple.value)) {
 					return 1;
 				}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_pack.c b/source4/lib/ldb/ldb_tdb/ldb_pack.c
index 1196e561a2..3ded595259 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_pack.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_pack.c
@@ -36,7 +36,10 @@
 #include "ldb/ldb_tdb/ldb_tdb.h"
 
 /* change this if the data format ever changes */
-#define LTDB_PACKING_FORMAT 0x26011966
+#define LTDB_PACKING_FORMAT 0x26011967
+
+/* old packing formats */
+#define LTDB_PACKING_FORMAT_NODN 0x26011966
 
 /*
   pack a ldb message into a linear buffer in a TDB_DATA
@@ -53,10 +56,13 @@ int ltdb_pack_data(struct ldb_context *ctx,
 	int i, j;
 	size_t size;
 	char *p;
+	size_t len;
 
 	/* work out how big it needs to be */
 	size = 8;
 
+	size += 1 + strlen(message->dn);
+
 	for (i=0;i<message->num_elements;i++) {
 		if (message->elements[i].num_values == 0) {
 			continue;
@@ -79,9 +85,14 @@ int ltdb_pack_data(struct ldb_context *ctx,
 	SIVAL(p, 0, LTDB_PACKING_FORMAT); 
 	SIVAL(p, 4, message->num_elements); 
 	p += 8;
+
+	/* the dn needs to be packed so we can be case preserving
+	   while hashing on a case folded dn */
+	len = strlen(message->dn);
+	memcpy(p, message->dn, len+1);
+	p += len + 1;
 	
 	for (i=0;i<message->num_elements;i++) {
-		size_t len;
 		if (message->elements[i].num_values == 0) {
 			continue;
 		}
@@ -133,33 +144,49 @@ int ltdb_unpack_data(struct ldb_context *ctx,
 	char *p;
 	unsigned int remaining;
 	int i, j;
+	unsigned format;
+	size_t len;
 
 	message->elements = NULL;
 
 	p = data->dptr;
-	if (data->dsize < 4) {
+	if (data->dsize < 8) {
 		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 */
+	format = IVAL(p, 0);
+	message->num_elements = IVAL(p, 4);
+	p += 8;
+
+	remaining = data->dsize - 8;
+
+	switch (format) {
+	case LTDB_PACKING_FORMAT_NODN:
+		message->dn = NULL;
+		break;
+
+	case LTDB_PACKING_FORMAT:
+		len = strnlen(p, remaining);
+		if (len == remaining) {
+			errno = EIO;
+			goto failed;
+		}
+		message->dn = p;
+		remaining -= len + 1;
+		p += len + 1;
+		break;
+
+	default:
 		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;
@@ -174,12 +201,15 @@ int ltdb_unpack_data(struct ldb_context *ctx,
 	}
 
 	for (i=0;i<message->num_elements;i++) {
-		size_t len;
 		if (remaining < 10) {
 			errno = EIO;
 			goto failed;
 		}
 		len = strnlen(p, remaining-6);
+		if (len == remaining-6) {
+			errno = EIO;
+			goto failed;
+		}
 		message->elements[i].flags = 0;
 		message->elements[i].name = p;
 		remaining -= len + 1;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
index fe84091303..7059030212 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_search.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -148,7 +148,7 @@ static int msg_add_all_elements(struct ldb_message *ret,
  */
 static struct ldb_message *ltdb_pull_attrs(struct ldb_context *ldb, 
 					   const struct ldb_message *msg, 
-					   const char **attrs)
+					   char * const *attrs)
 {
 	struct ldb_message *ret;
 	int i;
@@ -205,11 +205,20 @@ static struct ldb_message *ltdb_pull_attrs(struct ldb_context *ldb,
 /*
   see if a ldb_val is a wildcard
 */
-int ltdb_has_wildcard(const struct ldb_val *val)
+int ltdb_has_wildcard(struct ldb_context *ldb, const char *attr_name, 
+		      const struct ldb_val *val)
 {
-	if (val->length == 1 && ((char *)val->data)[0] == '*') {
+	int flags;
+
+	if (strpbrk(val->data, "*?") == NULL) {
+		return 0;
+	}
+
+	flags = ltdb_attribute_flags(ldb, attr_name);
+	if (flags & LTDB_FLAG_WILDCARD) {
 		return 1;
 	}
+
 	return 0;
 }
 
@@ -220,12 +229,12 @@ int ltdb_has_wildcard(const struct ldb_val *val)
 void ltdb_search_dn1_free(struct ldb_context *ldb, struct ldb_message *msg)
 {
 	int i;
-	if (msg->dn) free(msg->dn);
 	if (msg->private_data) free(msg->private_data);
 	for (i=0;i<msg->num_elements;i++) {
 		if (msg->elements[i].values) free(msg->elements[i].values);
 	}
 	if (msg->elements) free(msg->elements);
+	memset(msg, 0, sizeof(*msg));
 }
 
 
@@ -242,7 +251,7 @@ int ltdb_search_dn1(struct ldb_context *ldb, const char *dn, struct ldb_message
 	TDB_DATA tdb_key, tdb_data;
 
 	/* form the key */
-	tdb_key = ltdb_key(dn);
+	tdb_key = ltdb_key(ldb, dn);
 	if (!tdb_key.dptr) {
 		return -1;
 	}
@@ -253,11 +262,6 @@ int ltdb_search_dn1(struct ldb_context *ldb, const char *dn, struct ldb_message
 		return 0;
 	}
 
-	msg->dn = strdup(dn);
-	if (!msg->dn) {
-		free(tdb_data.dptr);
-		return -1;
-	}
 	msg->private_data = tdb_data.dptr;
 	msg->num_elements = 0;
 	msg->elements = NULL;
@@ -268,6 +272,14 @@ int ltdb_search_dn1(struct ldb_context *ldb, const char *dn, struct ldb_message
 		return -1;		
 	}
 
+	if (!msg->dn) {
+		msg->dn = strdup(dn);
+	}
+	if (!msg->dn) {
+		free(tdb_data.dptr);
+		return -1;
+	}
+
 	return 1;
 }
 
@@ -276,7 +288,7 @@ int ltdb_search_dn1(struct ldb_context *ldb, const char *dn, struct ldb_message
   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)
+		   char * const attrs[], struct ldb_message ***res)
 {
 	int ret;
 	struct ldb_message msg, *msg2;
@@ -312,7 +324,7 @@ int ltdb_search_dn(struct ldb_context *ldb, char *dn,
   return 0 on success, -1 on failure
 */
 int ltdb_add_attr_results(struct ldb_context *ldb, struct ldb_message *msg,
-			  const char *attrs[], 
+			  char * const attrs[], 
 			  unsigned int *count, 
 			  struct ldb_message ***res)
 {
@@ -350,7 +362,7 @@ struct ltdb_search_info {
 	struct ldb_parse_tree *tree;
 	const char *base;
 	enum ldb_scope scope;
-	const char **attrs;
+	char * const *attrs;
 	struct ldb_message **msgs;
 	int failures;
 	int count;
@@ -371,8 +383,6 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
 		return 0;
 	}
 
-	msg.dn = key.dptr + 3;
-
 	/* unpack the record */
 	ret = ltdb_unpack_data(sinfo->ldb, &data, &msg);
 	if (ret == -1) {
@@ -380,6 +390,10 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
 		return 0;
 	}
 
+	if (!msg.dn) {
+		msg.dn = key.dptr + 3;
+	}
+
 	/* see if it matches the given expression */
 	if (!ldb_message_match(sinfo->ldb, &msg, sinfo->tree, 
 			       sinfo->base, sinfo->scope)) {
@@ -425,7 +439,7 @@ 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)
+			    char * const attrs[], struct ldb_message ***res)
 {
 	struct ltdb_private *ltdb = ldb->private_data;
 	int ret;
@@ -458,11 +472,15 @@ static int ltdb_search_full(struct ldb_context *ldb,
 */
 int ltdb_search(struct ldb_context *ldb, const char *base,
 		enum ldb_scope scope, const char *expression,
-		const char *attrs[], struct ldb_message ***res)
+		char * const attrs[], struct ldb_message ***res)
 {
 	struct ldb_parse_tree *tree;
 	int ret;
 
+	if (ltdb_cache_load(ldb) != 0) {
+		return -1;
+	}
+
 	*res = NULL;
 
 	/* form a parse tree for the expression */
@@ -472,8 +490,8 @@ int ltdb_search(struct ldb_context *ldb, const char *base,
 	}
 
 	if (tree->operation == LDB_OP_SIMPLE && 
-	    strcmp(tree->u.simple.attr, "dn") == 0 &&
-	    !ltdb_has_wildcard(&tree->u.simple.value)) {
+	    ldb_attr_cmp(tree->u.simple.attr, "dn") == 0 &&
+	    !ltdb_has_wildcard(ldb, tree->u.simple.attr, &tree->u.simple.value)) {
 		/* yay! its a nice simple one */
 		ret = ltdb_search_dn(ldb, tree->u.simple.value.data, attrs, res);
 	} else {
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
index ff0c0a53b7..eb2decfe31 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -38,24 +38,70 @@
 /*
   form a TDB_DATA for a record key
   caller frees
+
+  note that the key for a record can depend on whether the 
+  dn refers to a case sensitive index record or not
 */
-struct TDB_DATA ltdb_key(const char *dn)
+struct TDB_DATA ltdb_key(struct ldb_context *ldb, const char *dn)
 {
 	TDB_DATA key;
 	char *key_str = NULL;
+	char *dn_folded = NULL;
+	const char *prefix = LTDB_INDEX ":";
+	const char *s;
+	int flags;
+
+	/*
+	  most DNs are case insensitive. The exception is index DNs for
+	  case sensitive attributes
+	*/
+	if (strncmp(dn, prefix, strlen(prefix)) == 0 &&
+	    (s = strchr(dn+strlen(prefix), ':'))) {
+		char *attr_name, *attr_name_folded;
+		attr_name = strndup(dn+strlen(prefix), (s-(dn+strlen(prefix))));
+		if (!attr_name) {
+			goto failed;
+		}
+		flags = ltdb_attribute_flags(ldb, attr_name);
+		
+		if (flags & LTDB_FLAG_CASE_INSENSITIVE) {
+			dn_folded = ldb_casefold(dn);
+		} else {
+			attr_name_folded = ldb_casefold(attr_name);
+			if (!attr_name_folded) {
+				goto failed;
+			}
+			asprintf(&dn_folded, "%s:%s:%s",
+				 prefix, attr_name_folded,
+				 s+1);
+			free(attr_name_folded);
+		}
+		free(attr_name);
+	} else {
+		dn_folded = ldb_casefold(dn);
+	}
+
+	if (!dn_folded) {
+		goto failed;
+	}
+
+	asprintf(&key_str, "DN=%s", dn_folded);
+	free(dn_folded);
 
-	asprintf(&key_str, "DN=%s", dn);
 	if (!key_str) {
-		errno = ENOMEM;
-		key.dptr = NULL;
-		key.dsize = 0;
-		return key;
+		goto failed;
 	}
 
 	key.dptr = key_str;
 	key.dsize = strlen(key_str)+1;
 
 	return key;
+
+failed:
+	errno = ENOMEM;
+	key.dptr = NULL;
+	key.dsize = 0;
+	return key;
 }
 
 /*
@@ -67,7 +113,7 @@ static int ltdb_lock(struct ldb_context *ldb)
 	TDB_DATA key;
 	int ret;
 
-	key = ltdb_key("LDBLOCK");
+	key = ltdb_key(ldb, "LDBLOCK");
 	if (!key.dptr) {
 		return -1;
 	}
@@ -87,7 +133,7 @@ static void ltdb_unlock(struct ldb_context *ldb)
 	struct ltdb_private *ltdb = ldb->private_data;
 	TDB_DATA key;
 
-	key = ltdb_key("LDBLOCK");
+	key = ltdb_key(ldb, "LDBLOCK");
 	if (!key.dptr) {
 		return;
 	}
@@ -97,6 +143,28 @@ static void ltdb_unlock(struct ldb_context *ldb)
 	free(key.dptr);
 }
 
+
+/*
+  we've made a modification to a dn - possibly reindex and 
+  update sequence number
+*/
+static int ltdb_modified(struct ldb_context *ldb, const char *dn)
+{
+	int ret = 0;
+
+	if (strcmp(dn, LTDB_INDEXLIST) == 0 ||
+	    strcmp(dn, LTDB_ATTRIBUTES) == 0) {
+		ret = ltdb_reindex(ldb);
+	}
+
+	if (ret == 0 &&
+	    strcmp(dn, LTDB_BASEINFO) != 0) {
+		ret = ltdb_increase_sequence_number(ldb);
+	}
+
+	return ret;
+}
+
 /*
   store a record into the db
 */
@@ -106,7 +174,7 @@ int ltdb_store(struct ldb_context *ldb, const struct ldb_message *msg, int flgs)
 	TDB_DATA tdb_key, tdb_data;
 	int ret;
 
-	tdb_key = ltdb_key(msg->dn);
+	tdb_key = ltdb_key(ldb, msg->dn);
 	if (!tdb_key.dptr) {
 		return -1;
 	}
@@ -145,15 +213,19 @@ static int ltdb_add(struct ldb_context *ldb, const struct ldb_message *msg)
 	if (ltdb_lock(ldb) != 0) {
 		return -1;
 	}
+
+	if (ltdb_cache_load(ldb) != 0) {
+		ltdb_unlock(ldb);
+		return -1;
+	}
 	
 	ret = ltdb_store(ldb, msg, TDB_INSERT);
 
-	if (strcmp(msg->dn, "@INDEXLIST") == 0) {
-		ltdb_reindex(ldb);
+	if (ret == 0) {
+		ltdb_modified(ldb, msg->dn);
 	}
 
 	ltdb_unlock(ldb);
-
 	return ret;
 }
 
@@ -168,7 +240,7 @@ int ltdb_delete_noindex(struct ldb_context *ldb, const char *dn)
 	TDB_DATA tdb_key;
 	int ret;
 
-	tdb_key = ltdb_key(dn);
+	tdb_key = ltdb_key(ldb, dn);
 	if (!tdb_key.dptr) {
 		return -1;
 	}
@@ -191,6 +263,11 @@ static int ltdb_delete(struct ldb_context *ldb, const char *dn)
 		return -1;
 	}
 
+	if (ltdb_cache_load(ldb) != 0) {
+		ltdb_unlock(ldb);
+		return -1;
+	}
+
 	/* in case any attribute of the message was indexed, we need
 	   to fetch the old record */
 	ret = ltdb_search_dn1(ldb, dn, &msg);
@@ -210,8 +287,8 @@ static int ltdb_delete(struct ldb_context *ldb, const char *dn)
 
 	ltdb_search_dn1_free(ldb, &msg);
 
-	if (strcmp(dn, "@INDEXLIST") == 0) {
-		ltdb_reindex(ldb);
+	if (ret == 0) {
+		ltdb_modified(ldb, dn);
 	}
 
 	ltdb_unlock(ldb);
@@ -234,7 +311,7 @@ static int find_element(const struct ldb_message *msg, const char *name)
 {
 	int i;
 	for (i=0;i<msg->num_elements;i++) {
-		if (strcmp(msg->elements[i].name, name) == 0) {
+		if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
 			return i;
 		}
 	}
@@ -301,7 +378,7 @@ static int msg_delete_attribute(struct ldb_message *msg, const char *name)
 	}
 
 	for (i=0;i<msg->num_elements;i++) {
-		if (strcmp(msg->elements[i].name, name) != 0) {
+		if (ldb_attr_cmp(msg->elements[i].name, name) != 0) {
 			el2[count++] = msg->elements[i];
 		} else {
 			if (msg->elements[i].values) free(msg->elements[i].values);
@@ -320,7 +397,8 @@ static int msg_delete_attribute(struct ldb_message *msg, const char *name)
 
   return 0 on success, -1 on failure
 */
-static int msg_delete_element(struct ldb_message *msg, 
+static int msg_delete_element(struct ldb_context *ldb,
+			      struct ldb_message *msg, 
 			      const char *name,
 			      const struct ldb_val *val)
 {
@@ -335,7 +413,7 @@ static int msg_delete_element(struct ldb_message *msg,
 	el = &msg->elements[i];
 
 	for (i=0;i<el->num_values;i++) {
-		if (ldb_val_equal(&el->values[i], val)) {
+		if (ldb_val_equal(ldb, msg->elements[i].name, &el->values[i], val)) {
 			if (i<el->num_values-1) {
 				memmove(&el->values[i], &el->values[i+1],
 					sizeof(el->values[i])*el->num_values-(i+1));
@@ -348,43 +426,42 @@ static int msg_delete_element(struct ldb_message *msg,
 	return -1;
 }
 
+
 /*
-  modify a record
+  modify a record - internal interface
 
   yuck - this is O(n^2). Luckily n is usually small so we probably
   get away with it, but if we ever have really large attribute lists 
   then we'll need to look at this again
 */
-static int ltdb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
+int ltdb_modify_internal(struct ldb_context *ldb, const struct ldb_message *msg)
 {
 	struct ltdb_private *ltdb = ldb->private_data;
 	TDB_DATA tdb_key, tdb_data;
 	struct ldb_message msg2;
 	int ret, i, j;
 
-	if (ltdb_lock(ldb) != 0) {
-		return -1;
-	}
-
-	tdb_key = ltdb_key(msg->dn);
+	tdb_key = ltdb_key(ldb, msg->dn);
 	if (!tdb_key.dptr) {
-		goto unlock_fail;
+		return -1;
 	}
 
 	tdb_data = tdb_fetch(ltdb->tdb, tdb_key);
 	if (!tdb_data.dptr) {
 		free(tdb_key.dptr);
-		goto unlock_fail;
+		return -1;
 	}
 
 	ret = ltdb_unpack_data(ldb, &tdb_data, &msg2);
 	if (ret == -1) {
 		free(tdb_key.dptr);
 		free(tdb_data.dptr);
-		goto unlock_fail;
+		return -1;
 	}
 
-	msg2.dn = msg->dn;
+	if (!msg2.dn) {
+		msg2.dn = msg->dn;
+	}
 
 	for (i=0;i<msg->num_elements;i++) {
 		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
@@ -425,9 +502,10 @@ static int ltdb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
 				break;
 			}
 			for (j=0;j<msg->elements[i].num_values;j++) {
-				if (msg_delete_element(&msg2, 
-							msg->elements[i].name,
-							&msg->elements[i].values[j]) != 0) {
+				if (msg_delete_element(ldb,
+						       &msg2, 
+						       msg->elements[i].name,
+						       &msg->elements[i].values[j]) != 0) {
 					goto failed;
 				}
 			}
@@ -438,26 +516,43 @@ static int ltdb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
 	/* we've made all the mods - save the modified record back into the database */
 	ret = ltdb_store(ldb, &msg2, TDB_MODIFY);
 
-	if (strcmp(msg2.dn, "@INDEXLIST") == 0) {
-		ltdb_reindex(ldb);
-	}
-
 	free(tdb_key.dptr);
 	free(tdb_data.dptr);
 	ltdb_unpack_data_free(&msg2);
-	ltdb_unlock(ldb);
-
 	return ret;
 
 failed:
 	free(tdb_key.dptr);
 	free(tdb_data.dptr);
 	ltdb_unpack_data_free(&msg2);
+	return -1;
+}
+
+/*
+  modify a record
+*/
+static int ltdb_modify(struct ldb_context *ldb, const struct ldb_message *msg)
+{
+	int ret;
+
+	if (ltdb_lock(ldb) != 0) {
+		return -1;
+	}
+
+	if (ltdb_cache_load(ldb) != 0) {
+		ltdb_unlock(ldb);
+		return -1;
+	}
+
+	ret = ltdb_modify_internal(ldb, msg);
+
+	if (ret == 0) {
+		ltdb_modified(ldb, msg->dn);
+	}
 
-unlock_fail:
 	ltdb_unlock(ldb);
-	
-	return -1;
+
+	return ret;
 }
 
 /*
@@ -467,6 +562,9 @@ static int ltdb_close(struct ldb_context *ldb)
 {
 	struct ltdb_private *ltdb = ldb->private_data;
 	int ret;
+
+	ltdb_cache_free(ldb);
+
 	ret = tdb_close(ltdb->tdb);
 	free(ltdb);
 	free(ldb);
@@ -538,7 +636,9 @@ struct ldb_context *ltdb_connect(const char *url,
 	}
 
 	ltdb->tdb = tdb;
-	
+	ltdb->sequence_number = 0;
+
+	memset(&ltdb->cache, 0, sizeof(ltdb->cache));
 
 	ldb = malloc_p(struct ldb_context);
 	if (!ldb) {
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.h b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
index efb0af1c9c..e87027db63 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.h
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -3,8 +3,44 @@
 struct ltdb_private {
 	TDB_CONTEXT *tdb;
 	unsigned int connect_flags;
+	
+	/* a double is used for portability and ease of string
+	   handling. It has plenty of digits of precision */
+	double sequence_number;
+
+	struct {
+		struct ldb_message baseinfo;
+		struct ldb_message indexlist;
+		struct ldb_message attributes;
+		struct ldb_message subclasses;
+
+		struct {
+			char *name;
+			int flags;
+		} last_attribute;
+	} cache;
 };
 
+/* special record types */
+#define LTDB_INDEX      "@INDEX"
+#define LTDB_INDEXLIST  "@INDEXLIST"
+#define LTDB_IDX        "@IDX"
+#define LTDB_IDXATTR    "@IDXATTR"
+#define LTDB_BASEINFO   "@BASEINFO"
+#define LTDB_ATTRIBUTES "@ATTRIBUTES"
+#define LTDB_SUBCLASSES "@SUBCLASSES"
+
+/* special attribute types */
+#define LTDB_SEQUENCE_NUMBER "sequenceNumber"
+#define LTDB_OBJECTCLASS "objectClass"
+
+/* well known attribute flags */
+#define LTDB_FLAG_CASE_INSENSITIVE (1<<0)
+#define LTDB_FLAG_INTEGER          (1<<1)
+#define LTDB_FLAG_WILDCARD         (1<<2)
+#define LTDB_FLAG_OBJECTCLASS      (1<<3)
+
+
 #ifndef IVAL
 #define IVAL(p, ofs) (((unsigned *)((char *)(p) + (ofs)))[0])
 #endif
diff --git a/source4/lib/ldb/tests/test-attribs.ldif b/source4/lib/ldb/tests/test-attribs.ldif
new file mode 100644
index 0000000000..bfa51b05fa
--- /dev/null
+++ b/source4/lib/ldb/tests/test-attribs.ldif
@@ -0,0 +1,13 @@
+dn: @ATTRIBUTES
+uid: CASE_INSENSITIVE WILDCARD
+dn: CASE_INSENSITIVE
+
+dn: @SUBCLASSES
+top: domain
+top: person
+domain: domainDNS
+person: organizationalPerson
+person: fooPerson
+organizationalPerson: user
+organizationalPerson: OpenLDAPperson
+user: computer
diff --git a/source4/lib/ldb/tests/test-generic.sh b/source4/lib/ldb/tests/test-generic.sh
index 41f5707e9c..79db49bb48 100755
--- a/source4/lib/ldb/tests/test-generic.sh
+++ b/source4/lib/ldb/tests/test-generic.sh
@@ -1,8 +1,8 @@
 echo "Adding base elements"
-bin/ldbadd < tests/test.ldif
+bin/ldbadd tests/test.ldif
 
 echo "Modifying elements"
-bin/ldbmodify < tests/test-modify.ldif
+bin/ldbmodify tests/test-modify.ldif
 
 echo "Showing modified record"
 bin/ldbsearch '(uid=uham)'
diff --git a/source4/lib/ldb/tools/ldbedit.c b/source4/lib/ldb/tools/ldbedit.c
index 07ed66d68a..eb95ed3267 100644
--- a/source4/lib/ldb/tools/ldbedit.c
+++ b/source4/lib/ldb/tools/ldbedit.c
@@ -102,7 +102,7 @@ static struct ldb_message *msg_find(struct ldb_message **msgs, int count,
 {
 	int i;
 	for (i=0;i<count;i++) {
-		if (strcmp(dn, msgs[i]->dn) == 0) {
+		if (ldb_dn_cmp(dn, msgs[i]->dn) == 0) {
 			return msgs[i];
 		}
 	}