1.1 --- a/lib/__builtins__/dict.py Fri Dec 02 18:31:20 2016 +0100
1.2 +++ b/lib/__builtins__/dict.py Fri Dec 02 21:16:06 2016 +0100
1.3 @@ -20,6 +20,7 @@
1.4 """
1.5
1.6 from __builtins__.iterator import itemiterator
1.7 +from __builtins__.sequence import _max
1.8 import native
1.9
1.10 class dict:
1.11 @@ -32,10 +33,7 @@
1.12
1.13 "Initialise the dictionary."
1.14
1.15 - # Reserve an attribute for a hashtable reference along with some space
1.16 - # for elements.
1.17 -
1.18 - self.__data__ = native._dict_init(args is not None and len(args) or 0)
1.19 + self.__data__ = self._get_data(args is not None and len(args) / 2 or 0)
1.20
1.21 if args is not None:
1.22 for key, value in args:
1.23 @@ -64,6 +62,15 @@
1.24
1.25 __repr__ = __str__
1.26
1.27 + def _get_data(self, capacity):
1.28 +
1.29 + """
1.30 + Reserve an attribute for a hashtable reference along with some space
1.31 + for elements.
1.32 + """
1.33 +
1.34 + return native._dict_init(_max(capacity, 5))
1.35 +
1.36 def _get_index(self, key):
1.37
1.38 "Check 'key' and return an index or raise TypeError."
1.39 @@ -78,20 +85,31 @@
1.40
1.41 "Search for 'key', using an 'index' identifying the bucket involved."
1.42
1.43 - size = native._dict_bucketsize(self, index)
1.44 + size = native._dict_bucketsize(self.__data__, index)
1.45 i = 0
1.46
1.47 while i < size:
1.48 - found = native._dict_key(self, index, i)
1.49 + found = native._dict_key(self.__data__, index, i)
1.50 if found == key:
1.51 return i
1.52 i += 1
1.53
1.54 return None
1.55
1.56 - def __setitem__(self, key, value):
1.57 + def _resize(self, capacity):
1.58 +
1.59 + "Resize the hashtable to have the given 'capacity'."
1.60 +
1.61 + newdata = self._get_data(capacity)
1.62
1.63 - "Set a mapping from 'key' to 'value' in the dictionary."
1.64 + for key, value in self.items():
1.65 + self._setitem(newdata, key, value)
1.66 +
1.67 + self.__data__ = newdata
1.68 +
1.69 + def _setitem(self, data, key, value):
1.70 +
1.71 + "Set in the 'data' an item having the given 'key' and 'value'."
1.72
1.73 # Find an index identifying the bucket involved.
1.74
1.75 @@ -104,12 +122,24 @@
1.76 # With no existing entry, append to the bucket.
1.77
1.78 if i is None:
1.79 - native._dict_additem(self, index, key, value)
1.80 + native._dict_additem(data, index, key, value)
1.81
1.82 # With an existing entry, replace the item.
1.83
1.84 else:
1.85 - native._dict_setitem(self, index, i, key, value)
1.86 + native._dict_setitem(data, index, i, key, value)
1.87 +
1.88 + def __setitem__(self, key, value):
1.89 +
1.90 + "Set a mapping from 'key' to 'value' in the dictionary."
1.91 +
1.92 + size = native._dict_items(self.__data__)
1.93 + capacity = native._dict_buckets(self.__data__)
1.94 +
1.95 + if size > capacity:
1.96 + self._resize(capacity * 2)
1.97 +
1.98 + self._setitem(self.__data__, key, value)
1.99
1.100 def __delitem__(self, key, value): pass
1.101
1.102 @@ -140,7 +170,7 @@
1.103 # With a valid entry index, obtain the corresponding value.
1.104
1.105 else:
1.106 - return native._dict_value(self, index, i)
1.107 + return native._dict_value(self.__data__, index, i)
1.108
1.109 def clear(self): pass
1.110 def has_key(self): pass
1.111 @@ -149,13 +179,13 @@
1.112
1.113 "Return the keys for this dictionary."
1.114
1.115 - return native._dict_keys(self)
1.116 + return native._dict_keys(self.__data__)
1.117
1.118 def values(self):
1.119
1.120 "Return the values in this dictionary."
1.121
1.122 - return native._dict_values(self)
1.123 + return native._dict_values(self.__data__)
1.124
1.125 def items(self):
1.126
2.1 --- a/lib/native.py Fri Dec 02 18:31:20 2016 +0100
2.2 +++ b/lib/native.py Fri Dec 02 21:16:06 2016 +0100
2.3 @@ -77,6 +77,8 @@
2.4 # Dictionary operations.
2.5
2.6 def _dict_init(size): pass
2.7 +def _dict_items(self): pass
2.8 +def _dict_buckets(self): pass
2.9 def _dict_bucketsize(self, index): pass
2.10 def _dict_key(self, index, element): pass
2.11 def _dict_value(self, index, element): pass
3.1 --- a/templates/native.c Fri Dec 02 18:31:20 2016 +0100
3.2 +++ b/templates/native.c Fri Dec 02 21:16:06 2016 +0100
3.3 @@ -515,12 +515,30 @@
3.4 return attr;
3.5 }
3.6
3.7 +__attr __fn_native__dict_items(__attr __args[])
3.8 +{
3.9 + __attr * const _data = &__args[1];
3.10 + /* _data interpreted as dict */
3.11 + __mapping *data = _data->mapvalue;
3.12 +
3.13 + return __new_int(data->size);
3.14 +}
3.15 +
3.16 +__attr __fn_native__dict_buckets(__attr __args[])
3.17 +{
3.18 + __attr * const _data = &__args[1];
3.19 + /* _data interpreted as dict */
3.20 + __mapping *data = _data->mapvalue;
3.21 +
3.22 + return __new_int(data->capacity);
3.23 +}
3.24 +
3.25 __attr __fn_native__dict_bucketsize(__attr __args[])
3.26 {
3.27 - __attr * const self = &__args[1];
3.28 + __attr * const _data = &__args[1];
3.29 __attr * const index = &__args[2];
3.30 - /* self.__data__ interpreted as dict */
3.31 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.32 + /* _data interpreted as dict */
3.33 + __mapping *data = _data->mapvalue;
3.34 /* index.__data__ interpreted as int */
3.35 int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.36
3.37 @@ -530,9 +548,9 @@
3.38
3.39 __attr __fn_native__dict_keys(__attr __args[])
3.40 {
3.41 - __attr * const self = &__args[1];
3.42 - /* self.__data__ interpreted as dict */
3.43 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.44 + __attr * const _data = &__args[1];
3.45 + /* _data interpreted as dict */
3.46 + __mapping *data = _data->mapvalue;
3.47 unsigned int k, i, j, size = 0;
3.48 __fragment *f;
3.49
3.50 @@ -555,9 +573,9 @@
3.51
3.52 __attr __fn_native__dict_values(__attr __args[])
3.53 {
3.54 - __attr * const self = &__args[1];
3.55 - /* self.__data__ interpreted as dict */
3.56 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.57 + __attr * const _data = &__args[1];
3.58 + /* _data interpreted as dict */
3.59 + __mapping *data = _data->mapvalue;
3.60 unsigned int k, i, j, size = 0;
3.61 __fragment *f;
3.62
3.63 @@ -580,11 +598,11 @@
3.64
3.65 __attr __fn_native__dict_key(__attr __args[])
3.66 {
3.67 - __attr * const self = &__args[1];
3.68 + __attr * const _data = &__args[1];
3.69 __attr * const index = &__args[2];
3.70 __attr * const element = &__args[3];
3.71 - /* self.__data__ interpreted as dict */
3.72 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.73 + /* _data interpreted as dict */
3.74 + __mapping *data = _data->mapvalue;
3.75 /* index.__data__ interpreted as int */
3.76 int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.77 /* element.__data__ interpreted as int */
3.78 @@ -596,11 +614,11 @@
3.79
3.80 __attr __fn_native__dict_value(__attr __args[])
3.81 {
3.82 - __attr * const self = &__args[1];
3.83 + __attr * const _data = &__args[1];
3.84 __attr * const index = &__args[2];
3.85 __attr * const element = &__args[3];
3.86 - /* self.__data__ interpreted as dict */
3.87 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.88 + /* _data interpreted as dict */
3.89 + __mapping *data = _data->mapvalue;
3.90 /* index.__data__ interpreted as int */
3.91 int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.92 /* element.__data__ interpreted as int */
3.93 @@ -612,12 +630,12 @@
3.94
3.95 __attr __fn_native__dict_additem(__attr __args[])
3.96 {
3.97 - __attr * const self = &__args[1];
3.98 + __attr * const _data = &__args[1];
3.99 __attr * const index = &__args[2];
3.100 __attr * const key = &__args[3];
3.101 __attr * const value = &__args[4];
3.102 - /* self.__data__ interpreted as dict */
3.103 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.104 + /* _data interpreted as dict */
3.105 + __mapping *data = _data->mapvalue;
3.106 /* index.__data__ interpreted as int */
3.107 int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.108 unsigned int size = data->size;
3.109 @@ -640,13 +658,13 @@
3.110
3.111 __attr __fn_native__dict_setitem(__attr __args[])
3.112 {
3.113 - __attr * const self = &__args[1];
3.114 + __attr * const _data = &__args[1];
3.115 __attr * const index = &__args[2];
3.116 __attr * const element = &__args[3];
3.117 __attr * const key = &__args[4];
3.118 __attr * const value = &__args[5];
3.119 - /* self.__data__ interpreted as dict */
3.120 - __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
3.121 + /* _data interpreted as dict */
3.122 + __mapping *data = _data->mapvalue;
3.123 /* index.__data__ interpreted as int */
3.124 int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.125 /* element.__data__ interpreted as int */
4.1 --- a/templates/native.h Fri Dec 02 18:31:20 2016 +0100
4.2 +++ b/templates/native.h Fri Dec 02 21:16:06 2016 +0100
4.3 @@ -53,6 +53,8 @@
4.4 __attr __fn_native__list_setelement(__attr __args[]);
4.5
4.6 __attr __fn_native__dict_init(__attr __args[]);
4.7 +__attr __fn_native__dict_items(__attr __args[]);
4.8 +__attr __fn_native__dict_buckets(__attr __args[]);
4.9 __attr __fn_native__dict_bucketsize(__attr __args[]);
4.10 __attr __fn_native__dict_keys(__attr __args[]);
4.11 __attr __fn_native__dict_values(__attr __args[]);
5.1 --- a/templates/progops.c Fri Dec 02 18:31:20 2016 +0100
5.2 +++ b/templates/progops.c Fri Dec 02 21:16:06 2016 +0100
5.3 @@ -27,42 +27,39 @@
5.4 __fragment *__new_fragment(unsigned int n)
5.5 {
5.6 /* Allocate space for the list. */
5.7 +
5.8 __fragment *data = (__fragment *) __ALLOCATE(1, __FRAGMENT_SIZE(n));
5.9
5.10 /* The initial capacity is the same as the given size. */
5.11 +
5.12 data->size = 0;
5.13 data->capacity = n;
5.14 return data;
5.15 }
5.16
5.17 -static inline unsigned int __mapping_buckets(unsigned int n)
5.18 -{
5.19 - return n > 0 ? n / 2 : 5;
5.20 -}
5.21 -
5.22 __mapping *__new_mapping(unsigned int n)
5.23 {
5.24 /* Allocate a number of buckets. */
5.25 - unsigned int capacity = __mapping_buckets(n);
5.26 - __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(capacity));
5.27 +
5.28 + __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(n));
5.29 unsigned int i;
5.30
5.31 /* Create arrays for key and value buckets. */
5.32
5.33 - data->keys = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
5.34 - data->values = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
5.35 + data->keys = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
5.36 + data->values = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
5.37
5.38 /* Allocate fragments with an initial size of 2, assuming a mostly uniform
5.39 distribution of values across the buckets will occur. */
5.40
5.41 - for (i = 0; i < capacity; i++)
5.42 + for (i = 0; i < n; i++)
5.43 {
5.44 data->keys[i] = __new_fragment(2);
5.45 data->values[i] = __new_fragment(2);
5.46 }
5.47
5.48 data->size = 0;
5.49 - data->capacity = capacity;
5.50 + data->capacity = n;
5.51 return data;
5.52 }
5.53