From 85f2231b381a232686a39e4962b3d5e3cad61161 Mon Sep 17 00:00:00 2001
From: Mark Pulford <mark@kyne.com.au>
Date: Mon, 25 Apr 2011 00:56:55 +0930
Subject: Add support for growing strbufs exponentially

- Change default to 1024 byte strings and doubling in size
- Add strbuf debug statistics
---
 lua_json.c |  6 ++---
 strbuf.c   | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++---------
 strbuf.h   | 11 ++++++---
 3 files changed, 79 insertions(+), 18 deletions(-)

diff --git a/lua_json.c b/lua_json.c
index 25078a3..10810f0 100644
--- a/lua_json.c
+++ b/lua_json.c
@@ -247,8 +247,7 @@ char *lua_json_encode(lua_State *l, int *len)
     strbuf_t buf;
     char *json;
 
-    strbuf_init(&buf);
-    strbuf_set_increment(&buf, 256);
+    strbuf_init(&buf, 0);
     json_append_data(l, &buf);
     json = strbuf_free_to_string(&buf, len);
 
@@ -637,8 +636,7 @@ void lua_json_decode(lua_State *l, const char *json_text)
 
     json.data = json_text;
     json.index = 0;
-    json.tmp = strbuf_new();
-    strbuf_set_increment(json.tmp, 256);
+    json.tmp = strbuf_new(0);
 
     json_next_token(&json, &token);
     json_process_value(l, &json, &token);
diff --git a/strbuf.c b/strbuf.c
index 9f0d212..227cb47 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -16,19 +16,31 @@ static void die(const char *format, ...)
     exit(-1);
 }
 
-void strbuf_init(strbuf_t *s)
+void strbuf_init(strbuf_t *s, int len)
 {
+    int size;
+
+    if (len <= 0)
+        size = STRBUF_DEFAULT_SIZE;
+    else
+        size = len + 1;         /* \0 terminator */
+
     s->buf = NULL;
-    s->size = 0;
+    s->size = size;
     s->length = 0;
     s->increment = STRBUF_DEFAULT_INCREMENT;
     s->dynamic = 0;
+    s->reallocs = 0;
+    s->debug = 0;
+
+    s->buf = malloc(size);
+    if (!s->buf)
+        die("Out of memory");
 
-    strbuf_resize(s, 0);
     strbuf_ensure_null(s);
 }
 
-strbuf_t *strbuf_new()
+strbuf_t *strbuf_new(int len)
 {
     strbuf_t *s;
 
@@ -36,7 +48,7 @@ strbuf_t *strbuf_new()
     if (!s)
         die("Out of memory");
 
-    strbuf_init(s);
+    strbuf_init(s, len);
 
     /* Dynamic strbuf allocation / deallocation */
     s->dynamic = 1;
@@ -46,14 +58,26 @@ strbuf_t *strbuf_new()
 
 void strbuf_set_increment(strbuf_t *s, int increment)
 {
-    if (increment <= 0)
+    /* Increment > 0:  Linear buffer growth rate
+     * Increment < -1: Exponential buffer growth rate */
+    if (increment == 0 || increment == -1)
         die("BUG: Invalid string increment");
 
     s->increment = increment;
 }
 
+static inline void debug_stats(strbuf_t *s)
+{
+    if (s->debug) {
+        fprintf(stderr, "strbuf(%lx) reallocs: %d, length: %d, size: %d\n",
+                (long)s, s->reallocs, s->length, s->size);
+    }
+}
+
 void strbuf_free(strbuf_t *s)
 {
+    debug_stats(s);
+
     if (s->buf)
         free(s->buf);
     if (s->dynamic)
@@ -64,6 +88,8 @@ char *strbuf_free_to_string(strbuf_t *s, int *len)
 {
     char *buf;
 
+    debug_stats(s);
+
     strbuf_ensure_null(s);
 
     buf = s->buf;
@@ -76,20 +102,52 @@ char *strbuf_free_to_string(strbuf_t *s, int *len)
     return buf;
 }
 
+static int calculate_new_size(strbuf_t *s, int len)
+{
+    int reqsize, newsize;
+
+    if (len <= 0)
+        die("BUG: Invalid strbuf length requested");
+
+    /* Ensure there is room for optional NULL termination */
+    reqsize = len + 1;
+
+    /* If the user has requested to shrink the buffer, do it exactly */
+    if (s->size > reqsize)
+        return reqsize;
+
+    newsize = s->size;
+    if (s->increment < 0) {
+        /* Exponential sizing */
+        while (newsize < reqsize)
+            newsize *= -s->increment;
+    } else {
+        /* Linear sizing */
+        newsize = ((newsize + s->increment - 1) / s->increment) * s->increment;
+    }
+
+    return newsize;
+}
+
+
 /* Ensure strbuf can handle a string length bytes long (ignoring NULL
  * optional termination). */
 void strbuf_resize(strbuf_t *s, int len)
 {
     int newsize;
 
-    /* Ensure there is room for optional NULL termination */
-    newsize = len + 1;
-    /* Round up to the next increment */
-    newsize = ((newsize + s->increment - 1) / s->increment) * s->increment;
+    newsize = calculate_new_size(s, len);
+
+    if (s->debug > 1) {
+        fprintf(stderr, "strbuf(%lx) resize: %d => %d\n",
+                (long)s, s->size, newsize);
+    }
+
     s->size = newsize;
     s->buf = realloc(s->buf, s->size);
     if (!s->buf)
         die("Out of memory");
+    s->reallocs++;
 }
 
 void strbuf_append_mem(strbuf_t *s, const char *c, int len)
@@ -109,7 +167,7 @@ void strbuf_append_string(strbuf_t *s, const char *str)
 
     for (i = 0; str[i]; i++) {
         if (space < 1) {
-            strbuf_resize(s, s->length + s->increment);
+            strbuf_resize(s, s->length + 1);
             space = strbuf_empty_length(s);
         }
 
diff --git a/strbuf.h b/strbuf.h
index 96dd97b..914274c 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -13,15 +13,20 @@ typedef struct {
     int length;
     int increment;
     int dynamic;
+    int reallocs;
+    int debug;
 } strbuf_t;
 
+#ifndef STRBUF_DEFAULT_SIZE
+#define STRBUF_DEFAULT_SIZE 1023
+#endif
 #ifndef STRBUF_DEFAULT_INCREMENT
-#define STRBUF_DEFAULT_INCREMENT 8
+#define STRBUF_DEFAULT_INCREMENT -2
 #endif
 
 /* Initialise */
-extern strbuf_t *strbuf_new();
-extern void strbuf_init(strbuf_t *s);
+extern strbuf_t *strbuf_new(int len);
+extern void strbuf_init(strbuf_t *s, int len);
 extern void strbuf_set_increment(strbuf_t *s, int increment);
 
 /* Release */
-- 
cgit v1.2.3-55-g6feb