# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1480709766 -3600
# Node ID f61d81fb98117a9cc9449e2f8a64e1eec978a1b5
# Parent  8e28983c45a716a53c24f7d7cc63614a7d20c00b
Changed the dictionary implementation to support resizing, changing the number
of buckets, also changing the native functions to use the __data__ attribute
directly.

diff -r 8e28983c45a7 -r f61d81fb9811 lib/__builtins__/dict.py
--- a/lib/__builtins__/dict.py	Fri Dec 02 18:31:20 2016 +0100
+++ b/lib/__builtins__/dict.py	Fri Dec 02 21:16:06 2016 +0100
@@ -20,6 +20,7 @@
 """
 
 from __builtins__.iterator import itemiterator
+from __builtins__.sequence import _max
 import native
 
 class dict:
@@ -32,10 +33,7 @@
 
         "Initialise the dictionary."
 
-        # Reserve an attribute for a hashtable reference along with some space
-        # for elements.
-
-        self.__data__ = native._dict_init(args is not None and len(args) or 0)
+        self.__data__ = self._get_data(args is not None and len(args) / 2 or 0)
 
         if args is not None:
             for key, value in args:
@@ -64,6 +62,15 @@
 
     __repr__ = __str__
 
+    def _get_data(self, capacity):
+
+        """
+        Reserve an attribute for a hashtable reference along with some space
+        for elements.
+        """
+
+        return native._dict_init(_max(capacity, 5))
+
     def _get_index(self, key):
 
         "Check 'key' and return an index or raise TypeError."
@@ -78,20 +85,31 @@
 
         "Search for 'key', using an 'index' identifying the bucket involved."
 
-        size = native._dict_bucketsize(self, index)
+        size = native._dict_bucketsize(self.__data__, index)
         i = 0
 
         while i < size:
-            found = native._dict_key(self, index, i)
+            found = native._dict_key(self.__data__, index, i)
             if found == key:
                 return i
             i += 1
 
         return None
 
-    def __setitem__(self, key, value):
+    def _resize(self, capacity):
+
+        "Resize the hashtable to have the given 'capacity'."
+
+        newdata = self._get_data(capacity)
 
-        "Set a mapping from 'key' to 'value' in the dictionary."
+        for key, value in self.items():
+            self._setitem(newdata, key, value)
+
+        self.__data__ = newdata
+
+    def _setitem(self, data, key, value):
+
+        "Set in the 'data' an item having the given 'key' and 'value'."
 
         # Find an index identifying the bucket involved.
 
@@ -104,12 +122,24 @@
         # With no existing entry, append to the bucket.
 
         if i is None:
-            native._dict_additem(self, index, key, value)
+            native._dict_additem(data, index, key, value)
 
         # With an existing entry, replace the item.
 
         else:
-            native._dict_setitem(self, index, i, key, value)
+            native._dict_setitem(data, index, i, key, value)
+
+    def __setitem__(self, key, value):
+
+        "Set a mapping from 'key' to 'value' in the dictionary."
+
+        size = native._dict_items(self.__data__)
+        capacity = native._dict_buckets(self.__data__)
+
+        if size > capacity:
+            self._resize(capacity * 2)
+
+        self._setitem(self.__data__, key, value)
 
     def __delitem__(self, key, value): pass
 
@@ -140,7 +170,7 @@
         # With a valid entry index, obtain the corresponding value.
 
         else:
-            return native._dict_value(self, index, i)
+            return native._dict_value(self.__data__, index, i)
 
     def clear(self): pass
     def has_key(self): pass
@@ -149,13 +179,13 @@
 
         "Return the keys for this dictionary."
 
-        return native._dict_keys(self)
+        return native._dict_keys(self.__data__)
 
     def values(self):
 
         "Return the values in this dictionary."
 
-        return native._dict_values(self)
+        return native._dict_values(self.__data__)
 
     def items(self):
 
diff -r 8e28983c45a7 -r f61d81fb9811 lib/native.py
--- a/lib/native.py	Fri Dec 02 18:31:20 2016 +0100
+++ b/lib/native.py	Fri Dec 02 21:16:06 2016 +0100
@@ -77,6 +77,8 @@
 # Dictionary operations.
 
 def _dict_init(size): pass
+def _dict_items(self): pass
+def _dict_buckets(self): pass
 def _dict_bucketsize(self, index): pass
 def _dict_key(self, index, element): pass
 def _dict_value(self, index, element): pass
diff -r 8e28983c45a7 -r f61d81fb9811 templates/native.c
--- a/templates/native.c	Fri Dec 02 18:31:20 2016 +0100
+++ b/templates/native.c	Fri Dec 02 21:16:06 2016 +0100
@@ -515,12 +515,30 @@
     return attr;
 }
 
+__attr __fn_native__dict_items(__attr __args[])
+{
+    __attr * const _data = &__args[1];
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
+
+    return __new_int(data->size);
+}
+
+__attr __fn_native__dict_buckets(__attr __args[])
+{
+    __attr * const _data = &__args[1];
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
+
+    return __new_int(data->capacity);
+}
+
 __attr __fn_native__dict_bucketsize(__attr __args[])
 {
-    __attr * const self = &__args[1];
+    __attr * const _data = &__args[1];
     __attr * const index = &__args[2];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     /* index.__data__ interpreted as int */
     int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
 
@@ -530,9 +548,9 @@
 
 __attr __fn_native__dict_keys(__attr __args[])
 {
-    __attr * const self = &__args[1];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    __attr * const _data = &__args[1];
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     unsigned int k, i, j, size = 0;
     __fragment *f;
 
@@ -555,9 +573,9 @@
 
 __attr __fn_native__dict_values(__attr __args[])
 {
-    __attr * const self = &__args[1];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    __attr * const _data = &__args[1];
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     unsigned int k, i, j, size = 0;
     __fragment *f;
 
@@ -580,11 +598,11 @@
 
 __attr __fn_native__dict_key(__attr __args[])
 {
-    __attr * const self = &__args[1];
+    __attr * const _data = &__args[1];
     __attr * const index = &__args[2];
     __attr * const element = &__args[3];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     /* index.__data__ interpreted as int */
     int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
     /* element.__data__ interpreted as int */
@@ -596,11 +614,11 @@
 
 __attr __fn_native__dict_value(__attr __args[])
 {
-    __attr * const self = &__args[1];
+    __attr * const _data = &__args[1];
     __attr * const index = &__args[2];
     __attr * const element = &__args[3];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     /* index.__data__ interpreted as int */
     int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
     /* element.__data__ interpreted as int */
@@ -612,12 +630,12 @@
 
 __attr __fn_native__dict_additem(__attr __args[])
 {
-    __attr * const self = &__args[1];
+    __attr * const _data = &__args[1];
     __attr * const index = &__args[2];
     __attr * const key = &__args[3];
     __attr * const value = &__args[4];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     /* index.__data__ interpreted as int */
     int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
     unsigned int size = data->size;
@@ -640,13 +658,13 @@
 
 __attr __fn_native__dict_setitem(__attr __args[])
 {
-    __attr * const self = &__args[1];
+    __attr * const _data = &__args[1];
     __attr * const index = &__args[2];
     __attr * const element = &__args[3];
     __attr * const key = &__args[4];
     __attr * const value = &__args[5];
-    /* self.__data__ interpreted as dict */
-    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* _data interpreted as dict */
+    __mapping *data = _data->mapvalue;
     /* index.__data__ interpreted as int */
     int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
     /* element.__data__ interpreted as int */
diff -r 8e28983c45a7 -r f61d81fb9811 templates/native.h
--- a/templates/native.h	Fri Dec 02 18:31:20 2016 +0100
+++ b/templates/native.h	Fri Dec 02 21:16:06 2016 +0100
@@ -53,6 +53,8 @@
 __attr __fn_native__list_setelement(__attr __args[]);
 
 __attr __fn_native__dict_init(__attr __args[]);
+__attr __fn_native__dict_items(__attr __args[]);
+__attr __fn_native__dict_buckets(__attr __args[]);
 __attr __fn_native__dict_bucketsize(__attr __args[]);
 __attr __fn_native__dict_keys(__attr __args[]);
 __attr __fn_native__dict_values(__attr __args[]);
diff -r 8e28983c45a7 -r f61d81fb9811 templates/progops.c
--- a/templates/progops.c	Fri Dec 02 18:31:20 2016 +0100
+++ b/templates/progops.c	Fri Dec 02 21:16:06 2016 +0100
@@ -27,42 +27,39 @@
 __fragment *__new_fragment(unsigned int n) 
 {
     /* Allocate space for the list. */
+
     __fragment *data = (__fragment *) __ALLOCATE(1, __FRAGMENT_SIZE(n));
 
     /* The initial capacity is the same as the given size. */
+
     data->size = 0;
     data->capacity = n;
     return data;
 }
 
-static inline unsigned int __mapping_buckets(unsigned int n)
-{
-    return n > 0 ? n / 2 : 5;
-}
-
 __mapping *__new_mapping(unsigned int n) 
 {
     /* Allocate a number of buckets. */
-    unsigned int capacity = __mapping_buckets(n);
-    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(capacity));
+
+    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(n));
     unsigned int i;
 
     /* Create arrays for key and value buckets. */
 
-    data->keys = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
-    data->values = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
+    data->keys = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
+    data->values = (__fragment **) __ALLOCATE(n, sizeof(__fragment *));
 
     /* Allocate fragments with an initial size of 2, assuming a mostly uniform
        distribution of values across the buckets will occur. */
 
-    for (i = 0; i < capacity; i++)
+    for (i = 0; i < n; i++)
     {
         data->keys[i] = __new_fragment(2);
         data->values[i] = __new_fragment(2);
     }
 
     data->size = 0;
-    data->capacity = capacity;
+    data->capacity = n;
     return data;
 }