# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1480519097 -3600
# Node ID 70939defa51d27bda84a77a9620a2ec8c93e87aa
# Parent  639a285a92feb5a62667ca8eeca6010a12cf0164
Added dict support, changing the literal instantiators to use functions
appropriate for sequences or mappings that set the __data__ attribute on each
new instance.
Added a __hash__ method for integers.

diff -r 639a285a92fe -r 70939defa51d encoders.py
--- a/encoders.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/encoders.py	Wed Nov 30 16:18:17 2016 +0100
@@ -321,6 +321,15 @@
     else:
         return '"%s"' % str(value).replace('"', '\\"').replace("\n", "\\n").replace("\t", "\\t").replace("\r", "\\r")
 
+def encode_literal_data_initialiser(style):
+
+    """
+    Encode a reference to a function populating the data for a literal having
+    the given 'style' ("mapping" or "sequence").
+    """
+
+    return "__newdata_%s" % style
+
 def encode_literal_instantiator(path):
 
     """
diff -r 639a285a92fe -r 70939defa51d generator.py
--- a/generator.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/generator.py	Wed Nov 30 16:18:17 2016 +0100
@@ -24,6 +24,7 @@
                      encode_instantiator_pointer, \
                      encode_literal_constant, encode_literal_constant_member, \
                      encode_literal_constant_value, \
+                     encode_literal_data_initialiser, \
                      encode_literal_instantiator, encode_literal_reference, \
                      encode_path, \
                      encode_predefined_reference, encode_size, \
@@ -65,12 +66,17 @@
         ("__builtins__.notimplemented", "NotImplemented"),
         )
 
-    literal_instantiator_types = (
+    literal_mapping_types = (
         "__builtins__.dict.dict",
+        )
+
+    literal_sequence_types = (
         "__builtins__.list.list",
         "__builtins__.tuple.tuple",
         )
 
+    literal_instantiator_types = literal_mapping_types + literal_sequence_types
+
     def __init__(self, importer, optimiser, output):
         self.importer = importer
         self.optimiser = optimiser
@@ -910,19 +916,19 @@
         # initialisers but instead populate the structures directly.
 
         if path in self.literal_instantiator_types:
+            if path in self.literal_mapping_types:
+                style = "mapping"
+            else:
+                style = "sequence"
+
             print >>f_code, """\
 __attr %s(__attr __args[], unsigned int number)
 {
-    __attr data;
-
     /* Allocate the structure. */
     __args[0] = __new(&%s, &%s, sizeof(%s));
 
-    /* Allocate a structure for the data. */
-    data = __newfragment(__args, number);
-
-    /* Store a reference to the data in the object's __data__ attribute. */
-    __store_via_object(__args[0].value, %s, data);
+    /* Allocate a structure for the data and set it on the __data__ attribute. */
+    %s(__args, number);
 
     /* Return the allocated object details. */
     return __args[0];
@@ -932,7 +938,7 @@
     encode_tablename("<instance>", path),
     encode_path(path),
     encode_symbol("obj", path),
-    encode_symbol("pos", "__data__")
+    encode_literal_data_initialiser(style)
     )
 
             print >>f_signatures, "__attr %s(__attr[], unsigned int);" % encode_literal_instantiator(path)
diff -r 639a285a92fe -r 70939defa51d lib/__builtins__/dict.py
--- a/lib/__builtins__/dict.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/lib/__builtins__/dict.py	Wed Nov 30 16:18:17 2016 +0100
@@ -3,7 +3,7 @@
 """
 Dictionary objects.
 
-Copyright (C) 2015 Paul Boddie <paul@boddie.org.uk>
+Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk>
 
 This program is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
@@ -20,20 +20,120 @@
 """
 
 from __builtins__.iterator import listiterator
+import native
 
-class dict(object):
-    def __init__(self, *args): pass
-    def __setitem__(self, key, value): pass
+class dict:
+
+    "A dictionary representation mapping keys to values."
+
+    MISSING = object()
+
+    def __init__(self, args=None):
+
+        "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)
+
+        if args is not None:
+            for key, value in args:
+                self.__setitem__(key, value)
+
+    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
+
+    def _find_entry(self, key, index):
+
+        "Search for 'key', using an 'index' identifying the bucket involved."
+
+        size = native._dict_bucketsize(self, index)
+        i = 0
+
+        while i < size:
+            found = native._dict_key(self, index, i)
+            if found == key:
+                return i
+            i += 1
+
+        return None
+
+    def __setitem__(self, key, value):
+
+        "Set a mapping from 'key' to 'value' in the dictionary."
+
+        # Find an index identifying the bucket involved.
+
+        index = self._get_index(key)
+
+        # Find the entry index within the bucket of the key.
+
+        i = self._find_entry(key, index)
+
+        # With no existing entry, append to the bucket.
+
+        if i is None:
+            native._dict_additem(self, index, key, value)
+
+        # With an existing entry, replace the item.
+
+        else:
+            native._dict_setitem(self, index, i, key, value)
+
     def __delitem__(self, key, value): pass
 
-    def __getitem__(self, key):
-        # Note usage.
-        KeyError
+    def __getitem__(self, key, default=MISSING):
+
+        """
+        Return the value stored for 'key'. If 'key' does not have an entry in
+        the dictionary, a KeyError will be raised unless 'default' is specified.
+        In which case, 'default' will be returned instead.
+        """
+
+        # Find an index identifying the bucket involved.
+
+        index = self._get_index(key)
+
+        # Find the entry index within the bucket of the key.
+
+        i = self._find_entry(key, index)
+
+        # With no entry index, either raise an exception or return the default.
+
+        if i is None:
+            if default is self.MISSING:
+                raise KeyError
+            else:
+                return default
+
+        # With a valid entry index, obtain the corresponding value.
+
+        else:
+            return native._dict_value(self, index, i)
 
     def clear(self): pass
     def has_key(self): pass
-    def keys(self): pass
-    def values(self): pass
+
+    def keys(self):
+
+        "Return the keys for this dictionary."
+
+        return native._dict_keys(self)
+
+    def values(self):
+
+        "Return the values in this dictionary."
+
+        return native._dict_values(self)
+
     def items(self): pass
     def get(self, key): pass
     def setdefault(self, key, value): pass
diff -r 639a285a92fe -r 70939defa51d lib/__builtins__/int.py
--- a/lib/__builtins__/int.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/lib/__builtins__/int.py	Wed Nov 30 16:18:17 2016 +0100
@@ -36,6 +36,10 @@
             # NOTE: To be implemented.
             self.__data__ = None
 
+    def __hash__(self):
+        "Return a value for hashing purposes."
+        return self
+
     def __iadd__(self, other):
         "Return a new int for the operation."
         return _binary_op(self, other, native._int_add)
diff -r 639a285a92fe -r 70939defa51d lib/native.py
--- a/lib/native.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/lib/native.py	Wed Nov 30 16:18:17 2016 +0100
@@ -72,6 +72,17 @@
 def _list_element(self, index): pass
 def _list_setelement(self, index, value): pass
 
+# Dictionary operations.
+
+def _dict_init(size): 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 639a285a92fe -r 70939defa51d templates/native.c
--- a/templates/native.c	Tue Nov 29 23:13:18 2016 +0100
+++ b/templates/native.c	Wed Nov 30 16:18:17 2016 +0100
@@ -29,6 +29,36 @@
     return attr;
 }
 
+static __attr __new_list(__fragment *f)
+{
+    /* Create a new list and mutate the __data__ attribute. */
+    __attr attr = __new(&__InstanceTable___builtins___list_list, &__builtins___list_list, sizeof(__obj___builtins___list_list));
+    attr.value->attrs[__pos___data__].seqvalue = f;
+    return attr;
+}
+
+static __fragment *__fragment_append(__fragment *data, __attr * const value)
+{
+    __fragment *newdata = data;
+    unsigned int size = data->size, capacity = data->capacity;
+    unsigned int n;
+
+    /* Re-allocate the fragment if the capacity has been reached. */
+    if (size >= capacity)
+    {
+        /* NOTE: Consider various restrictions on capacity increases. */
+        n = capacity ? capacity * 2 : 1;
+        newdata = (__fragment *) __REALLOCATE(data, __FRAGMENT_SIZE(n));
+        newdata->capacity = n;
+    }
+
+    /* Insert the new element and increment the list size. */
+    newdata->attrs[size] = *value;
+    newdata->size = size + 1;
+
+    return newdata;
+}
+
 /* Native functions. */
 
 __attr __fn_native__exit(__attr __args[])
@@ -338,14 +368,9 @@
     __attr * const size = &__args[1];
     /* size.__data__ interpreted as int */
     unsigned int n = __load_via_object(size->value, __pos___data__).intvalue;
+    __attr attr = {0, .seqvalue=__new_fragment(n)};
 
-    /* Allocate space for the list. */
-    __fragment *data = (__fragment *) __ALLOCATE(1, __FRAGMENT_SIZE(n));
-    __attr attr = {0, .seqvalue=data};
-
-    /* The initial capacity is the same as the given size. */
-    data->size = 0;
-    data->capacity = n;
+    /* Return the __data__ attribute. */
     return attr;
 }
 
@@ -368,22 +393,7 @@
     __attr * const value = &__args[2];
     /* self.__data__ interpreted as list */
     __fragment *data = __load_via_object(self->value, __pos___data__).seqvalue;
-    __fragment *newdata = data;
-    unsigned int size = data->size, capacity = data->capacity;
-    unsigned int n;
-
-    /* Re-allocate the fragment if the capacity has been reached. */
-    if (size >= capacity)
-    {
-        /* NOTE: Consider various restrictions on capacity increases. */
-        n = capacity ? capacity * 2 : 1;
-        newdata = (__fragment *) __REALLOCATE(data, __FRAGMENT_SIZE(n));
-        newdata->capacity = n;
-    }
-
-    /* Insert the new element and increment the list size. */
-    newdata->attrs[size] = *value;
-    newdata->size = size + 1;
+    __fragment *newdata = __fragment_append(data, value);
 
     /* Replace the __data__ attribute if appropriate. */
     if (newdata != data)
@@ -466,6 +476,159 @@
     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_bucketsize(__attr __args[])
+{
+    __attr * const self = &__args[1];
+    __attr * const index = &__args[2];
+    /* self.__data__ interpreted as dict */
+    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    /* index.__data__ interpreted as int */
+    int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
+
+    /* Return size of bucket k. */
+    return __new_int(data->keys[k]->size);
+}
+
+__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;
+    unsigned int k, i, j, size = 0;
+    __fragment *f;
+
+    /* Count the number of keys. */
+    for (k = 0; k < __MAPPING_BUCKETS; 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 < __MAPPING_BUCKETS; 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 self = &__args[1];
+    /* self.__data__ interpreted as dict */
+    __mapping *data = __load_via_object(self->value, __pos___data__).mapvalue;
+    unsigned int k, i, j, size = 0;
+    __fragment *f;
+
+    /* Count the number of values. */
+    for (k = 0; k < __MAPPING_BUCKETS; 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 < __MAPPING_BUCKETS; 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 self = &__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;
+    /* index.__data__ interpreted as int */
+    int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
+    /* 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 self = &__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;
+    /* index.__data__ interpreted as int */
+    int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
+    /* 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 self = &__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;
+    /* index.__data__ interpreted as int */
+    int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
+    __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;
+    return __builtins___none_None;
+}
+
+__attr __fn_native__dict_setitem(__attr __args[])
+{
+    __attr * const self = &__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;
+    /* index.__data__ interpreted as int */
+    int k = __load_via_object(index->value, __pos___data__).intvalue % __MAPPING_BUCKETS;
+    /* 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 self = &__args[1];
diff -r 639a285a92fe -r 70939defa51d templates/native.h
--- a/templates/native.h	Tue Nov 29 23:13:18 2016 +0100
+++ b/templates/native.h	Wed Nov 30 16:18:17 2016 +0100
@@ -50,6 +50,15 @@
 __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_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 639a285a92fe -r 70939defa51d templates/progops.c
--- a/templates/progops.c	Tue Nov 29 23:13:18 2016 +0100
+++ b/templates/progops.c	Wed Nov 30 16:18:17 2016 +0100
@@ -24,11 +24,40 @@
 
 /* Generic internal data allocation. */
 
-__attr __newfragment(__attr args[], unsigned int number)
+__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;
+}
+
+__mapping *__new_mapping(unsigned int n) 
+{
+    /* Allocate a number of buckets. */
+    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(__MAPPING_BUCKETS));
+    unsigned int i;
+
+    /* Allocate fragments with an initial size of 2 * n / __MAPPING_BUCKETS,
+       assuming a mostly uniform distribution of values across the buckets. */
+
+    for (i = 0; i < __MAPPING_BUCKETS; i++)
+    {
+        data->keys[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
+        data->values[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
+    }
+
+    return data;
+}
+
+void __newdata_sequence(__attr args[], unsigned int number)
 {
     /* Calculate the size of the fragment. */
 
-    __fragment *data = (__fragment *) __ALLOCATE(1, __FRAGMENT_SIZE(number));
+    __fragment *data = __new_fragment(number);
     __attr attr = {0, .seqvalue=data};
     unsigned int i, j;
 
@@ -38,8 +67,39 @@
         data->attrs[j] = args[i];
 
     data->size = number;
-    data->capacity = number;
-    return attr;
+
+    /* Store a reference to the data in the object's __data__ attribute. */
+
+    __store_via_object(args[0].value, __pos___data__, attr);
+}
+
+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;
+
+    /* Store a reference to the data in the object's __data__ attribute. */
+
+    __store_via_object(args[0].value, __pos___data__, attr);
+
+    /* Store the given number of values, starting from the second element. */
+
+    for (i = 1; i <= number; i++)
+    {
+        /* Obtain the tuple elements. */
+
+        f = __load_via_object(args[i].value, __pos___data__).seqvalue;
+        callargs[0] = args[0];
+        callargs[1] = f->attrs[0];
+        callargs[2] = f->attrs[1];
+
+        /* Call __setitem__ with the key and value. */
+
+        __fn___builtins___dict_dict___setitem__(callargs);
+    }
 }
 
 /* A helper for raising type errors within common operations. */
diff -r 639a285a92fe -r 70939defa51d templates/progops.h
--- a/templates/progops.h	Tue Nov 29 23:13:18 2016 +0100
+++ b/templates/progops.h	Wed Nov 30 16:18:17 2016 +0100
@@ -7,7 +7,13 @@
 
 __attr __new(const __table *table, __ref cls, size_t size);
 
-__attr __newfragment(__attr args[], unsigned int number);
+__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);
 
 __attr __invoke(__attr callable, int always_callable,
                 unsigned int nkwargs, __param kwcodes[], __attr kwargs[],
diff -r 639a285a92fe -r 70939defa51d templates/types.h
--- a/templates/types.h	Tue Nov 29 23:13:18 2016 +0100
+++ b/templates/types.h	Wed Nov 30 16:18:17 2016 +0100
@@ -32,6 +32,7 @@
 
 typedef struct __obj __obj;
 typedef struct __fragment __fragment;
+typedef struct __mapping __mapping;
 
 typedef struct __attr
 {
@@ -54,6 +55,7 @@
         double floatvalue;      /* floating point value */
         char * strvalue;        /* string value */
         __fragment * seqvalue;  /* sequence data */
+        __mapping * mapvalue;   /* mapping data */
     };
 } __attr;
 
@@ -77,6 +79,20 @@
 
 #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. */
+
+#define __MAPPING_BUCKETS 10
+
+typedef struct __mapping
+{
+    __fragment *keys[__MAPPING_BUCKETS];
+    __fragment *values[__MAPPING_BUCKETS];
+} __mapping;
+
+#define __MAPPING_SIZE(NUMBER) (2 * NUMBER * sizeof(__fragment *) + 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 639a285a92fe -r 70939defa51d tests/dict.py
--- a/tests/dict.py	Tue Nov 29 23:13:18 2016 +0100
+++ b/tests/dict.py	Wed Nov 30 16:18:17 2016 +0100
@@ -1,10 +1,21 @@
 def f(d):
     return d.keys()
 
-def g(d):
-    for key, value in d.items():
-        return value
+#def g(d):
+#    for key, value in d.items():
+#        return value
 
-d = {"a" : 1, "b" : 2}
-f(d) # ["a", "b"]
-g(d) # either 1 or 2
+d = {10 : "a", 20 : "b"}
+l = f(d)
+print 10 in l                          	# True
+print 20 in l                          	# True
+print 30 in l                          	# False
+
+l = d.values()
+print "a" in l                          # True
+print "b" in l                          # True
+print "c" in l                          # False
+
+
+#v = g(d) # either "a" or "b"
+#print v == "a" or v == "b"              # True