1.1 --- a/lib/__builtins__/dict.py Fri Dec 02 22:26:53 2016 +0100
1.2 +++ b/lib/__builtins__/dict.py Sat Dec 03 01:23:18 2016 +0100
1.3 @@ -33,7 +33,8 @@
1.4
1.5 "Initialise the dictionary."
1.6
1.7 - self.__data__ = self._get_data(args is not None and len(args) / 2 or 0)
1.8 + self.size = 0
1.9 + self.buckets = self._get_buckets(args is not None and len(args) / 2 or 0)
1.10
1.11 if args is not None:
1.12 for key, value in args:
1.13 @@ -62,34 +63,41 @@
1.14
1.15 __repr__ = __str__
1.16
1.17 - def _get_data(self, capacity):
1.18 + def _get_buckets(self, capacity):
1.19
1.20 """
1.21 Reserve an attribute for a hashtable reference along with some space
1.22 for elements.
1.23 """
1.24
1.25 - return native._dict_init(_max(capacity, 5))
1.26 + buckets = []
1.27 + capacity = _max(capacity, 5)
1.28 + i = 0
1.29 +
1.30 + while i < capacity:
1.31 + buckets.append([])
1.32 + i += 1
1.33 +
1.34 + return buckets
1.35
1.36 def _get_index(self, key):
1.37
1.38 "Check 'key' and return an index or raise TypeError."
1.39
1.40 index = key.__hash__()
1.41 +
1.42 if not native._isinstance(index, int):
1.43 raise TypeError
1.44
1.45 - return index
1.46 + return index % len(self.buckets)
1.47
1.48 def _find_entry(self, key, index):
1.49
1.50 "Search for 'key', using an 'index' identifying the bucket involved."
1.51
1.52 - size = native._dict_bucketsize(self.__data__, index)
1.53 i = 0
1.54
1.55 - while i < size:
1.56 - found = native._dict_key(self.__data__, index, i)
1.57 + for found, value in self.buckets[index]:
1.58 if found == key:
1.59 return i
1.60 i += 1
1.61 @@ -100,16 +108,16 @@
1.62
1.63 "Resize the hashtable to have the given 'capacity'."
1.64
1.65 - newdata = self._get_data(capacity)
1.66 + buckets = self._get_buckets(capacity)
1.67
1.68 for key, value in self.items():
1.69 - self._setitem(newdata, key, value)
1.70 + self._setitem(buckets, key, value)
1.71
1.72 - self.__data__ = newdata
1.73 + self.buckets = buckets
1.74
1.75 - def _setitem(self, data, key, value):
1.76 + def _setitem(self, buckets, key, value):
1.77
1.78 - "Set in the 'data' an item having the given 'key' and 'value'."
1.79 + "Set in the 'buckets' an item having the given 'key' and 'value'."
1.80
1.81 # Find an index identifying the bucket involved.
1.82
1.83 @@ -122,24 +130,24 @@
1.84 # With no existing entry, append to the bucket.
1.85
1.86 if i is None:
1.87 - native._dict_additem(data, index, key, value)
1.88 + buckets[index].append((key, value))
1.89 + self.size += 1
1.90
1.91 # With an existing entry, replace the item.
1.92
1.93 else:
1.94 - native._dict_setitem(data, index, i, key, value)
1.95 + buckets[index][i] = key, value
1.96
1.97 def __setitem__(self, key, value):
1.98
1.99 "Set a mapping from 'key' to 'value' in the dictionary."
1.100
1.101 - size = native._dict_items(self.__data__)
1.102 - capacity = native._dict_buckets(self.__data__)
1.103 + capacity = len(self.buckets)
1.104
1.105 - if size > capacity:
1.106 + if self.size > capacity:
1.107 self._resize(capacity * 2)
1.108
1.109 - self._setitem(self.__data__, key, value)
1.110 + self._setitem(self.buckets, key, value)
1.111
1.112 def __delitem__(self, key, value): pass
1.113
1.114 @@ -170,7 +178,7 @@
1.115 # With a valid entry index, obtain the corresponding value.
1.116
1.117 else:
1.118 - return native._dict_value(self.__data__, index, i)
1.119 + return self.buckets[index][i][1]
1.120
1.121 def clear(self): pass
1.122 def has_key(self): pass
1.123 @@ -179,19 +187,28 @@
1.124
1.125 "Return the keys for this dictionary."
1.126
1.127 - return native._dict_keys(self.__data__)
1.128 + l = []
1.129 + for key, value in self.items():
1.130 + l.append(key)
1.131 + return l
1.132
1.133 def values(self):
1.134
1.135 "Return the values in this dictionary."
1.136
1.137 - return native._dict_values(self.__data__)
1.138 + l = []
1.139 + for key, value in self.items():
1.140 + l.append(value)
1.141 + return l
1.142
1.143 def items(self):
1.144
1.145 "Return the items, each being a (key, value) tuple, in this dictionary."
1.146
1.147 - return zip([self.keys(), self.values()])
1.148 + l = []
1.149 + for bucket in self.buckets:
1.150 + l += bucket
1.151 + return l
1.152
1.153 def get(self, key): pass
1.154 def setdefault(self, key, value): pass
2.1 --- a/lib/native.py Fri Dec 02 22:26:53 2016 +0100
2.2 +++ b/lib/native.py Sat Dec 03 01:23:18 2016 +0100
2.3 @@ -74,19 +74,6 @@
2.4 def _list_element(self, index): pass
2.5 def _list_setelement(self, index, value): pass
2.6
2.7 -# Dictionary operations.
2.8 -
2.9 -def _dict_init(size): pass
2.10 -def _dict_items(self): pass
2.11 -def _dict_buckets(self): pass
2.12 -def _dict_bucketsize(self, index): pass
2.13 -def _dict_key(self, index, element): pass
2.14 -def _dict_value(self, index, element): pass
2.15 -def _dict_additem(self, index, key, value): pass
2.16 -def _dict_setitem(self, index, element, key, value): pass
2.17 -def _dict_keys(self): pass
2.18 -def _dict_values(self): pass
2.19 -
2.20 # Buffer operations.
2.21
2.22 def _buffer_str(self): pass
3.1 --- a/templates/native.c Fri Dec 02 22:26:53 2016 +0100
3.2 +++ b/templates/native.c Sat Dec 03 01:23:18 2016 +0100
3.3 @@ -503,180 +503,6 @@
3.4 return __builtins___none_None;
3.5 }
3.6
3.7 -__attr __fn_native__dict_init(__attr __args[])
3.8 -{
3.9 - __attr * const size = &__args[1];
3.10 - /* size.__data__ interpreted as int */
3.11 - unsigned int n = __load_via_object(size->value, __pos___data__).intvalue;
3.12 - __mapping *data = __new_mapping(n);
3.13 - __attr attr = {0, .mapvalue=data};
3.14 -
3.15 - /* Return the __data__ attribute. */
3.16 - return attr;
3.17 -}
3.18 -
3.19 -__attr __fn_native__dict_items(__attr __args[])
3.20 -{
3.21 - __attr * const _data = &__args[1];
3.22 - /* _data interpreted as dict */
3.23 - __mapping *data = _data->mapvalue;
3.24 -
3.25 - return __new_int(data->size);
3.26 -}
3.27 -
3.28 -__attr __fn_native__dict_buckets(__attr __args[])
3.29 -{
3.30 - __attr * const _data = &__args[1];
3.31 - /* _data interpreted as dict */
3.32 - __mapping *data = _data->mapvalue;
3.33 -
3.34 - return __new_int(data->capacity);
3.35 -}
3.36 -
3.37 -__attr __fn_native__dict_bucketsize(__attr __args[])
3.38 -{
3.39 - __attr * const _data = &__args[1];
3.40 - __attr * const index = &__args[2];
3.41 - /* _data interpreted as dict */
3.42 - __mapping *data = _data->mapvalue;
3.43 - /* index.__data__ interpreted as int */
3.44 - int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.45 -
3.46 - /* Return size of bucket k. */
3.47 - return __new_int(data->keys[k]->size);
3.48 -}
3.49 -
3.50 -__attr __fn_native__dict_keys(__attr __args[])
3.51 -{
3.52 - __attr * const _data = &__args[1];
3.53 - /* _data interpreted as dict */
3.54 - __mapping *data = _data->mapvalue;
3.55 - unsigned int k, i, j, size = 0;
3.56 - __fragment *f;
3.57 -
3.58 - /* Count the number of keys. */
3.59 - for (k = 0; k < data->capacity; k++)
3.60 - size += data->keys[k]->size;
3.61 -
3.62 - /* Create a fragment for the keys. */
3.63 - f = __new_fragment(size);
3.64 -
3.65 - /* Populate the fragment with the keys. */
3.66 - for (j = 0, k = 0; k < data->capacity; k++)
3.67 - for (i = 0; i < data->keys[k]->size; i++, j++)
3.68 - f->attrs[j] = data->keys[k]->attrs[i];
3.69 - f->size = size;
3.70 -
3.71 - /* Return a list. */
3.72 - return __new_list(f);
3.73 -}
3.74 -
3.75 -__attr __fn_native__dict_values(__attr __args[])
3.76 -{
3.77 - __attr * const _data = &__args[1];
3.78 - /* _data interpreted as dict */
3.79 - __mapping *data = _data->mapvalue;
3.80 - unsigned int k, i, j, size = 0;
3.81 - __fragment *f;
3.82 -
3.83 - /* Count the number of values. */
3.84 - for (k = 0; k < data->capacity; k++)
3.85 - size += data->values[k]->size;
3.86 -
3.87 - /* Create a fragment for the values. */
3.88 - f = __new_fragment(size);
3.89 -
3.90 - /* Populate the fragment with the values. */
3.91 - for (j = 0, k = 0; k < data->capacity; k++)
3.92 - for (i = 0; i < data->values[k]->size; i++, j++)
3.93 - f->attrs[j] = data->values[k]->attrs[i];
3.94 - f->size = size;
3.95 -
3.96 - /* Return a list. */
3.97 - return __new_list(f);
3.98 -}
3.99 -
3.100 -__attr __fn_native__dict_key(__attr __args[])
3.101 -{
3.102 - __attr * const _data = &__args[1];
3.103 - __attr * const index = &__args[2];
3.104 - __attr * const element = &__args[3];
3.105 - /* _data interpreted as dict */
3.106 - __mapping *data = _data->mapvalue;
3.107 - /* index.__data__ interpreted as int */
3.108 - int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.109 - /* element.__data__ interpreted as int */
3.110 - int i = __load_via_object(element->value, __pos___data__).intvalue;
3.111 -
3.112 - /* Return key from bucket k, element i. */
3.113 - return data->keys[k]->attrs[i];
3.114 -}
3.115 -
3.116 -__attr __fn_native__dict_value(__attr __args[])
3.117 -{
3.118 - __attr * const _data = &__args[1];
3.119 - __attr * const index = &__args[2];
3.120 - __attr * const element = &__args[3];
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 */
3.126 - int i = __load_via_object(element->value, __pos___data__).intvalue;
3.127 -
3.128 - /* Return value from bucket k, element i. */
3.129 - return data->values[k]->attrs[i];
3.130 -}
3.131 -
3.132 -__attr __fn_native__dict_additem(__attr __args[])
3.133 -{
3.134 - __attr * const _data = &__args[1];
3.135 - __attr * const index = &__args[2];
3.136 - __attr * const key = &__args[3];
3.137 - __attr * const value = &__args[4];
3.138 - /* _data interpreted as dict */
3.139 - __mapping *data = _data->mapvalue;
3.140 - /* index.__data__ interpreted as int */
3.141 - int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.142 - unsigned int size = data->size;
3.143 - __fragment *keys = data->keys[k], *newkeys;
3.144 - __fragment *values = data->values[k], *newvalues;
3.145 -
3.146 - /* Append the item. */
3.147 - newkeys = __fragment_append(keys, key);
3.148 - newvalues = __fragment_append(values, value);
3.149 -
3.150 - /* Replace the fragments if appropriate. */
3.151 - if (newkeys != keys)
3.152 - data->keys[k] = newkeys;
3.153 - if (newvalues != values)
3.154 - data->values[k] = newvalues;
3.155 -
3.156 - data->size = size + 1;
3.157 - return __builtins___none_None;
3.158 -}
3.159 -
3.160 -__attr __fn_native__dict_setitem(__attr __args[])
3.161 -{
3.162 - __attr * const _data = &__args[1];
3.163 - __attr * const index = &__args[2];
3.164 - __attr * const element = &__args[3];
3.165 - __attr * const key = &__args[4];
3.166 - __attr * const value = &__args[5];
3.167 - /* _data interpreted as dict */
3.168 - __mapping *data = _data->mapvalue;
3.169 - /* index.__data__ interpreted as int */
3.170 - int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
3.171 - /* element.__data__ interpreted as int */
3.172 - int i = __load_via_object(element->value, __pos___data__).intvalue;
3.173 -
3.174 - /* Replace the item. */
3.175 - data->keys[k]->attrs[i] = *key;
3.176 - data->values[k]->attrs[i] = *value;
3.177 -
3.178 - return __builtins___none_None;
3.179 -}
3.180 -
3.181 __attr __fn_native__buffer_str(__attr __args[])
3.182 {
3.183 __attr * const _data = &__args[1];
4.1 --- a/templates/native.h Fri Dec 02 22:26:53 2016 +0100
4.2 +++ b/templates/native.h Sat Dec 03 01:23:18 2016 +0100
4.3 @@ -52,17 +52,6 @@
4.4 __attr __fn_native__list_element(__attr __args[]);
4.5 __attr __fn_native__list_setelement(__attr __args[]);
4.6
4.7 -__attr __fn_native__dict_init(__attr __args[]);
4.8 -__attr __fn_native__dict_items(__attr __args[]);
4.9 -__attr __fn_native__dict_buckets(__attr __args[]);
4.10 -__attr __fn_native__dict_bucketsize(__attr __args[]);
4.11 -__attr __fn_native__dict_keys(__attr __args[]);
4.12 -__attr __fn_native__dict_values(__attr __args[]);
4.13 -__attr __fn_native__dict_key(__attr __args[]);
4.14 -__attr __fn_native__dict_value(__attr __args[]);
4.15 -__attr __fn_native__dict_additem(__attr __args[]);
4.16 -__attr __fn_native__dict_setitem(__attr __args[]);
4.17 -
4.18 __attr __fn_native__buffer_str(__attr __args[]);
4.19
4.20 __attr __fn_native__get_using(__attr __args[]);
5.1 --- a/templates/progops.c Fri Dec 02 22:26:53 2016 +0100
5.2 +++ b/templates/progops.c Sat Dec 03 01:23:18 2016 +0100
5.3 @@ -37,32 +37,6 @@
5.4 return data;
5.5 }
5.6
5.7 -__mapping *__new_mapping(unsigned int n)
5.8 -{
5.9 - /* Allocate a number of buckets. */
5.10 -
5.11 - __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(n));
5.12 - unsigned int i;
5.13 -
5.14 - /* Create arrays for key and value buckets. */
5.15 -
5.16 - data->keys = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
5.17 - data->values = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
5.18 -
5.19 - /* Allocate fragments with an initial size of 2, assuming a mostly uniform
5.20 - distribution of values across the buckets will occur. */
5.21 -
5.22 - for (i = 0; i < n; i++)
5.23 - {
5.24 - data->keys[i] = __new_fragment(2);
5.25 - data->values[i] = __new_fragment(2);
5.26 - }
5.27 -
5.28 - data->size = 0;
5.29 - data->capacity = n;
5.30 - return data;
5.31 -}
5.32 -
5.33 void __newdata_sequence(__attr args[], unsigned int number)
5.34 {
5.35 /* Calculate the size of the fragment. */
5.36 @@ -87,32 +61,20 @@
5.37
5.38 void __newdata_mapping(__attr args[], unsigned int number)
5.39 {
5.40 - __mapping *data = __new_mapping(number);
5.41 - __attr attr = {0, .mapvalue=data};
5.42 - __fragment *f;
5.43 - __attr callargs[3];
5.44 - unsigned int i;
5.45 + __attr dict = args[0];
5.46 + __attr callargs[2];
5.47
5.48 - /* Store a reference to the data in the object's __data__ attribute. */
5.49 + /* Create a temporary list using the arguments. */
5.50
5.51 - __store_via_object(args[0].value, __pos___data__, attr);
5.52 -
5.53 - /* Store the given number of values, starting from the second element. */
5.54 + __newliteral___builtins___list_list(args, number);
5.55
5.56 - callargs[0] = args[0];
5.57 -
5.58 - for (i = 1; i <= number; i++)
5.59 - {
5.60 - /* Obtain the tuple elements. */
5.61 + /* Call __init__ with the dict object and list argument. */
5.62
5.63 - f = __load_via_object(args[i].value, __pos___data__).seqvalue;
5.64 - callargs[1] = f->attrs[0];
5.65 - callargs[2] = f->attrs[1];
5.66 + callargs[0] = dict;
5.67 + callargs[1] = args[0];
5.68
5.69 - /* Call __setitem__ with the key and value. */
5.70 -
5.71 - __fn___builtins___dict_dict___setitem__(callargs);
5.72 - }
5.73 + __fn___builtins___dict_dict___init__(callargs);
5.74 + args[0] = dict;
5.75 }
5.76
5.77 #endif /* __HAVE___builtins___dict_dict */
6.1 --- a/templates/progops.h Fri Dec 02 22:26:53 2016 +0100
6.2 +++ b/templates/progops.h Sat Dec 03 01:23:18 2016 +0100
6.3 @@ -9,8 +9,6 @@
6.4
6.5 __fragment *__new_fragment(unsigned int n);
6.6
6.7 -__mapping *__new_mapping(unsigned int n);
6.8 -
6.9 void __newdata_sequence(__attr args[], unsigned int number);
6.10
6.11 void __newdata_mapping(__attr args[], unsigned int number);
7.1 --- a/templates/types.h Fri Dec 02 22:26:53 2016 +0100
7.2 +++ b/templates/types.h Sat Dec 03 01:23:18 2016 +0100
7.3 @@ -32,7 +32,6 @@
7.4
7.5 typedef struct __obj __obj;
7.6 typedef struct __fragment __fragment;
7.7 -typedef struct __mapping __mapping;
7.8
7.9 typedef struct __attr
7.10 {
7.11 @@ -55,7 +54,6 @@
7.12 double floatvalue; /* floating point value */
7.13 char * strvalue; /* string value */
7.14 __fragment * seqvalue; /* sequence data */
7.15 - __mapping * mapvalue; /* mapping data */
7.16 };
7.17 } __attr;
7.18
7.19 @@ -79,19 +77,6 @@
7.20
7.21 #define __FRAGMENT_SIZE(NUMBER) (NUMBER * sizeof(__attr) + 2 * sizeof(unsigned int))
7.22
7.23 -/* Mappings are simple collections of fragment references used to hold the
7.24 - "buckets" used in hash tables. Here, separate lists of keys and values hold
7.25 - attributes referring to the actual keys and corresponding values. */
7.26 -
7.27 -typedef struct __mapping
7.28 -{
7.29 - unsigned int size, capacity;
7.30 - __fragment **keys; /* array of key arrays */
7.31 - __fragment **values; /* array of value arrays */
7.32 -} __mapping;
7.33 -
7.34 -#define __MAPPING_SIZE(NUMBER) (2 * NUMBER * sizeof(__fragment *) + 2 * sizeof(unsigned int))
7.35 -
7.36 /* Special instance position value. The pos member of __obj refers to the
7.37 special type attribute for classes, indicating which position holds the
7.38 attribute describing the class type. For instances, it is set to zero. */
8.1 --- a/tests/list.py Fri Dec 02 22:26:53 2016 +0100
8.2 +++ b/tests/list.py Sat Dec 03 01:23:18 2016 +0100
8.3 @@ -1,6 +1,6 @@
8.4 l = [1, 2, 3]
8.5 l.append("four")
8.6 -print len(l) # 3
8.7 +print len(l) # 4
8.8 print l[0] # 1
8.9 print l[1] # 2
8.10 print l[2] # 3