From 5a31f694a7cd276c29645bf560160d068f76ce50 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Sat, 28 Feb 2009 12:15:48 -0800 Subject: Implemented the array part of the fieldnum lookup. --- pbstream.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++---- pbstream.h | 16 +++++++++++++--- tests.c | 48 +++++++++++++++++++++++++----------------------- 3 files changed, 84 insertions(+), 30 deletions(-) diff --git a/pbstream.c b/pbstream.c index d5ddc1c..2362e5c 100644 --- a/pbstream.c +++ b/pbstream.c @@ -4,6 +4,8 @@ * Copyright (c) 2008-2009 Joshua Haberman. See LICENSE for details. */ +#include +#include #include #include "pbstream.h" @@ -236,10 +238,8 @@ static pbstream_status_t parse_unknown_value( static struct pbstream_field *find_field(struct pbstream_fieldset* fs, pbstream_field_number_t num) { - /* TODO: a hybrid array/hashtable structure. */ - /* TODO: can zero be a tag number? */ - if(num <= fs->num_fields) return &fs->fields[num-1]; - else return NULL; + /* TODO: the hashtable part. */ + return fs->array[num-1]; } /* Parses and processes the next value from buf. */ @@ -296,3 +296,45 @@ void pbstream_init_parser( state->top->fieldset = toplevel_fieldset; state->top->end_offset = SIZE_MAX; } + +static int compare_fields(const void *f1, const void *f2) +{ + return ((struct pbstream_field*)f1)->field_number - + ((struct pbstream_field*)f2)->field_number; +} + +void pbstream_init_fieldset(struct pbstream_fieldset *fieldset, + struct pbstream_field *fields, + int num_fields) +{ + qsort(fields, num_fields, sizeof(*fields), compare_fields); + + /* Find the largest n for which at least half the fieldnums 8 && maybe_n/(i+1) > 2) break; + n = maybe_n; + } + + fieldset->num_fields = num_fields; + fieldset->fields = malloc(sizeof(*fieldset->fields)*num_fields); + memcpy(fieldset->fields, fields, sizeof(*fields)*num_fields); + + fieldset->array_size = n; + fieldset->array = malloc(sizeof(*fieldset->array)*n); + memset(fieldset->array, 0, sizeof(*fieldset->array)*n); + + for (int i = 0; i < num_fields && fields[i].field_number <= n; i++) + fieldset->array[fields[i].field_number-1] = &fieldset->fields[i]; + + /* Until we support the hashtable part... */ + assert(n == fields[num_fields-1].field_number); +} + +void pbstream_free_fieldset(struct pbstream_fieldset *fieldset) +{ + free(fieldset->fields); + free(fieldset->array); +} diff --git a/pbstream.h b/pbstream.h index b8befc6..cd6fe3a 100644 --- a/pbstream.h +++ b/pbstream.h @@ -91,11 +91,21 @@ struct pbstream_field { /* The set of fields corresponding to a message definition. */ struct pbstream_fieldset { - /* TODO: a hybrid array/hashtable structure. */ int num_fields; - struct pbstream_field fields[]; + struct pbstream_field *fields; + int array_size; + struct pbstream_field **array; + /* TODO: the hashtable part. */ }; +/* Takes an array of num_fields fields and builds an optimized table for fast + * lookup of fields by number. The input fields need not be sorted. This + * fieldset must be freed with pbstream_free_fieldset(). */ +void pbstream_init_fieldset(struct pbstream_fieldset *fieldset, + struct pbstream_field *fields, + int num_fields); +void pbstream_free_fieldset(struct pbstream_fieldset *fieldset); + struct pbstream_parse_stack_frame { struct pbstream_fieldset *fieldset; size_t end_offset; /* unknown for the top frame, so we set to SIZE_MAX */ @@ -134,7 +144,7 @@ typedef enum pbstream_status { // Encountered a "group" on the wire (deprecated and unsupported). PBSTREAM_ERROR_GROUP = -3, - // Input was nested more than 64 deep. + // Input was nested more than PBSTREAM_MAX_STACK deep. PBSTREAM_ERROR_STACK_OVERFLOW = -4, /** NONFATAL ERRORS: the input was invalid, but we can continue if desired. */ diff --git a/tests.c b/tests.c index 2cc9128..cea6911 100644 --- a/tests.c +++ b/tests.c @@ -47,57 +47,57 @@ void test_simple_proto() { /* These are the examples from * http://code.google.com/apis/protocolbuffers/docs/encoding.html */ - struct pbstream_fieldset *fieldset1 = malloc(sizeof(*fieldset1) + - sizeof(struct pbstream_field[2])); - fieldset1->num_fields = 2; - fieldset1->fields[0].field_number = 1; - fieldset1->fields[0].type = PBSTREAM_TYPE_INT32; - fieldset1->fields[1].field_number = 2; - fieldset1->fields[1].type = PBSTREAM_TYPE_STRING; + struct pbstream_field *fields1 = malloc(sizeof(struct pbstream_field[2])); + fields1[0].field_number = 1; + fields1[0].type = PBSTREAM_TYPE_INT32; + fields1[1].field_number = 2; + fields1[1].type = PBSTREAM_TYPE_STRING; + struct pbstream_fieldset fieldset1; + pbstream_init_fieldset(&fieldset1, fields1, 2); char message1[] = {0x08, 0x96, 0x01}; struct pbstream_parse_state s; - pbstream_init_parser(&s, fieldset1); + pbstream_init_parser(&s, &fieldset1); assert(s.offset == 0); pbstream_field_number_t fieldnum; struct pbstream_value val; struct pbstream_wire_value wv; assert(pbstream_parse_field(&s, message1, &fieldnum, &val, &wv) == PBSTREAM_STATUS_OK); - assert(val.field == &fieldset1->fields[0]); + assert(val.field->field_number == 1); assert(val.v.int32 == 150); assert(s.offset == 3); char message2[] = {0x12, 0x07, 0x74, 0x65, 0x73, 0x74, 0x69, 0x6e, 0x67}; - pbstream_init_parser(&s, fieldset1); + pbstream_init_parser(&s, &fieldset1); assert(pbstream_parse_field(&s, message2, &fieldnum, &val, &wv) == PBSTREAM_STATUS_OK); - assert(val.field == &fieldset1->fields[1]); + assert(val.field->field_number == 2); assert(val.v.delimited.offset == 2); assert(val.v.delimited.len == 7); assert(s.offset == 9); - struct pbstream_fieldset *fieldset2 = malloc(sizeof(*fieldset1) + - sizeof(struct pbstream_field[3])); - fieldset2->num_fields = 3; - fieldset2->fields[2].field_number = 3; - fieldset2->fields[2].type = PBSTREAM_TYPE_MESSAGE; - fieldset2->fields[2].fieldset = fieldset1; + struct pbstream_field *fields2 = malloc(sizeof(struct pbstream_field[1])); + fields2[0].field_number = 3; + fields2[0].type = PBSTREAM_TYPE_MESSAGE; + fields2[0].fieldset = &fieldset1; + struct pbstream_fieldset fieldset2; + pbstream_init_fieldset(&fieldset2, fields2, 1); char message3[] = {0x1a, 0x03, 0x08, 0x96, 0x01}; - pbstream_init_parser(&s, fieldset2); + pbstream_init_parser(&s, &fieldset2); assert(pbstream_parse_field(&s, message3, &fieldnum, &val, &wv) == PBSTREAM_STATUS_OK); - assert(val.field == &fieldset2->fields[2]); + assert(val.field->field_number == 3); assert(val.v.delimited.offset == 2); assert(val.v.delimited.len == 3); assert(s.offset == 2); assert(s.top-1 == s.stack); - assert(s.top->fieldset == fieldset1); + assert(s.top->fieldset == &fieldset1); assert(s.top->end_offset == 5); assert(pbstream_parse_field(&s, message3+s.offset, &fieldnum, &val, &wv) == PBSTREAM_STATUS_OK); - assert(val.field == &fieldset1->fields[0]); + assert(val.field->field_number == 1); assert(val.v.int32 == 150); assert(s.offset == 5); @@ -106,8 +106,10 @@ void test_simple_proto() PBSTREAM_STATUS_SUBMESSAGE_END); assert(s.top == s.stack); - free(fieldset1); - free(fieldset2); + pbstream_free_fieldset(&fieldset1); + pbstream_free_fieldset(&fieldset2); + free(fields1); + free(fields2); } int main() -- cgit v1.2.3