[950] in BarnOwl Developers
[D-O-H] r936 - branches/barnowl_sqlite/owl
daemon@ATHENA.MIT.EDU (nelhage@MIT.EDU)
Thu Oct 29 18:11:28 2009
Resent-From: nelhage@mit.edu
Resent-To: barnowl-dev-mtg@charon.mit.edu
X-Original-To: nelhage@nelhage.com
To: dirty-owl-hackers@MIT.EDU
From: nelhage@MIT.EDU
Reply-to: dirty-owl-hackers@MIT.EDU
Date: Sat, 9 Feb 2008 22:25:53 -0500 (EST)
Author: nelhage
Date: 2008-02-09 22:25:53 -0500 (Sat, 09 Feb 2008)
New Revision: 936
Modified:
branches/barnowl_sqlite/owl/list.c
Log:
owl_list now supports efficient prepend
Modified: branches/barnowl_sqlite/owl/list.c
===================================================================
--- branches/barnowl_sqlite/owl/list.c 2008-02-10 03:11:18 UTC (rev 935)
+++ branches/barnowl_sqlite/owl/list.c 2008-02-10 03:25:53 UTC (rev 936)
@@ -10,6 +10,7 @@
{
l->size=0;
l->list=(void **)owl_malloc(INITSIZE*sizeof(void *));
+ l->alloc=l->list;
l->avail=INITSIZE;
if (l->list==NULL) return(-1);
return(0);
@@ -21,17 +22,34 @@
}
-void owl_list_grow(owl_list *l, int n) /*noproto*/
+void owl_list_grow_end(owl_list *l) /*noproto*/
{
void *ptr;
- if ((l->size+n) > l->avail) {
- ptr=owl_realloc(l->list, l->avail*GROWBY*sizeof(void *));
- if (ptr==NULL) abort();
- l->list=ptr;
- l->avail=l->avail*GROWBY;
+ if (l->size == l->avail) {
+ int front = (l->list - l->alloc);
+ int alloc = l->avail*GROWBY;
+ ptr=owl_realloc(l->alloc, front + alloc*sizeof(void *));
+ l->alloc = ptr;
+ l->list = ptr+front;
+ l->avail = alloc;
}
+}
+void owl_list_grow_front(owl_list *l) /*noproto*/
+{
+ void *ptr;
+
+ if (l->alloc == l->list) {
+ void *newlist;
+ int alloc = (l->avail + l->list - l->alloc)*GROWBY;
+ ptr=owl_malloc(alloc*sizeof(void *));
+ l->alloc = ptr;
+ newlist = l->alloc + alloc - l->avail;
+ memcpy(newlist, l->list, l->size * sizeof(void*));
+ owl_free(l->list);
+ l->list = newlist;
+ }
}
void *owl_list_get_element(owl_list *l, int n)
@@ -44,7 +62,7 @@
{
int i;
if(at < 0 || at > l->size) return -1;
- owl_list_grow(l, 1);
+ owl_list_grow_end(l);
for (i=l->size; i>at; i--) {
l->list[i]=l->list[i-1];
@@ -62,7 +80,11 @@
int owl_list_prepend_element(owl_list *l, void *element)
{
- return owl_list_insert_element(l, 0, element);
+ owl_list_grow_front(l);
+ l->list--;
+ l->size++;
+ l->list[0] = element;
+ return 0;
}
int owl_list_remove_element(owl_list *l, int n)
@@ -141,7 +163,9 @@
FAIL_UNLESS("size", 30 == owl_list_get_size(&l));
for(i=0;i<10;i++) {
- FAIL_UNLESS("get", -i == (int)owl_list_get_element(&l, i));
+ FAIL_UNLESS("get beg", -i == (int)owl_list_get_element(&l, i));
+ FAIL_UNLESS("get mid", i == (int)owl_list_get_element(&l, 10+i));
+ FAIL_UNLESS("get end", 10+i == (int)owl_list_get_element(&l, 20+i));
}
printf("# END testing owl_list\n");
