r7276: - moved static tdb function ltdb_dn_fold() into common/ so that it can be

  called from multiple backends.  (ldb_sqlite3 needs it too.)  Added parameter
  for a callback function that determines whether an attribute needs case
  folding.
- begin to prepare for sqlite3 in build process
- work-in-progress updates, on ldb_sqlite3
(This used to be commit a80bced0b96ffb655559a43cf7f4d7a34deb5a7d)

13 files changed, 465 insertions, 644 deletions

diff --git a/source4/include/smb_macros.h b/source4/include/smb_macros.h
index 276076955f..23b1fd1a4e 100644
--- a/source4/include/smb_macros.h
+++ b/source4/include/smb_macros.h
@@ -72,7 +72,7 @@
  * @note You are explicitly allowed to pass NULL pointers -- they will
  * always be ignored.
  **/
-#define SAFE_FREE(x) do { if ((x) != NULL) {free(x); (x)=NULL;} } while(0)
+#define SAFE_FREE(x) do { if ((x) != NULL) {free(discard_const_p(void *, (x))); (x)=NULL;} } while(0)
 #endif
 
 
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
index 600c7063f0..649b0a0f24 100644
--- a/source4/lib/ldb/common/ldb.c
+++ b/source4/lib/ldb/common/ldb.c
@@ -62,6 +62,12 @@ struct ldb_context *ldb_connect(const char *url, unsigned int flags,
 	}
 #endif
 
+#if HAVE_SQLITE3
+	if (strncmp(url, "sqlite:", 7) == 0) {
+		ldb_ctx = lsqlite3_connect(url, flags, options);
+	}
+#endif
+
 
 	if (!ldb_ctx) {
 		errno = EINVAL;
diff --git a/source4/lib/ldb/common/ldb_utf8.c b/source4/lib/ldb/common/ldb_utf8.c
index 577766d9f7..9cbb5646dd 100644
--- a/source4/lib/ldb/common/ldb_utf8.c
+++ b/source4/lib/ldb/common/ldb_utf8.c
@@ -88,3 +88,80 @@ int ldb_attr_cmp(const char *dn1, const char *dn2)
 {
 	return ldb_caseless_cmp(dn1, dn2);
 }
+
+
+/*
+  casefold a dn. We need to uppercase the attribute names, and the 
+  attribute values of case insensitive attributes. We also need to remove
+  extraneous spaces between elements
+*/
+char *ldb_dn_fold(struct ldb_module *module, const char *dn, int (*case_fold_attr_fn)(struct ldb_module * module, char * attr))
+{
+	const char *dn_orig = dn;
+	struct ldb_context *ldb = module->ldb;
+	TALLOC_CTX *tmp_ctx = talloc_new(ldb);
+	char *ret;
+	size_t len;
+
+	ret = talloc_strdup(tmp_ctx, "");
+	if (ret == NULL) goto failed;
+
+	while ((len = strcspn(dn, ",")) > 0) {
+		char *p = strchr(dn, '=');
+		char *attr, *value;
+		int case_fold_required;
+
+		if (p == NULL || (p-dn) > len) goto failed;
+
+		attr = talloc_strndup(tmp_ctx, dn, p-dn);
+		if (attr == NULL) goto failed;
+
+		/* trim spaces from the attribute name */
+		while (' ' == *attr) attr++;
+		while (' ' == attr[strlen(attr)-1]) {
+			attr[strlen(attr)-1] = 0;
+		}
+		if (*attr == 0) goto failed;
+
+		value = talloc_strndup(tmp_ctx, p+1, len-(p+1-dn));
+		if (value == NULL) goto failed;
+
+		/* trim spaces from the value */
+		while (' ' == *value) value++;
+		while (' ' == value[strlen(value)-1]) {
+			value[strlen(value)-1] = 0;
+		}
+		if (*value == 0) goto failed;
+
+		case_fold_required = (* case_fold_attr_fn)(module, attr);
+
+		attr = ldb_casefold(ldb, attr);
+		if (attr == NULL) goto failed;
+		talloc_steal(tmp_ctx, attr);
+
+		if (case_fold_required) {
+			value = ldb_casefold(ldb, value);
+			if (value == NULL) goto failed;
+			talloc_steal(tmp_ctx, value);
+		}		
+
+		if (dn[len] == ',') {
+			ret = talloc_asprintf_append(ret, "%s=%s,", attr, value);
+		} else {
+			ret = talloc_asprintf_append(ret, "%s=%s", attr, value);
+		}
+		if (ret == NULL) goto failed;
+
+		dn += len;
+		if (*dn == ',') dn++;
+	}
+
+	talloc_steal(ldb, ret);
+	talloc_free(tmp_ctx);
+	return ret;
+
+failed:
+	talloc_free(tmp_ctx);
+	return ldb_casefold(ldb, dn_orig);
+}
+
diff --git a/source4/lib/ldb/config.m4 b/source4/lib/ldb/config.m4
index 1a65eebd01..dfa72e4cd3 100644
--- a/source4/lib/ldb/config.m4
+++ b/source4/lib/ldb/config.m4
@@ -3,6 +3,11 @@ if test x"$with_ldap_support" = x"yes"; then
     SMB_MODULE_DEFAULT(libldb_ldap,STATIC)
 fi
 
+SMB_MODULE_DEFAULT(libldb_sqlite3,NOT)
+if test x"$with_sqlite3_support" = x"yes"; then
+    SMB_MODULE_DEFAULT(libldb_sqlite3,STATIC)
+fi
+
 SMB_LIBRARY_ENABLE(libldb,NO)
 if test x"$experimental" = x"yes"; then
 	SMB_LIBRARY_ENABLE(libldb,YES)
diff --git a/source4/lib/ldb/config.mk b/source4/lib/ldb/config.mk
index 87ec89e5d3..e5757a92f4 100644
--- a/source4/lib/ldb/config.mk
+++ b/source4/lib/ldb/config.mk
@@ -29,6 +29,18 @@ NOPROTO = YES
 ################################################
 
 ################################################
+# Start MODULE libldb_sqlite3
+[MODULE::libldb_sqlite3]
+SUBSYSTEM = LIBLDB
+INIT_OBJ_FILES = \
+		lib/ldb/ldb_sqlite3/ldb_sqlite3.o
+REQUIRED_SUBSYSTEMS = \
+		EXT_LIB_SQLITE3
+NOPROTO = YES
+# End MODULE libldb_tdb
+################################################
+
+################################################
 # Start MODULE libldb_tdb
 [MODULE::libldb_tdb]
 SUBSYSTEM = LIBLDB
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index 18d974cf42..8ccf8967cb 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -225,6 +225,9 @@ int ldb_ldif_write_file(struct ldb_context *ldb, FILE *f, const struct ldb_ldif
 int ldb_dn_cmp(const char *dn1, const char *dn2);
 int ldb_attr_cmp(const char *dn1, const char *dn2);
 
+/* case-fold a DN */
+char *ldb_dn_fold(struct ldb_module *module, const char *dn, int (*case_fold_attr_fn)(struct ldb_module * module, char * attr));
+
 /* create an empty message */
 struct ldb_message *ldb_msg_new(void *mem_ctx);
 
diff --git a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
index d36ced2667..0bce078a85 100644
--- a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
+++ b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
@@ -37,15 +37,16 @@
 #include "ldb/include/ldb_private.h"
 #include "ldb/ldb_sqlite3/ldb_sqlite3.h"
 
-#undef SQL_EXEC                 /* just in case; not expected to be defined */
-#define SQL_EXEC(lsqlite3, query, reset)                        \
-        do {                                                    \
-                lsqlite3->last_rc =                             \
-                        sqlite3_step(lsqlite3->queries.query);  \
-                if (lsqlite3->last_rc == SQLITE_BUSY || reset)  \
-                        (void) sqlite3_reset(lsqlite3->queries.query);  \
-        } while lsqlite3->last_rc == SQLITE_BUSY;
-
+#define QUERY(lsqlite3, pppValues, pNumRows, bRollbackOnError, sql...)  \
+    do                                                                  \
+    {                                                                   \
+            if (query(lsqlite3, pppValues, pNumRows, sql) != 0) {       \
+                if (bRollbackOnError) {                                 \
+                        query(lsqlite3, NULL, NULL, "ROLLBACK;");       \
+                }                                                       \
+                return -1;                                              \
+        }                                                               \
+    } while (0)
 
 
 #if 0
@@ -93,28 +94,8 @@ lsqlite3_rename(struct ldb_module *module,
 		return 0;
 	}
 
-        /* Bind old distinguished names */
-        column = sqlite3_bind_parameter_index(lsqlite3->queries.renameDN,
-                                              ":oldDN");
-        if (sqlite3_bind_text(lsqlite3->queries.renameDN, column,
-                              olddn, strlen(olddn),
-                              SQLITE_STATIC) != SQLITE_OK) {
-                return -1;
-        }
-
-        /* Bind new distinguished names */
-        column = sqlite3_bind_parameter_index(lsqlite3->queries.renameDN,
-                                              ":newDN");
-        if (sqlite3_bind_text(lsqlite3->queries.renameDN, column,
-                              newdn, strlen(newdn),
-                              SQLITE_STATIC) != SQLITE_OK) {
-                return -1;
-        }
-
-        /* Execute the query.  This sets lsqlite3->last_rc */
-        SQL_EXEC(lsqlite3, renameDN, TRUE);
-
-	return lsqlite3->last_rc == 0 ? 0 : -1;
+#warning "rename() is not yet supported"
+        return -1;
 }
 
 /*
@@ -133,19 +114,7 @@ lsqlite3_delete(struct ldb_module *module,
 		return 0;
 	}
 	
-        /* Bind distinguished names */
-        column = sqlite3_bind_parameter_index(lsqlite3->queries.deleteDN,
-                                              ":dn");
-        if (sqlite3_bind_text(lsqlite3->queries.deleteDN, column,
-                              dn, strlen(dn),
-                              SQLITE_STATIC) != SQLITE_OK) {
-                return -1;
-        }
-
-        /* Execute the query.  This sets lsqlite3->last_rc */
-        SQL_EXEC(lsqlite3, deleteDN, TRUE);
-
-	return lsqlite3->last_rc == 0 ? 0 : -1;
+        return -1;
 }
 
 /*
@@ -332,9 +301,9 @@ failed:
  * requests in the ldb_message
  */
 static int
-lsqlite3_msg_to_sql(struct ldb_context *ldb,
+lsqlite3_msg_to_sql(struct ldb_module *module,
                     const struct ldb_message *msg,
-                    long long dn_id,
+                    long long eid,
                     int use_flags)
 {
         int                         flags;
@@ -353,88 +322,75 @@ lsqlite3_msg_to_sql(struct ldb_context *ldb,
                         flags = el->flags & LDB_FLAG_MOD_MASK;
                 }
 
-                /* Determine which query to use */
-                switch (flags) {
-                case LDB_FLAG_MOD_ADD:
-                        stmt = lsqlite3->queries.addAttrValuePair;
-                        break;
-                        
-                case LDB_FLAG_MOD_DELETE:
-                        stmt = lsqlite3->queries.deleteAttrValuePairs;
-                        break;
-
-                case LDB_FLAG_MOD_REPLACE:
-                        stmt = lsqlite3->queries.replaceAttrValuePairs;
-                        break;
-                }
-
-                /*
-                 * All queries use dn id and attribute name.  Bind them now.
-                 */
-
-                /* Bind distinguished name id */
-                column =
-                        sqlite3_bind_parameter_index(
-                                stmt,
-                                ":dn_id");
-                if (sqlite3_bind_int64(stmt,
-                                      column,
-                                      dn_id) != SQLITE_OK) {
-
-                        return -1;
-                }
-
-                /* Bind attribute name */
-                column =
-                        sqlite3_bind_parameter_index(
-                                stmt,
-                                ":attr_name");
-                if (sqlite3_bind_text(lsqlite3->queries.deleteDN, column,
-                                      el->name, strlen(el->name),
-                                      SQLITE_STATIC) != SQLITE_OK) {
-
-                        return -1;
+                if (flags == LDB_FLAG_MOD_ADD) {
+                        /* Create the attribute table if it doesn't exist */
+                        if (create_attr_table(module, el->name) != 0) {
+                                return -1;
+                        }
                 }
 
-
                 /* For each value of the specified attribute name... */
 		for (j = 0; j < el->num_values; j++) {
 
                         /* ... bind the attribute value, if necessary */
                         switch (flags) {
                         case LDB_FLAG_MOD_ADD:
-                        case LDB_FLAG_MOD_REPLACE:
-                                /* Bind attribute value */
-                                column =
-                                        sqlite3_bind_parameter_index(
-                                                stmt,
-                                                ":attr_value");
-                                if (sqlite3_bind_text(
-                                            stmt, column,
-                                            el->values[j].data,
-                                            el->values[j].length,
-                                            SQLITE_STATIC) != SQLITE_OK) {
-
-                                        return -1;
-                                }
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "INSERT INTO ldb_attr_%q "
+                                      "    (eid, attr_value) "
+                                      "  VALUES "
+                                      "    (%lld, %Q);",
+                                      eid, el->data);
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "UPDATE ldb_entry "
+                                      "  SET entry_data = "
+                                      "        add_attr(entry_data, %Q, %Q) "
+                                      "  WHERE eid = %lld;",
+                                      el->name, el->data, eid);
+                                      
+                                break;
 
+                        case LDB_FLAG_MOD_REPLACE:
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "UPDATE ldb_attr_%q "
+                                      "  SET attr_value = %Q "
+                                      "  WHERE eid = %lld;",
+                                      el->data, eid);
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "UPDATE ldb_entry "
+                                      "  SET entry_data = "
+                                      "        mod_attr(entry_data, %Q, %Q) "
+                                      "  WHERE eid = %lld;",
+                                      el->name, el->data, eid);
                                 break;
 
                         case LDB_FLAG_MOD_DELETE:
                                 /* No additional parameters to this query */
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "DELETE FROM ldb_attr_%q "
+                                      "  WHERE eid = %lld "
+                                      "    AND attr_value = %Q;",
+                                      eid, el->data);
+                                QUERY(lsqlite3,
+                                      NULL, NULL,
+                                      FALSE,
+                                      "UPDATE ldb_entry "
+                                      "  SET entry_data = "
+                                      "        del_attr(entry_data, %Q, %Q) "
+                                      "  WHERE eid = %lld;",
+                                      el->name, el->data, eid);
                                 break;
                         }
-
-                        /* Execute the query */
-                        do {
-                                lsqlite3->last_rc = sqlite3_step(stmt);
-                                (void) sqlite3_reset(stmt);
-                        } while lsqlite3->last_rc == SQLITE_BUSY;
-
-                        /* Make sure we succeeded */
-                        if (lsqlite3->last_rc != SQLITE_OK) {
-                                return -1;
-                        }
 		}
 	}
 
@@ -442,6 +398,35 @@ lsqlite3_msg_to_sql(struct ldb_context *ldb,
 }
 
 
+static char *
+lsqlite3_normalize_dn(struct ldb_context * ldb,
+                      char * pDN)
+{
+        char *          pSrc;
+        char *          pDest;
+        char *          pNormalized;
+
+	pNormalized = talloc_size(ldb, strlen(pDN) + 1);
+	if (pNormalized == NULL) {
+		errno = ENOMEM;
+                return -1;
+	}
+        
+        for (pSrc = pDN, pDest = pNormalized; *pSrc != '\0'; ) {
+                
+        }
+}
+
+
+static int
+lsqlite3_insert_dn_recursive(struct lsqlite3_private * lsqlite3,
+                             char * pDN,
+                             long long * pEID)
+{
+        
+}
+
+
 /*
  * add a record
  */
@@ -450,6 +435,7 @@ lsqlite3_add(struct ldb_module *module,
              const struct ldb_message *msg)
 {
 	int                         ret;
+        long long                   eid;
 	struct ldb_context *        ldb = module->ldb;
 	struct lsqlite3_private *   lsqlite3 = module->private_data;
 
@@ -459,42 +445,28 @@ lsqlite3_add(struct ldb_module *module,
 	}
 
         /* Begin a transaction */
-        SQL_EXEC(lsqlite3, begin, TRUE);
+        QUERY(lsqlite3, NULL, NULL< FALSE, "BEGIN EXCLUSIVE;");
 
-        /* This is a new DN.  Bind new distinguished name */
-        column = sqlite3_bind_parameter_index(lsqlite3->queries.newDN, ":dn");
-        if (sqlite3_bind_text(lsqlite3->queries.newDN, column,
-                              msg->dn, strlen(msg->dn),
-                              SQLITE_STATIC) != SQLITE_OK) {
-                return -1;
-        }
-        
-        /* Add this new DN.  This sets lsqlite3->last_rc */
-        SQL_EXEC(lsqlite3, newDN, TRUE);
-        
-        if (lsqlite3->last_rc != SQLITE_DONE) {
+        /*
+         * Build any portions of the directory tree that don't exist.  If the
+         * final component already exists, it's an error.
+         */
+        if (lsqlite3_insert_dn_recursive(lsqlite3,
+                                         lsqlite3_normalize_dn(ldb, msg->dn),
+                                         &eid) != 0) {
+                QUERY(lsqlite3, NULL, NULL, FALSE, "ROLLBACK;");
                 return -1;
         }
-        
-        /* Get the id of the just-added DN */
-        dn_id = sqlite3_last_insert_rowid(lsqlite3->sqlite3);
-        
-	ret = lsqlite3_msg_to_sql(ldb, msg, dn_id, FALSE);
 
-        /* Did the attribute additions (if any) succeeded? */
-        if (ret == 0)
-        {
-                /* Yup.  Commit the transaction */
-                SQL_EXEC(lsqlite3, commit, TRUE);
-        }
-        else
-        {
-                /* Attribute addition failed.  Rollback the transaction */
-                SQL_EXEC(lsqlite3, rollback, TRUE);
+        /* Add attributes to this new entry */
+	if (lsqlite3_msg_to_sql(module, msg, eid, FALSE) != 0) {
+                QUERY(lsqlite3, NULL, NULL, FALSE, "ROLLBACK;");
+                return -1;
         }
 
-        /* If everything succeeded, return success */
-        return lsqlite3->last_rc == SQLITE_DONE && ret == 0 ? 0 : -1;
+        /* Everything worked.  Commit it! */
+        QUERY(lsqlite3, NULL, NULL, TRUE, "COMMIT;");
+        return 0;
 }
 
 
@@ -506,6 +478,8 @@ lsqlite3_modify(struct ldb_module *module,
                 const struct ldb_message *msg)
 {
 	int                         ret = 0;
+        int                         numRows;
+        char **                     ppValues;
 	struct ldb_context *        ldb = module->ldb;
 	struct lsqlite3_private *   lsqlite3 = module->private_data;
 
@@ -515,47 +489,37 @@ lsqlite3_modify(struct ldb_module *module,
 	}
 
         /* Begin a transaction */
-        SQL_EXEC(lsqlite3, begin, TRUE);
-
-        /* Get the dn_id for the specified DN */
-        column =
-                sqlite3_bind_parameter_index(
-                        lsqlite3->queries.getDNID,
-                        ":dn");
-        if (sqlite3_bind_text(lsqlite3->queries.getDNID,
-                              column,
-                              msg->dn, strlen(msg->dn),
-                              SQLITE_STATIC) != SQLITE_OK) {
+        QUERY(lsqlite3, NULL, NULL, FALSE, "BEGIN EXCLUSIVE;");
+
+        /* Get the id of this DN. */
+        QUERY(lsqlite3,
+              &ppValues,
+              &numRows,
+              TRUE, 
+              "SELECT eid "
+              "  FROM ldb_entry "
+              "  WHERE dn = %Q;",
+              lsqlite3_normalize_dn(ldb, msg->dn));
+
+        /* Did it exist? */
+        if (numRows != 1) {
+                /* Nope.  See ya! */
+                sqlite_free_table(ppValues);
                 return -1;
         }
 
-        /* Get the id of this DN.  This sets lsqlite3->last_rc */
-        SQL_EXEC(lsqlite3, getDNID, FALSE);
-                        
-        if (lsqlite3->last_rc != SQLITE_ROW) {
-                return -1;
-        }
-
-        dn_id = sqlite3_column_int64(lsqlite3->queries.getDNID,
-                                     column);
-        (void) sqlite3_reset(lsqlite3->queries.getDNID);
-
-	ret = lsqlite3_msg_to_sql(ldb, msg, dn_id, FALSE);
+        /* Retrieve the eid */
+        eid = strtoll(ppValues[1], NULL, 10);
 
-        /* Did the attribute additions (if any) succeeded? */
-        if (ret == 0)
-        {
-                /* Yup.  Commit the transaction */
-                SQL_EXEC(lsqlite3, commit, TRUE);
-        }
-        else
-        {
-                /* Attribute addition failed.  Rollback the transaction */
-                SQL_EXEC(lsqlite3, rollback, TRUE);
+        /* Modify attributes as specified */
+	if (lsqlite3_msg_to_sql(module, msg, eid, FALSE) != 0) {
+                QUERY(lsqlite3, NULL, NULL, FALSE, "ROLLBACK;");
+                return -1;
         }
 
-        /* If everything succeeded, return success */
-        return lsqlite3->last_rc == SQLITE_DONE && ret == 0 ? 0 : -1;
+        /* Everything worked.  Commit it! */
+        QUERY(lsqlite3, NULL, NULL, TRUE, "COMMIT;");
+        return 0 ;
 }
 
 static int
@@ -570,15 +534,9 @@ lsqlite3_lock(struct ldb_module *module,
 		return -1;
 	}
 
-        /* If we're already locked, just update lock count */
-        if (++lsqlite3->lock_count > 1) {
-                return -1;
-        }
-            
-        /* Write-lock (but not read-lock) the database */
-        SQL_EXEC(lsqlite3, begin, TRUE);
+	/* TODO implement a local locking mechanism here */
 
-	return lsqlite3->last_rc == 0 ? 0 : -1;
+	return 0;
 }
 
 static int
@@ -593,19 +551,9 @@ lsqlite3_unlock(struct ldb_module *module,
 		return -1;
 	}
 
-        /* If we're not already locked, there's nothing to do */
-        if (lsqlite3->lock_count == 0) {
-                return 0;
-        }
+	/* TODO implement a local locking mechanism here */
 
-        /* Decrement lock count */
-        if (--lsqlite3->lock_count == 0) {
-        
-                /* Final unlock.  Unlock the database */
-                SQL_EXEC(lsqlite3, commit, TRUE);
-        }
-
-	return lsqlite3->last_rc == 0 ? 0 : -1;
+        return 0;
 }
 
 /*
@@ -647,6 +595,7 @@ static int
 lsqlite3_initialize(lsqlite3_private *lsqlite3,
                     const char *url)
 {
+        int             ret;
         int             bNewDatabase = False;
         char *          p;
         char *          pTail;
@@ -668,110 +617,124 @@ lsqlite3_initialize(lsqlite3_private *lsqlite3,
                   SELECT 'LDB' AS database_type, 
                          '1.0' AS version;
 
-                CREATE TABLE ldb_distinguished_names 
-                (
-                  dn_id         INTEGER PRIMARY KEY AUTOINCREMENT, 
-                  dn            TEXT UNIQUE
-                );
+                -- ------------------------------------------------------
+                -- Schema
 
-                CREATE TABLE ldb_object_classes 
+                /*
+                 * The entry table holds the information about an entry.  This
+                 * table is used to obtain the EID of the entry and to support
+                 * scope=one and scope=base.  The parent and child table
+                 * is included in the entry table since all the other
+                 * attributes on EID.
+                 */
+                CREATE TABLE ldb_entry
                 (
-                  class_name    TEXT PRIMARY KEY,
-                  tree_key      TEXT,
-                  max_child_num INTEGER
+                  -- Unique identifier of this LDB entry
+                  eid                   INTEGER PRIMARY KEY,
+
+                  -- Unique identifier of the parent LDB entry
+                  peid                  INTEGER REFERENCES ldb_entry,
+
+                  -- Distinguished name of this entry
+                  dn                    TEXT,
+
+                  -- Time when the entry was created
+                  create_timestamp      INTEGER,
+
+                  -- Time when the entry was last modified
+                  modify_timestamp      INTEGER,
+
+                  -- Attributes of this entry, in the form
+                  --   attr\1value\0[attr\1value\0]*\0
+                  entry_data            TEXT
                 );
 
-                CREATE TABLE ldb_dn_object_classes 
+
+                /*
+                 * The purpose of the descendant table is to support the
+                 * subtree search feature.  For each LDB entry with a unique
+                 * ID (AEID), this table contains the unique identifiers
+                 * (DEID) of the descendant entries.
+                 *
+                 * For evern entry in the directory, a row exists in this
+                 * table for each of its ancestors including itself.  The size
+                 * of the table depends on the depth of each entry.  In the
+                 * worst case, if all the entries were at the same depth, the
+                 * number of rows in the table is O(nm) where n is the number
+                 * of nodes in the directory and m is the depth of the tree.
+                 */
+                CREATE TABLE ldb_descendants
                 (
-                  dn_id         INTEGER REFERENCES ldb_distinguished_names, 
-                  class_name    TEXT REFERENCES ldb_object_classes 
+                  -- The unique identifier of the ancestor LDB entry
+                  aeid                  INTEGER REFERENCES ldb_entry,
+
+                  -- The unique identifier of the descendant LDB entry
+                  deid                  INTEGER REFERENCES ldb_entry
                 );
 
-                CREATE TABLE ldb_attributes
+
+                CREATE TABLE ldb_object_classes
                 (
-                  attr_name             TEXT PRIMARY KEY,
-                  case_insensitive_p    BOOLEAN DEFAULT FALSE,
-                  wildcard_p            BOOLEAN DEFAULT FALSE,
-                  hidden_p              BOOLEAN DEFAULT FALSE,
-                  integer_p             BOOLEAN DEFAULT FALSE
+                  -- Object classes are inserted into this table to track
+                  -- their class hierarchy.  'top' is the top-level class
+                  -- of which all other classes are subclasses.
+                  class_name            TEXT PRIMARY KEY,
+
+                  -- tree_key tracks the position of the class in
+                  -- the hierarchy 
+                  tree_key              TEXT UNIQUE
                 );
 
-                CREATE TABLE ldb_attr_value_pairs 
+                /*
+                 * There is one attribute table per searchable attribute.
+                 */
+/*
+                CREATE TABLE ldb_attr_ATTRIBUTE_NAME
                 (
-                  dn_id         INTEGER REFERENCES ldb_distinguished_names, 
-                  attr_name     TEXT, -- optionally REFERENCES ldb_attributes
-                  attr_value    TEXT,
+                  -- The unique identifier of the LDB entry
+                  eid                   INTEGER REFERENCES ldb_entry,
 
-                  UNIQUE (dn_id, attr_name, attr_value)
+                  -- Normalized attribute value
+                  attr_value            TEXT
                 );
+*/
+
 
                 -- ------------------------------------------------------
+                -- Indexes
 
-                CREATE TRIGGER ldb_distinguished_names_delete_tr
-                  AFTER DELETE
-                  ON ldb_distinguished_names
-                  FOR EACH ROW
-                    BEGIN
-                      DELETE FROM ldb_attr_value_pairs
-                        WHERE dn_id = old.dn_id;
-                      DELETE FROM ldb_dn_object_classes
-                        WHERE dn_id = old.dn_id;
-                    END;
 
-                CREATE TRIGGER ldb_attr_value_pairs_insert_tr
-                  BEFORE INSERT
-                  ON ldb_attr_value_pairs
+                -- ------------------------------------------------------
+                -- Triggers
+
+                CREATE TRIGGER ldb_entry_insert_tr
+                  AFTER INSERT
+                  ON ldb_entry
                   FOR EACH ROW
                     BEGIN
-                      INSERT OR IGNORE INTO ldb_attributes
-                          (attr_name)
-                        VALUES
-                          (new.attr_name);
+                      UPDATE ldb_entry
+                        SET create_timestamp = strftime('%s', 'now'),
+                            modify_timestamp = strftime('%s', 'now')
+                        WHERE eid = new.eid;
                     END;
 
-                CREATE TRIGGER ldb_attr_value_pairs_delete_tr
-                  AFTER DELETE
-                  ON ldb_attr_value_pairs
+                CREATE TRIGGER ldb_entry_update_tr
+                  AFTER UPDATE
+                  ON ldb_entry
                   FOR EACH ROW
                     BEGIN
-                      DELETE FROM ldb_attributes
-                        WHERE (SELECT COUNT(*)
-                                 FROM ldb_attr_value_pairs
-                                 WHERE attr_name = old.attr_name) = 0
-                          AND attr_name = old.attr_name;
+                      UPDATE ldb_entry
+                        SET modify_timestamp = strftime('%s', 'now')
+                        WHERE eid = old.eid;
                     END;
 
                 -- ------------------------------------------------------
+                -- Table initialization
 
-                CREATE INDEX ldb_distinguished_names_dn_idx
-                  ON ldb_distinguished_names (dn);
-
-                CREATE INDEX ldb_object_classes_tree_key_idx
-                  ON ldb_object_classes (tree_key);
-
-
-                CREATE INDEX ldb_dn_object_classes_dn_id_idx
-                  ON ldb_dn_object_classes (dn_id);
-
-                CREATE INDEX ldb_dn_object_classes_class_name_idx
-                  ON ldb_dn_object_classes (class_name);
-
-
-                CREATE INDEX ldb_attr_value_pairs_dn_id_name_case_idx
-                  ON ldb_attr_value_pairs (dn_id, attr_name);
-
-                CREATE INDEX ldb_attr_value_pairs_dn_id_name_nocase_idx
-                  ON ldb_attr_value_pairs (dn_id, attr_name COLLATE NOCASE);
-
-                -- ------------------------------------------------------
-
-                /* all defaults for dn, initially */
-                INSERT INTO ldb_attributes (attr_name)
-                  VALUES ('dn');
-
-                /* We need an implicit 'top' level object class */
-                INSERT INTO ldb_object_classes (class_name, tree_key)
-                  SELECT 'top', /* next_tree_key(NULL) */ '0001';
+                /* We need an implicit "top" level object class */
+                INSERT INTO ldb_attributes (attr_name,
+                                            parent_tree_key)
+                  SELECT 'top', '';
 
                 -- ------------------------------------------------------
 
@@ -797,7 +760,7 @@ lsqlite3_initialize(lsqlite3_private *lsqlite3,
         }
 
         /* Try to open the (possibly empty/non-existent) database */
-        if ((lsqlite3->last_rc = sqlite3_open(p, &lsqlite3->sqlite3)) != SQLITE_SUCCESS) {
+        if ((ret = sqlite3_open(p, &lsqlite3->sqlite3)) != SQLITE_SUCCESS) {
                 return ret;
         }
 
@@ -831,18 +794,15 @@ lsqlite3_initialize(lsqlite3_private *lsqlite3,
                              "  WHERE type = 'table' "
                              "    AND name IN "
                              "      ("
-                             "        'ldb_info', "
-                             "        'ldb_distinguished_names', "
-                             "        'ldb_object_classes', "
-                             "        'ldb_dn_object_classes', "
-                             "        'ldb_attributes', "
-                             "        'ldb_attr_value_pairs' "
+                             "        'ldb_entry', "
+                             "        'ldb_descendants', "
+                             "        'ldb_object_classes' "
                              "      );",
                              -1,
                              &stmt,
                              &pTail)) != SQLITE_SUCCESS ||
                     (lsqlite3->last_rc = sqlite3_step(stmt)) != SQLITE_ROW ||
-                    sqlite3_column_int(stmt, 0) != 6 ||
+                    sqlite3_column_int(stmt, 0) != 3 ||
                     (lsqlite3->last_rc = sqlite_finalize(stmt)) != SQLITE_SUCCESS ||
 
                     (lsqlite3->last_rc = sqlite3_prepare(
@@ -863,149 +823,6 @@ lsqlite3_initialize(lsqlite3_private *lsqlite3,
                 }
         }
 
-        /*
-         * Pre-compile each of the queries we'll be using.
-         */
-
-        if ((lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "BEGIN IMMEDIATE;",
-                     -1,
-                     &lsqlite3->queries.begin,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "COMMIT;",
-                     -1,
-                     &lsqlite3->queries.commit,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "ROLLBACK;",
-                     -1,
-                     &lsqlite3->queries.rollback,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT INTO ldb_distinguished_names (dn_id, dn) "
-                     "  VALUES (:dn_id, :dn);",
-                     -1,
-                     &lsqlite3->queries.newDN,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "UPDATE ldb_distinguished_names "
-                     "  SET dn = :newDN "
-                     "  WHERE dn = :oldDN;",
-                     -1,
-                     &lsqlite3->queries.renameDN,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "DELETE FROM ldb_distinguished_names "
-                     "  WHERE dn = :dn;",
-                     -1,
-                     &lsqlite3->queries.deleteDN,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT OR IGNORE INTO ldb_object_classes "
-                     "    (class_name, tree_key)"
-                     "  SELECT :class_name, next_tree_key(NULL);",
-                     -1,
-                     &lsqlite3->queries.newObjectClass,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT OR REPLACE INTO ldb_dn_object_classes "
-                     "    (dn_id, class_name) "
-                     "  VALUES (:dn_id, :class_name);",
-                     -1,
-                     &lsqlite3->queries.assignObjectClass,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT OR IGNORE INTO ldb_attributes (name) "
-                     "  VALUES (:name);",
-                     -1,
-                     &lsqlite3->queries.newAttributeUseDefaults,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT OR REPLACE INTO ldb_attributes "
-                     "    (name, "
-                     "     case_insensitive_p, "
-                     "     wildcard_p, "
-                     "     hidden_p, "
-                     "     integer_p) "
-                     "  VALUES (:name, "
-                     "          :case_insensitive_p, "
-                     "          :wildcard_p, "
-                     "          :hidden_p, "
-                     "          :integer_p);",
-                     -1,
-                     &lsqlite3->queries.newAttribute,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT INTO ldb_attr_value_pairs "
-                     "    (dn_id, attr_name, attr_value) "
-                     "  VALUES (:dn_id, :attr_name, :attr_value);",
-                     -1,
-                     &lsqlite3->queries.addAttrValuePair,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "UPDATE ldb_attr_value_pairs "
-                     "  SET attr_value = :attr_value "
-                     "  WHERE dn_id = :dn_id "
-                     "    AND attr_name = :attr_name;",
-                     -1,
-                     &lsqlite3->queries.addAttrValuePair,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "DELETE FROM ldb_attr_value_pairs "
-                     "  WHERE dn_id = :dn_id "
-                     "    AND attr_name = :attr_name;"
-                     -1,
-                     &lsqlite3->queries.deleteAttrValuePair,
-                     &pTail)) != SQLITE_SUCCESS ||
-            
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "INSERT OR REPLACE INTO ldb_object_classes "
-                     "    (class_name, tree_key) "
-                     "  SELECT :child_class, next_tree_key(:parent_class);"
-                     -1,
-                     &lsqlite3->queries.insertSubclass,
-                     &pTail)) != SQLITE_SUCCESS ||
-
-            (lsqlite3->last_rc = sqlite3_prepare(
-                     lsqlite3->sqlite3,
-                     "SELECT dn_id "
-                     "  FROM ldb_distinguished_names "
-                     "  WHERE dn = :dn;"
-                     -1,
-                     &lsqlite3->queries.getDNID,
-                     &pTail)) != SQLITE_SUCCESS) {
-
-                (void) sqlite3_close(lsqlite3->sqlite3);
-                return ret;
-        }
-
         return SQLITE_SUCCESS;
 }
 
diff --git a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.h b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.h
index 2fa08fdcb7..192e28f3dc 100644
--- a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.h
+++ b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.h
@@ -5,24 +5,6 @@ struct lsqlite3_private {
 	const char *basedn;
         sqlite3 * sqlite;
         int lock_count;
-	int last_rc;
-        struct {
-                sqlite3_stmt *begin;
-                sqlite3_stmt *commit;
-                sqlite3_stmt *rollback;
-                sqlite3_stmt *newDN;
-                sqlite3_stmt *renameDN;
-                sqlite3_stmt *deleteDN;
-                sqlite3_stmt *newObjectClass;
-                sqlite3_stmt *assignObjectClass;
-                sqlite3_stmt *newAttributeUseDefaults;
-                sqlite3_stmt *newAttribute;
-                sqlite3_stmt *addAttrValuePair;
-                sqlite3_stmt *replaceAttrValuePairs;
-                sqlite3_stmt *deleteAttrValuePairs;
-                sqlite3_stmt *insertSubclass;
-                sqlite3_stmt *getDNID;
-        } queries;
 };
 
 void
diff --git a/source4/lib/ldb/ldb_sqlite3/schema b/source4/lib/ldb/ldb_sqlite3/schema
index 08dc50de08..78550985d4 100644
--- a/source4/lib/ldb/ldb_sqlite3/schema
+++ b/source4/lib/ldb/ldb_sqlite3/schema
@@ -12,158 +12,119 @@
                   SELECT 'LDB' AS database_type, 
                          '1.0' AS version;
 
+                -- ------------------------------------------------------
+                -- Schema
+
                 /*
-                 * Get the next USN value with:
-                 *   BEGIN EXCLUSIVE;
-                 *   UPDATE usn SET value = value + 1;
-                 *   SELECT value FROM usn;
-                 *   COMMIT;
+                 * The entry table holds the information about an entry.  This
+                 * table is used to obtain the EID of the entry and to support
+                 * scope="one" and scope="base".  The parent and child table
+                 * is included in the entry table since all the other
+                 * attributes on EID.
                  */
-                CREATE TABLE usn
+                CREATE TABLE ldb_entry
                 (
-                  value           INTEGER
+                  -- Unique identifier of this LDB entry
+                  eid                   INTEGER PRIMARY KEY,
+
+                  -- Unique identifier of the parent LDB entry
+                  peid                  INTEGER REFERENCES ldb_entry,
+
+                  -- Distinguished name of this entry
+                  dn                    TEXT,
+
+                  -- Time when the entry was created
+                  create_timestamp      INTEGER,
+
+                  -- Time when the entry was last modified
+                  modify_timestamp      INTEGER,
+
+                  -- Attributes of this entry, in the form
+                  --   attr\1value\0[attr\1value\0]*\0
+                  entry_data            TEXT
                 );
 
-                CREATE TABLE ldb_object
+
+                /*
+                 * The purpose of the descendant table is to support the
+                 * subtree search feature.  For each LDB entry with a unique
+                 * ID (AEID), this table contains the unique identifiers
+                 * (DEID) of the descendant entries.
+                 *
+                 * For evern entry in the directory, a row exists in this
+                 * table for each of its ancestors including itself.  The size
+                 * of the table depends on the depth of each entry.  In the
+                 * worst case, if all the entries were at the same depth, the
+                 * number of rows in the table is O(nm) where n is the number
+                 * of nodes in the directory and m is the depth of the tree.
+                 */
+                CREATE TABLE ldb_descendants
                 (
-                  /* tree_key is auto-generated by the insert trigger */
-                  tree_key        TEXT PRIMARY KEY,
-
-                  parent_tree_key TEXT,
-                  dn              TEXT,
-
-                  attr_name       TEXT REFERENCES ldb_attributes,
-                  attr_value      TEXT,
-
-                  /*
-                   * object_type can take on these values (to date):
-                   *   1: object is a node of a DN
-                   *   2: object is an attribute/value pair of its parent DN
-                   */
-                  object_type     INTEGER,
-
-                  /*
-                   * if object_type is 1, the node can have children.
-                   * this tracks the maximum previously assigned child
-                   * number so we can generate a new unique tree key for
-                   * a new child object.  note that this is always incremented,
-                   * so if children are deleted, this will not represent
-                   * the _number_ of children.
-                   */
-                  max_child_num   INTEGER,
-
-                  /*
-                   * Automatically maintained meta-data (a gift for metze)
-                   */
-                  object_guid     TEXT UNIQUE,
-                  timestamp       INTEGER,  -- originating_time
-                  invoke_id       TEXT,     -- GUID: originating_invocation_id
-                  usn             INTEGER,  -- hyper: originating_usn
-
-                  /* do not allow duplicate name/value pairs */
-                  UNIQUE (parent_tree_key, attr_name, attr_value, object_type)
+                  -- The unique identifier of the ancestor LDB entry
+                  aeid                  INTEGER REFERENCES ldb_entry,
+
+                  -- The unique identifier of the descendant LDB entry
+                  deid                  INTEGER REFERENCES ldb_entry
                 );
 
-                CREATE TABLE ldb_attributes
-                (
-                  attr_name             TEXT PRIMARY KEY,
-                  parent_tree_key       TEXT,
 
-                  objectclass_p         BOOLEAN DEFAULT 0,
+                CREATE TABLE ldb_object_classes
+                (
+                  -- Object classes are inserted into this table to track
+                  -- their class hierarchy.  'top' is the top-level class
+                  -- of which all other classes are subclasses.
+                  class_name            TEXT PRIMARY KEY,
+
+                  -- tree_key tracks the position of the class in
+                  -- the hierarchy 
+                  tree_key              TEXT UNIQUE
+                );
 
-                  case_insensitive_p    BOOLEAN DEFAULT 0,
-                  wildcard_p            BOOLEAN DEFAULT 0,
-                  hidden_p              BOOLEAN DEFAULT 0,
-                  integer_p             BOOLEAN DEFAULT 0,
+                /*
+                 * There is one attribute table per searchable attribute.
+                 */
+/*
+                CREATE TABLE ldb_attr_ATTRIBUTE_NAME
+                (
+                  -- The unique identifier of the LDB entry
+                  eid                   INTEGER REFERENCES ldb_entry,
 
-                  /* tree_key is auto-generated by the insert trigger */
-                  tree_key              TEXT, -- null if not a object/sub class
-                                              -- level 1 if an objectclass
-                                              -- level 1-n if a subclass
-                  max_child_num         INTEGER
+                  -- Normalized attribute value
+                  attr_value            TEXT
                 );
+*/
 
-                -- ------------------------------------------------------
 
-                CREATE INDEX ldb_object_dn_idx
-                  ON ldb_object (dn);
+                -- ------------------------------------------------------
+                -- Indexes
 
-                CREATE INDEX ldb_attributes_tree_key_ids
-                  ON ldb_attributes (tree_key);
 
                 -- ------------------------------------------------------
+                -- Triggers
 
-                /* Gifts for metze.  Automatically updated meta-data */
-                CREATE TRIGGER ldb_object_insert_tr
+                CREATE TRIGGER ldb_entry_insert_tr
                   AFTER INSERT
-                  ON ldb_object
+                  ON ldb_entry
                   FOR EACH ROW
                     BEGIN
-                      UPDATE ldb_object
-                        SET max_child_num = max_child_num + 1
-                        WHERE tree_key = new.parent_tree_key;
-                      UPDATE usn SET value = value + 1;
-                      UPDATE ldb_object
-                        SET tree_key =
-                              (SELECT
-                                 new.tree_key ||
-                                 base160(SELECT max_child_num
-                                           FROM ldb_object
-                                           WHERE tree_key =
-                                                 new.parent_tree_key));
-                            max_child_num = 0,
-                            object_guid = random_guid(),
-                            timestamp = strftime('%s', 'now'),
-                            usn = (SELECT value FROM usn);
-                        WHERE tree_key = new.tree_key;
+                      UPDATE ldb_entry
+                        SET create_timestamp = strftime('%s', 'now'),
+                            modify_timestamp = strftime('%s', 'now')
+                        WHERE eid = new.eid;
                     END;
 
-                CREATE TRIGGER ldb_object_update_tr
+                CREATE TRIGGER ldb_entry_update_tr
                   AFTER UPDATE
-                  ON ldb_object
+                  ON ldb_entry
                   FOR EACH ROW
                     BEGIN
-                      UPDATE usn SET value = value + 1;
-                      UPDATE ldb_object
-                        SET timestamp = strftime('%s', 'now'),
-                            usn = (SELECT value FROM usn);
-                        WHERE tree_key = new.tree_key;
+                      UPDATE ldb_entry
+                        SET modify_timestamp = strftime('%s', 'now')
+                        WHERE eid = old.eid;
                     END;
 
-                CREATE TRIGGER ldb_attributes_insert_tr
-                  AFTER INSERT
-                  ON ldb_attributes
-                  FOR EACH ROW
-                    BEGIN
-                      UPDATE ldb_attributes
-                        SET max_child_num = max_child_num + 1
-                        WHERE tree_key = new.parent_tree_key;
-                      UPDATE ldb_attributes
-                        SET tree_key =
-                              (SELECT
-                                 new.tree_key ||
-                                 base160(SELECT max_child_num
-                                           FROM ldb_attributes
-                                           WHERE tree_key =
-                                                 new.parent_tree_key));
-                            max_child_num = 0
-                        WHERE tree_key = new.tree_key;
-                    END;
-
-
                 -- ------------------------------------------------------
-
-                /* Initialize usn */
-                INSERT INTO usn (value) VALUES (0);
-
-                /* Create root object */
-                INSERT INTO ldb_object
-                    (tree_key, parent_tree_key,
-                     dn,
-                     object_type, max_child_num)
-                  VALUES ('', NULL,
-                          '',
-                          1, 0);
+                -- Table initialization
 
                 /* We need an implicit "top" level object class */
                 INSERT INTO ldb_attributes (attr_name,
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
index f6a23d7433..9c126c1dfd 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -44,78 +44,12 @@
 
 
 /*
-  casefold a dn. We need to uppercase the attribute names, and the 
-  attribute values of case insensitive attributes. We also need to remove
-  extraneous spaces between elements
+  callback function used in call to ldb_dn_fold() for determining whether an
+  attribute type requires case folding.
 */
-static char *ltdb_dn_fold(struct ldb_module *module, const char *dn)
+static int ltdb_case_fold_attr_required(struct ldb_module *module, char *attr)
 {
-	const char *dn_orig = dn;
-	struct ldb_context *ldb = module->ldb;
-	TALLOC_CTX *tmp_ctx = talloc_new(ldb);
-	char *ret;
-	size_t len;
-
-	ret = talloc_strdup(tmp_ctx, "");
-	if (ret == NULL) goto failed;
-
-	while ((len = strcspn(dn, ",")) > 0) {
-		char *p = strchr(dn, '=');
-		char *attr, *value;
-		int flags;
-
-		if (p == NULL || (p-dn) > len) goto failed;
-
-		attr = talloc_strndup(tmp_ctx, dn, p-dn);
-		if (attr == NULL) goto failed;
-
-		/* trim spaces from the attribute name */
-		while (' ' == *attr) attr++;
-		while (' ' == attr[strlen(attr)-1]) {
-			attr[strlen(attr)-1] = 0;
-		}
-		if (*attr == 0) goto failed;
-
-		value = talloc_strndup(tmp_ctx, p+1, len-(p+1-dn));
-		if (value == NULL) goto failed;
-
-		/* trim spaces from the value */
-		while (' ' == *value) value++;
-		while (' ' == value[strlen(value)-1]) {
-			value[strlen(value)-1] = 0;
-		}
-		if (*value == 0) goto failed;
-
-		flags = ltdb_attribute_flags(module, attr);
-
-		attr = ldb_casefold(ldb, attr);
-		if (attr == NULL) goto failed;
-		talloc_steal(tmp_ctx, attr);
-
-		if (flags & LTDB_FLAG_CASE_INSENSITIVE) {
-			value = ldb_casefold(ldb, value);
-			if (value == NULL) goto failed;
-			talloc_steal(tmp_ctx, value);
-		}		
-
-		if (dn[len] == ',') {
-			ret = talloc_asprintf_append(ret, "%s=%s,", attr, value);
-		} else {
-			ret = talloc_asprintf_append(ret, "%s=%s", attr, value);
-		}
-		if (ret == NULL) goto failed;
-
-		dn += len;
-		if (*dn == ',') dn++;
-	}
-
-	talloc_steal(ldb, ret);
-	talloc_free(tmp_ctx);
-	return ret;
-
-failed:
-	talloc_free(tmp_ctx);
-	return ldb_casefold(ldb, dn_orig);
+    return ltdb_attribute_flags(module, attr) & LTDB_FLAG_CASE_INSENSITIVE;
 }
 
 /*
@@ -172,7 +106,7 @@ struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn)
 		}
 		talloc_free(attr_name);
 	} else {
-		dn_folded = ltdb_dn_fold(module, dn);
+                dn_folded = ldb_dn_fold(module, dn, ltdb_case_fold_attr_required);
 	}
 
 	if (!dn_folded) {
diff --git a/source4/lib/ldb/tools/ldbsearch.c b/source4/lib/ldb/tools/ldbsearch.c
index 3e6e7d7feb..26bd198d1d 100644
--- a/source4/lib/ldb/tools/ldbsearch.c
+++ b/source4/lib/ldb/tools/ldbsearch.c
@@ -48,6 +48,7 @@ static void usage(void)
 	printf("  -s base|sub|one  choose search scope\n");
 	printf("  -b basedn        choose baseDN\n");
 	printf("  -i               read search expressions from stdin\n");
+        printf("  -S               sort returned attributes\n");
 	printf("  -o options       pass options like modules to activate\n");
 	printf("              e.g: -o modules:timestamps\n");
 	exit(1);
@@ -56,6 +57,7 @@ static void usage(void)
 static int do_search(struct ldb_context *ldb,
 		     const char *basedn,
 		     int scope,
+                     int sort_attribs,
 		     const char *expression,
 		     const char * const *attrs)
 {
@@ -77,6 +79,15 @@ static int do_search(struct ldb_context *ldb,
 		ldif.changetype = LDB_CHANGETYPE_NONE;
 		ldif.msg = msgs[i];
 
+                if (sort_attribs) {
+                        /*
+                         * Ensure attributes are always returned in the same
+                         * order.  For testing, this makes comparison of old
+                         * vs. new much easier.
+                         */
+                        ldb_msg_sort_elements(ldif.msg);
+                }
+                
 		ldb_ldif_write_file(ldb, stdout, &ldif);
 	}
 
@@ -100,7 +111,7 @@ static int do_search(struct ldb_context *ldb,
 	const char **options = NULL;
 	int opt, ldbopts;
 	enum ldb_scope scope = LDB_SCOPE_SUBTREE;
-	int interactive = 0, ret=0;
+	int interactive = 0, sort_attribs=0, ret=0;
 
 	ldb_url = getenv("LDB_URL");
 
@@ -129,6 +140,10 @@ static int do_search(struct ldb_context *ldb,
 			interactive = 1;
 			break;
 
+                case 'S':
+                        sort_attribs = 1;
+                        break;
+
 		case 'o':
 			options = ldb_options_parse(options, &ldbopts, optarg);
 			break;
@@ -168,12 +183,12 @@ static int do_search(struct ldb_context *ldb,
 	if (interactive) {
 		char line[1024];
 		while (fgets(line, sizeof(line), stdin)) {
-			if (do_search(ldb, basedn, scope, line, attrs) == -1) {
+			if (do_search(ldb, basedn, scope, sort_attribs, line, attrs) == -1) {
 				ret = -1;
 			}
 		}
 	} else {
-		ret = do_search(ldb, basedn, scope, argv[0], attrs);
+		ret = do_search(ldb, basedn, scope, sort_attribs, argv[0], attrs);
 	}
 
 	talloc_free(ldb);
diff --git a/source4/lib/tdb/common/tdb.c b/source4/lib/tdb/common/tdb.c
index 670fdda7cd..e9cbc12b91 100644
--- a/source4/lib/tdb/common/tdb.c
+++ b/source4/lib/tdb/common/tdb.c
@@ -105,9 +105,18 @@
 #define MAP_FAILED ((void *)-1)
 #endif
 
+#ifndef discard_const_p
+# if defined(__intptr_t_defined) || defined(HAVE_INTPTR_T)
+#  define discard_const(ptr) ((void *)((intptr_t)(ptr)))
+# else
+#  define discard_const(ptr) ((void *)(ptr))
+# endif
+# define discard_const_p(type, ptr) ((type *)discard_const(ptr))
+#endif
+
 /* free memory if the pointer is valid and zero the pointer */
 #ifndef SAFE_FREE
-#define SAFE_FREE(x) do { if ((x) != NULL) {free((x)); (x)=NULL;} } while(0)
+#define SAFE_FREE(x) do { if ((x) != NULL) {free(discard_const_p(void *, (x))); (x)=NULL;} } while(0)
 #endif
 
 #define BUCKET(hash) ((hash) % tdb->header.hash_size)
diff --git a/source4/nsswitch/winbindd_nss.h b/source4/nsswitch/winbindd_nss.h
index 9a99bad9d7..d785b8420c 100644
--- a/source4/nsswitch/winbindd_nss.h
+++ b/source4/nsswitch/winbindd_nss.h
@@ -22,7 +22,7 @@
 */
 
 #ifndef SAFE_FREE
-#define SAFE_FREE(x) do { if(x) {free(x); x=NULL;} } while(0)
+#define SAFE_FREE(x) do { if(x) {free(discard_const_p(void *, (x)); x=NULL;} } while(0)
 #endif
 
 #ifndef _WINBINDD_NTDOM_H