Commits

Remi Meier  committed d6733f7

over-allocate lists

  • Participants
  • Parent commits 9ac9542

Comments (0)

Files changed (1)

File listobject.c

 typedef struct {
     DuOBJECT_HEAD
     int ob_count;
+    int ob_capacity;
     DuObject **ob_items;
 } DuListObject;
 
     /* XXX either this ob_items or the original one is never freed */
 }
 
+int overallocated_size(int size)
+{
+    return size + (size >> 3) + (size < 9 ? 3 : 6);
+}
+
 void _list_append(DuListObject *ob, DuObject *x)
 {
     Du_AME_WRITE(ob);
     int i, newcount = ob->ob_count + 1;
     DuObject **olditems = ob->ob_items;
-    DuObject **newitems = malloc(sizeof(DuObject*) * newcount);
-    assert(newitems);
-    for (i=0; i<newcount-1; i++)
-        newitems[i] = olditems[i];
-    Du_INCREF(x);
-    newitems[newcount-1] = x;
-    ob->ob_items = newitems;
-    ob->ob_count = newcount;
-    free(olditems);
+
+    if (newcount <= ob->ob_capacity) {
+        olditems[newcount-1] = x;
+        ob->ob_count = newcount;
+        Du_INCREF(x);
+    } else {
+        int over_newcount = overallocated_size(newcount);
+        DuObject **newitems = malloc(
+            sizeof(DuObject*) * over_newcount);
+        assert(newitems);
+        for (i=0; i<newcount-1; i++)
+            newitems[i] = olditems[i];
+        Du_INCREF(x);
+        newitems[newcount-1] = x;
+        ob->ob_items = newitems;
+        ob->ob_count = newcount;
+        ob->ob_capacity = over_newcount;
+        free(olditems);
+    }
 }
 
 void DuList_Append(DuObject *ob, DuObject *item)
 {
     DuListObject *ob = (DuListObject *)DuObject_New(&DuList_Type);
     ob->ob_count = 0;
+    ob->ob_capacity = 0;
     ob->ob_items = NULL;
     return (DuObject *)ob;
 }