Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset d7c8e39f in mainline


Ignore:
Timestamp:
2012-07-29T03:02:24Z (9 years ago)
Author:
Sean Bartell <wingedtachikoma@…>
Branches:
lfn, master
Children:
d1e580a
Parents:
84e8a70
Message:

Bithenge: struct node performance improvement

Location:
uspace
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • uspace/app/bithenge/transform.c

    r84e8a70 rd7c8e39f  
    384384typedef struct {
    385385        bithenge_node_t base;
     386        bithenge_scope_t scope;
    386387        struct struct_transform *transform;
    387         bithenge_scope_t scope;
    388388        bithenge_blob_t *blob;
     389        aoff64_t *ends;
     390        size_t num_ends;
    389391        bool prefix;
    390392} struct_node_t;
     
    393395        bithenge_transform_t base;
    394396        bithenge_named_transform_t *subtransforms;
     397        size_t num_subtransforms;
    395398} struct_transform_t;
    396399
     
    415418}
    416419
    417 static int struct_node_for_one(const char *name,
    418     bithenge_transform_t *subxform, bithenge_scope_t *scope,
    419     bithenge_blob_t **blob, bithenge_for_each_func_t func, void *data)
    420 {
    421         int rc;
    422         bithenge_node_t *subxform_result = NULL;
    423 
    424         aoff64_t sub_size;
    425         rc = bithenge_transform_prefix_length(subxform, scope, *blob,
    426             &sub_size);
    427         if (rc != EOK)
    428                 goto error;
    429 
    430         bithenge_node_t *subblob_node;
    431         bithenge_blob_inc_ref(*blob);
    432         rc = bithenge_new_subblob(&subblob_node, *blob, 0, sub_size);
    433         if (rc != EOK)
    434                 goto error;
    435 
    436         rc = bithenge_transform_apply(subxform, scope, subblob_node,
    437             &subxform_result);
    438         bithenge_node_dec_ref(subblob_node);
    439         if (rc != EOK)
    440                 goto error;
    441 
    442         if (name) {
    443                 bithenge_node_t *name_node;
    444                 rc = bithenge_new_string_node(&name_node, name, false);
     420static int struct_node_field_offset(struct_node_t *self, aoff64_t *out,
     421    size_t index)
     422{
     423        if (index == 0) {
     424                *out = 0;
     425                return EOK;
     426        }
     427        index--;
     428        aoff64_t prev_offset =
     429            self->num_ends ? self->ends[self->num_ends - 1] : 0;
     430        for (; self->num_ends <= index; self->num_ends++) {
     431                bithenge_node_t *subblob_node;
     432                bithenge_blob_inc_ref(self->blob);
     433                int rc = bithenge_new_offset_blob(&subblob_node, self->blob,
     434                    prev_offset);
    445435                if (rc != EOK)
    446                         goto error;
    447                 rc = func(name_node, subxform_result, data);
    448                 subxform_result = NULL;
     436                        return rc;
     437
     438                bithenge_blob_t *subblob = bithenge_node_as_blob(subblob_node);
     439                aoff64_t field_size;
     440                rc = bithenge_transform_prefix_length(
     441                    self->transform->subtransforms[self->num_ends].transform,
     442                    &self->scope, subblob, &field_size);
     443                bithenge_node_dec_ref(subblob_node);
    449444                if (rc != EOK)
    450                         goto error;
    451         } else {
     445                        return rc;
     446
     447                prev_offset = self->ends[self->num_ends] =
     448                    prev_offset + field_size;
     449        }
     450        *out = self->ends[index];
     451        return EOK;
     452}
     453
     454static int struct_node_subtransform(struct_node_t *self, bithenge_node_t **out,
     455    size_t index)
     456{
     457        aoff64_t start_pos, end_pos;
     458        int rc = struct_node_field_offset(self, &start_pos, index);
     459        if (rc != EOK)
     460                return rc;
     461        rc = struct_node_field_offset(self, &end_pos, index + 1);
     462        if (rc != EOK)
     463                return rc;
     464
     465        bithenge_node_t *blob_node;
     466        bithenge_blob_inc_ref(self->blob);
     467        rc = bithenge_new_subblob(&blob_node, self->blob, start_pos,
     468            end_pos - start_pos);
     469        if (rc != EOK)
     470                return rc;
     471
     472        rc = bithenge_transform_apply(
     473            self->transform->subtransforms[index].transform, &self->scope,
     474            blob_node, out);
     475        bithenge_node_dec_ref(blob_node);
     476        if (rc != EOK)
     477                return rc;
     478
     479        return EOK;
     480}
     481
     482static int struct_node_for_each(bithenge_node_t *base,
     483    bithenge_for_each_func_t func, void *data)
     484{
     485        int rc = EOK;
     486        struct_node_t *self = node_as_struct(base);
     487        bithenge_named_transform_t *subxforms =
     488            self->transform->subtransforms;
     489
     490        for (size_t i = 0; subxforms[i].transform; i++) {
     491                bithenge_node_t *subxform_result;
     492                rc = struct_node_subtransform(self, &subxform_result, i);
     493                if (rc != EOK)
     494                        return rc;
     495
     496                if (subxforms[i].name) {
     497                        bithenge_node_t *name_node;
     498                        rc = bithenge_new_string_node(&name_node,
     499                            subxforms[i].name, false);
     500                        if (rc == EOK) {
     501                                rc = func(name_node, subxform_result, data);
     502                                subxform_result = NULL;
     503                        }
     504                } else {
     505                        if (bithenge_node_type(subxform_result) !=
     506                            BITHENGE_NODE_INTERNAL) {
     507                                rc = EINVAL;
     508                        } else {
     509                                rc = bithenge_node_for_each(subxform_result,
     510                                    func, data);
     511                        }
     512                }
     513                bithenge_node_dec_ref(subxform_result);
     514                if (rc != EOK)
     515                        return rc;
     516        }
     517
     518        if (!self->prefix) {
     519                aoff64_t blob_size, end_pos;
     520                rc = bithenge_blob_size(self->blob, &blob_size);
     521                if (rc != EOK)
     522                        return rc;
     523                rc = struct_node_field_offset(self, &end_pos,
     524                    self->transform->num_subtransforms);
     525                if (rc != EOK)
     526                        return rc;
     527                if (blob_size != end_pos) {
     528                        rc = EINVAL;
     529                        return rc;
     530                }
     531        }
     532
     533        return rc;
     534}
     535
     536static int struct_node_get(bithenge_node_t *base, bithenge_node_t *key,
     537    bithenge_node_t **out)
     538{
     539        struct_node_t *self = node_as_struct(base);
     540
     541        if (bithenge_node_type(key) != BITHENGE_NODE_STRING) {
     542                bithenge_node_dec_ref(key);
     543                return ENOENT;
     544        }
     545        const char *name = bithenge_string_node_value(key);
     546
     547        for (size_t i = 0; self->transform->subtransforms[i].transform; i++) {
     548                if (self->transform->subtransforms[i].name
     549                    && !str_cmp(name, self->transform->subtransforms[i].name)) {
     550                        bithenge_node_dec_ref(key);
     551                        return struct_node_subtransform(self, out, i);
     552                }
     553        }
     554
     555        for (size_t i = 0; self->transform->subtransforms[i].transform; i++) {
     556                if (self->transform->subtransforms[i].name)
     557                        continue;
     558                bithenge_node_t *subxform_result;
     559                int rc = struct_node_subtransform(self, &subxform_result, i);
     560                if (rc != EOK) {
     561                        bithenge_node_dec_ref(key);
     562                        return rc;
     563                }
    452564                if (bithenge_node_type(subxform_result) !=
    453565                    BITHENGE_NODE_INTERNAL) {
    454                         rc = EINVAL;
    455                         goto error;
     566                        bithenge_node_dec_ref(subxform_result);
     567                        bithenge_node_dec_ref(key);
     568                        return EINVAL;
    456569                }
    457                 rc = bithenge_node_for_each(subxform_result, func, data);
    458                 if (rc != EOK)
    459                         goto error;
    460         }
    461 
    462         bithenge_node_t *blob_node;
    463         rc = bithenge_new_offset_blob(&blob_node, *blob, sub_size);
    464         *blob = NULL;
    465         if (rc != EOK)
    466                 goto error;
    467         *blob = bithenge_node_as_blob(blob_node);
    468 
    469 error:
    470         bithenge_node_dec_ref(subxform_result);
    471         return rc;
    472 }
    473 
    474 static int struct_node_for_each(bithenge_node_t *base,
    475     bithenge_for_each_func_t func, void *data)
    476 {
    477         int rc = EOK;
    478         struct_node_t *struct_node = node_as_struct(base);
    479         bithenge_named_transform_t *subxforms =
    480             struct_node->transform->subtransforms;
    481 
    482         bithenge_node_t *blob_node = NULL;
    483         bithenge_blob_t *blob = NULL;
    484         bithenge_blob_inc_ref(struct_node->blob);
    485         rc = bithenge_new_offset_blob(&blob_node, struct_node->blob, 0);
    486         if (rc != EOK) {
    487                 blob = NULL;
    488                 goto error;
    489         }
    490         blob = bithenge_node_as_blob(blob_node);
    491 
    492         for (size_t i = 0; subxforms[i].transform; i++) {
    493                 rc = struct_node_for_one(subxforms[i].name,
    494                     subxforms[i].transform, &struct_node->scope, &blob, func,
    495                     data);
    496                 if (rc != EOK)
    497                         goto error;
    498         }
    499 
    500         if (!struct_node->prefix) {
    501                 aoff64_t remaining;
    502                 rc = bithenge_blob_size(blob, &remaining);
    503                 if (rc != EOK)
    504                         goto error;
    505                 if (remaining != 0) {
    506                         rc = EINVAL;
    507                         goto error;
     570                bithenge_node_inc_ref(key);
     571                rc = bithenge_node_get(subxform_result, key, out);
     572                bithenge_node_dec_ref(subxform_result);
     573                if (rc != ENOENT) {
     574                        bithenge_node_dec_ref(key);
     575                        return rc;
    508576                }
    509577        }
    510578
    511 error:
    512         bithenge_blob_dec_ref(blob);
    513         return rc;
     579        bithenge_node_dec_ref(key);
     580        return ENOENT;
    514581}
    515582
     
    525592        bithenge_transform_dec_ref(struct_as_transform(node->transform));
    526593        bithenge_blob_dec_ref(node->blob);
     594        free(node->ends);
    527595        free(node);
    528596}
     
    530598static const bithenge_internal_node_ops_t struct_node_ops = {
    531599        .for_each = struct_node_for_each,
     600        .get = struct_node_get,
    532601        .destroy = struct_node_destroy,
    533602};
     
    540609        if (!node)
    541610                return ENOMEM;
     611
    542612        bithenge_scope_init(&node->scope);
    543613        int rc = bithenge_scope_copy(&node->scope, scope);
     
    546616                return rc;
    547617        }
     618
     619        node->ends = malloc(sizeof(*node->ends) * self->num_subtransforms);
     620        if (!node->ends) {
     621                bithenge_scope_destroy(&node->scope);
     622                free(node);
     623                return ENOMEM;
     624        }
     625
    548626        rc = bithenge_init_internal_node(struct_as_node(node),
    549627            &struct_node_ops);
    550628        if (rc != EOK) {
    551629                bithenge_scope_destroy(&node->scope);
     630                free(node->ends);
    552631                free(node);
    553632                return rc;
    554633        }
     634
    555635        bithenge_transform_inc_ref(struct_as_transform(self));
    556636        bithenge_blob_inc_ref(blob);
     
    558638        node->blob = blob;
    559639        node->prefix = prefix;
     640        node->num_ends = 0;
    560641        *out = struct_as_node(node);
    561642
     
    588669        if (rc != EOK)
    589670                return rc;
    590         bithenge_scope_t *inner = &node_as_struct(struct_node)->scope;
    591 
    592         bithenge_node_t *node;
    593         bithenge_blob_inc_ref(blob);
    594         rc = bithenge_new_offset_blob(&node, blob, 0);
    595         blob = NULL;
    596         if (rc != EOK)
    597                 goto error;
    598         blob = bithenge_node_as_blob(node);
    599         *out = 0;
    600         for (size_t i = 0; self->subtransforms[i].transform; i++) {
    601                 bithenge_transform_t *subxform =
    602                     self->subtransforms[i].transform;
    603                 aoff64_t sub_size;
    604                 rc = bithenge_transform_prefix_length(subxform, inner, blob,
    605                     &sub_size);
    606                 if (rc != EOK)
    607                         goto error;
    608                 *out += sub_size;
    609                 rc = bithenge_new_offset_blob(&node, blob, sub_size);
    610                 blob = NULL;
    611                 if (rc != EOK)
    612                         goto error;
    613                 blob = bithenge_node_as_blob(node);
    614         }
    615 
    616 error:
     671
     672        rc = struct_node_field_offset(node_as_struct(struct_node), out,
     673            self->num_subtransforms);
    617674        bithenge_node_dec_ref(struct_node);
    618         bithenge_blob_dec_ref(blob);
    619675        return rc;
    620676}
     
    664720                goto error;
    665721        self->subtransforms = subtransforms;
     722        self->num_subtransforms = 0;
     723        for (self->num_subtransforms = 0;
     724            subtransforms[self->num_subtransforms].transform;
     725            self->num_subtransforms++);
    666726        *out = struct_as_transform(self);
    667727        return EOK;
  • uspace/dist/src/bithenge/test.bh

    r84e8a70 rd7c8e39f  
     1transform length = struct {
     2        .len <- uint8;
     3};
     4
    15transform pascal_string = struct {
    2         .len <- uint8;
     6        <- length;
    37        .string <- ascii <- known_length(.len);
    48};
Note: See TracChangeset for help on using the changeset viewer.