Changeset d7c8e39f in mainline

Timestamp:

2012-07-29T03:02:24Z (12 years ago)

Author:

Sean Bartell <wingedtachikoma@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

d1e580a

Parents:

84e8a70

Message:

Bithenge: struct node performance improvement

Location:

uspace

Files:

• app/bithenge/transform.c (modified) (10 diffs)
• dist/src/bithenge/test.bh (modified) (1 diff)

uspace/app/bithenge/transform.c

@@ -384 +384 @@
 typedef struct {
         bithenge_node_t base;
+        bithenge_scope_t scope;
         struct struct_transform *transform;
-        bithenge_scope_t scope;
         bithenge_blob_t *blob;
+        aoff64_t *ends;
+        size_t num_ends;
         bool prefix;
 } struct_node_t;
@@ -393 +395 @@
         bithenge_transform_t base;
         bithenge_named_transform_t *subtransforms;
+        size_t num_subtransforms;
 } struct_transform_t;
 
@@ -415 +418 @@
 }
 
-static int struct_node_for_one(const char *name,
-    bithenge_transform_t *subxform, bithenge_scope_t *scope,
-    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, scope, *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, scope, 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);
+static int struct_node_field_offset(struct_node_t *self, aoff64_t *out,
+    size_t index)
+{
+        if (index == 0) {
+                *out = 0;
+                return EOK;
+        }
+        index--;
+        aoff64_t prev_offset =
+            self->num_ends ? self->ends[self->num_ends - 1] : 0;
+        for (; self->num_ends <= index; self->num_ends++) {
+                bithenge_node_t *subblob_node;
+                bithenge_blob_inc_ref(self->blob);
+                int rc = bithenge_new_offset_blob(&subblob_node, self->blob,
+                    prev_offset);
                 if (rc != EOK)
-                        goto error;
-                rc = func(name_node, subxform_result, data);
-                subxform_result = NULL;
+                        return rc;
+
+                bithenge_blob_t *subblob = bithenge_node_as_blob(subblob_node);
+                aoff64_t field_size;
+                rc = bithenge_transform_prefix_length(
+                    self->transform->subtransforms[self->num_ends].transform,
+                    &self->scope, subblob, &field_size);
+                bithenge_node_dec_ref(subblob_node);
                 if (rc != EOK)
-                        goto error;
-        } else {
+                        return rc;
+
+                prev_offset = self->ends[self->num_ends] =
+                    prev_offset + field_size;
+        }
+        *out = self->ends[index];
+        return EOK;
+}
+
+static int struct_node_subtransform(struct_node_t *self, bithenge_node_t **out,
+    size_t index)
+{
+        aoff64_t start_pos, end_pos;
+        int rc = struct_node_field_offset(self, &start_pos, index);
+        if (rc != EOK)
+                return rc;
+        rc = struct_node_field_offset(self, &end_pos, index + 1);
+        if (rc != EOK)
+                return rc;
+
+        bithenge_node_t *blob_node;
+        bithenge_blob_inc_ref(self->blob);
+        rc = bithenge_new_subblob(&blob_node, self->blob, start_pos,
+            end_pos - start_pos);
+        if (rc != EOK)
+                return rc;
+
+        rc = bithenge_transform_apply(
+            self->transform->subtransforms[index].transform, &self->scope,
+            blob_node, out);
+        bithenge_node_dec_ref(blob_node);
+        if (rc != EOK)
+                return rc;
+
+        return EOK;
+}
+
+static int struct_node_for_each(bithenge_node_t *base,
+    bithenge_for_each_func_t func, void *data)
+{
+        int rc = EOK;
+        struct_node_t *self = node_as_struct(base);
+        bithenge_named_transform_t *subxforms =
+            self->transform->subtransforms;
+
+        for (size_t i = 0; subxforms[i].transform; i++) {
+                bithenge_node_t *subxform_result;
+                rc = struct_node_subtransform(self, &subxform_result, i);
+                if (rc != EOK)
+                        return rc;
+
+                if (subxforms[i].name) {
+                        bithenge_node_t *name_node;
+                        rc = bithenge_new_string_node(&name_node,
+                            subxforms[i].name, false);
+                        if (rc == EOK) {
+                                rc = func(name_node, subxform_result, data);
+                                subxform_result = NULL;
+                        }
+                } else {
+                        if (bithenge_node_type(subxform_result) !=
+                            BITHENGE_NODE_INTERNAL) {
+                                rc = EINVAL;
+                        } else {
+                                rc = bithenge_node_for_each(subxform_result,
+                                    func, data);
+                        }
+                }
+                bithenge_node_dec_ref(subxform_result);
+                if (rc != EOK)
+                        return rc;
+        }
+
+        if (!self->prefix) {
+                aoff64_t blob_size, end_pos;
+                rc = bithenge_blob_size(self->blob, &blob_size);
+                if (rc != EOK)
+                        return rc;
+                rc = struct_node_field_offset(self, &end_pos,
+                    self->transform->num_subtransforms);
+                if (rc != EOK)
+                        return rc;
+                if (blob_size != end_pos) {
+                        rc = EINVAL;
+                        return rc;
+                }
+        }
+
+        return rc;
+}
+
+static int struct_node_get(bithenge_node_t *base, bithenge_node_t *key,
+    bithenge_node_t **out)
+{
+        struct_node_t *self = node_as_struct(base);
+
+        if (bithenge_node_type(key) != BITHENGE_NODE_STRING) {
+                bithenge_node_dec_ref(key);
+                return ENOENT;
+        }
+        const char *name = bithenge_string_node_value(key);
+
+        for (size_t i = 0; self->transform->subtransforms[i].transform; i++) {
+                if (self->transform->subtransforms[i].name
+                    && !str_cmp(name, self->transform->subtransforms[i].name)) {
+                        bithenge_node_dec_ref(key);
+                        return struct_node_subtransform(self, out, i);
+                }
+        }
+
+        for (size_t i = 0; self->transform->subtransforms[i].transform; i++) {
+                if (self->transform->subtransforms[i].name)
+                        continue;
+                bithenge_node_t *subxform_result;
+                int rc = struct_node_subtransform(self, &subxform_result, i);
+                if (rc != EOK) {
+                        bithenge_node_dec_ref(key);
+                        return rc;
+                }
                 if (bithenge_node_type(subxform_result) !=
                     BITHENGE_NODE_INTERNAL) {
-                        rc = EINVAL;
-                        goto error;
+                        bithenge_node_dec_ref(subxform_result);
+                        bithenge_node_dec_ref(key);
+                        return EINVAL;
                 }
-                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, &struct_node->scope, &blob, func,
-                    data);
-                if (rc != EOK)
-                        goto error;
-        }
-
-        if (!struct_node->prefix) {
-                aoff64_t remaining;
-                rc = bithenge_blob_size(blob, &remaining);
-                if (rc != EOK)
-                        goto error;
-                if (remaining != 0) {
-                        rc = EINVAL;
-                        goto error;
+                bithenge_node_inc_ref(key);
+                rc = bithenge_node_get(subxform_result, key, out);
+                bithenge_node_dec_ref(subxform_result);
+                if (rc != ENOENT) {
+                        bithenge_node_dec_ref(key);
+                        return rc;
                 }
         }
 
-error:
-        bithenge_blob_dec_ref(blob);
-        return rc;
+        bithenge_node_dec_ref(key);
+        return ENOENT;
 }
 
@@ -525 +592 @@
         bithenge_transform_dec_ref(struct_as_transform(node->transform));
         bithenge_blob_dec_ref(node->blob);
+        free(node->ends);
         free(node);
 }
@@ -530 +598 @@
 static const bithenge_internal_node_ops_t struct_node_ops = {
         .for_each = struct_node_for_each,
+        .get = struct_node_get,
         .destroy = struct_node_destroy,
 };
@@ -540 +609 @@
         if (!node)
                 return ENOMEM;
+
         bithenge_scope_init(&node->scope);
         int rc = bithenge_scope_copy(&node->scope, scope);
@@ -546 +616 @@
                 return rc;
         }
+
+        node->ends = malloc(sizeof(*node->ends) * self->num_subtransforms);
+        if (!node->ends) {
+                bithenge_scope_destroy(&node->scope);
+                free(node);
+                return ENOMEM;
+        }
+
         rc = bithenge_init_internal_node(struct_as_node(node),
             &struct_node_ops);
         if (rc != EOK) {
                 bithenge_scope_destroy(&node->scope);
+                free(node->ends);
                 free(node);
                 return rc;
         }
+
         bithenge_transform_inc_ref(struct_as_transform(self));
         bithenge_blob_inc_ref(blob);
@@ -558 +638 @@
         node->blob = blob;
         node->prefix = prefix;
+        node->num_ends = 0;
         *out = struct_as_node(node);
 
@@ -588 +669 @@
         if (rc != EOK)
                 return rc;
-        bithenge_scope_t *inner = &node_as_struct(struct_node)->scope;
-
-        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; self->subtransforms[i].transform; i++) {
-                bithenge_transform_t *subxform =
-                    self->subtransforms[i].transform;
-                aoff64_t sub_size;
-                rc = bithenge_transform_prefix_length(subxform, inner, 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:
+
+        rc = struct_node_field_offset(node_as_struct(struct_node), out,
+            self->num_subtransforms);
         bithenge_node_dec_ref(struct_node);
-        bithenge_blob_dec_ref(blob);
         return rc;
 }
@@ -664 +720 @@
                 goto error;
         self->subtransforms = subtransforms;
+        self->num_subtransforms = 0;
+        for (self->num_subtransforms = 0;
+            subtransforms[self->num_subtransforms].transform;
+            self->num_subtransforms++);
         *out = struct_as_transform(self);
         return EOK;

uspace/dist/src/bithenge/test.bh

@@ +1 @@
+transform length = struct {
+        .len <- uint8;
+};
+
 transform pascal_string = struct {
-        .len <- uint8;
+        <- length;
         .string <- ascii <- known_length(.len);
 };