1.1 --- a/templates/native.c Fri Dec 02 00:55:45 2016 +0100
1.2 +++ b/templates/native.c Fri Dec 02 18:31:20 2016 +0100
1.3 @@ -522,7 +522,7 @@
1.4 /* self.__data__ interpreted as dict */
1.5 __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
1.6 /* index.__data__ interpreted as int */
1.7 - int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
1.8 + int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
1.9
1.10 /* Return size of bucket k. */
1.11 return __new_int(data->keys[k]->size);
1.12 @@ -537,14 +537,14 @@
1.13 __fragment *f;
1.14
1.15 /* Count the number of keys. */
1.16 - for (k = 0; k < __MAPPING_BUCKETS; k++)
1.17 + for (k = 0; k < data->capacity; k++)
1.18 size += data->keys[k]->size;
1.19
1.20 /* Create a fragment for the keys. */
1.21 f = __new_fragment(size);
1.22
1.23 /* Populate the fragment with the keys. */
1.24 - for (j = 0, k = 0; k < __MAPPING_BUCKETS; k++)
1.25 + for (j = 0, k = 0; k < data->capacity; k++)
1.26 for (i = 0; i < data->keys[k]->size; i++, j++)
1.27 f->attrs[j] = data->keys[k]->attrs[i];
1.28 f->size = size;
1.29 @@ -562,14 +562,14 @@
1.30 __fragment *f;
1.31
1.32 /* Count the number of values. */
1.33 - for (k = 0; k < __MAPPING_BUCKETS; k++)
1.34 + for (k = 0; k < data->capacity; k++)
1.35 size += data->values[k]->size;
1.36
1.37 /* Create a fragment for the values. */
1.38 f = __new_fragment(size);
1.39
1.40 /* Populate the fragment with the values. */
1.41 - for (j = 0, k = 0; k < __MAPPING_BUCKETS; k++)
1.42 + for (j = 0, k = 0; k < data->capacity; k++)
1.43 for (i = 0; i < data->values[k]->size; i++, j++)
1.44 f->attrs[j] = data->values[k]->attrs[i];
1.45 f->size = size;
1.46 @@ -586,7 +586,7 @@
1.47 /* self.__data__ interpreted as dict */
1.48 __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
1.49 /* index.__data__ interpreted as int */
1.50 - int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
1.51 + int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
1.52 /* element.__data__ interpreted as int */
1.53 int i = __load_via_object(element->value, __pos___data__).intvalue;
1.54
1.55 @@ -602,7 +602,7 @@
1.56 /* self.__data__ interpreted as dict */
1.57 __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
1.58 /* index.__data__ interpreted as int */
1.59 - int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
1.60 + int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
1.61 /* element.__data__ interpreted as int */
1.62 int i = __load_via_object(element->value, __pos___data__).intvalue;
1.63
1.64 @@ -619,7 +619,8 @@
1.65 /* self.__data__ interpreted as dict */
1.66 __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
1.67 /* index.__data__ interpreted as int */
1.68 - int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
1.69 + int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
1.70 + unsigned int size = data->size;
1.71 __fragment *keys = data->keys[k], *newkeys;
1.72 __fragment *values = data->values[k], *newvalues;
1.73
1.74 @@ -632,6 +633,8 @@
1.75 data->keys[k] = newkeys;
1.76 if (newvalues != values)
1.77 data->values[k] = newvalues;
1.78 +
1.79 + data->size = size + 1;
1.80 return __builtins___none_None;
1.81 }
1.82
1.83 @@ -645,7 +648,7 @@
1.84 /* self.__data__ interpreted as dict */
1.85 __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
1.86 /* index.__data__ interpreted as int */
1.87 - int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
1.88 + int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
1.89 /* element.__data__ interpreted as int */
1.90 int i = __load_via_object(element->value, __pos___data__).intvalue;
1.91
2.1 --- a/templates/progops.c Fri Dec 02 00:55:45 2016 +0100
2.2 +++ b/templates/progops.c Fri Dec 02 18:31:20 2016 +0100
2.3 @@ -35,21 +35,34 @@
2.4 return data;
2.5 }
2.6
2.7 +static inline unsigned int __mapping_buckets(unsigned int n)
2.8 +{
2.9 + return n > 0 ? n / 2 : 5;
2.10 +}
2.11 +
2.12 __mapping *__new_mapping(unsigned int n)
2.13 {
2.14 /* Allocate a number of buckets. */
2.15 - __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(__MAPPING_BUCKETS));
2.16 + unsigned int capacity = __mapping_buckets(n);
2.17 + __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(capacity));
2.18 unsigned int i;
2.19
2.20 - /* Allocate fragments with an initial size of 2 * n / __MAPPING_BUCKETS,
2.21 - assuming a mostly uniform distribution of values across the buckets. */
2.22 + /* Create arrays for key and value buckets. */
2.23 +
2.24 + data->keys = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
2.25 + data->values = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
2.26
2.27 - for (i = 0; i < __MAPPING_BUCKETS; i++)
2.28 + /* Allocate fragments with an initial size of 2, assuming a mostly uniform
2.29 + distribution of values across the buckets will occur. */
2.30 +
2.31 + for (i = 0; i < capacity; i++)
2.32 {
2.33 - data->keys[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
2.34 - data->values[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
2.35 + data->keys[i] = __new_fragment(2);
2.36 + data->values[i] = __new_fragment(2);
2.37 }
2.38
2.39 + data->size = 0;
2.40 + data->capacity = capacity;
2.41 return data;
2.42 }
2.43
3.1 --- a/templates/types.h Fri Dec 02 00:55:45 2016 +0100
3.2 +++ b/templates/types.h Fri Dec 02 18:31:20 2016 +0100
3.3 @@ -83,15 +83,14 @@
3.4 "buckets" used in hash tables. Here, separate lists of keys and values hold
3.5 attributes referring to the actual keys and corresponding values. */
3.6
3.7 -#define __MAPPING_BUCKETS 10
3.8 -
3.9 typedef struct __mapping
3.10 {
3.11 - __fragment *keys[__MAPPING_BUCKETS];
3.12 - __fragment *values[__MAPPING_BUCKETS];
3.13 + unsigned int size, capacity;
3.14 + __fragment **keys; /* array of key arrays */
3.15 + __fragment **values; /* array of value arrays */
3.16 } __mapping;
3.17
3.18 -#define __MAPPING_SIZE(NUMBER) (2 * NUMBER * sizeof(__fragment *) + sizeof(unsigned int))
3.19 +#define __MAPPING_SIZE(NUMBER) (2 * NUMBER * sizeof(__fragment *) + 2 * sizeof(unsigned int))
3.20
3.21 /* Special instance position value. The pos member of __obj refers to the
3.22 special type attribute for classes, indicating which position holds the