From abcf3d934186d02e54253a57504138b900521ef7 Mon Sep 17 00:00:00 2001
From: Nick Mathewson <nickm@torproject.org>
Date: Tue, 30 Mar 2004 19:25:43 +0000
Subject: Make smartlists start small and grow as needed.

svn:r1394
---
 src/common/util.c | 22 +++++++++++++++++++---
 src/common/util.h |  2 ++
 2 files changed, 21 insertions(+), 3 deletions(-)

diff --git a/src/common/util.c b/src/common/util.c
index 80299c4e3..7afc854e0 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -117,12 +117,17 @@ void set_uint32(char *cp, uint32_t v)
  * _add() adds an element, _remove() removes an element if it's there,
  * _choose() returns a random element.
  */
+#define SL_DEFAULT_CAPACITY 32
 
 smartlist_t *smartlist_create(int max_elements) {
   smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
-  sl->list = tor_malloc(sizeof(void *) * max_elements);
   sl->num_used = 0;
   sl->max = max_elements;
+  if (max_elements <= SL_DEFAULT_CAPACITY)
+    sl->capacity = max_elements;
+  else
+    sl->capacity = SL_DEFAULT_CAPACITY;
+  sl->list = tor_malloc(sizeof(void *) * sl->capacity);
   return sl;
 }
 
@@ -131,11 +136,22 @@ void smartlist_free(smartlist_t *sl) {
   free(sl);
 }
 
+void smartlist_grow_capacity(smartlist_t *sl, int n) {
+  if (sl->capacity < n) {
+    sl->capacity = n;
+    sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
+  }
+}
+
 /* add element to the list, but only if there's room */
 void smartlist_add(smartlist_t *sl, void *element) {
-  if(sl->num_used < sl->max)
+  if (sl->num_used < sl->max) {
+    if (sl->num_used >= sl->capacity) {
+      sl->capacity *= 2;
+      sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
+    }
     sl->list[sl->num_used++] = element;
-  else
+  } else
     log_fn(LOG_WARN,"We've already got %d elements, discarding.",sl->max);
 }
 
diff --git a/src/common/util.h b/src/common/util.h
index f7ac07fca..3907a0d94 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -62,10 +62,12 @@ typedef struct {
   void **list;
   int num_used;
   int max;
+  int capacity;
 } smartlist_t;
 
 smartlist_t *smartlist_create(int max_elements);
 void smartlist_free(smartlist_t *sl);
+void smartlist_grow_capacity(smartlist_t *sl, int n);
 void smartlist_add(smartlist_t *sl, void *element);
 void smartlist_remove(smartlist_t *sl, void *element);
 int smartlist_isin(smartlist_t *sl, void *element);
-- 
cgit v1.2.3