# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1480699880 -3600
# Node ID 8e28983c45a716a53c24f7d7cc63614a7d20c00b
# Parent  503985ccf89356b025d382e8ed45f958ccf9fb90
Changed the hashtable/mapping representation to have a configurable number of
buckets and for the number to be set initially depending on the number of items
provided.

diff -r 503985ccf893 -r 8e28983c45a7 templates/native.c
--- a/templates/native.c	Fri Dec 02 00:55:45 2016 +0100
+++ b/templates/native.c	Fri Dec 02 18:31:20 2016 +0100
@@ -522,7 +522,7 @@
     /* 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;
+    int k = __load_via_object(index->value, __pos___data__).intvalue % data->capacity;
 
     /* Return size of bucket k. */
     return __new_int(data->keys[k]->size);
@@ -537,14 +537,14 @@
     __fragment *f;
 
     /* Count the number of keys. */
-    for (k = 0; k < __MAPPING_BUCKETS; k++)
+    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 < __MAPPING_BUCKETS; k++)
+    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;
@@ -562,14 +562,14 @@
     __fragment *f;
 
     /* Count the number of values. */
-    for (k = 0; k < __MAPPING_BUCKETS; k++)
+    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 < __MAPPING_BUCKETS; k++)
+    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;
@@ -586,7 +586,7 @@
     /* 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;
+    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;
 
@@ -602,7 +602,7 @@
     /* 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;
+    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;
 
@@ -619,7 +619,8 @@
     /* 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;
+    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;
 
@@ -632,6 +633,8 @@
         data->keys[k] = newkeys;
     if (newvalues != values)
         data->values[k] = newvalues;
+
+    data->size = size + 1;
     return __builtins___none_None;
 }
 
@@ -645,7 +648,7 @@
     /* 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;
+    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;
 
diff -r 503985ccf893 -r 8e28983c45a7 templates/progops.c
--- a/templates/progops.c	Fri Dec 02 00:55:45 2016 +0100
+++ b/templates/progops.c	Fri Dec 02 18:31:20 2016 +0100
@@ -35,21 +35,34 @@
     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. */
-    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(__MAPPING_BUCKETS));
+    unsigned int capacity = __mapping_buckets(n);
+    __mapping *data = (__mapping *) __ALLOCATE(1, __MAPPING_SIZE(capacity));
     unsigned int i;
 
-    /* Allocate fragments with an initial size of 2 * n / __MAPPING_BUCKETS,
-       assuming a mostly uniform distribution of values across the buckets. */
+    /* Create arrays for key and value buckets. */
+
+    data->keys = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
+    data->values = (__fragment **) __ALLOCATE(capacity, sizeof(__fragment *));
 
-    for (i = 0; i < __MAPPING_BUCKETS; i++)
+    /* 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++)
     {
-        data->keys[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
-        data->values[i] = __new_fragment(2 * n / __MAPPING_BUCKETS);
+        data->keys[i] = __new_fragment(2);
+        data->values[i] = __new_fragment(2);
     }
 
+    data->size = 0;
+    data->capacity = capacity;
     return data;
 }
 
diff -r 503985ccf893 -r 8e28983c45a7 templates/types.h
--- a/templates/types.h	Fri Dec 02 00:55:45 2016 +0100
+++ b/templates/types.h	Fri Dec 02 18:31:20 2016 +0100
@@ -83,15 +83,14 @@
    "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];
+    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 *) + sizeof(unsigned int))
+#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