Index: uspace/app/bithenge/Makefile.linux
===================================================================
--- uspace/app/bithenge/Makefile.linux	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/Makefile.linux	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -27,5 +27,7 @@
 #
 
-CFLAGS += -fexec-charset=UTF-8 -finput-charset=UTF-8 -Wall -Wextra -Werror -Wno-clobbered -Wno-unused-parameter -Wmissing-prototypes -std=gnu99 -Werror-implicit-function-declaration -Wwrite-strings -pipe
+CFLAGS += -fexec-charset=UTF-8 -finput-charset=UTF-8 -std=gnu99 -pipe
+CFLAGS += -Wall -Wextra -Werror -Wno-clobbered -Wno-unused-parameter -Wmissing-prototypes -Werror-implicit-function-declaration -Wwrite-strings
+CFLAGS += -g
 CFLAGS += -Ilinux
 
Index: uspace/app/bithenge/blob.c
===================================================================
--- uspace/app/bithenge/blob.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/blob.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -296,4 +296,154 @@
 }
 
+typedef struct {
+	bithenge_blob_t base;
+	bithenge_blob_t *source;
+	aoff64_t offset;
+	aoff64_t size;
+	bool size_matters;
+} subblob_t;
+
+static inline subblob_t *blob_as_subblob(bithenge_blob_t *base)
+{
+	return (subblob_t *)base;
+}
+
+static inline bithenge_blob_t *subblob_as_blob(subblob_t *blob)
+{
+	return &blob->base;
+}
+
+static int subblob_size(bithenge_blob_t *base, aoff64_t *size)
+{
+	subblob_t *blob = blob_as_subblob(base);
+	if (blob->size_matters) {
+		*size = blob->size;
+		return EOK;
+	} else {
+		int rc = bithenge_blob_size(blob->source, size);
+		*size -= blob->offset;
+		return rc;
+	}
+}
+
+static int subblob_read(bithenge_blob_t *base, aoff64_t offset,
+    char *buffer, aoff64_t *size)
+{
+	subblob_t *blob = blob_as_subblob(base);
+	if (blob->size_matters) {
+		if (offset > blob->size)
+			return EINVAL;
+		*size = min(*size, blob->size - offset);
+	}
+	offset += blob->offset;
+	return bithenge_blob_read(blob->source, offset, buffer, size);
+}
+
+static int subblob_destroy(bithenge_blob_t *base)
+{
+	subblob_t *blob = blob_as_subblob(base);
+	bithenge_blob_dec_ref(blob->source);
+	free(blob);
+	return EOK;
+}
+
+static const bithenge_random_access_blob_ops_t subblob_ops = {
+	.size = subblob_size,
+	.read = subblob_read,
+	.destroy = subblob_destroy,
+};
+
+static bool is_subblob(bithenge_blob_t *blob)
+{
+	return blob->base.blob_ops == &subblob_ops;
+}
+
+static int new_subblob(bithenge_node_t **out, bithenge_blob_t *source,
+    aoff64_t offset, aoff64_t size, bool size_matters)
+{
+	assert(out);
+	assert(source);
+	int rc;
+	subblob_t *blob = 0;
+
+	if (is_subblob(source)) {
+		/* We can do some optimizations this way */
+		if (!size_matters)
+			size = 0;
+		subblob_t *source_subblob = blob_as_subblob(source);
+		if (source_subblob->size_matters &&
+		    offset + size > source_subblob->size) {
+			rc = EINVAL;
+			goto error;
+		}
+
+		if (source->base.refs == 1) {
+			source_subblob->offset += offset;
+			source_subblob->size -= offset;
+			if (size_matters) {
+				source_subblob->size_matters = true;
+				source_subblob->size = size;
+			}
+			*out = bithenge_blob_as_node(source);
+			return EOK;
+		}
+
+		if (!size_matters && source_subblob->size_matters) {
+			size_matters = true;
+			size = source_subblob->size - offset;
+		}
+		offset += source_subblob->offset;
+		source = source_subblob->source;
+		bithenge_blob_inc_ref(source);
+		bithenge_blob_dec_ref(subblob_as_blob(source_subblob));
+	}
+
+	blob = malloc(sizeof(*blob));
+	if (!blob) {
+		rc = ENOMEM;
+		goto error;
+	}
+	rc = bithenge_new_random_access_blob(subblob_as_blob(blob),
+	    &subblob_ops);
+	if (rc != EOK)
+		goto error;
+	blob->source = source;
+	blob->offset = offset;
+	blob->size = size;
+	blob->size_matters = size_matters;
+	*out = bithenge_blob_as_node(subblob_as_blob(blob));
+	return EOK;
+
+error:
+	bithenge_blob_dec_ref(source);
+	free(blob);
+	return rc;
+}
+
+/** Create a blob from data offset within another blob. This function takes
+ * ownership of a reference to @a blob.
+ * @param[out] out Stores the created blob node. On error, this is unchanged.
+ * @param[in] source The input blob.
+ * @param offset The offset within the input blob at which the new blob will start.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_new_offset_blob(bithenge_node_t **out, bithenge_blob_t *source,
+    aoff64_t offset)
+{
+	return new_subblob(out, source, offset, 0, false);
+}
+
+/** Create a blob from part of another blob. This function takes ownership of a
+ * reference to @a blob.
+ * @param[out] out Stores the created blob node. On error, this is unchanged.
+ * @param[in] source The input blob.
+ * @param offset The offset within the input blob at which the new blob will start.
+ * @param size The size of the new blob.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_new_subblob(bithenge_node_t **out, bithenge_blob_t *source,
+    aoff64_t offset, aoff64_t size)
+{
+	return new_subblob(out, source, offset, size, true);
+}
+
 /** Check whether the contents of two blobs are equal.
  * @memberof bithenge_blob_t
Index: uspace/app/bithenge/blob.h
===================================================================
--- uspace/app/bithenge/blob.h	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/blob.h	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -170,4 +170,16 @@
 }
 
+static inline int bithenge_blob_inc_ref(bithenge_blob_t *blob)
+{
+	return bithenge_node_inc_ref(bithenge_blob_as_node(blob));
+}
+
+static inline int bithenge_blob_dec_ref(bithenge_blob_t *blob)
+{
+	if (!blob)
+		return EOK;
+	return bithenge_node_dec_ref(bithenge_blob_as_node(blob));
+}
+
 int bithenge_new_random_access_blob(bithenge_blob_t *blob,
     const bithenge_random_access_blob_ops_t *ops);
@@ -182,4 +194,10 @@
     size_t len, bool needs_free);
 
+int bithenge_new_offset_blob(bithenge_node_t **out, bithenge_blob_t *blob,
+    aoff64_t offset);
+
+int bithenge_new_subblob(bithenge_node_t **out, bithenge_blob_t *blob,
+    aoff64_t offset, aoff64_t size);
+
 bool bithenge_blob_equal(bithenge_blob_t *a, bithenge_blob_t *b);
 
Index: uspace/app/bithenge/print.c
===================================================================
--- uspace/app/bithenge/print.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/print.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -49,5 +49,5 @@
 {
 	print_internal_data_t *data = (print_internal_data_t *)data_;
-	int rc;
+	int rc = EOK;
 	if (!data->first)
 		printf(", ");
@@ -59,5 +59,5 @@
 	rc = bithenge_print_node(data->type, key);
 	if (rc != EOK)
-		return rc;
+		goto end;
 	if (add_quotes)
 		printf("\"");
@@ -65,6 +65,9 @@
 	rc = bithenge_print_node(data->type, value);
 	if (rc != EOK)
-		return rc;
-	return EOK;
+		goto end;
+end:
+	bithenge_node_dec_ref(key);
+	bithenge_node_dec_ref(value);
+	return rc;
 }
 
Index: uspace/app/bithenge/script.c
===================================================================
--- uspace/app/bithenge/script.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/script.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -53,6 +53,8 @@
 	TOKEN_EOF,
 	TOKEN_IDENTIFIER,
+	TOKEN_LEFT_ARROW,
 
 	/* Keywords */
+	TOKEN_STRUCT,
 	TOKEN_TRANSFORM,
 } token_type_t;
@@ -181,4 +183,7 @@
 		if (!value) {
 			error_errno(state, ENOMEM);
+		} else if (!str_cmp(value, "struct")) {
+			state->token = TOKEN_STRUCT;
+			free(value);
 		} else if (!str_cmp(value, "transform")) {
 			state->token = TOKEN_TRANSFORM;
@@ -188,4 +193,11 @@
 			state->token_string = value;
 		}
+	} else if (ch == '<') {
+		state->token = ch;
+		state->buffer_pos++;
+		if (state->buffer[state->buffer_pos] == '-') {
+			state->buffer_pos++;
+			state->token = TOKEN_LEFT_ARROW;
+		}
 	} else {
 		state->token = ch;
@@ -207,4 +219,18 @@
 }
 
+/** Reallocate memory and handle failure by setting the error in the state. If
+ * an error occurs, the existing pointer will be returned. */
+static void *state_realloc(state_t *state, void *ptr, size_t size)
+{
+	if (state->error != EOK)
+		return ptr;
+	void *result = realloc(ptr, size);
+	if (result == NULL) {
+		error_errno(state, ENOMEM);
+		return ptr;
+	}
+	return result;
+}
+
 /** Expect and consume a certain token. If the next token is of the wrong type,
  * an error is caused. */
@@ -255,5 +281,5 @@
 
 /** Add a named transform. This function takes ownership of the name and a
- * reference to the transform. */
+ * reference to the transform. If an error has occurred, either may be null. */
 static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name)
 {
@@ -269,4 +295,46 @@
 	entry->next = state->transform_list;
 	state->transform_list = entry;
+}
+
+static bithenge_transform_t *parse_transform(state_t *state);
+
+static bithenge_transform_t *parse_struct(state_t *state)
+{
+	size_t num = 0;
+	bithenge_named_transform_t *subxforms;
+	/* We keep an extra space for the {NULL, NULL} terminator. */
+	subxforms = state_malloc(state, sizeof(*subxforms));
+	expect(state, TOKEN_STRUCT);
+	expect(state, '{');
+	while (state->error == EOK && state->token != '}') {
+		expect(state, '.');
+		subxforms[num].name = expect_identifier(state);
+		expect(state, TOKEN_LEFT_ARROW);
+		subxforms[num].transform = parse_transform(state);
+		expect(state, ';');
+		num++;
+		subxforms = state_realloc(state, subxforms,
+		    (num + 1)*sizeof(*subxforms));
+	}
+	expect(state, '}');
+
+	if (state->error != EOK) {
+		while (num--) {
+			free((void *)subxforms[num].name);
+			bithenge_transform_dec_ref(subxforms[num].transform);
+		}
+		free(subxforms);
+		return NULL;
+	}
+
+	subxforms[num].name = NULL;
+	subxforms[num].transform = NULL;
+	bithenge_transform_t *result;
+	int rc = bithenge_new_struct(&result, subxforms);
+	if (rc != EOK) {
+		error_errno(state, rc);
+		return NULL;
+	}
+	return result;
 }
 
@@ -282,4 +350,6 @@
 		next_token(state);
 		return result;
+	} else if (state->token == TOKEN_STRUCT) {
+		return parse_struct(state);
 	} else {
 		syntax_error(state, "unexpected (transform expected)");
Index: uspace/app/bithenge/test.c
===================================================================
--- uspace/app/bithenge/test.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/test.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -69,16 +69,16 @@
 		bithenge_node_dec_ref(node);
 	} else {
-		bithenge_transform_t *transform;
+		bithenge_transform_t *transform = NULL;
+		bithenge_node_t *node = NULL, *node2 = NULL;
 		rc = bithenge_parse_script(argv[1], &transform);
 		if (rc != EOK) {
 			printf("Error parsing script: %s\n", str_error(rc));
-			return 1;
+			goto error;
 		}
 
-		bithenge_node_t *node, *node2;
 		int rc = bithenge_node_from_source(&node, argv[2]);
 		if (rc != EOK) {
 			printf("Error creating node from source: %s\n", str_error(rc));
-			return 1;
+			goto error;
 		}
 
@@ -86,17 +86,28 @@
 		if (rc != EOK) {
 			printf("Error applying transform: %s\n", str_error(rc));
-			return 1;
+			goto error;
 		}
 
 		bithenge_node_dec_ref(node);
+		node = NULL;
 		bithenge_transform_dec_ref(transform);
+		transform = NULL;
 
 		rc = bithenge_print_node(BITHENGE_PRINT_PYTHON, node2);
 		if (rc != EOK) {
 			printf("Error printing node: %s\n", str_error(rc));
-			return 1;
+			goto error;
 		}
 		bithenge_node_dec_ref(node2);
+		node2 = NULL;
 		printf("\n");
+
+		return 0;
+
+error:
+		bithenge_node_dec_ref(node);
+		bithenge_node_dec_ref(node2);
+		bithenge_transform_dec_ref(transform);
+		return 1;
 	}
 
Index: uspace/app/bithenge/transform.c
===================================================================
--- uspace/app/bithenge/transform.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/transform.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -41,4 +41,19 @@
 #include "transform.h"
 
+/** Initialize a new transform.
+ * @param[out] xform Transform to initialize.
+ * @param[in] ops Operations provided by the transform.
+ * @return EOK or an error code from errno.h. */
+int bithenge_new_transform(bithenge_transform_t *xform,
+    const bithenge_transform_ops_t *ops)
+{
+	assert(ops);
+	assert(ops->apply);
+	assert(ops->destroy);
+	xform->ops = ops;
+	xform->refs = 1;
+	return EOK;
+}
+
 static int transform_indestructible(bithenge_transform_t *xform)
 {
@@ -125,4 +140,253 @@
 bithenge_named_transform_t *bithenge_primitive_transforms = primitive_transforms;
 
+typedef struct {
+	bithenge_node_t base;
+	struct struct_transform *transform;
+	bithenge_blob_t *blob;
+} struct_node_t;
+
+typedef struct struct_transform {
+	bithenge_transform_t base;
+	bithenge_named_transform_t *subtransforms;
+} struct_transform_t;
+
+static bithenge_node_t *struct_as_node(struct_node_t *node)
+{
+	return &node->base;
+}
+
+static struct_node_t *node_as_struct(bithenge_node_t *node)
+{
+	return (struct_node_t *)node;
+}
+
+static bithenge_transform_t *struct_as_transform(struct_transform_t *xform)
+{
+	return &xform->base;
+}
+
+static struct_transform_t *transform_as_struct(bithenge_transform_t *xform)
+{
+	return (struct_transform_t *)xform;
+}
+
+static int struct_node_for_one(const char *name,
+    bithenge_transform_t *subxform, bithenge_blob_t **blob,
+    bithenge_for_each_func_t func, void *data)
+{
+	int rc;
+	bithenge_node_t *subxform_result = NULL;
+
+	aoff64_t sub_size;
+	rc = bithenge_transform_prefix_length(subxform, *blob, &sub_size);
+	if (rc != EOK)
+		goto error;
+
+	bithenge_node_t *subblob_node;
+	bithenge_blob_inc_ref(*blob);
+	rc = bithenge_new_subblob(&subblob_node, *blob, 0, sub_size);
+	if (rc != EOK)
+		goto error;
+
+	rc = bithenge_transform_apply(subxform, subblob_node,
+	    &subxform_result);
+	bithenge_node_dec_ref(subblob_node);
+	if (rc != EOK)
+		goto error;
+
+	if (name) {
+		bithenge_node_t *name_node;
+		rc = bithenge_new_string_node(&name_node, name, false);
+		if (rc != EOK)
+			goto error;
+		rc = func(name_node, subxform_result, data);
+		subxform_result = NULL;
+		if (rc != EOK)
+			goto error;
+	} else {
+		if (bithenge_node_type(subxform_result) !=
+		    BITHENGE_NODE_INTERNAL) {
+			rc = EINVAL;
+			goto error;
+		}
+		rc = bithenge_node_for_each(subxform_result, func, data);
+		if (rc != EOK)
+			goto error;
+	}
+
+	bithenge_node_t *blob_node;
+	rc = bithenge_new_offset_blob(&blob_node, *blob, sub_size);
+	*blob = NULL;
+	if (rc != EOK)
+		goto error;
+	*blob = bithenge_node_as_blob(blob_node);
+
+error:
+	bithenge_node_dec_ref(subxform_result);
+	return rc;
+}
+
+static int struct_node_for_each(bithenge_node_t *base,
+    bithenge_for_each_func_t func, void *data)
+{
+	int rc = EOK;
+	struct_node_t *struct_node = node_as_struct(base);
+	bithenge_named_transform_t *subxforms =
+	    struct_node->transform->subtransforms;
+
+	bithenge_node_t *blob_node = NULL;
+	bithenge_blob_t *blob = NULL;
+	bithenge_blob_inc_ref(struct_node->blob);
+	rc = bithenge_new_offset_blob(&blob_node, struct_node->blob, 0);
+	if (rc != EOK) {
+		blob = NULL;
+		goto error;
+	}
+	blob = bithenge_node_as_blob(blob_node);
+
+	for (size_t i = 0; subxforms[i].transform; i++) {
+		rc = struct_node_for_one(subxforms[i].name,
+		    subxforms[i].transform, &blob, func, data);
+		if (rc != EOK)
+			goto error;
+	}
+
+	aoff64_t remaining;
+	rc = bithenge_blob_size(blob, &remaining);
+	if (rc != EOK)
+		goto error;
+	if (remaining != 0) {
+		rc = EINVAL;
+		goto error;
+	}
+
+error:
+	bithenge_blob_dec_ref(blob);
+	return rc;
+}
+
+static int struct_node_destroy(bithenge_node_t *base)
+{
+	struct_node_t *node = node_as_struct(base);
+	bithenge_transform_dec_ref(struct_as_transform(node->transform));
+	bithenge_blob_dec_ref(node->blob);
+	free(node);
+	return EOK;
+}
+
+static const bithenge_internal_node_ops_t struct_node_ops = {
+	.for_each = struct_node_for_each,
+	.destroy = struct_node_destroy,
+};
+
+static int struct_transform_apply(bithenge_transform_t *xform,
+    bithenge_node_t *in, bithenge_node_t **out)
+{
+	struct_transform_t *struct_transform = transform_as_struct(xform);
+	if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
+		return EINVAL;
+	struct_node_t *node = malloc(sizeof(*node));
+	if (!node)
+		return ENOMEM;
+	int rc = bithenge_init_internal_node(struct_as_node(node),
+	    &struct_node_ops);
+	if (rc != EOK) {
+		free(node);
+		return rc;
+	}
+	bithenge_transform_inc_ref(xform);
+	node->transform = struct_transform;
+	bithenge_node_inc_ref(in);
+	node->blob = bithenge_node_as_blob(in);
+	*out = struct_as_node(node);
+	return EOK;
+}
+
+static int struct_transform_prefix_length(bithenge_transform_t *xform,
+    bithenge_blob_t *blob, aoff64_t *out)
+{
+	struct_transform_t *struct_transform = transform_as_struct(xform);
+	int rc = EOK;
+	bithenge_node_t *node;
+	bithenge_blob_inc_ref(blob);
+	rc = bithenge_new_offset_blob(&node, blob, 0);
+	blob = NULL;
+	if (rc != EOK)
+		goto error;
+	blob = bithenge_node_as_blob(node);
+	*out = 0;
+	for (size_t i = 0; struct_transform->subtransforms[i].transform; i++) {
+		bithenge_transform_t *subxform =
+		    struct_transform->subtransforms[i].transform;
+		aoff64_t sub_size;
+		rc = bithenge_transform_prefix_length(subxform, blob, &sub_size);
+		if (rc != EOK)
+			goto error;
+		*out += sub_size;
+		rc = bithenge_new_offset_blob(&node, blob, sub_size);
+		blob = NULL;
+		if (rc != EOK)
+			goto error;
+		blob = bithenge_node_as_blob(node);
+	}
+error:
+	bithenge_blob_dec_ref(blob);
+	return EOK;
+}
+
+static void free_subtransforms(bithenge_named_transform_t *subtransforms)
+{
+	for (size_t i = 0; subtransforms[i].transform; i++) {
+		free((void *)subtransforms[i].name);
+		bithenge_transform_dec_ref(subtransforms[i].transform);
+	}
+	free(subtransforms);
+}
+
+static int struct_transform_destroy(bithenge_transform_t *xform)
+{
+	struct_transform_t *struct_transform = transform_as_struct(xform);
+	free_subtransforms(struct_transform->subtransforms);
+	free(struct_transform);
+	return EOK;
+}
+
+static bithenge_transform_ops_t struct_transform_ops = {
+	.apply = struct_transform_apply,
+	.prefix_length = struct_transform_prefix_length,
+	.destroy = struct_transform_destroy,
+};
+
+/** Create a struct transform. The transform will apply its subtransforms
+ * sequentially to a blob to create an internal node. Each result is either
+ * given a key from @a subtransforms or, if the name is NULL, the result's keys
+ * and values are merged into the struct transform's result. This function
+ * takes ownership of @a subtransforms and the names and references therein.
+ * @param[out] out Stores the created transform.
+ * @param subtransforms The subtransforms and field names.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_new_struct(bithenge_transform_t **out,
+    bithenge_named_transform_t *subtransforms)
+{
+	int rc;
+	struct_transform_t *struct_transform =
+	    malloc(sizeof(*struct_transform));
+	if (!struct_transform) {
+		rc = ENOMEM;
+		goto error;
+	}
+	rc = bithenge_new_transform(struct_as_transform(struct_transform),
+	    &struct_transform_ops);
+	if (rc != EOK)
+		goto error;
+	struct_transform->subtransforms = subtransforms;
+	*out = struct_as_transform(struct_transform);
+	return EOK;
+error:
+	free_subtransforms(subtransforms);
+	free(struct_transform);
+	return rc;
+}
+
 /** @}
  */
Index: uspace/app/bithenge/transform.h
===================================================================
--- uspace/app/bithenge/transform.h	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/transform.h	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -44,10 +44,10 @@
 typedef struct {
 	/** @privatesection */
-	const struct bithenge_transform_ops_t *ops;
+	const struct bithenge_transform_ops *ops;
 	unsigned int refs;
 } bithenge_transform_t;
 
 /** Operations that may be provided by a transform. */
-typedef struct bithenge_transform_ops_t {
+typedef struct bithenge_transform_ops {
 	/** @copydoc bithenge_transform_t::bithenge_transform_apply */
 	int (*apply)(bithenge_transform_t *xform, bithenge_node_t *in, bithenge_node_t **out);
@@ -55,5 +55,5 @@
 	int (*prefix_length)(bithenge_transform_t *xform, bithenge_blob_t *blob, aoff64_t *out);
 	/** Destroy the transform.
-	 * @param blob The transform.
+	 * @param xform The transform.
 	 * @return EOK on success or an error code from errno.h. */
 	int (*destroy)(bithenge_transform_t *xform);
@@ -127,4 +127,10 @@
 extern bithenge_named_transform_t *bithenge_primitive_transforms;
 
+int bithenge_new_transform(bithenge_transform_t *xform,
+    const bithenge_transform_ops_t *ops);
+
+int bithenge_new_struct(bithenge_transform_t **out,
+    bithenge_named_transform_t *subtransforms);
+
 #endif
 
Index: uspace/app/bithenge/tree.c
===================================================================
--- uspace/app/bithenge/tree.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/tree.c	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -105,4 +105,6 @@
 	simple_internal_node_t *node = node_as_simple(base);
 	for (bithenge_int_t i = 0; i < node->len; i++) {
+		bithenge_node_inc_ref(node->nodes[2*i+0]);
+		bithenge_node_inc_ref(node->nodes[2*i+1]);
 		rc = func(node->nodes[2*i+0], node->nodes[2*i+1], data);
 		if (rc != EOK)
@@ -132,4 +134,18 @@
 };
 
+/** Initialize an internal node.
+ * @memberof bithenge_node_t
+ * @param[out] node The node.
+ * @param[in] ops The operations provided.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_init_internal_node(bithenge_node_t *node,
+    const bithenge_internal_node_ops_t *ops)
+{
+	node->type = BITHENGE_NODE_INTERNAL;
+	node->refs = 1;
+	node->internal_ops = ops;
+	return EOK;
+}
+
 /** Create an internal node from a set of keys and values. This function takes
  * ownership of a reference to the key and value nodes, and optionally the
@@ -146,16 +162,15 @@
     bithenge_node_t **nodes, bithenge_int_t len, bool needs_free)
 {
+	int rc;
 	assert(out);
 	simple_internal_node_t *node = malloc(sizeof(*node));
 	if (!node) {
-		for (bithenge_int_t i = 0; i < 2 * len; i++)
-			bithenge_node_dec_ref(nodes[i]);
-		if (needs_free)
-			free(nodes);
-		return ENOMEM;
-	}
-	node->base.type = BITHENGE_NODE_INTERNAL;
-	node->base.refs = 1;
-	node->base.internal_ops = &simple_internal_node_ops;
+		rc = ENOMEM;
+		goto error;
+	}
+	rc = bithenge_init_internal_node(simple_as_node(node),
+	    &simple_internal_node_ops);
+	if (rc != EOK)
+		goto error;
 	node->nodes = nodes;
 	node->len = len;
@@ -163,4 +178,11 @@
 	*out = simple_as_node(node);
 	return EOK;
+error:
+	for (bithenge_int_t i = 0; i < 2 * len; i++)
+		bithenge_node_dec_ref(nodes[i]);
+	if (needs_free)
+		free(nodes);
+	free(node);
+	return rc;
 }
 
@@ -201,5 +223,5 @@
 /** Create a string node.
  * @memberof bithenge_node_t
- * @param[out] out Stores the created string node.
+ * @param[out] out Stores the created string node. On error, this is unchanged.
  * @param value The value for the node to hold.
  * @param needs_free Whether the string should be freed when the node is
Index: uspace/app/bithenge/tree.h
===================================================================
--- uspace/app/bithenge/tree.h	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
+++ uspace/app/bithenge/tree.h	(revision 04a7435f4ee13d275f9b652482de1d377eed4a8f)
@@ -81,5 +81,6 @@
 } bithenge_node_t;
 
-/** A callback function used to iterate over a node's children.
+/** A callback function used to iterate over a node's children. It takes
+ * ownership of a reference to both the key and the value.
  * @memberof bithenge_node_t
  * @param key The key.
@@ -161,4 +162,6 @@
 }
 
+int bithenge_init_internal_node(bithenge_node_t *,
+    const bithenge_internal_node_ops_t *);
 int bithenge_new_simple_internal_node(bithenge_node_t **, bithenge_node_t **,
     bithenge_int_t, bool needs_free);