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