# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1480724598 -3600
# Node ID e4bad4af5d439c687076bd94404086da10d4a283
# Parent  c07a749f5bd041fbb767292a377725cddded9b49
Changed the dict implementation to not use native functions or types directly
for its representation.

diff -r c07a749f5bd0 -r e4bad4af5d43 lib/__builtins__/dict.py
--- a/lib/__builtins__/dict.py	Fri Dec 02 22:26:53 2016 +0100
+++ b/lib/__builtins__/dict.py	Sat Dec 03 01:23:18 2016 +0100
@@ -33,7 +33,8 @@
 
         "Initialise the dictionary."
 
-        self.__data__ = self._get_data(args is not None and len(args) / 2 or 0)
+        self.size = 0
+        self.buckets = self._get_buckets(args is not None and len(args) / 2 or 0)
 
         if args is not None:
             for key, value in args:
@@ -62,34 +63,41 @@
 
     __repr__ = __str__
 
-    def _get_data(self, capacity):
+    def _get_buckets(self, capacity):
 
         """
         Reserve an attribute for a hashtable reference along with some space
         for elements.
         """
 
-        return native._dict_init(_max(capacity, 5))
+        buckets = []
+        capacity = _max(capacity, 5)
+        i = 0
+
+        while i < capacity:
+            buckets.append([])
+            i += 1
+
+        return buckets
 
     def _get_index(self, key):
 
         "Check 'key' and return an index or raise TypeError."
 
         index = key.__hash__()
+
         if not native._isinstance(index, int):
             raise TypeError
 
-        return index
+        return index % len(self.buckets)
 
     def _find_entry(self, key, index):
 
         "Search for 'key', using an 'index' identifying the bucket involved."
 
-        size = native._dict_bucketsize(self.__data__, index)
         i = 0
 
-        while i < size:
-            found = native._dict_key(self.__data__, index, i)
+        for found, value in self.buckets[index]:
             if found == key:
                 return i
             i += 1
@@ -100,16 +108,16 @@
 
         "Resize the hashtable to have the given 'capacity'."
 
-        newdata = self._get_data(capacity)
+        buckets = self._get_buckets(capacity)
 
         for key, value in self.items():
-            self._setitem(newdata, key, value)
+            self._setitem(buckets, key, value)
 
-        self.__data__ = newdata
+        self.buckets = buckets
 
-    def _setitem(self, data, key, value):
+    def _setitem(self, buckets, key, value):
 
-        "Set in the 'data' an item having the given 'key' and 'value'."
+        "Set in the 'buckets' an item having the given 'key' and 'value'."
 
         # Find an index identifying the bucket involved.
 
@@ -122,24 +130,24 @@
         # With no existing entry, append to the bucket.
 
         if i is None:
-            native._dict_additem(data, index, key, value)
+            buckets[index].append((key, value))
+            self.size += 1
 
         # With an existing entry, replace the item.
 
         else:
-            native._dict_setitem(data, index, i, key, value)
+            buckets[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__)
+        capacity = len(self.buckets)
 
-        if size > capacity:
+        if self.size > capacity:
             self._resize(capacity * 2)
 
-        self._setitem(self.__data__, key, value)
+        self._setitem(self.buckets, key, value)
 
     def __delitem__(self, key, value): pass
 
@@ -170,7 +178,7 @@
         # With a valid entry index, obtain the corresponding value.
 
         else:
-            return native._dict_value(self.__data__, index, i)
+            return self.buckets[index][i][1]
 
     def clear(self): pass
     def has_key(self): pass
@@ -179,19 +187,28 @@
 
         "Return the keys for this dictionary."
 
-        return native._dict_keys(self.__data__)
+        l = []
+        for key, value in self.items():
+            l.append(key)
+        return l
 
     def values(self):
 
         "Return the values in this dictionary."
 
-        return native._dict_values(self.__data__)
+        l = []
+        for key, value in self.items():
+            l.append(value)
+        return l
 
     def items(self):
 
         "Return the items, each being a (key, value) tuple, in this dictionary."
 
-        return zip([self.keys(), self.values()])
+        l = []
+        for bucket in self.buckets:
+            l += bucket
+        return l
 
     def get(self, key): pass
     def setdefault(self, key, value): pass
diff -r c07a749f5bd0 -r e4bad4af5d43 lib/native.py
--- a/lib/native.py	Fri Dec 02 22:26:53 2016 +0100
+++ b/lib/native.py	Sat Dec 03 01:23:18 2016 +0100
@@ -74,19 +74,6 @@
 def _list_element(self, index): pass
 def _list_setelement(self, index, value): pass
 
-# 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
-def _dict_additem(self, index, key, value): pass
-def _dict_setitem(self, index, element, key, value): pass
-def _dict_keys(self): pass
-def _dict_values(self): pass
-
 # Buffer operations.
 
 def _buffer_str(self): pass
diff -r c07a749f5bd0 -r e4bad4af5d43 templates/native.c
--- a/templates/native.c	Fri Dec 02 22:26:53 2016 +0100
+++ b/templates/native.c	Sat Dec 03 01:23:18 2016 +0100
@@ -503,180 +503,6 @@
     return __builtins___none_None;
 }
 
-__attr __fn_native__dict_init(__attr __args[])
-{
-    __attr * const size = &__args[1];
-    /* size.__data__ interpreted as int */
-    unsigned int n = __load_via_object(size->value, __pos___data__).intvalue;
-    __mapping *data = __new_mapping(n);
-    __attr attr = {0, .mapvalue=data};
-
-    /* Return the __data__ attribute. */
-    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 _data = &__args[1];
-    __attr * const index = &__args[2];
-    /* _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;
-
-    /* Return size of bucket k. */
-    return __new_int(data->keys[k]->size);
-}
-
-__attr __fn_native__dict_keys(__attr __args[])
-{
-    __attr * const _data = &__args[1];
-    /* _data interpreted as dict */
-    __mapping *data = _data->mapvalue;
-    unsigned int k, i, j, size = 0;
-    __fragment *f;
-
-    /* Count the number of keys. */
-    for (k = 0; k < data->capacity; k++)
-        size += data->keys[k]->size;
-
-    /* Create a fragment for the keys. */
-    f =  __new_fragment(size);
-
-    /* Populate the fragment with the keys. */
-    for (j = 0, k = 0; k < data->capacity; k++)
-        for (i = 0; i < data->keys[k]->size; i++, j++)
-            f->attrs[j] = data->keys[k]->attrs[i];
-    f->size = size;
-
-    /* Return a list. */
-    return __new_list(f);
-}
-
-__attr __fn_native__dict_values(__attr __args[])
-{
-    __attr * const _data = &__args[1];
-    /* _data interpreted as dict */
-    __mapping *data = _data->mapvalue;
-    unsigned int k, i, j, size = 0;
-    __fragment *f;
-
-    /* Count the number of values. */
-    for (k = 0; k < data->capacity; k++)
-        size += data->values[k]->size;
-
-    /* Create a fragment for the values. */
-    f =  __new_fragment(size);
-
-    /* Populate the fragment with the values. */
-    for (j = 0, k = 0; k < data->capacity; k++)
-        for (i = 0; i < data->values[k]->size; i++, j++)
-            f->attrs[j] = data->values[k]->attrs[i];
-    f->size = size;
-
-    /* Return a list. */
-    return __new_list(f);
-}
-
-__attr __fn_native__dict_key(__attr __args[])
-{
-    __attr * const _data = &__args[1];
-    __attr * const index = &__args[2];
-    __attr * const element = &__args[3];
-    /* _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 */
-    int i = __load_via_object(element->value, __pos___data__).intvalue;
-
-    /* Return key from bucket k, element i. */
-    return data->keys[k]->attrs[i];
-}
-
-__attr __fn_native__dict_value(__attr __args[])
-{
-    __attr * const _data = &__args[1];
-    __attr * const index = &__args[2];
-    __attr * const element = &__args[3];
-    /* _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 */
-    int i = __load_via_object(element->value, __pos___data__).intvalue;
-
-    /* Return value from bucket k, element i. */
-    return data->values[k]->attrs[i];
-}
-
-__attr __fn_native__dict_additem(__attr __args[])
-{
-    __attr * const _data = &__args[1];
-    __attr * const index = &__args[2];
-    __attr * const key = &__args[3];
-    __attr * const value = &__args[4];
-    /* _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;
-    __fragment *keys = data->keys[k], *newkeys;
-    __fragment *values = data->values[k], *newvalues;
-
-    /* Append the item. */
-    newkeys = __fragment_append(keys, key);
-    newvalues = __fragment_append(values, value);
-
-    /* Replace the fragments if appropriate. */
-    if (newkeys != keys)
-        data->keys[k] = newkeys;
-    if (newvalues != values)
-        data->values[k] = newvalues;
-
-    data->size = size + 1;
-    return __builtins___none_None;
-}
-
-__attr __fn_native__dict_setitem(__attr __args[])
-{
-    __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];
-    /* _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 */
-    int i = __load_via_object(element->value, __pos___data__).intvalue;
-
-    /* Replace the item. */
-    data->keys[k]->attrs[i] = *key;
-    data->values[k]->attrs[i] = *value;
-
-    return __builtins___none_None;
-}
-
 __attr __fn_native__buffer_str(__attr __args[])
 {
     __attr * const _data = &__args[1];
diff -r c07a749f5bd0 -r e4bad4af5d43 templates/native.h
--- a/templates/native.h	Fri Dec 02 22:26:53 2016 +0100
+++ b/templates/native.h	Sat Dec 03 01:23:18 2016 +0100
@@ -52,17 +52,6 @@
 __attr __fn_native__list_element(__attr __args[]);
 __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[]);
-__attr __fn_native__dict_key(__attr __args[]);
-__attr __fn_native__dict_value(__attr __args[]);
-__attr __fn_native__dict_additem(__attr __args[]);
-__attr __fn_native__dict_setitem(__attr __args[]);
-
 __attr __fn_native__buffer_str(__attr __args[]);
 
 __attr __fn_native__get_using(__attr __args[]);
diff -r c07a749f5bd0 -r e4bad4af5d43 templates/progops.c
--- a/templates/progops.c	Fri Dec 02 22:26:53 2016 +0100
+++ b/templates/progops.c	Sat Dec 03 01:23:18 2016 +0100
@@ -37,32 +37,6 @@
     return data;
 }
 
-__mapping *__new_mapping(unsigned int n) 
-{
-    /* Allocate a number of buckets. */
-
-    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(n));
-    unsigned int i;
-
-    /* Create arrays for key and value buckets. */
-
-    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 < n; i++)
-    {
-        data->keys[i] = __new_fragment(2);
-        data->values[i] = __new_fragment(2);
-    }
-
-    data->size = 0;
-    data->capacity = n;
-    return data;
-}
-
 void __newdata_sequence(__attr args[], unsigned int number)
 {
     /* Calculate the size of the fragment. */
@@ -87,32 +61,20 @@
 
 void __newdata_mapping(__attr args[], unsigned int number)
 {
-    __mapping *data = __new_mapping(number);
-    __attr attr = {0, .mapvalue=data};
-    __fragment *f;
-    __attr callargs[3];
-    unsigned int i;
+    __attr dict = args[0];
+    __attr callargs[2];
 
-    /* Store a reference to the data in the object's __data__ attribute. */
+    /* Create a temporary list using the arguments. */
 
-    __store_via_object(args[0].value, __pos___data__, attr);
-
-    /* Store the given number of values, starting from the second element. */
+    __newliteral___builtins___list_list(args, number);
 
-    callargs[0] = args[0];
-
-    for (i = 1; i <= number; i++)
-    {
-        /* Obtain the tuple elements. */
+    /* Call __init__ with the dict object and list argument. */
 
-        f = __load_via_object(args[i].value, __pos___data__).seqvalue;
-        callargs[1] = f->attrs[0];
-        callargs[2] = f->attrs[1];
+    callargs[0] = dict;
+    callargs[1] = args[0];
 
-        /* Call __setitem__ with the key and value. */
-
-        __fn___builtins___dict_dict___setitem__(callargs);
-    }
+    __fn___builtins___dict_dict___init__(callargs);
+    args[0] = dict;
 }
 
 #endif /* __HAVE___builtins___dict_dict */
diff -r c07a749f5bd0 -r e4bad4af5d43 templates/progops.h
--- a/templates/progops.h	Fri Dec 02 22:26:53 2016 +0100
+++ b/templates/progops.h	Sat Dec 03 01:23:18 2016 +0100
@@ -9,8 +9,6 @@
 
 __fragment *__new_fragment(unsigned int n);
 
-__mapping *__new_mapping(unsigned int n);
-
 void __newdata_sequence(__attr args[], unsigned int number);
 
 void __newdata_mapping(__attr args[], unsigned int number);
diff -r c07a749f5bd0 -r e4bad4af5d43 templates/types.h
--- a/templates/types.h	Fri Dec 02 22:26:53 2016 +0100
+++ b/templates/types.h	Sat Dec 03 01:23:18 2016 +0100
@@ -32,7 +32,6 @@
 
 typedef struct __obj __obj;
 typedef struct __fragment __fragment;
-typedef struct __mapping __mapping;
 
 typedef struct __attr
 {
@@ -55,7 +54,6 @@
         double floatvalue;      /* floating point value */
         char * strvalue;        /* string value */
         __fragment * seqvalue;  /* sequence data */
-        __mapping * mapvalue;   /* mapping data */
     };
 } __attr;
 
@@ -79,19 +77,6 @@
 
 #define __FRAGMENT_SIZE(NUMBER) (NUMBER * sizeof(__attr) + 2 * sizeof(unsigned int))
 
-/* Mappings are simple collections of fragment references used to hold the
-   "buckets" used in hash tables. Here, separate lists of keys and values hold
-   attributes referring to the actual keys and corresponding values. */
-
-typedef struct __mapping
-{
-    unsigned int size, capacity;
-    __fragment **keys;          /* array of key arrays */
-    __fragment **values;        /* array of value arrays */
-} __mapping;
-
-#define __MAPPING_SIZE(NUMBER) (2 * NUMBER * sizeof(__fragment *) + 2 * sizeof(unsigned int))
-
 /* Special instance position value. The pos member of __obj refers to the
    special type attribute for classes, indicating which position holds the
    attribute describing the class type. For instances, it is set to zero. */
diff -r c07a749f5bd0 -r e4bad4af5d43 tests/list.py
--- a/tests/list.py	Fri Dec 02 22:26:53 2016 +0100
+++ b/tests/list.py	Sat Dec 03 01:23:18 2016 +0100
@@ -1,6 +1,6 @@
 l = [1, 2, 3]
 l.append("four")
-print len(l)            # 3
+print len(l)            # 4
 print l[0]              # 1
 print l[1]              # 2
 print l[2]              # 3