15 files changed, 823 insertions, 297 deletions

diff --git a/source3/registry/reg_api.c b/source3/registry/reg_api.c
index a5f3935821..67767a2e56 100644
--- a/source3/registry/reg_api.c
+++ b/source3/registry/reg_api.c
@@ -94,15 +94,16 @@ static WERROR fill_value_cache(struct registry_key *key)
 
 static WERROR fill_subkey_cache(struct registry_key *key)
 {
+	WERROR werr;
+
 	if (key->subkeys != NULL) {
 		if (!reg_subkeys_need_update(key->key, key->subkeys)) {
 			return WERR_OK;
 		}
 	}
 
-	if (!(key->subkeys = TALLOC_ZERO_P(key, REGSUBKEY_CTR))) {
-		return WERR_NOMEM;
-	}
+	werr = regsubkey_ctr_init(key, &(key->subkeys));
+	W_ERROR_NOT_OK_RETURN(werr);
 
 	if (fetch_reg_keys(key->key, key->subkeys) == -1) {
 		TALLOC_FREE(key->subkeys);
@@ -127,7 +128,7 @@ static WERROR regkey_open_onelevel(TALLOC_CTX *mem_ctx,
 	WERROR     	result = WERR_OK;
 	struct registry_key *regkey;
 	REGISTRY_KEY *key;
-	REGSUBKEY_CTR	*subkeys = NULL;
+	struct regsubkey_ctr	*subkeys = NULL;
 
 	DEBUG(7,("regkey_open_onelevel: name = [%s]\n", name));
 
@@ -193,8 +194,8 @@ static WERROR regkey_open_onelevel(TALLOC_CTX *mem_ctx,
 	/* check if the path really exists; failed is indicated by -1 */
 	/* if the subkey count failed, bail out */
 
-	if ( !(subkeys = TALLOC_ZERO_P( key, REGSUBKEY_CTR )) ) {
-		result = WERR_NOMEM;
+	result = regsubkey_ctr_init(key, &subkeys);
+	if (!W_ERROR_IS_OK(result)) {
 		goto done;
 	}
 
@@ -308,11 +309,13 @@ WERROR reg_enumkey(TALLOC_CTX *mem_ctx, struct registry_key *key,
 		return err;
 	}
 
-	if (idx >= key->subkeys->num_subkeys) {
+	if (idx >= regsubkey_ctr_numkeys(key->subkeys)) {
 		return WERR_NO_MORE_ITEMS;
 	}
 
-	if (!(*name = talloc_strdup(mem_ctx, key->subkeys->subkeys[idx]))) {
+	if (!(*name = talloc_strdup(mem_ctx,
+			regsubkey_ctr_specific_key(key->subkeys, idx))))
+	{
 		return WERR_NOMEM;
 	}
 
@@ -406,11 +409,12 @@ WERROR reg_queryinfokey(struct registry_key *key, uint32_t *num_subkeys,
 	}
 
 	max_len = 0;
-	for (i=0; i<key->subkeys->num_subkeys; i++) {
-		max_len = MAX(max_len, strlen(key->subkeys->subkeys[i]));
+	for (i=0; i< regsubkey_ctr_numkeys(key->subkeys); i++) {
+		max_len = MAX(max_len,
+			strlen(regsubkey_ctr_specific_key(key->subkeys, i)));
 	}
 
-	*num_subkeys = key->subkeys->num_subkeys;
+	*num_subkeys = regsubkey_ctr_numkeys(key->subkeys);
 	*max_subkeylen = max_len;
 	*max_subkeysize = 0;	/* Class length? */
 
@@ -520,14 +524,8 @@ WERROR reg_createkey(TALLOC_CTX *ctx, struct registry_key *parent,
 	err = fill_subkey_cache(create_parent);
 	if (!W_ERROR_IS_OK(err)) goto done;
 
-	err = regsubkey_ctr_addkey(create_parent->subkeys, path);
-	if (!W_ERROR_IS_OK(err)) goto done;
-
-	if (!store_reg_keys(create_parent->key, create_parent->subkeys)) {
-		TALLOC_FREE(create_parent->subkeys);
-		err = WERR_REG_IO_FAILURE;
-		goto done;
-	}
+	err = create_reg_subkey(key->key, path);
+	W_ERROR_NOT_OK_GOTO_DONE(err);
 
 	/*
 	 * Now open the newly created key
@@ -546,40 +544,36 @@ WERROR reg_createkey(TALLOC_CTX *ctx, struct registry_key *parent,
 WERROR reg_deletekey(struct registry_key *parent, const char *path)
 {
 	WERROR err;
-	TALLOC_CTX *mem_ctx;
 	char *name, *end;
-	int num_subkeys;
 	struct registry_key *tmp_key, *key;
+	TALLOC_CTX *mem_ctx = talloc_stackframe();
 
-	if (!(mem_ctx = talloc_init("reg_createkey"))) return WERR_NOMEM;
-
-	if (!(name = talloc_strdup(mem_ctx, path))) {
+	name = talloc_strdup(mem_ctx, path);
+	if (name == NULL) {
 		err = WERR_NOMEM;
-		goto error;
+		goto done;
 	}
 
 	/* check if the key has subkeys */
 	err = reg_openkey(mem_ctx, parent, name, REG_KEY_READ, &key);
-	if (!W_ERROR_IS_OK(err)) {
-		goto error;
-	}
-	if (!W_ERROR_IS_OK(err = fill_subkey_cache(key))) {
-		goto error;
-	}
-	if (key->subkeys->num_subkeys > 0) {
+	W_ERROR_NOT_OK_GOTO_DONE(err);
+
+	err = fill_subkey_cache(key);
+	W_ERROR_NOT_OK_GOTO_DONE(err);
+
+	if (regsubkey_ctr_numkeys(key->subkeys) > 0) {
 		err = WERR_ACCESS_DENIED;
-		goto error;
+		goto done;
 	}
 
 	/* no subkeys - proceed with delete */
-	if ((end = strrchr(name, '\\')) != NULL) {
+	end = strrchr(name, '\\');
+	if (end != NULL) {
 		*end = '\0';
 
 		err = reg_openkey(mem_ctx, parent, name,
 				  SEC_RIGHTS_CREATE_SUBKEY, &tmp_key);
-		if (!W_ERROR_IS_OK(err)) {
-			goto error;
-		}
+		W_ERROR_NOT_OK_GOTO_DONE(err);
 
 		parent = tmp_key;
 		name = end+1;
@@ -587,31 +581,12 @@ WERROR reg_deletekey(struct registry_key *parent, const char *path)
 
 	if (name[0] == '\0') {
 		err = WERR_INVALID_PARAM;
-		goto error;
-	}
-
-	if (!W_ERROR_IS_OK(err = fill_subkey_cache(parent))) {
-		goto error;
-	}
-
-	num_subkeys = parent->subkeys->num_subkeys;
-
-	if (regsubkey_ctr_delkey(parent->subkeys, name) == num_subkeys) {
-		err = WERR_BADFILE;
-		goto error;
-	}
-
-	if (!store_reg_keys(parent->key, parent->subkeys)) {
-		TALLOC_FREE(parent->subkeys);
-		err = WERR_REG_IO_FAILURE;
-		goto error;
+		goto done;
 	}
 
-	regkey_set_secdesc(key->key, NULL);
-
-	err = WERR_OK;
+	err = delete_reg_subkey(parent->key, name);
 
- error:
+done:
 	TALLOC_FREE(mem_ctx);
 	return err;
 }
@@ -726,7 +701,7 @@ static WERROR reg_load_tree(REGF_FILE *regfile, const char *topkeypath,
 	REGF_NK_REC *subkey;
 	REGISTRY_KEY registry_key;
 	REGVAL_CTR *values;
-	REGSUBKEY_CTR *subkeys;
+	struct regsubkey_ctr *subkeys;
 	int i;
 	char *path = NULL;
 	WERROR result = WERR_OK;
@@ -748,10 +723,8 @@ static WERROR reg_load_tree(REGF_FILE *regfile, const char *topkeypath,
 
 	/* now start parsing the values and subkeys */
 
-	subkeys = TALLOC_ZERO_P(regfile->mem_ctx, REGSUBKEY_CTR);
-	if (subkeys == NULL) {
-		return WERR_NOMEM;
-	}
+	result = regsubkey_ctr_init(regfile->mem_ctx, &subkeys);
+	W_ERROR_NOT_OK_RETURN(result);
 
 	values = TALLOC_ZERO_P(subkeys, REGVAL_CTR);
 	if (values == NULL) {
@@ -767,7 +740,7 @@ static WERROR reg_load_tree(REGF_FILE *regfile, const char *topkeypath,
 				    (key->values[i].data_size & ~VK_DATA_IN_OFFSET));
 	}
 
-	/* copy subkeys into the REGSUBKEY_CTR */
+	/* copy subkeys into the struct regsubkey_ctr */
 
 	key->subkey_index = 0;
 	while ((subkey = regfio_fetch_subkey( regfile, key ))) {
@@ -861,7 +834,7 @@ static WERROR reg_write_tree(REGF_FILE *regfile, const char *keypath,
 {
 	REGF_NK_REC *key;
 	REGVAL_CTR *values;
-	REGSUBKEY_CTR *subkeys;
+	struct regsubkey_ctr *subkeys;
 	int i, num_subkeys;
 	char *key_tmp = NULL;
 	char *keyname, *parentpath;
@@ -909,10 +882,8 @@ static WERROR reg_write_tree(REGF_FILE *regfile, const char *keypath,
 
 	/* lookup the values and subkeys */
 
-	subkeys = TALLOC_ZERO_P(regfile->mem_ctx, REGSUBKEY_CTR);
-	if (subkeys == NULL) {
-		return WERR_NOMEM;
-	}
+	result = regsubkey_ctr_init(regfile->mem_ctx, &subkeys);
+	W_ERROR_NOT_OK_RETURN(result);
 
 	values = TALLOC_ZERO_P(subkeys, REGVAL_CTR);
 	if (values == NULL) {
@@ -1091,6 +1062,7 @@ static WERROR reg_deletekey_recursive_internal(TALLOC_CTX *ctx,
 	WERROR werr = WERR_OK;
 	struct registry_key *key;
 	char *subkey_name = NULL;
+	uint32 i;
 
 	mem_ctx = talloc_new(ctx);
 	if (mem_ctx == NULL) {
@@ -1104,25 +1076,21 @@ static WERROR reg_deletekey_recursive_internal(TALLOC_CTX *ctx,
 		goto done;
 	}
 
-	while (W_ERROR_IS_OK(werr = reg_enumkey(mem_ctx, key, 0,
-						&subkey_name, NULL)))
-	{
+	werr = fill_subkey_cache(key);
+	W_ERROR_NOT_OK_GOTO_DONE(werr);
+
+	/*
+	 * loop from top to bottom for perfomance:
+	 * this way, we need to rehash the regsubkey containers less
+	 */
+	for (i = regsubkey_ctr_numkeys(key->subkeys) ; i > 0; i--) {
+		subkey_name = regsubkey_ctr_specific_key(key->subkeys, i-1);
 		werr = reg_deletekey_recursive_internal(mem_ctx, key,
-							subkey_name,
-							true);
-		if (!W_ERROR_IS_OK(werr)) {
-			goto done;
-		}
-	}
-	if (!W_ERROR_EQUAL(WERR_NO_MORE_ITEMS, werr)) {
-		DEBUG(1, ("reg_deletekey_recursive_internal: "
-			  "Error enumerating subkeys: %s\n",
-			  win_errstr(werr)));
-		goto done;
+					subkey_name,
+					true);
+		W_ERROR_NOT_OK_GOTO_DONE(werr);
 	}
 
-	werr = WERR_OK;
-
 	if (del_key) {
 		/* now delete the actual key */
 		werr = reg_deletekey(parent, path);
@@ -1133,18 +1101,57 @@ done:
 	return werr;
 }
 
+static WERROR reg_deletekey_recursive_trans(TALLOC_CTX *ctx,
+					    struct registry_key *parent,
+					    const char *path,
+					    bool del_key)
+{
+	WERROR werr;
+
+	werr = regdb_transaction_start();
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(0, ("reg_deletekey_recursive_trans: "
+			  "error starting transaction: %s\n",
+			  win_errstr(werr)));
+		return werr;
+	}
+
+	werr = reg_deletekey_recursive_internal(ctx, parent, path, del_key);
+
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, (__location__ " failed to delete key '%s' from key "
+			  "'%s': %s\n", path, parent->key->name,
+			  win_errstr(werr)));
+		werr = regdb_transaction_cancel();
+		if (!W_ERROR_IS_OK(werr)) {
+			DEBUG(0, ("reg_deletekey_recursive_trans: "
+				  "error cancelling transaction: %s\n",
+				  win_errstr(werr)));
+		}
+	} else {
+		werr = regdb_transaction_commit();
+		if (!W_ERROR_IS_OK(werr)) {
+			DEBUG(0, ("reg_deletekey_recursive_trans: "
+				  "error committing transaction: %s\n",
+				  win_errstr(werr)));
+		}
+	}
+
+	return werr;
+}
+
 WERROR reg_deletekey_recursive(TALLOC_CTX *ctx,
 			       struct registry_key *parent,
 			       const char *path)
 {
-	return reg_deletekey_recursive_internal(ctx, parent, path, true);
+	return reg_deletekey_recursive_trans(ctx, parent, path, true);
 }
 
 WERROR reg_deletesubkeys_recursive(TALLOC_CTX *ctx,
 				   struct registry_key *parent,
 				   const char *path)
 {
-	return reg_deletekey_recursive_internal(ctx, parent, path, false);
+	return reg_deletekey_recursive_trans(ctx, parent, path, false);
 }
 
 #if 0
diff --git a/source3/registry/reg_backend_current_version.c b/source3/registry/reg_backend_current_version.c
index 04cc0ebfa7..f76840ee22 100644
--- a/source3/registry/reg_backend_current_version.c
+++ b/source3/registry/reg_backend_current_version.c
@@ -70,7 +70,7 @@ static int current_version_fetch_values(const char *key, REGVAL_CTR *values)
 }
 
 static int current_version_fetch_subkeys(const char *key,
-					 REGSUBKEY_CTR *subkey_ctr)
+					 struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_backend_db.c b/source3/registry/reg_backend_db.c
index 8ef83a19a1..30f1db9c53 100644
--- a/source3/registry/reg_backend_db.c
+++ b/source3/registry/reg_backend_db.c
@@ -103,7 +103,7 @@ static WERROR init_registry_key_internal(const char *add_path)
 	char *remaining = NULL;
 	char *keyname;
 	char *subkeyname;
-	REGSUBKEY_CTR *subkeys;
+	struct regsubkey_ctr *subkeys;
 	const char *p, *p2;
 
 	DEBUG(6, ("init_registry_key: Adding [%s]\n", add_path));
@@ -167,9 +167,9 @@ static WERROR init_registry_key_internal(const char *add_path)
 		 * since we are about to update the record.
 		 * We just want any subkeys already present */
 
-		if (!(subkeys = TALLOC_ZERO_P(frame, REGSUBKEY_CTR))) {
+		werr = regsubkey_ctr_init(frame, &subkeys);
+		if (!W_ERROR_IS_OK(werr)) {
 			DEBUG(0,("talloc() failure!\n"));
-			werr = WERR_NOMEM;
 			goto fail;
 		}
 
@@ -482,6 +482,24 @@ int regdb_close( void )
 	return 0;
 }
 
+WERROR regdb_transaction_start(void)
+{
+	return (regdb->transaction_start(regdb) == 0) ?
+		WERR_OK : WERR_REG_IO_FAILURE;
+}
+
+WERROR regdb_transaction_commit(void)
+{
+	return (regdb->transaction_commit(regdb) == 0) ?
+		WERR_OK : WERR_REG_IO_FAILURE;
+}
+
+WERROR regdb_transaction_cancel(void)
+{
+	return (regdb->transaction_cancel(regdb) == 0) ?
+		WERR_OK : WERR_REG_IO_FAILURE;
+}
+
 /***********************************************************************
  return the tdb sequence number of the registry tdb.
  this is an indicator for the content of the registry
@@ -492,13 +510,97 @@ int regdb_get_seqnum(void)
 	return regdb->get_seqnum(regdb);
 }
 
+
+static WERROR regdb_delete_key_with_prefix(const char *keyname,
+					   const char *prefix)
+{
+	char *path;
+	WERROR werr = WERR_NOMEM;
+	TALLOC_CTX *mem_ctx = talloc_stackframe();
+
+	if (keyname == NULL) {
+		werr = WERR_INVALID_PARAM;
+		goto done;
+	}
+
+	if (prefix == NULL) {
+		path = discard_const_p(char, keyname);
+	} else {
+		path = talloc_asprintf(mem_ctx, "%s/%s", prefix, keyname);
+		if (path == NULL) {
+			goto done;
+		}
+	}
+
+	path = normalize_reg_path(mem_ctx, path);
+	if (path == NULL) {
+		goto done;
+	}
+
+	werr = ntstatus_to_werror(dbwrap_delete_bystring(regdb, path));
+
+	/* treat "not" found" as ok */
+	if (W_ERROR_EQUAL(werr, WERR_NOT_FOUND)) {
+		werr = WERR_OK;
+	}
+
+done:
+	talloc_free(mem_ctx);
+	return werr;
+}
+
+
+static WERROR regdb_delete_values(const char *keyname)
+{
+	return regdb_delete_key_with_prefix(keyname, REG_VALUE_PREFIX);
+}
+
+static WERROR regdb_delete_secdesc(const char *keyname)
+{
+	return regdb_delete_key_with_prefix(keyname, REG_SECDESC_PREFIX);
+}
+
+static WERROR regdb_delete_subkeylist(const char *keyname)
+{
+	return regdb_delete_key_with_prefix(keyname, NULL);
+}
+
+static WERROR regdb_delete_key_lists(const char *keyname)
+{
+	WERROR werr;
+
+	werr = regdb_delete_values(keyname);
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, (__location__ " Deleting %s/%s failed: %s\n",
+			  REG_VALUE_PREFIX, keyname, win_errstr(werr)));
+		goto done;
+	}
+
+	werr = regdb_delete_secdesc(keyname);
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, (__location__ " Deleting %s/%s failed: %s\n",
+			  REG_SECDESC_PREFIX, keyname, win_errstr(werr)));
+		goto done;
+	}
+
+	werr = regdb_delete_subkeylist(keyname);
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, (__location__ " Deleting %s failed: %s\n",
+			  keyname, win_errstr(werr)));
+		goto done;
+	}
+
+done:
+	return werr;
+}
+
 /***********************************************************************
  Add subkey strings to the registry tdb under a defined key
  fmt is the same format as tdb_pack except this function only supports
  fstrings
  ***********************************************************************/
 
-static bool regdb_store_keys_internal(const char *key, REGSUBKEY_CTR *ctr)
+static bool regdb_store_keys_internal(const char *key, struct regsubkey_ctr *ctr)
 {
 	TDB_DATA dbuf;
 	uint8 *buffer = NULL;
@@ -578,6 +680,16 @@ static bool regdb_store_keys_internal(const char *key, REGSUBKEY_CTR *ctr)
 		goto done;
 	}
 
+	/*
+	 * Delete a sorted subkey cache for regdb_key_exists, will be
+	 * recreated automatically
+	 */
+	keyname = talloc_asprintf(ctx, "%s/%s", REG_SORTED_SUBKEYS_PREFIX,
+				  keyname);
+	if (keyname != NULL) {
+		dbwrap_delete_bystring(regdb, keyname);
+	}
+
 done:
 	TALLOC_FREE(ctx);
 	SAFE_FREE(buffer);
@@ -589,14 +701,14 @@ done:
  do not currently exist
  ***********************************************************************/
 
-bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
+bool regdb_store_keys(const char *key, struct regsubkey_ctr *ctr)
 {
-	int num_subkeys, i;
+	int num_subkeys, old_num_subkeys, i;
 	char *path = NULL;
-	REGSUBKEY_CTR *subkeys = NULL, *old_subkeys = NULL;
+	struct regsubkey_ctr *subkeys = NULL, *old_subkeys = NULL;
 	char *oldkeyname = NULL;
 	TALLOC_CTX *ctx = talloc_stackframe();
-	NTSTATUS status;
+	WERROR werr;
 
 	if (!regdb_key_is_base_key(key) && !regdb_key_exists(key)) {
 		goto fail;
@@ -607,23 +719,28 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 	 * changed
 	 */
 
-	if (!(old_subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR))) {
+	werr = regsubkey_ctr_init(ctx, &old_subkeys);
+	if (!W_ERROR_IS_OK(werr)) {
 		DEBUG(0,("regdb_store_keys: talloc() failure!\n"));
 		return false;
 	}
 
 	regdb_fetch_keys(key, old_subkeys);
 
-	if ((ctr->num_subkeys && old_subkeys->num_subkeys) &&
-	    (ctr->num_subkeys == old_subkeys->num_subkeys)) {
-
-		for (i = 0; i<ctr->num_subkeys; i++) {
-			if (strcmp(ctr->subkeys[i],
-				   old_subkeys->subkeys[i]) != 0) {
+	num_subkeys = regsubkey_ctr_numkeys(ctr);
+	old_num_subkeys = regsubkey_ctr_numkeys(old_subkeys);
+	if ((num_subkeys && old_num_subkeys) &&
+	    (num_subkeys == old_num_subkeys)) {
+
+		for (i = 0; i < num_subkeys; i++) {
+			if (strcmp(regsubkey_ctr_specific_key(ctr, i),
+				   regsubkey_ctr_specific_key(old_subkeys, i))
+			    != 0)
+			{
 				break;
 			}
 		}
-		if (i == ctr->num_subkeys) {
+		if (i == num_subkeys) {
 			/*
 			 * Nothing changed, no point to even start a tdb
 			 * transaction
@@ -644,7 +761,8 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 	 * Re-fetch the old keys inside the transaction
 	 */
 
-	if (!(old_subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR))) {
+	werr = regsubkey_ctr_init(ctx, &old_subkeys);
+	if (!W_ERROR_IS_OK(werr)) {
 		DEBUG(0,("regdb_store_keys: talloc() failure!\n"));
 		goto cancel;
 	}
@@ -686,66 +804,14 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 			continue;
 		}
 
-		/* (a) Delete the value list for this key */
-
-		path = talloc_asprintf(ctx, "%s/%s/%s",
-				REG_VALUE_PREFIX,
-				key,
-				oldkeyname );
-		if (!path) {
-			goto cancel;
-		}
-		path = normalize_reg_path(ctx, path);
-		if (!path) {
-			goto cancel;
-		}
-		/* Ignore errors here, we might have no values around */
-		dbwrap_delete_bystring(regdb, path);
-		TALLOC_FREE(path);
-
-		/* (b) Delete the secdesc for this key */
-
-		path = talloc_asprintf(ctx, "%s/%s/%s",
-				REG_SECDESC_PREFIX,
-				key,
-				oldkeyname );
-		if (!path) {
-			goto cancel;
-		}
-		path = normalize_reg_path(ctx, path);
+		path = talloc_asprintf(ctx, "%s/%s", key, oldkeyname);
 		if (!path) {
 			goto cancel;
 		}
-		status = dbwrap_delete_bystring(regdb, path);
-		/* Don't fail if there are no values around. */
-		if (!NT_STATUS_IS_OK(status) &&
-		    !NT_STATUS_EQUAL(status, NT_STATUS_NOT_FOUND))
-		{
-			DEBUG(1, ("Deleting %s failed: %s\n", path,
-				  nt_errstr(status)));
-			goto cancel;
-		}
-		TALLOC_FREE(path);
 
-		/* (c) Delete the list of subkeys of this key */
+		werr = regdb_delete_key_lists(path);
+		W_ERROR_NOT_OK_GOTO(werr, cancel);
 
-		path = talloc_asprintf(ctx, "%s/%s", key, oldkeyname);
-		if (!path) {
-			goto cancel;
-		}
-		path = normalize_reg_path(ctx, path);
-		if (!path) {
-			goto cancel;
-		}
-		status = dbwrap_delete_bystring(regdb, path);
-		/* Don't fail if the subkey record was not found. */
-		if (!NT_STATUS_IS_OK(status) &&
-		    !NT_STATUS_EQUAL(status, NT_STATUS_NOT_FOUND))
-		{
-			DEBUG(1, ("Deleting %s failed: %s\n", path,
-				  nt_errstr(status)));
-			goto cancel;
-		}
 		TALLOC_FREE(path);
 	}
 
@@ -764,7 +830,8 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 	num_subkeys = regsubkey_ctr_numkeys(ctr);
 
 	if (num_subkeys == 0) {
-		if (!(subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR)) ) {
+		werr = regsubkey_ctr_init(ctx, &subkeys);
+		if (!W_ERROR_IS_OK(werr)) {
 			DEBUG(0,("regdb_store_keys: talloc() failure!\n"));
 			goto cancel;
 		}
@@ -785,7 +852,8 @@ bool regdb_store_keys(const char *key, REGSUBKEY_CTR *ctr)
 		if (!path) {
 			goto cancel;
 		}
-		if (!(subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR)) ) {
+		werr = regsubkey_ctr_init(ctx, &subkeys);
+		if (!W_ERROR_IS_OK(werr)) {
 			DEBUG(0,("regdb_store_keys: talloc() failure!\n"));
 			goto cancel;
 		}
@@ -822,6 +890,139 @@ fail:
 	return false;
 }
 
+static WERROR regdb_create_subkey(const char *key, const char *subkey)
+{
+	WERROR werr;
+	struct regsubkey_ctr *subkeys;
+	TALLOC_CTX *mem_ctx = talloc_stackframe();
+
+	if (!regdb_key_is_base_key(key) && !regdb_key_exists(key)) {
+		werr = WERR_NOT_FOUND;
+		goto done;
+	}
+
+	werr = regsubkey_ctr_init(mem_ctx, &subkeys);
+	W_ERROR_NOT_OK_GOTO_DONE(werr);
+
+	if (regdb_fetch_keys(key, subkeys) < 0) {
+		werr = WERR_REG_IO_FAILURE;
+		goto done;
+	}
+
+	if (regsubkey_ctr_key_exists(subkeys, subkey)) {
+		werr = WERR_OK;
+		goto done;
+	}
+
+	talloc_free(subkeys);
+
+	werr = regdb_transaction_start();
+	W_ERROR_NOT_OK_GOTO_DONE(werr);
+
+	werr = regsubkey_ctr_init(mem_ctx, &subkeys);
+	W_ERROR_NOT_OK_GOTO(werr, cancel);
+
+	if (regdb_fetch_keys(key, subkeys) < 0) {
+		werr = WERR_REG_IO_FAILURE;
+		goto cancel;
+	}
+
+	werr = regsubkey_ctr_addkey(subkeys, subkey);
+	W_ERROR_NOT_OK_GOTO(werr, cancel);
+
+	if (!regdb_store_keys_internal(key, subkeys)) {
+		DEBUG(0, (__location__ " failed to store new subkey list for "
+			 "parent key %s\n", key));
+		werr = WERR_REG_IO_FAILURE;
+		goto cancel;
+	}
+
+	werr = regdb_transaction_commit();
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(0, (__location__ " failed to commit transaction: %s\n",
+			 win_errstr(werr)));
+	}
+
+	goto done;
+
+cancel:
+	werr = regdb_transaction_cancel();
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(0, (__location__ " failed to cancel transaction: %s\n",
+			 win_errstr(werr)));
+	}
+
+done:
+	talloc_free(mem_ctx);
+	return werr;
+}
+
+static WERROR regdb_delete_subkey(const char *key, const char *subkey)
+{
+	WERROR werr, werr2;
+	struct regsubkey_ctr *subkeys;
+	char *path;
+	TALLOC_CTX *mem_ctx = talloc_stackframe();
+
+	if (!regdb_key_is_base_key(key) && !regdb_key_exists(key)) {
+		werr = WERR_NOT_FOUND;
+		goto done;
+	}
+
+	path = talloc_asprintf(mem_ctx, "%s/%s", key, subkey);
+	if (path == NULL) {
+		werr = WERR_NOMEM;
+		goto done;
+	}
+
+	if (!regdb_key_exists(path)) {
+		werr = WERR_OK;
+		goto done;
+	}
+
+	werr = regdb_transaction_start();
+	W_ERROR_NOT_OK_GOTO_DONE(werr);
+
+	werr = regdb_delete_key_lists(path);
+	W_ERROR_NOT_OK_GOTO(werr, cancel);
+
+	werr = regsubkey_ctr_init(mem_ctx, &subkeys);
+	W_ERROR_NOT_OK_GOTO(werr, cancel);
+
+	if (regdb_fetch_keys(key, subkeys) < 0) {
+		werr = WERR_REG_IO_FAILURE;
+		goto cancel;
+	}
+
+	werr = regsubkey_ctr_delkey(subkeys, subkey);
+	W_ERROR_NOT_OK_GOTO(werr, cancel);
+
+	if (!regdb_store_keys_internal(key, subkeys)) {
+		DEBUG(0, (__location__ " failed to store new subkey_list for "
+			 "parent key %s\n", key));
+		werr = WERR_REG_IO_FAILURE;
+		goto cancel;
+	}
+
+	werr = regdb_transaction_commit();
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(0, (__location__ " failed to commit transaction: %s\n",
+			 win_errstr(werr)));
+	}
+
+	goto done;
+
+cancel:
+	werr2 = regdb_transaction_cancel();
+	if (!W_ERROR_IS_OK(werr2)) {
+		DEBUG(0, (__location__ " failed to cancel transaction: %s\n",
+			 win_errstr(werr2)));
+	}
+
+done:
+	talloc_free(mem_ctx);
+	return werr;
+}
 
 static TDB_DATA regdb_fetch_key_internal(TALLOC_CTX *mem_ctx, const char *key)
 {
@@ -871,6 +1072,223 @@ done:
 	return ret;
 }
 
+/*
+ * regdb_key_exists() is a very frequent operation. It can be quite
+ * time-consuming to fully fetch the parent's subkey list, talloc_strdup all
+ * subkeys and then compare the keyname linearly to all the parent's subkeys.
+ *
+ * The following code tries to make this operation as efficient as possible:
+ * Per registry key we create a list of subkeys that is very efficient to
+ * search for existence of a subkey. Its format is:
+ *
+ * 4 bytes num_subkeys
+ * 4*num_subkey bytes offset into the string array
+ * then follows a sorted list of subkeys in uppercase
+ *
+ * This record is created by create_sorted_subkeys() on demand if it does not
+ * exist. scan_parent_subkeys() uses regdb->parse_record to search the sorted
+ * list, the parsing code and the binary search can be found in
+ * parent_subkey_scanner. The code uses parse_record() to avoid a memcpy of
+ * the potentially large subkey record.
+ *
+ * The sorted subkey record is deleted in regdb_store_keys_internal and
+ * recreated on demand.
+ */
+
+static int cmp_keynames(const void *p1, const void *p2)
+{
+	return StrCaseCmp(*((char **)p1), *((char **)p2));
+}
+
+static bool create_sorted_subkeys(const char *key, const char *sorted_keyname)
+{
+	char **sorted_subkeys;
+	struct regsubkey_ctr *ctr;
+	bool result = false;
+	NTSTATUS status;
+	char *buf;
+	char *p;
+	int i, res;
+	size_t len;
+	int num_subkeys;
+	WERROR werr;
+
+	if (regdb->transaction_start(regdb) != 0) {
+		DEBUG(0, ("create_sorted_subkeys: transaction_start "
+			  "failed\n"));
+		return false;
+	}
+
+	werr = regsubkey_ctr_init(talloc_tos(), &ctr);
+	if (!W_ERROR_IS_OK(werr)) {
+		goto fail;
+	}
+
+	res = regdb_fetch_keys(key, ctr);
+	if (res == -1) {
+		goto fail;
+	}
+
+	num_subkeys = regsubkey_ctr_numkeys(ctr);
+	sorted_subkeys = talloc_array(ctr, char *, num_subkeys);
+	if (sorted_subkeys == NULL) {
+		goto fail;
+	}
+
+	len = 4 + 4*num_subkeys;
+
+	for (i = 0; i < num_subkeys; i++) {
+		sorted_subkeys[i] = talloc_strdup_upper(sorted_subkeys,
+					regsubkey_ctr_specific_key(ctr, i));
+		if (sorted_subkeys[i] == NULL) {
+			goto fail;
+		}
+		len += strlen(sorted_subkeys[i])+1;
+	}
+
+	qsort(sorted_subkeys, num_subkeys, sizeof(char *), cmp_keynames);
+
+	buf = talloc_array(ctr, char, len);
+	if (buf == NULL) {
+		goto fail;
+	}
+	p = buf + 4 + 4*num_subkeys;
+
+	SIVAL(buf, 0, num_subkeys);
+
+	for (i=0; i < num_subkeys; i++) {
+		ptrdiff_t offset = p - buf;
+		SIVAL(buf, 4 + 4*i, offset);
+		strlcpy(p, sorted_subkeys[i], len-offset);
+		p += strlen(sorted_subkeys[i]) + 1;
+	}
+
+	status = dbwrap_store_bystring(
+		regdb, sorted_keyname, make_tdb_data((uint8_t *)buf, len),
+		TDB_REPLACE);
+	if (!NT_STATUS_IS_OK(status)) {
+		/*
+		 * Don't use a "goto fail;" here, this would commit the broken
+		 * transaction. See below for an explanation.
+		 */
+		if (regdb->transaction_cancel(regdb) == -1) {
+			DEBUG(0, ("create_sorted_subkeys: transaction_cancel "
+				  "failed\n"));
+		}
+		TALLOC_FREE(ctr);
+		return false;
+	}
+
+	result = true;
+ fail:
+	/*
+	 * We only get here via the "goto fail" when we did not write anything
+	 * yet. Using transaction_commit even in a failure case is necessary
+	 * because this (disposable) call might be nested in other
+	 * transactions. Doing a cancel here would destroy the possibility of
+	 * a transaction_commit for transactions that we might be wrapped in.
+	 */
+	if (regdb->transaction_commit(regdb) == -1) {
+		DEBUG(0, ("create_sorted_subkeys: transaction_start "
+			  "failed\n"));
+		goto fail;
+	}
+
+	TALLOC_FREE(ctr);
+	return result;
+}
+
+struct scan_subkey_state {
+	char *name;
+	bool scanned;
+	bool found;
+};
+
+static int parent_subkey_scanner(TDB_DATA key, TDB_DATA data,
+				 void *private_data)
+{
+	struct scan_subkey_state *state =
+		(struct scan_subkey_state *)private_data;
+	uint32_t num_subkeys;
+	uint32_t l, u;
+
+	if (data.dsize < sizeof(uint32_t)) {
+		return -1;
+	}
+
+	state->scanned = true;
+	state->found = false;
+
+	tdb_unpack(data.dptr, data.dsize, "d", &num_subkeys);
+
+	l = 0;
+	u = num_subkeys;
+
+	while (l < u) {
+		uint32_t idx = (l+u)/2;
+		char *s = (char *)data.dptr + IVAL(data.dptr, 4 + 4*idx);
+		int comparison = strcmp(state->name, s);
+
+		if (comparison < 0) {
+			u = idx;
+		} else if (comparison > 0) {
+			l = idx + 1;
+		} else {
+			state->found = true;
+			return 0;
+		}
+	}
+	return 0;
+}
+
+static bool scan_parent_subkeys(const char *parent, const char *name)
+{
+	char *path = NULL;
+	char *key = NULL;
+	struct scan_subkey_state state = { 0, };
+	bool result = false;
+	int res;
+
+	state.name = NULL;
+
+	path = normalize_reg_path(talloc_tos(), parent);
+	if (path == NULL) {
+		goto fail;
+	}
+
+	key = talloc_asprintf(talloc_tos(), "%s/%s",
+			      REG_SORTED_SUBKEYS_PREFIX, path);
+	if (key == NULL) {
+		goto fail;
+	}
+
+	state.name = talloc_strdup_upper(talloc_tos(), name);
+	if (state.name == NULL) {
+		goto fail;
+	}
+	state.scanned = false;
+
+	res = regdb->parse_record(regdb, string_term_tdb_data(key),
+				  parent_subkey_scanner, &state);
+
+	if (state.scanned) {
+		result = state.found;
+	} else {
+		if (!create_sorted_subkeys(path, key)) {
+			goto fail;
+		}
+		res = regdb->parse_record(regdb, string_term_tdb_data(key),
+					  parent_subkey_scanner, &state);
+		if ((res == 0) && (state.scanned)) {
+			result = state.found;
+		}
+	}
+
+ fail:
+	TALLOC_FREE(path);
+	TALLOC_FREE(state.name);
+	return result;
+}
 
 /**
  * Check for the existence of a key.
@@ -907,26 +1325,8 @@ static bool regdb_key_exists(const char *key)
 		value = regdb_fetch_key_internal(mem_ctx, path);
 		ret = (value.dptr != NULL);
 	} else {
-		/* get the list of subkeys of the parent key */
-		uint32 num_items, len, i;
-		fstring subkeyname;
-
 		*p = '\0';
-		p++;
-		value = regdb_fetch_key_internal(mem_ctx, path);
-		if (value.dptr == NULL) {
-			goto done;
-		}
-
-		len = tdb_unpack(value.dptr, value.dsize, "d", &num_items);
-		for (i = 0; i < num_items; i++) {
-			len += tdb_unpack(value.dptr +len, value.dsize -len,
-					  "f", &subkeyname);
-			if (strequal(subkeyname, p)) {
-				ret = true;
-				goto done;
-			}
-		}
+		ret = scan_parent_subkeys(path, p+1);
 	}
 
 done:
@@ -940,8 +1340,9 @@ done:
  released by the caller.
  ***********************************************************************/
 
-int regdb_fetch_keys(const char *key, REGSUBKEY_CTR *ctr)
+int regdb_fetch_keys(const char *key, struct regsubkey_ctr *ctr)
 {
+	WERROR werr;
 	uint32 num_items;
 	uint8 *buf;
 	uint32 buflen, len;
@@ -957,7 +1358,10 @@ int regdb_fetch_keys(const char *key, REGSUBKEY_CTR *ctr)
 		goto done;
 	}
 
-	ctr->seqnum = regdb_get_seqnum();
+	werr = regsubkey_ctr_set_seqnum(ctr, regdb_get_seqnum());
+	if (!W_ERROR_IS_OK(werr)) {
+		goto done;
+	}
 
 	value = regdb_fetch_key_internal(frame, key);
 
@@ -972,35 +1376,12 @@ int regdb_fetch_keys(const char *key, REGSUBKEY_CTR *ctr)
 	buflen = value.dsize;
 	len = tdb_unpack( buf, buflen, "d", &num_items);
 
-	/*
-	 * The following code breaks the abstraction that reg_objects.c sets
-	 * up with regsubkey_ctr_addkey(). But if we use that with the current
-	 * data structure of ctr->subkeys being an unsorted array, we end up
-	 * with an O(n^2) algorithm for retrieving keys from the tdb
-	 * file. This is pretty pointless, as we have to trust the data
-	 * structure on disk not to have duplicates anyway. The alternative to
-	 * breaking this abstraction would be to set up a more sophisticated
-	 * data structure in REGSUBKEY_CTR.
-	 *
-	 * This makes "net conf list" for a registry with >1000 shares
-	 * actually usable :-)
-	 */
-
-	ctr->subkeys = talloc_array(ctr, char *, num_items);
-	if (ctr->subkeys == NULL) {
-		DEBUG(5, ("regdb_fetch_keys: could not allocate subkeys\n"));
-		goto done;
-	}
-	ctr->num_subkeys = num_items;
-
 	for (i=0; i<num_items; i++) {
 		len += tdb_unpack(buf+len, buflen-len, "f", subkeyname);
-		ctr->subkeys[i] = talloc_strdup(ctr->subkeys, subkeyname);
-		if (ctr->subkeys[i] == NULL) {
-			DEBUG(5, ("regdb_fetch_keys: could not allocate "
-				  "subkeyname\n"));
-			TALLOC_FREE(ctr->subkeys);
-			ctr->num_subkeys = 0;
+		werr = regsubkey_ctr_addkey(ctr, subkeyname);
+		if (!W_ERROR_IS_OK(werr)) {
+			DEBUG(5, ("regdb_fetch_keys: regsubkey_ctr_addkey "
+				  "failed: %s\n", win_errstr(werr)));
 			goto done;
 		}
 	}
@@ -1238,7 +1619,6 @@ static WERROR regdb_set_secdesc(const char *key,
 {
 	TALLOC_CTX *mem_ctx = talloc_stackframe();
 	char *tdbkey;
-	NTSTATUS status;
 	WERROR err = WERR_NOMEM;
 	TDB_DATA tdbdata;
 
@@ -1255,36 +1635,27 @@ static WERROR regdb_set_secdesc(const char *key,
 
 	if (secdesc == NULL) {
 		/* assuming a delete */
-		status = dbwrap_trans_delete_bystring(regdb, tdbkey);
-		if (NT_STATUS_IS_OK(status)) {
-			err = WERR_OK;
-		} else {
-			err = ntstatus_to_werror(status);
-		}
+		err = ntstatus_to_werror(dbwrap_trans_delete_bystring(regdb,
+								      tdbkey));
 		goto done;
 	}
 
 	err = ntstatus_to_werror(marshall_sec_desc(mem_ctx, secdesc,
 						   &tdbdata.dptr,
 						   &tdbdata.dsize));
-	if (!W_ERROR_IS_OK(err)) {
-		goto done;
-	}
+	W_ERROR_NOT_OK_GOTO_DONE(err);
 
-	status = dbwrap_trans_store_bystring(regdb, tdbkey, tdbdata, 0);
-	if (!NT_STATUS_IS_OK(status)) {
-		err = ntstatus_to_werror(status);
-		goto done;
-	}
+	err = ntstatus_to_werror(dbwrap_trans_store_bystring(regdb, tdbkey,
+							     tdbdata, 0));
 
  done:
 	TALLOC_FREE(mem_ctx);
 	return err;
 }
 
-bool regdb_subkeys_need_update(REGSUBKEY_CTR *subkeys)
+bool regdb_subkeys_need_update(struct regsubkey_ctr *subkeys)
 {
-	return (regdb_get_seqnum() != subkeys->seqnum);
+	return (regdb_get_seqnum() != regsubkey_ctr_get_seqnum(subkeys));
 }
 
 bool regdb_values_need_update(REGVAL_CTR *values)
@@ -1301,6 +1672,8 @@ REGISTRY_OPS regdb_ops = {
 	.fetch_values = regdb_fetch_values,
 	.store_subkeys = regdb_store_keys,
 	.store_values = regdb_store_values,
+	.create_subkey = regdb_create_subkey,
+	.delete_subkey = regdb_delete_subkey,
 	.get_secdesc = regdb_get_secdesc,
 	.set_secdesc = regdb_set_secdesc,
 	.subkeys_need_update = regdb_subkeys_need_update,
diff --git a/source3/registry/reg_backend_hkpt_params.c b/source3/registry/reg_backend_hkpt_params.c
index 2ed5e78e1c..c67f7b3ea4 100644
--- a/source3/registry/reg_backend_hkpt_params.c
+++ b/source3/registry/reg_backend_hkpt_params.c
@@ -59,7 +59,7 @@ static int hkpt_params_fetch_values(const char *key, REGVAL_CTR *regvals)
 }
 
 static int hkpt_params_fetch_subkeys(const char *key,
-					 REGSUBKEY_CTR *subkey_ctr)
+					 struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_backend_netlogon_params.c b/source3/registry/reg_backend_netlogon_params.c
index 71f88144c8..17abf038a6 100644
--- a/source3/registry/reg_backend_netlogon_params.c
+++ b/source3/registry/reg_backend_netlogon_params.c
@@ -46,7 +46,7 @@ static int netlogon_params_fetch_values(const char *key, REGVAL_CTR *regvals)
 }
 
 static int netlogon_params_fetch_subkeys(const char *key,
-					 REGSUBKEY_CTR *subkey_ctr)
+					 struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_backend_perflib.c b/source3/registry/reg_backend_perflib.c
index 999bca2682..e23c87efe8 100644
--- a/source3/registry/reg_backend_perflib.c
+++ b/source3/registry/reg_backend_perflib.c
@@ -95,7 +95,7 @@ static int perflib_fetch_values(const char *key, REGVAL_CTR *regvals)
 }
 
 static int perflib_fetch_subkeys(const char *key,
-					 REGSUBKEY_CTR *subkey_ctr)
+				 struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_backend_printing.c b/source3/registry/reg_backend_printing.c
index 5c1e6eb543..192bc78e09 100644
--- a/source3/registry/reg_backend_printing.c
+++ b/source3/registry/reg_backend_printing.c
@@ -42,8 +42,8 @@ struct reg_dyn_tree {
 	const char *path;
 
 	/* callbscks for fetch/store operations */
-	int ( *fetch_subkeys) ( const char *path, REGSUBKEY_CTR *subkeys );
-	bool (*store_subkeys) ( const char *path, REGSUBKEY_CTR *subkeys );
+	int ( *fetch_subkeys) ( const char *path, struct regsubkey_ctr *subkeys );
+	bool (*store_subkeys) ( const char *path, struct regsubkey_ctr *subkeys );
 	int  (*fetch_values)  ( const char *path, REGVAL_CTR *values );
 	bool (*store_values)  ( const char *path, REGVAL_CTR *values );
 };
@@ -77,7 +77,7 @@ static const char *dos_basename(const char *path)
  *********************************************************************
  *********************************************************************/
 
-static int key_forms_fetch_keys(const char *key, REGSUBKEY_CTR *subkeys)
+static int key_forms_fetch_keys(const char *key, struct regsubkey_ctr *subkeys)
 {
 	char *p = reg_remaining_path(talloc_tos(), key + strlen(KEY_FORMS));
 
@@ -196,7 +196,7 @@ static char *strip_printers_prefix(const char *key)
 /*********************************************************************
  *********************************************************************/
 
-static int key_printers_fetch_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static int key_printers_fetch_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	int n_services = lp_numservices();
 	int snum;
@@ -275,7 +275,7 @@ done:
  keyname is the sharename and not the printer name.
  *********************************************************************/
 
-static bool add_printers_by_registry( REGSUBKEY_CTR *subkeys )
+static bool add_printers_by_registry( struct regsubkey_ctr *subkeys )
 {
 	int i, num_keys, snum;
 	char *printername;
@@ -310,7 +310,7 @@ static bool add_printers_by_registry( REGSUBKEY_CTR *subkeys )
 /**********************************************************************
  *********************************************************************/
 
-static bool key_printers_store_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static bool key_printers_store_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	char *printers_key;
 	char *printername, *printerdatakey;
@@ -738,7 +738,7 @@ static bool key_printers_store_values( const char *key, REGVAL_CTR *values )
  *********************************************************************
  *********************************************************************/
 
-static int key_driver_fetch_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static int key_driver_fetch_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	const char *environments[] = {
 		"Windows 4.0",
@@ -1085,7 +1085,7 @@ static int key_driver_fetch_values( const char *key, REGVAL_CTR *values )
  *********************************************************************
  *********************************************************************/
 
-static int key_print_fetch_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static int key_print_fetch_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	int key_len = strlen(key);
 
@@ -1192,7 +1192,7 @@ static int match_registry_path(const char *key)
 /***********************************************************************
  **********************************************************************/
 
-static int regprint_fetch_reg_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static int regprint_fetch_reg_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	int i = match_registry_path( key );
 
@@ -1208,7 +1208,7 @@ static int regprint_fetch_reg_keys( const char *key, REGSUBKEY_CTR *subkeys )
 /**********************************************************************
  *********************************************************************/
 
-static bool regprint_store_reg_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static bool regprint_store_reg_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	int i = match_registry_path( key );
 
diff --git a/source3/registry/reg_backend_prod_options.c b/source3/registry/reg_backend_prod_options.c
index 7ac5c5b4b9..3e9d32cd97 100644
--- a/source3/registry/reg_backend_prod_options.c
+++ b/source3/registry/reg_backend_prod_options.c
@@ -59,7 +59,7 @@ static int prod_options_fetch_values(const char *key, REGVAL_CTR *regvals)
 }
 
 static int prod_options_fetch_subkeys(const char *key,
-				      REGSUBKEY_CTR *subkey_ctr)
+				      struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_backend_shares.c b/source3/registry/reg_backend_shares.c
index ee9e5dc5a1..a30ae34b4e 100644
--- a/source3/registry/reg_backend_shares.c
+++ b/source3/registry/reg_backend_shares.c
@@ -66,7 +66,7 @@ static char* trim_reg_path( const char *path )
  Caller is responsible for freeing memory to **subkeys
  *********************************************************************/
  
-static int shares_subkey_info( const char *key, REGSUBKEY_CTR *subkey_ctr )
+static int shares_subkey_info( const char *key, struct regsubkey_ctr *subkey_ctr )
 {
 	char 		*path;
 	bool		top_level = False;
@@ -134,7 +134,7 @@ static int shares_value_info( const char *key, REGVAL_CTR *val )
  (for now at least)
  *********************************************************************/
 
-static bool shares_store_subkey( const char *key, REGSUBKEY_CTR *subkeys )
+static bool shares_store_subkey( const char *key, struct regsubkey_ctr *subkeys )
 {
 	return False;
 }
diff --git a/source3/registry/reg_backend_smbconf.c b/source3/registry/reg_backend_smbconf.c
index 2e4a5f1c1d..8e1bbcab6f 100644
--- a/source3/registry/reg_backend_smbconf.c
+++ b/source3/registry/reg_backend_smbconf.c
@@ -25,16 +25,26 @@
 
 extern REGISTRY_OPS regdb_ops;		/* these are the default */
 
-static int smbconf_fetch_keys( const char *key, REGSUBKEY_CTR *subkey_ctr )
+static int smbconf_fetch_keys( const char *key, struct regsubkey_ctr *subkey_ctr )
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
 
-static bool smbconf_store_keys( const char *key, REGSUBKEY_CTR *subkeys )
+static bool smbconf_store_keys( const char *key, struct regsubkey_ctr *subkeys )
 {
 	return regdb_ops.store_subkeys(key, subkeys);
 }
 
+static WERROR smbconf_create_subkey(const char *key, const char *subkey)
+{
+	return regdb_ops.create_subkey(key, subkey);
+}
+
+static WERROR smbconf_delete_subkey(const char *key, const char *subkey)
+{
+	return regdb_ops.delete_subkey(key, subkey);
+}
+
 static int smbconf_fetch_values( const char *key, REGVAL_CTR *val )
 {
 	return regdb_ops.fetch_values(key, val);
@@ -79,6 +89,8 @@ REGISTRY_OPS smbconf_reg_ops = {
 	.fetch_values = smbconf_fetch_values,
 	.store_subkeys = smbconf_store_keys,
 	.store_values = smbconf_store_values,
+	.create_subkey = smbconf_create_subkey,
+	.delete_subkey = smbconf_delete_subkey,
 	.reg_access_check = smbconf_reg_access_check,
 	.get_secdesc = smbconf_get_secdesc,
 	.set_secdesc = smbconf_set_secdesc,
diff --git a/source3/registry/reg_backend_tcpip_params.c b/source3/registry/reg_backend_tcpip_params.c
index db7df5dd8f..a6aa2fc2ea 100644
--- a/source3/registry/reg_backend_tcpip_params.c
+++ b/source3/registry/reg_backend_tcpip_params.c
@@ -56,7 +56,7 @@ static int tcpip_params_fetch_values(const char *key, REGVAL_CTR *regvals)
 }
 
 static int tcpip_params_fetch_subkeys(const char *key,
-					 REGSUBKEY_CTR *subkey_ctr)
+				      struct regsubkey_ctr *subkey_ctr)
 {
 	return regdb_ops.fetch_subkeys(key, subkey_ctr);
 }
diff --git a/source3/registry/reg_dispatcher.c b/source3/registry/reg_dispatcher.c
index c160622054..f8c382536f 100644
--- a/source3/registry/reg_dispatcher.c
+++ b/source3/registry/reg_dispatcher.c
@@ -80,7 +80,7 @@ static WERROR construct_registry_sd(TALLOC_CTX *ctx, SEC_DESC **psd)
  High level wrapper function for storing registry subkeys
  ***********************************************************************/
 
-bool store_reg_keys( REGISTRY_KEY *key, REGSUBKEY_CTR *subkeys )
+bool store_reg_keys( REGISTRY_KEY *key, struct regsubkey_ctr *subkeys )
 {
 	if (key->ops && key->ops->store_subkeys)
 		return key->ops->store_subkeys(key->name, subkeys);
@@ -100,12 +100,30 @@ bool store_reg_values( REGISTRY_KEY *key, REGVAL_CTR *val )
 	return false;
 }
 
+WERROR create_reg_subkey(REGISTRY_KEY *key, const char *subkey)
+{
+	if (key->ops && key->ops->create_subkey) {
+		return key->ops->create_subkey(key->name, subkey);
+	}
+
+	return WERR_NOT_SUPPORTED;
+}
+
+WERROR delete_reg_subkey(REGISTRY_KEY *key, const char *subkey)
+{
+	if (key->ops && key->ops->delete_subkey) {
+		return key->ops->delete_subkey(key->name, subkey);
+	}
+
+	return WERR_NOT_SUPPORTED;
+}
+
 /***********************************************************************
  High level wrapper function for enumerating registry subkeys
  Initialize the TALLOC_CTX if necessary
  ***********************************************************************/
 
-int fetch_reg_keys( REGISTRY_KEY *key, REGSUBKEY_CTR *subkey_ctr )
+int fetch_reg_keys( REGISTRY_KEY *key, struct regsubkey_ctr *subkey_ctr )
 {
 	int result = -1;
 
@@ -143,7 +161,6 @@ bool regkey_access_check( REGISTRY_KEY *key, uint32 requested, uint32 *granted,
 	SEC_DESC *sec_desc;
 	NTSTATUS status;
 	WERROR err;
-	TALLOC_CTX *mem_ctx;
 
 	/* use the default security check if the backend has not defined its
 	 * own */
@@ -153,30 +170,20 @@ bool regkey_access_check( REGISTRY_KEY *key, uint32 requested, uint32 *granted,
 						  granted, token);
 	}
 
-	/*
-	 * The secdesc routines can't yet cope with a NULL talloc ctx sanely.
-	 */
-
-	if (!(mem_ctx = talloc_init("regkey_access_check"))) {
-		return false;
-	}
-
-	err = regkey_get_secdesc(mem_ctx, key, &sec_desc);
+	err = regkey_get_secdesc(talloc_tos(), key, &sec_desc);
 
 	if (!W_ERROR_IS_OK(err)) {
-		TALLOC_FREE(mem_ctx);
 		return false;
 	}
 
 	se_map_generic( &requested, &reg_generic_map );
 
 	status =se_access_check(sec_desc, token, requested, granted);
+	TALLOC_FREE(sec_desc);
 	if (!NT_STATUS_IS_OK(status)) {
-		TALLOC_FREE(mem_ctx);
 		return false;
 	}
 
-	TALLOC_FREE(mem_ctx);
 	return NT_STATUS_IS_OK(status);
 }
 
@@ -216,7 +223,7 @@ WERROR regkey_set_secdesc(REGISTRY_KEY *key,
  * Check whether the in-memory version of the subkyes of a
  * registry key needs update from disk.
  */
-bool reg_subkeys_need_update(REGISTRY_KEY *key, REGSUBKEY_CTR *subkeys)
+bool reg_subkeys_need_update(REGISTRY_KEY *key, struct regsubkey_ctr *subkeys)
 {
 	if (key->ops && key->ops->subkeys_need_update)
 	{
diff --git a/source3/registry/reg_eventlog.c b/source3/registry/reg_eventlog.c
index 8994acf107..c02318beac 100644
--- a/source3/registry/reg_eventlog.c
+++ b/source3/registry/reg_eventlog.c
@@ -35,16 +35,18 @@ bool eventlog_init_keys(void)
 	const char **elogs = lp_eventlog_list();
 	char *evtlogpath = NULL;
 	char *evtfilepath = NULL;
-	REGSUBKEY_CTR *subkeys;
+	struct regsubkey_ctr *subkeys;
 	REGVAL_CTR *values;
 	uint32 uiMaxSize;
 	uint32 uiRetention;
 	uint32 uiCategoryCount;
 	UNISTR2 data;
 	TALLOC_CTX *ctx = talloc_tos();
+	WERROR werr;
 
 	while (elogs && *elogs) {
-		if (!(subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR ) ) ) {
+		werr = regsubkey_ctr_init(ctx, &subkeys);
+		if (!W_ERROR_IS_OK(werr)) {
 			DEBUG( 0, ( "talloc() failure!\n" ) );
 			return False;
 		}
@@ -70,7 +72,8 @@ bool eventlog_init_keys(void)
 		DEBUG( 5,
 		       ( "Adding key of [%s] to path of [%s]\n", *elogs,
 			 evtlogpath ) );
-		if (!(subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR))) {
+		werr = regsubkey_ctr_init(ctx, &subkeys);
+		if (!W_ERROR_IS_OK(werr)) {
 			DEBUG( 0, ( "talloc() failure!\n" ) );
 			return False;
 		}
@@ -197,7 +200,7 @@ bool eventlog_add_source( const char *eventlog, const char *sourcename,
 	const char **elogs = lp_eventlog_list(  );
 	char **wrklist, **wp;
 	char *evtlogpath = NULL;
-	REGSUBKEY_CTR *subkeys;
+	struct regsubkey_ctr *subkeys;
 	REGVAL_CTR *values;
 	REGISTRY_VALUE *rval;
 	UNISTR2 data;
@@ -207,6 +210,7 @@ bool eventlog_add_source( const char *eventlog, const char *sourcename,
 	int i;
 	int numsources;
 	TALLOC_CTX *ctx = talloc_tos();
+	WERROR werr;
 
 	if (!elogs) {
 		return False;
@@ -315,7 +319,8 @@ bool eventlog_add_source( const char *eventlog, const char *sourcename,
 	TALLOC_FREE(values);
 	TALLOC_FREE(wrklist);	/*  */
 
-	if ( !( subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR ) ) ) {
+	werr = regsubkey_ctr_init(ctx, &subkeys);
+	if (!W_ERROR_IS_OK(werr)) {
 		DEBUG( 0, ( "talloc() failure!\n" ) );
 		return False;
 	}
@@ -342,7 +347,8 @@ bool eventlog_add_source( const char *eventlog, const char *sourcename,
 
 	/* now allocate room for the source's subkeys */
 
-	if ( !( subkeys = TALLOC_ZERO_P(ctx, REGSUBKEY_CTR ) ) ) {
+	werr = regsubkey_ctr_init(ctx, &subkeys);
+	if (!W_ERROR_IS_OK(werr)) {
 		DEBUG( 0, ( "talloc() failure!\n" ) );
 		return False;
 	}
diff --git a/source3/registry/reg_objects.c b/source3/registry/reg_objects.c
index 47122ccad2..b975ced324 100644
--- a/source3/registry/reg_objects.c
+++ b/source3/registry/reg_objects.c
@@ -24,25 +24,135 @@
 #undef DBGC_CLASS
 #define DBGC_CLASS DBGC_REGISTRY
 
+struct regsubkey_ctr {
+	uint32_t        num_subkeys;
+	char            **subkeys;
+	struct db_context *subkeys_hash;
+	int seqnum;
+};
+
 /**********************************************************************
 
- Note that the REGSUB_CTR and REGVAL_CTR objects *must* be talloc()'d
- since the methods use the object pointer as the talloc context for
- internal private data.
+ Note that the struct regsubkey_ctr and REGVAL_CTR objects *must* be
+ talloc()'d since the methods use the object pointer as the talloc
+ context for internal private data.
 
- There is no longer a regXXX_ctr_intit() and regXXX_ctr_destroy()
+ There is no longer a regval_ctr_intit() and regval_ctr_destroy()
  pair of functions.  Simply TALLOC_ZERO_P() and TALLOC_FREE() the
  object.
 
  **********************************************************************/
 
+WERROR regsubkey_ctr_init(TALLOC_CTX *mem_ctx, struct regsubkey_ctr **ctr)
+{
+	if (ctr == NULL) {
+		return WERR_INVALID_PARAM;
+	}
+
+	*ctr = talloc_zero(mem_ctx, struct regsubkey_ctr);
+	if (*ctr == NULL) {
+		return WERR_NOMEM;
+	}
+
+	(*ctr)->subkeys_hash = db_open_rbt(*ctr);
+	if ((*ctr)->subkeys_hash == NULL) {
+		talloc_free(*ctr);
+		return WERR_NOMEM;
+	}
+
+	return WERR_OK;
+}
+
+WERROR regsubkey_ctr_set_seqnum(struct regsubkey_ctr *ctr, int seqnum)
+{
+	if (ctr == NULL) {
+		return WERR_INVALID_PARAM;
+	}
+
+	ctr->seqnum = seqnum;
+
+	return WERR_OK;
+}
+
+int regsubkey_ctr_get_seqnum(struct regsubkey_ctr *ctr)
+{
+	if (ctr == NULL) {
+		return -1;
+	}
+
+	return ctr->seqnum;
+}
+
+static WERROR regsubkey_ctr_hash_keyname(struct regsubkey_ctr *ctr,
+					 const char *keyname,
+					 uint32 idx)
+{
+	WERROR werr;
+
+	werr = ntstatus_to_werror(dbwrap_store_bystring(ctr->subkeys_hash,
+						keyname,
+						make_tdb_data((uint8 *)&idx,
+							      sizeof(idx)),
+						TDB_REPLACE));
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, ("error hashing new key '%s' in container: %s\n",
+			  keyname, win_errstr(werr)));
+	}
+
+	return werr;
+}
+
+static WERROR regsubkey_ctr_unhash_keyname(struct regsubkey_ctr *ctr,
+					   const char *keyname)
+{
+	WERROR werr;
+
+	werr = ntstatus_to_werror(dbwrap_delete_bystring(ctr->subkeys_hash,
+				  keyname));
+	if (!W_ERROR_IS_OK(werr)) {
+		DEBUG(1, ("error unhashing key '%s' in container: %s\n",
+			  keyname, win_errstr(werr)));
+	}
+
+	return werr;
+}
+
+static WERROR regsubkey_ctr_index_for_keyname(struct regsubkey_ctr *ctr,
+					      const char *keyname,
+					      uint32 *idx)
+{
+	TDB_DATA data;
+
+	if ((ctr == NULL) || (keyname == NULL)) {
+		return WERR_INVALID_PARAM;
+	}
+
+	data = dbwrap_fetch_bystring(ctr->subkeys_hash, ctr, keyname);
+	if (data.dptr == NULL) {
+		return WERR_NOT_FOUND;
+	}
+
+	if (data.dsize != sizeof(*idx)) {
+		talloc_free(data.dptr);
+		return WERR_INVALID_DATATYPE;
+	}
+
+	if (idx != NULL) {
+		*idx = *(uint32 *)data.dptr;
+	}
+
+	talloc_free(data.dptr);
+	return WERR_OK;
+}
+
 /***********************************************************************
  Add a new key to the array
  **********************************************************************/
 
-WERROR regsubkey_ctr_addkey( REGSUBKEY_CTR *ctr, const char *keyname )
+WERROR regsubkey_ctr_addkey( struct regsubkey_ctr *ctr, const char *keyname )
 {
 	char **newkeys;
+	WERROR werr;
 
 	if ( !keyname ) {
 		return WERR_OK;
@@ -68,6 +178,10 @@ WERROR regsubkey_ctr_addkey( REGSUBKEY_CTR *ctr, const char *keyname )
 		 */
 		return WERR_NOMEM;
 	}
+
+	werr = regsubkey_ctr_hash_keyname(ctr, keyname, ctr->num_subkeys);
+	W_ERROR_NOT_OK_RETURN(werr);
+
 	ctr->num_subkeys++;
 
 	return WERR_OK;
@@ -77,57 +191,64 @@ WERROR regsubkey_ctr_addkey( REGSUBKEY_CTR *ctr, const char *keyname )
  Delete a key from the array
  **********************************************************************/
 
-int regsubkey_ctr_delkey( REGSUBKEY_CTR *ctr, const char *keyname )
+WERROR regsubkey_ctr_delkey( struct regsubkey_ctr *ctr, const char *keyname )
 {
-	int i;
+	WERROR werr;
+	uint32 idx, j;
 
-	if ( !keyname )
-		return ctr->num_subkeys;
+	if (keyname == NULL) {
+		return WERR_INVALID_PARAM;
+	}
 
 	/* make sure the keyname is actually already there */
 
-	for ( i=0; i<ctr->num_subkeys; i++ ) {
-		if ( strequal( ctr->subkeys[i], keyname ) )
-			break;
-	}
+	werr = regsubkey_ctr_index_for_keyname(ctr, keyname, &idx);
+	W_ERROR_NOT_OK_RETURN(werr);
 
-	if ( i == ctr->num_subkeys )
-		return ctr->num_subkeys;
+	werr = regsubkey_ctr_unhash_keyname(ctr, keyname);
+	W_ERROR_NOT_OK_RETURN(werr);
 
 	/* update if we have any keys left */
 	ctr->num_subkeys--;
-	if ( i < ctr->num_subkeys )
-		memmove(&ctr->subkeys[i], &ctr->subkeys[i+1],
-			sizeof(char*) * (ctr->num_subkeys-i));
+	if (idx < ctr->num_subkeys) {
+		memmove(&ctr->subkeys[idx], &ctr->subkeys[idx+1],
+			sizeof(char *) * (ctr->num_subkeys - idx));
+
+		/* we have to re-hash rest of the array...  :-( */
+		for (j = idx; j < ctr->num_subkeys; j++) {
+			werr = regsubkey_ctr_hash_keyname(ctr, ctr->subkeys[j], j);
+			W_ERROR_NOT_OK_RETURN(werr);
+		}
+	}
 
-	return ctr->num_subkeys;
+	return WERR_OK;
 }
 
 /***********************************************************************
  Check for the existance of a key
  **********************************************************************/
 
-bool regsubkey_ctr_key_exists( REGSUBKEY_CTR *ctr, const char *keyname )
+bool regsubkey_ctr_key_exists( struct regsubkey_ctr *ctr, const char *keyname )
 {
-	int 	i;
+	WERROR werr;
 
 	if (!ctr->subkeys) {
 		return False;
 	}
 
-	for ( i=0; i<ctr->num_subkeys; i++ ) {
-		if ( strequal( ctr->subkeys[i],keyname ) )
-			return True;
+	werr = regsubkey_ctr_index_for_keyname(ctr, keyname, NULL);
+	if (!W_ERROR_IS_OK(werr)) {
+		return false;
 	}
 
-	return False;
+	return true;
 }
 
 /***********************************************************************
  How many keys does the container hold ?
  **********************************************************************/
 
-int regsubkey_ctr_numkeys( REGSUBKEY_CTR *ctr )
+int regsubkey_ctr_numkeys( struct regsubkey_ctr *ctr )
 {
 	return ctr->num_subkeys;
 }
@@ -136,7 +257,7 @@ int regsubkey_ctr_numkeys( REGSUBKEY_CTR *ctr )
  Retreive a specific key string
  **********************************************************************/
 
-char* regsubkey_ctr_specific_key( REGSUBKEY_CTR *ctr, uint32 key_index )
+char* regsubkey_ctr_specific_key( struct regsubkey_ctr *ctr, uint32_t key_index )
 {
 	if ( ! (key_index < ctr->num_subkeys) )
 		return NULL;
diff --git a/source3/registry/regfio.c b/source3/registry/regfio.c
index 5395f225f1..d002bd72e7 100644
--- a/source3/registry/regfio.c
+++ b/source3/registry/regfio.c
@@ -1693,7 +1693,7 @@ static int hashrec_cmp( REGF_HASH_REC *h1, REGF_HASH_REC *h2 )
 *******************************************************************/
 
  REGF_NK_REC* regfio_write_key( REGF_FILE *file, const char *name, 
-                               REGVAL_CTR *values, REGSUBKEY_CTR *subkeys, 
+                               REGVAL_CTR *values, struct regsubkey_ctr *subkeys,
                                SEC_DESC *sec_desc, REGF_NK_REC *parent )
 {
 	REGF_NK_REC *nk;