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

Changeset 3a7356dc in mainline


Ignore:
Timestamp:
2012-08-18T03:58:10Z (9 years ago)
Author:
Sean Bartell <wingedtachikoma@…>
Branches:
lfn, master
Children:
1f9c9a4
Parents:
681a985
Message:

Bithenge: make concatenation lazier

Location:
uspace
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • uspace/dist/src/bithenge/fat.bh

    r681a985 r3a7356dc  
    5555                .data <- (.cluster);
    5656        } else {
    57                 .rest <- file_data(data, bits, fat, cluster_size, .next);
     57                .rest <- file_data(data, bits, fat, cluster_size, .next) <- known_length(0);
    5858                .data <- (.cluster ++ .rest);
    5959        }
  • uspace/lib/bithenge/blob.c

    r681a985 r3a7356dc  
    459459}
    460460
    461 typedef struct {
    462         bithenge_blob_t base;
    463         bithenge_blob_t *a, *b;
    464         aoff64_t a_size;
    465 } concat_blob_t;
    466 
    467 static inline concat_blob_t *blob_as_concat(bithenge_blob_t *base)
    468 {
    469         return (concat_blob_t *)base;
    470 }
    471 
    472 static inline bithenge_blob_t *concat_as_blob(concat_blob_t *blob)
    473 {
    474         return &blob->base;
    475 }
    476 
    477 static int concat_blob_size(bithenge_blob_t *base, aoff64_t *size)
    478 {
    479         concat_blob_t *self = blob_as_concat(base);
    480         int rc = bithenge_blob_size(self->b, size);
    481         *size += self->a_size;
    482         return rc;
    483 }
    484 
    485 static int concat_blob_read(bithenge_blob_t *base, aoff64_t offset,
    486     char *buffer, aoff64_t *size)
    487 {
    488         int rc = EOK;
    489         concat_blob_t *self = blob_as_concat(base);
    490 
    491         aoff64_t a_size = 0, b_size = 0;
    492         if (offset < self->a_size) {
    493                 a_size = *size;
    494                 rc = bithenge_blob_read(self->a, offset, buffer, &a_size);
    495                 if (rc != EOK)
    496                         return rc;
    497         }
    498         if (offset + *size > self->a_size) {
    499                 b_size = *size - a_size;
    500                 rc = bithenge_blob_read(self->b,
    501                     offset + a_size - self->a_size, buffer + a_size, &b_size);
    502                 if (rc != EOK)
    503                         return rc;
    504         }
    505         assert(a_size + b_size <= *size);
    506         *size = a_size + b_size;
    507         return rc;
    508 }
    509 
    510 static int concat_blob_read_bits(bithenge_blob_t *base, aoff64_t offset,
    511     char *buffer, aoff64_t *size, bool little_endian)
    512 {
    513         int rc = EOK;
    514         concat_blob_t *self = blob_as_concat(base);
    515 
    516         aoff64_t a_size = 0, b_size = 0;
    517         if (offset < self->a_size) {
    518                 a_size = *size;
    519                 rc = bithenge_blob_read_bits(self->a, offset, buffer, &a_size,
    520                     little_endian);
    521                 if (rc != EOK)
    522                         return rc;
    523         }
    524         if (offset + *size > self->a_size) {
    525                 b_size = offset + *size - self->a_size;
    526                 rc = bithenge_blob_read_bits(self->b,
    527                     offset + a_size - self->a_size, buffer + a_size, &b_size,
    528                     little_endian);
    529                 if (rc != EOK)
    530                         return rc;
    531         }
    532         *size = a_size + b_size;
    533         return rc;
    534 }
    535 
    536 static void concat_blob_destroy(bithenge_blob_t *base)
    537 {
    538         concat_blob_t *self = blob_as_concat(base);
    539         bithenge_blob_dec_ref(self->a);
    540         bithenge_blob_dec_ref(self->b);
    541         free(self);
    542 }
    543 
    544 static const bithenge_random_access_blob_ops_t concat_blob_ops = {
    545         .size = concat_blob_size,
    546         .read = concat_blob_read,
    547         .read_bits = concat_blob_read_bits,
    548         .destroy = concat_blob_destroy,
    549 };
    550 
    551 /** Create a concatenated blob. Takes references to @a a and @a b.
    552  * @param[out] out Holds the new blob.
    553  * @param a The first blob.
    554  * @param b The second blob.
    555  * @return EOK on success or an error code from errno.h. */
    556 int bithenge_concat_blob(bithenge_node_t **out, bithenge_blob_t *a,
    557     bithenge_blob_t *b)
    558 {
    559         assert(out);
    560         assert(a);
    561         assert(b);
    562         int rc;
    563         concat_blob_t *self = malloc(sizeof(*self));
    564         if (!self) {
    565                 rc = ENOMEM;
    566                 goto error;
    567         }
    568 
    569         rc = bithenge_blob_size(a, &self->a_size);
    570         if (rc != EOK)
    571                 goto error;
    572 
    573         rc = bithenge_init_random_access_blob(concat_as_blob(self),
    574             &concat_blob_ops);
    575         if (rc != EOK)
    576                 goto error;
    577         self->a = a;
    578         self->b = b;
    579         *out = bithenge_blob_as_node(concat_as_blob(self));
    580         return EOK;
    581 
    582 error:
    583         bithenge_blob_dec_ref(a);
    584         bithenge_blob_dec_ref(b);
    585         free(self);
    586         return rc;
    587 }
    588 
    589461/** Check whether the contents of two blobs are equal.
    590462 * @memberof bithenge_blob_t
  • uspace/lib/bithenge/blob.h

    r681a985 r3a7356dc  
    243243int bithenge_new_subblob(bithenge_node_t **, bithenge_blob_t *, aoff64_t,
    244244    aoff64_t);
    245 int bithenge_concat_blob(bithenge_node_t **, bithenge_blob_t *,
    246     bithenge_blob_t *);
    247245bool bithenge_blob_equal(bithenge_blob_t *, bithenge_blob_t *);
    248246
  • uspace/lib/bithenge/expression.c

    r681a985 r3a7356dc  
    8888    bithenge_scope_t *scope, bithenge_node_t **out)
    8989{
     90        int rc;
    9091        binary_expression_t *self = expression_as_binary(base);
    9192        bithenge_node_t *a, *b;
    92         int rc = bithenge_expression_evaluate(self->a, scope, &a);
     93        rc = bithenge_expression_evaluate(self->a, scope, &a);
    9394        if (rc != EOK)
    9495                return rc;
    95         rc = bithenge_expression_evaluate(self->b, scope, &b);
    96         if (rc != EOK) {
    97                 bithenge_node_dec_ref(a);
    98                 return rc;
     96        if (self->op != BITHENGE_EXPRESSION_CONCAT) {
     97                rc = bithenge_expression_evaluate(self->b, scope, &b);
     98                if (rc != EOK) {
     99                        bithenge_node_dec_ref(a);
     100                        return rc;
     101                }
    99102        }
    100103
     
    133136                if (bithenge_node_type(a) != BITHENGE_NODE_BLOB)
    134137                        goto error;
    135                 if (bithenge_node_type(b) != BITHENGE_NODE_BLOB)
    136                         goto error;
    137138                break;
    138139        default:
     
    203204                break;
    204205        case BITHENGE_EXPRESSION_CONCAT:
    205                 rc = bithenge_concat_blob(out, bithenge_node_as_blob(a),
    206                     bithenge_node_as_blob(b));
     206                bithenge_expression_inc_ref(self->b);
     207                bithenge_scope_inc_ref(scope);
     208                rc = bithenge_concat_blob_lazy(out, bithenge_node_as_blob(a),
     209                    self->b, scope);
    207210                a = NULL;
    208211                b = NULL;
     
    962965}
    963966
     967
     968
     969/***************** concat_blob                    *****************/
     970
     971typedef struct {
     972        bithenge_blob_t base;
     973        bithenge_blob_t *a, *b;
     974        aoff64_t a_size;
     975        bithenge_expression_t *b_expr;
     976        bithenge_scope_t *scope;
     977} concat_blob_t;
     978
     979static inline concat_blob_t *blob_as_concat(bithenge_blob_t *base)
     980{
     981        return (concat_blob_t *)base;
     982}
     983
     984static inline bithenge_blob_t *concat_as_blob(concat_blob_t *blob)
     985{
     986        return &blob->base;
     987}
     988
     989static int concat_blob_evaluate_b(concat_blob_t *self)
     990{
     991        if (self->b)
     992                return EOK;
     993        bithenge_node_t *b_node;
     994        int rc = bithenge_expression_evaluate(self->b_expr, self->scope,
     995            &b_node);
     996        if (rc != EOK)
     997                return rc;
     998        if (bithenge_node_type(b_node) != BITHENGE_NODE_BLOB) {
     999                bithenge_node_dec_ref(b_node);
     1000                return bithenge_scope_error(self->scope,
     1001                    "Concatenation arguments must be blobs");
     1002        }
     1003        self->b = bithenge_node_as_blob(b_node);
     1004        bithenge_expression_dec_ref(self->b_expr);
     1005        bithenge_scope_dec_ref(self->scope);
     1006        self->b_expr = NULL;
     1007        self->scope = NULL;
     1008        return EOK;
     1009}
     1010
     1011static int concat_blob_size(bithenge_blob_t *base, aoff64_t *size)
     1012{
     1013        concat_blob_t *self = blob_as_concat(base);
     1014        int rc = concat_blob_evaluate_b(self);
     1015        if (rc != EOK)
     1016                return rc;
     1017        rc = bithenge_blob_size(self->b, size);
     1018        *size += self->a_size;
     1019        return rc;
     1020}
     1021
     1022static int concat_blob_read(bithenge_blob_t *base, aoff64_t offset,
     1023    char *buffer, aoff64_t *size)
     1024{
     1025        int rc;
     1026        concat_blob_t *self = blob_as_concat(base);
     1027
     1028        aoff64_t a_size = 0, b_size = 0;
     1029        if (offset < self->a_size) {
     1030                a_size = *size;
     1031                rc = bithenge_blob_read(self->a, offset, buffer, &a_size);
     1032                if (rc != EOK)
     1033                        return rc;
     1034        }
     1035        if (offset + *size > self->a_size) {
     1036                rc = concat_blob_evaluate_b(self);
     1037                if (rc != EOK)
     1038                        return rc;
     1039                b_size = *size - a_size;
     1040                rc = bithenge_blob_read(self->b,
     1041                    offset + a_size - self->a_size, buffer + a_size, &b_size);
     1042                if (rc != EOK)
     1043                        return rc;
     1044        }
     1045        assert(a_size + b_size <= *size);
     1046        *size = a_size + b_size;
     1047        return EOK;
     1048}
     1049
     1050static int concat_blob_read_bits(bithenge_blob_t *base, aoff64_t offset,
     1051    char *buffer, aoff64_t *size, bool little_endian)
     1052{
     1053        int rc;
     1054        concat_blob_t *self = blob_as_concat(base);
     1055
     1056        aoff64_t a_size = 0, b_size = 0;
     1057        if (offset < self->a_size) {
     1058                a_size = *size;
     1059                rc = bithenge_blob_read_bits(self->a, offset, buffer, &a_size,
     1060                    little_endian);
     1061                if (rc != EOK)
     1062                        return rc;
     1063        }
     1064        if (offset + *size > self->a_size) {
     1065                rc = concat_blob_evaluate_b(self);
     1066                if (rc != EOK)
     1067                        return rc;
     1068                b_size = offset + *size - self->a_size;
     1069                rc = bithenge_blob_read_bits(self->b,
     1070                    offset + a_size - self->a_size, buffer + a_size, &b_size,
     1071                    little_endian);
     1072                if (rc != EOK)
     1073                        return rc;
     1074        }
     1075        assert(a_size + b_size <= *size);
     1076        *size = a_size + b_size;
     1077        return EOK;
     1078}
     1079
     1080static void concat_blob_destroy(bithenge_blob_t *base)
     1081{
     1082        concat_blob_t *self = blob_as_concat(base);
     1083        bithenge_blob_dec_ref(self->a);
     1084        bithenge_blob_dec_ref(self->b);
     1085        bithenge_expression_dec_ref(self->b_expr);
     1086        bithenge_scope_dec_ref(self->scope);
     1087        free(self);
     1088}
     1089
     1090static const bithenge_random_access_blob_ops_t concat_blob_ops = {
     1091        .size = concat_blob_size,
     1092        .read = concat_blob_read,
     1093        .read_bits = concat_blob_read_bits,
     1094        .destroy = concat_blob_destroy,
     1095};
     1096
     1097/** Create a concatenated blob. Takes references to @a a and @a b.
     1098 * @param[out] out Holds the new blob.
     1099 * @param a The first blob.
     1100 * @param b The second blob.
     1101 * @return EOK on success or an error code from errno.h. */
     1102int bithenge_concat_blob(bithenge_node_t **out, bithenge_blob_t *a,
     1103    bithenge_blob_t *b)
     1104{
     1105        assert(out);
     1106        assert(a);
     1107        assert(b);
     1108        int rc;
     1109        concat_blob_t *self = malloc(sizeof(*self));
     1110        if (!self) {
     1111                rc = ENOMEM;
     1112                goto error;
     1113        }
     1114
     1115        rc = bithenge_blob_size(a, &self->a_size);
     1116        if (rc != EOK)
     1117                goto error;
     1118
     1119        rc = bithenge_init_random_access_blob(concat_as_blob(self),
     1120            &concat_blob_ops);
     1121        if (rc != EOK)
     1122                goto error;
     1123        self->a = a;
     1124        self->b = b;
     1125        self->b_expr = NULL;
     1126        self->scope = NULL;
     1127        *out = bithenge_blob_as_node(concat_as_blob(self));
     1128        return EOK;
     1129
     1130error:
     1131        bithenge_blob_dec_ref(a);
     1132        bithenge_blob_dec_ref(b);
     1133        free(self);
     1134        return rc;
     1135}
     1136
     1137/** Create a lazy concatenated blob. Takes references to @a a, @a b_expr, and
     1138 * @a scope.
     1139 * @param[out] out Holds the new blob.
     1140 * @param a The first blob.
     1141 * @param b_expr An expression to calculate the second blob.
     1142 * @param scope The scope in which @a b_expr should be evaluated.
     1143 * @return EOK on success or an error code from errno.h. */
     1144int bithenge_concat_blob_lazy(bithenge_node_t **out, bithenge_blob_t *a,
     1145    bithenge_expression_t *b_expr, bithenge_scope_t *scope)
     1146{
     1147        assert(out);
     1148        assert(a);
     1149        assert(b_expr);
     1150        assert(scope);
     1151        int rc;
     1152        concat_blob_t *self = malloc(sizeof(*self));
     1153        if (!self) {
     1154                rc = ENOMEM;
     1155                goto error;
     1156        }
     1157
     1158        rc = bithenge_blob_size(a, &self->a_size);
     1159        if (rc != EOK)
     1160                goto error;
     1161
     1162        rc = bithenge_init_random_access_blob(concat_as_blob(self),
     1163            &concat_blob_ops);
     1164        if (rc != EOK)
     1165                goto error;
     1166        self->a = a;
     1167        self->b = NULL;
     1168        self->b_expr = b_expr;
     1169        self->scope = scope;
     1170        *out = bithenge_blob_as_node(concat_as_blob(self));
     1171        return EOK;
     1172
     1173error:
     1174        bithenge_blob_dec_ref(a);
     1175        bithenge_expression_dec_ref(b_expr);
     1176        bithenge_scope_dec_ref(scope);
     1177        free(self);
     1178        return rc;
     1179}
     1180
    9641181/** @}
    9651182 */
  • uspace/lib/bithenge/expression.h

    r681a985 r3a7356dc  
    3838#define BITHENGE_EXPRESSION_H_
    3939
     40#include "blob.h"
    4041#include "transform.h"
    4142#include "tree.h"
     
    135136    bithenge_expression_t *);
    136137
     138int bithenge_concat_blob(bithenge_node_t **, bithenge_blob_t *,
     139    bithenge_blob_t *);
     140int bithenge_concat_blob_lazy(bithenge_node_t **, bithenge_blob_t *,
     141    bithenge_expression_t *, bithenge_scope_t *);
     142
    137143#endif
    138144
Note: See TracChangeset for help on using the changeset viewer.