Changeset 13687

Timestamp:

Dec 24, 2012, 10:38:41 PM (10 years ago)

Author:

jordan

Message:

(trunk, libT) more tr_variant revision: faster serialization, dictionaries use less space

Location:

trunk

Files:

• libtransmission/variant-benc.c (modified) (8 diffs)
• libtransmission/variant-common.h (modified) (1 diff)
• libtransmission/variant-json.c (modified) (5 diffs)
• libtransmission/variant.c (modified) (43 diffs)
• libtransmission/variant.h (modified) (5 diffs)
• qt/my-valgrind.sh (modified) (1 diff)

trunk/libtransmission/variant-benc.c

@@ -12 +12 @@
 
 #include <assert.h>
-#include <ctype.h> /* isdigit () */
+#include <ctype.h> /* isdigit() */
 #include <errno.h>
-#include <stdlib.h> /* strtoul (), strtod (), realloc (), qsort (), mkstemp () */
-#include <string.h> /* strlen (), memchr () */
-
-#include <locale.h> /* setlocale () */
+#include <stdlib.h> /* strtoul(), strtod(), realloc(), qsort(), mkstemp() */
+#include <string.h> /* strlen(), memchr() */
 
 #include <event2/buffer.h>
@@ -26 +24 @@
 #include "transmission.h"
 #include "ptrarray.h"
-#include "utils.h" /* tr_strlcpy () */
+#include "utils.h" /* tr_snprintf() */
 #include "variant.h"
 #include "variant-common.h"
 
 /***
-****  tr_variantParse ()
-****  tr_variantLoad ()
+****  tr_variantParse()
+****  tr_variantLoad()
 ***/
 
@@ -118 +116 @@
 }
 
-static int
-makeroom (tr_variant * container, size_t count)
-{
-  const size_t needed = container->val.l.count + count;
-
-  assert (tr_variantIsContainer (container));
-
-  if (needed > container->val.l.alloc)
+static tr_variant*
+get_node (tr_ptrArray * stack, tr_quark * key, tr_variant * top, int * err)
+{
+  tr_variant * node = NULL;
+
+  if (tr_ptrArrayEmpty (stack))
     {
-      size_t n;
-      void * tmp;
-
-      /* scale the alloc size in powers-of-2 */
-      n = container->val.l.alloc ? container->val.l.alloc : 8;
-      while (n < needed)
-        n *= 2u;
-
-      tmp = realloc (container->val.l.vals, n * sizeof (tr_variant));
-      if (tmp == NULL)
-        return 1;
-
-      container->val.l.alloc = n;
-      container->val.l.vals = tmp;
+      node = top;
     }
-
-  return 0;
-}
-
-static inline bool
-isReadyForDictKey (tr_ptrArray * parentStack)
-{
-  tr_variant * parent = tr_ptrArrayBack (parentStack);
-
-  return (parent != NULL)
-      && (tr_variantIsDict(parent))
-      && ((parent->val.l.count%2)==0);
-}
-
-static tr_variant*
-getNode (tr_variant  * top,
-         tr_ptrArray * parentStack,
-         int           type)
-{
-  tr_variant * parent;
-
-  assert (top);
-  assert (parentStack);
-
-  if (tr_ptrArrayEmpty (parentStack))
-    return top;
-
-  parent = tr_ptrArrayBack (parentStack);
-  assert (parent);
-
-  /* dictionary keys must be strings */
-  if ((parent->type == TR_VARIANT_TYPE_DICT)
-      && (type != TR_VARIANT_TYPE_STR)
-      && (! (parent->val.l.count % 2)))
-    return NULL;
-
-  makeroom (parent, 1);
-  return parent->val.l.vals + parent->val.l.count++;
+  else
+    {
+      tr_variant * parent = tr_ptrArrayBack (stack);
+
+      if (tr_variantIsList (parent))
+        {
+          node = tr_variantListAdd (parent);
+        }
+      else if (*key && tr_variantIsDict (parent))
+        {
+          node = tr_variantDictAdd (parent, *key);
+          *key = 0;
+        }
+      else
+        {
+          *err = EILSEQ;
+        }
+    }
+
+  return node;
 }
 
@@ -187 +152 @@
  * attack via maliciously-crafted bencoded data. (#667)
  */
-static int
-tr_variantParseImpl (const void    * buf_in,
+int
+tr_variantParseBenc (const void    * buf_in,
                      const void    * bufend_in,
                      tr_variant    * top,
-                     tr_ptrArray   * parentStack,
                      const char   ** setme_end)
 {
-  int err;
+  int err = 0;
   const uint8_t * buf = buf_in;
   const uint8_t * bufend = bufend_in;
+  tr_ptrArray stack = TR_PTR_ARRAY_INIT;
+  tr_quark key = 0;
 
   tr_variantInit (top, 0);
@@ -203 +169 @@
     {
       if (buf > bufend) /* no more text to parse... */
-        return 1;
+        err = EILSEQ;
+
+      if (err)
+        break;
 
       if (*buf == 'i') /* int */
@@ -209 +178 @@
           int64_t val;
           const uint8_t * end;
-          tr_variant * node;
+          tr_variant * v;
 
           if ((err = tr_bencParseInt (buf, bufend, &end, &val)))
-            return err;
-
-          node = getNode (top, parentStack, TR_VARIANT_TYPE_INT);
-          if (!node)
-            return EILSEQ;
-
-          tr_variantInitInt (node, val);
+            break;
           buf = end;
 
-          if (tr_ptrArrayEmpty (parentStack))
-            break;
+          if ((v = get_node (&stack, &key, top, &err)))
+            tr_variantInitInt (v, val);
         }
       else if (*buf == 'l') /* list */
         {
-          tr_variant * node = getNode (top, parentStack, TR_VARIANT_TYPE_LIST);
-          if (!node)
-            return EILSEQ;
-
-          tr_variantInit (node, TR_VARIANT_TYPE_LIST);
-          tr_ptrArrayAppend (parentStack, node);
+          tr_variant * v;
+
           ++buf;
+
+          if ((v = get_node (&stack, &key, top, &err)))
+            {
+              tr_variantInitList (v, 0);
+              tr_ptrArrayAppend (&stack, v);
+            }
         }
       else if (*buf == 'd') /* dict */
         {
-          tr_variant * node = getNode (top, parentStack, TR_VARIANT_TYPE_DICT);
-          if (!node)
-            return EILSEQ;
-
-          tr_variantInit (node, TR_VARIANT_TYPE_DICT);
-          tr_ptrArrayAppend (parentStack, node);
+          tr_variant * v;
+
           ++buf;
+
+          if ((v = get_node (&stack, &key, top, &err)))
+            {
+              tr_variantInitDict (v, 0);
+              tr_ptrArrayAppend (&stack, v);
+            }
         }
       else if (*buf == 'e') /* end of list or dict */
         {
-          tr_variant * node;
           ++buf;
-          if (tr_ptrArrayEmpty (parentStack))
-              return EILSEQ;
-
-          node = tr_ptrArrayBack (parentStack);
-          if (tr_variantIsDict (node) && (node->val.l.count % 2))
+
+          if (tr_ptrArrayEmpty (&stack) || (key != 0))
             {
-              /* odd # of children in dict */
-              tr_variantFree (&node->val.l.vals[--node->val.l.count]);
-              return EILSEQ;
+              err = EILSEQ;
+              break;
             }
-
-          tr_ptrArrayPop (parentStack);
-          if (tr_ptrArrayEmpty (parentStack))
-            break;
+          else
+            {
+              tr_ptrArrayPop (&stack);
+              if (tr_ptrArrayEmpty (&stack))
+                break;
+            }
         }
       else if (isdigit (*buf)) /* string? */
         {
+          tr_variant * v;
           const uint8_t * end;
           const uint8_t * str;
           size_t str_len;
-          tr_variant * node;
-          const bool is_key = isReadyForDictKey (parentStack);
 
           if ((err = tr_bencParseStr (buf, bufend, &end, &str, &str_len)))
-            return err;
-
-          node = getNode (top, parentStack, TR_VARIANT_TYPE_STR);
-          if (!node)
-            return EILSEQ;
-
-          if (is_key)
-            tr_variantInitQuark (node, tr_quark_new (str, str_len));
-          else
-            tr_variantInitStr (node, str, str_len);
-
+            break;
           buf = end;
 
-          if (tr_ptrArrayEmpty (parentStack))
-            break;
+          if (!key && !tr_ptrArrayEmpty(&stack) && tr_variantIsDict(tr_ptrArrayBack(&stack)))
+            key = tr_quark_new (str, str_len);
+          else if ((v = get_node (&stack, &key, top, &err)))
+            tr_variantInitStr (v, str, str_len);
         }
       else /* invalid bencoded text... march past it */
@@ -292 +247 @@
           ++buf;
         }
+
+      if (tr_ptrArrayEmpty (&stack))
+        break;
     }
 
-  err = !tr_variantIsSomething (top) || !tr_ptrArrayEmpty (parentStack);
+  if (!err)
+    err = !top->type || !tr_ptrArrayEmpty(&stack);
 
   if (!err && setme_end)
     *setme_end = (const char*) buf;
 
-  return err;
-}
-
-
-int
-tr_variantParseBenc (const void     * buf,
-                     const void     * end,
-                     tr_variant     * top,
-                     const char    ** setme_end)
-{
-  int err;
-  tr_ptrArray parentStack = TR_PTR_ARRAY_INIT;
-
-  top->type = 0; /* set to `uninitialized' */
-  err = tr_variantParseImpl (buf, end, top, &parentStack, setme_end);
-  if (err)
-    tr_variantFree (top);
-
-  tr_ptrArrayDestruct (&parentStack, NULL);
+  tr_ptrArrayDestruct (&stack, NULL);
   return err;
 }
@@ -343 +284 @@
 saveRealFunc (const tr_variant * val, void * evbuf)
 {
+  int len;
   char buf[128];
-  char locale[128];
-  size_t len;
-
-  /* always use a '.' decimal point s.t. locale-hopping doesn't bite us */
-  tr_strlcpy (locale, setlocale (LC_NUMERIC, NULL), sizeof (locale));
-  setlocale (LC_NUMERIC, "POSIX");
-  tr_snprintf (buf, sizeof (buf), "%f", val->val.d);
-  setlocale (LC_NUMERIC, locale);
-
-  len = strlen (buf);
-  evbuffer_add_printf (evbuf, "%lu:", (unsigned long)len);
+
+  len = tr_snprintf (buf, sizeof (buf), "%f", val->val.d);
+  evbuffer_add_printf (evbuf, "%d:", len);
   evbuffer_add (evbuf, buf, len);
 }

trunk/libtransmission/variant-common.h

@@ -41 +41 @@
 void tr_variantToBufBenc (const tr_variant * top, struct evbuffer * buf);
 
-bool tr_variantIsSomething (const tr_variant * v);
-
-bool tr_variantIsContainer (const tr_variant * v);
-
 void tr_variantInit (tr_variant * v, char type);
 

trunk/libtransmission/variant-json.c

@@ -17 +17 @@
 #include <string.h>
 #include <errno.h> /* EILSEQ, EINVAL */
-
-#include <locale.h> /* setlocale() */
 
 #include <event2/buffer.h> /* evbuffer_add() */
@@ -390 +388 @@
 jsonIndent (struct jsonWalk * data)
 {
+  static char buf[1024] = { '\0' };
+  if (!*buf)
+    {
+      memset (buf, ' ', sizeof(buf));
+      buf[0] = '\n';
+    }
+
   if (data->doIndent)
-    {
-      char buf[1024];
-      const int width = tr_list_size (data->parents) * 4;
-
-      buf[0] = '\n';
-      memset (buf+1, ' ', width);
-      evbuffer_add (data->out, buf, 1+width);
-    }
+    evbuffer_add (data->out, buf, tr_list_size(data->parents)*4 + 1);
 }
 
@@ -456 +454 @@
   pstate->childIndex = 0;
   pstate->childCount = v->val.l.count;
+  if (tr_variantIsDict (v))
+    pstate->childCount *= 2;
+
   tr_list_prepend (&data->parents, pstate);
 }
@@ -621 +622 @@
 tr_variantToBufJson (const tr_variant * top, struct evbuffer * buf, bool lean)
 {
-  char lc_numeric[128];
   struct jsonWalk data;
 
@@ -628 +628 @@
   data.parents = NULL;
 
-  /* json requires a '.' decimal point regardless of locale */
-  tr_strlcpy (lc_numeric, setlocale (LC_NUMERIC, NULL), sizeof (lc_numeric));
-  setlocale (LC_NUMERIC, "POSIX");
   tr_variantWalk (top, &walk_funcs, &data, true);
-  setlocale (LC_NUMERIC, lc_numeric);
 
   if (evbuffer_get_length (buf))

trunk/libtransmission/variant.c

@@ -13 +13 @@
 #include <assert.h>
 #include <errno.h>
-#include <stdio.h> /* rename () */
-#include <stdlib.h> /* strtoul (), strtod (), realloc (), qsort (), mkstemp () */
+#include <stdio.h> /* rename() */
+#include <stdlib.h> /* strtoul(), strtod(), realloc(), qsort(), mkstemp() */
 #include <string.h>
 
-#ifdef WIN32 /* tr_mkstemp () */
+#ifdef WIN32 /* tr_mkstemp() */
  #include <fcntl.h>
  #define _S_IREAD 256
@@ -23 +23 @@
 #endif
 
-#include <locale.h> /* setlocale () */
-#include <unistd.h> /* write (), unlink () */
+#include <locale.h> /* setlocale() */
+#include <unistd.h> /* write(), unlink() */
 
 #include <event2/buffer.h>
@@ -31 +31 @@
 #include "transmission.h"
 #include "ConvertUTF.h"  
-#include "fdlimit.h" /* tr_close_file () */
+#include "fdlimit.h" /* tr_close_file() */
 #include "platform.h" /* TR_PATH_MAX */
-#include "utils.h" /* tr_new (), tr_free () */
+#include "utils.h" /* tr_new(), tr_free() */
 #include "variant.h"
 #include "variant-common.h"
@@ -41 +41 @@
 **/
 
-bool
+static bool
 tr_variantIsContainer (const tr_variant * v)
 {
@@ -47 +47 @@
 }
 
-bool
+static bool
 tr_variantIsSomething (const tr_variant * v)
 {
@@ -60 +60 @@
 tr_variantInit (tr_variant * v, char type)
 {
-  memset (v, 0, sizeof (*v));
   v->type = type;
+  memset (&v->val, 0, sizeof(v->val));
 }
 
@@ -67 +67 @@
 ****
 ***/
-
-/*
-zzz
-
-typedef enum
-{
-  TR_STRING_TYPE_KEY,
-  TR_STRING_TYPE_HEAP,
-  TR_STRING_TYPE_BUF
-}
-tr_string_type;
-
-struct tr_variant_string
-{
-  tr_key key;
-  tr_string_type type;
-  size_t len;
-  union { char buf[8]; char * ptr; } str;
-};
-*/
 
 static const struct tr_variant_string STRING_INIT =
@@ -123 +103 @@
 
 static void
-tr_variant_string_set_quark (struct tr_variant_string * str, const tr_quark quark)
+tr_variant_string_set_quark (struct tr_variant_string  * str,
+                             const tr_quark              quark)
 {
   tr_variant_string_clear (str);
@@ -133 +114 @@
 
 static void
-tr_variant_string_set_string (struct tr_variant_string * str, const char * bytes, int len)
+tr_variant_string_set_string (struct tr_variant_string  * str,
+                              const char                * bytes,
+                              int                         len)
 {
   tr_quark quark;
@@ -189 +172 @@
       const tr_variant * const end = begin + dict->val.l.count;
 
-      for (walk=begin; walk!=end; walk+=2)
-      {
-        assert (walk->type == TR_VARIANT_TYPE_STR);
-        assert (walk->val.s.type == TR_STRING_TYPE_QUARK);
-
-        if (walk->val.s.quark == key)
+      for (walk=begin; walk!=end; ++walk)
+        if (walk->key == key)
           return walk - begin;
-      }
     }
 
@@ -207 +185 @@
   const int i = dictIndexOf (dict, key);
 
-  return i < 0 ? NULL : &dict->val.l.vals[i + 1];
+  return i < 0 ? NULL : dict->val.l.vals+i;
 }
 
@@ -226 +204 @@
 
 tr_variant*
-tr_variantListChild (tr_variant * val,
-                  size_t    i)
+tr_variantListChild (tr_variant * v,
+                     size_t    i)
 {
   tr_variant * ret = NULL;
 
-  if (tr_variantIsList (val) && (i < val->val.l.count))
-    ret = val->val.l.vals + i;
+  if (tr_variantIsList (v) && (i < v->val.l.count))
+    ret = v->val.l.vals + i;
 
   return ret;
 }
 
-int
+bool
 tr_variantListRemove (tr_variant * list, size_t i)
 {
+  bool removed = false;
+
   if (tr_variantIsList (list) && (i < list->val.l.count))
     {
+      removed = true;
       tr_variantFree (&list->val.l.vals[i]);
       tr_removeElementFromArray (list->val.l.vals, i,
                                  sizeof (tr_variant),
                                  list->val.l.count--);
-      return 1;
-    }
-
-  return 0;
-}
-
-static void
-tr_variant_warning (const char * err)
-{
-  fprintf (stderr, "warning: %s\n", err);
-}
-
-bool
-tr_variantGetInt (const tr_variant  * val,
+    }
+
+  return removed;
+}
+
+bool
+tr_variantGetInt (const tr_variant  * v,
                   int64_t           * setme)
 {
   bool success = false;
 
-  if (!success && ((success = tr_variantIsInt (val))))
+  if (!success && ((success = tr_variantIsInt (v))))
     if (setme)
-      *setme = val->val.i;
-
-  if (!success && ((success = tr_variantIsBool (val))))
-    {
-      tr_variant_warning ("reading bool as an int");
-      if (setme)
-        *setme = val->val.b ? 1 : 0;
-    }
+      *setme = v->val.i;
+
+  if (!success && ((success = tr_variantIsBool (v))))
+    if (setme)
+      *setme = v->val.b ? 1 : 0;
 
   return success;
@@ -279 +250 @@
 
 bool
-tr_variantGetStr (const tr_variant   * val,
+tr_variantGetStr (const tr_variant   * v,
                   const char        ** setme,
                   size_t             * len)
 {
-  const bool success = tr_variantIsString (val);
+  const bool success = tr_variantIsString (v);
 
   if (success)
-    *setme = getStr (val);
+    *setme = getStr (v);
 
   if (len != NULL)
-    *len = success ? val->val.s.len : 0;
+    *len = success ? v->val.s.len : 0;
 
   return success;
@@ -295 +266 @@
 
 bool
-tr_variantGetRaw (const tr_variant   * val,
+tr_variantGetRaw (const tr_variant   * v,
                   const uint8_t     ** setme_raw,
                   size_t             * setme_len)
 {
-  const bool success = tr_variantIsString (val);
+  const bool success = tr_variantIsString (v);
 
   if (success)
     {
-      *setme_raw = (uint8_t*) getStr (val);
-      *setme_len = val->val.s.len;
+      *setme_raw = (uint8_t*) getStr (v);
+      *setme_len = v->val.s.len;
     }
 
@@ -311 +282 @@
 
 bool
-tr_variantGetBool (const tr_variant * val, bool * setme)
+tr_variantGetBool (const tr_variant * v, bool * setme)
 {
   const char * str;
   bool success = false;
 
-  if ((success = tr_variantIsBool (val)))
-    *setme = val->val.b;
-
-  if (!success && tr_variantIsInt (val))
-    if ((success = (val->val.i==0 || val->val.i==1)))
-      *setme = val->val.i!=0;
-
-  if (!success && tr_variantGetStr (val, &str, NULL))
+  if ((success = tr_variantIsBool (v)))
+    *setme = v->val.b;
+
+  if (!success && tr_variantIsInt (v))
+    if ((success = (v->val.i==0 || v->val.i==1)))
+      *setme = v->val.i!=0;
+
+  if (!success && tr_variantGetStr (v, &str, NULL))
     if ((success = (!strcmp (str,"true") || !strcmp (str,"false"))))
       *setme = !strcmp (str,"true");
@@ -331 +302 @@
 
 bool
-tr_variantGetReal (const tr_variant * val, double * setme)
+tr_variantGetReal (const tr_variant * v, double * setme)
 {
   bool success = false;
 
-  if (!success && ((success = tr_variantIsReal (val))))
-    *setme = val->val.d;
-
-  if (!success && ((success = tr_variantIsInt (val))))
-    *setme = val->val.i;
-
-  if (!success && tr_variantIsString (val))
+  if (!success && ((success = tr_variantIsReal (v))))
+    *setme = v->val.d;
+
+  if (!success && ((success = tr_variantIsInt (v))))
+    *setme = v->val.i;
+
+  if (!success && tr_variantIsString (v))
     {
       char * endptr;
@@ -350 +321 @@
       tr_strlcpy (locale, setlocale (LC_NUMERIC, NULL), sizeof (locale));
       setlocale (LC_NUMERIC, "POSIX");
-      d  = strtod (getStr (val), &endptr);
+      d  = strtod (getStr (v), &endptr);
       setlocale (LC_NUMERIC, locale);
 
-      if ((success = (getStr (val) != endptr) && !*endptr))
+      if ((success = (getStr (v) != endptr) && !*endptr))
         *setme = d;
     }
@@ -402 +373 @@
                         tr_variant      ** setme)
 {
-  return tr_variantDictFindType (dict,
-                                 key,
-                                 TR_VARIANT_TYPE_LIST,
-                                 setme);
+  return tr_variantDictFindType (dict, key, TR_VARIANT_TYPE_LIST, setme);
 }
 
@@ -413 +381 @@
                         tr_variant      ** setme)
 {
-  return tr_variantDictFindType (dict,
-                                 key,
-                                 TR_VARIANT_TYPE_DICT,
-                                 setme);
+  return tr_variantDictFindType (dict, key, TR_VARIANT_TYPE_DICT, setme);
 }
 
@@ -455 +420 @@
 
 void
-tr_variantInitBool (tr_variant * variant, bool value)
-{
-  tr_variantInit (variant, TR_VARIANT_TYPE_BOOL);
-  variant->val.b = value != 0;
-}
-
-void
-tr_variantInitReal (tr_variant * b, double value)
-{
-  tr_variantInit (b, TR_VARIANT_TYPE_REAL);
-  b->val.d = value;
-}
-
-void
-tr_variantInitInt (tr_variant * variant, int64_t value)
-{
-  tr_variantInit (variant, TR_VARIANT_TYPE_INT);
-  variant->val.i = value;
-}
-
-int
-tr_variantInitList (tr_variant * variant, size_t reserve_count)
-{
-  tr_variantInit (variant, TR_VARIANT_TYPE_LIST);
-  return tr_variantListReserve (variant, reserve_count);
-}
-
-static int
-containerReserve (tr_variant * container, size_t count)
-{
-  const size_t needed = container->val.l.count + count;
-
-  assert (tr_variantIsContainer (container));
-
-  if (needed > container->val.l.alloc)
-    {
-      size_t n;
-      void * tmp;
-
+tr_variantInitBool (tr_variant * v, bool value)
+{
+  tr_variantInit (v, TR_VARIANT_TYPE_BOOL);
+  v->val.b = value != 0;
+}
+
+void
+tr_variantInitReal (tr_variant * v, double value)
+{
+  tr_variantInit (v, TR_VARIANT_TYPE_REAL);
+  v->val.d = value;
+}
+
+void
+tr_variantInitInt (tr_variant * v, int64_t value)
+{
+  tr_variantInit (v, TR_VARIANT_TYPE_INT);
+  v->val.i = value;
+}
+
+void
+tr_variantInitList (tr_variant * v, size_t reserve_count)
+{
+  tr_variantInit (v, TR_VARIANT_TYPE_LIST);
+  tr_variantListReserve (v, reserve_count);
+}
+
+static void
+containerReserve (tr_variant * v, size_t count)
+{
+  const size_t needed = v->val.l.count + count;
+
+  assert (tr_variantIsContainer (v));
+
+  if (needed > v->val.l.alloc)
+    {
       /* scale the alloc size in powers-of-2 */
-      n = container->val.l.alloc ? container->val.l.alloc : 8;
+      size_t n = v->val.l.alloc ? v->val.l.alloc : 8;
       while (n < needed)
         n *= 2u;
 
-      tmp = tr_renew (tr_variant, container->val.l.vals, n);
-      if (tmp == NULL)
-        return 1;
-
-      container->val.l.alloc = n;
-      container->val.l.vals = tmp;
-    }
-
-  return 0;
-}
-
-int
+      v->val.l.vals = tr_renew (tr_variant, v->val.l.vals, n);
+      v->val.l.alloc = n;
+    }
+}
+
+void
 tr_variantListReserve (tr_variant * list, size_t count)
 {
   assert (tr_variantIsList (list));
-  return containerReserve (list, count);
-}
-
-int
-tr_variantInitDict (tr_variant * variant, size_t reserve_count)
-{
-  tr_variantInit (variant, TR_VARIANT_TYPE_DICT);
-  return tr_variantDictReserve (variant, reserve_count);
-}
-
-int
+  containerReserve (list, count);
+}
+
+void
+tr_variantInitDict (tr_variant * v, size_t reserve_count)
+{
+  tr_variantInit (v, TR_VARIANT_TYPE_DICT);
+  tr_variantDictReserve (v, reserve_count);
+}
+
+void
 tr_variantDictReserve (tr_variant  * dict,
                        size_t        reserve_count)
 {
   assert (tr_variantIsDict (dict));
-  return containerReserve (dict, reserve_count * 2);
+  containerReserve (dict, reserve_count);
 }
 
@@ -541 +497 @@
   containerReserve (list, 1);
   child = &list->val.l.vals[list->val.l.count++];
+  child->key = 0;
   tr_variantInit (child, TR_VARIANT_TYPE_INT);
 
@@ -623 +580 @@
                    const tr_quark    key)
 {
-  tr_variant * child_key;
-  tr_variant * child_val;
+  tr_variant * val;
 
   assert (tr_variantIsDict (dict));
 
-  containerReserve (dict, 2);
-
-  child_key = dict->val.l.vals + dict->val.l.count++;
-  tr_variantInitQuark (child_key, key);
-
-  child_val = dict->val.l.vals + dict->val.l.count++;
-  tr_variantInit (child_val, TR_VARIANT_TYPE_INT);
-  return child_val;
+  containerReserve (dict, 1);
+
+  val = dict->val.l.vals + dict->val.l.count++;
+  tr_variantInit (val, TR_VARIANT_TYPE_INT);
+  val->key = key;
+  return val;
 }
 
@@ -675 +629 @@
 
 tr_variant*
-tr_variantDictAddBool (tr_variant * dict, const tr_quark key, bool val)
+tr_variantDictAddBool (tr_variant      * dict,
+                       const tr_quark    key,
+                       bool              val)
 {
   tr_variant * child = dictFindOrAdd (dict, key, TR_VARIANT_TYPE_BOOL);
@@ -683 +639 @@
 
 tr_variant*
-tr_variantDictAddReal (tr_variant * dict, const tr_quark key, double val)
+tr_variantDictAddReal (tr_variant      * dict,
+                       const tr_quark    key,
+                       double            val)
 {
   tr_variant * child = dictFindOrAdd (dict, key, TR_VARIANT_TYPE_REAL);
@@ -691 +649 @@
 
 tr_variant*
-tr_variantDictAddQuark (tr_variant * dict, const tr_quark key, const tr_quark val)
+tr_variantDictAddQuark (tr_variant      * dict,
+                        const tr_quark    key,
+                        const tr_quark    val)
 {
   tr_variant * child = dictFindOrAdd (dict, key, TR_VARIANT_TYPE_STR);
@@ -699 +659 @@
 
 tr_variant*
-tr_variantDictAddStr (tr_variant * dict, const tr_quark key, const char * val)
+tr_variantDictAddStr (tr_variant      * dict,
+                      const tr_quark    key,
+                      const char      * val)
 {
   tr_variant * child = dictFindOrAdd (dict, key, TR_VARIANT_TYPE_STR);
@@ -737 +699 @@
 }
 
-int
+bool
 tr_variantDictRemove (tr_variant     * dict,
                       const tr_quark   key)
 {
+  bool removed = false;
   const int i = dictIndexOf (dict, key);
 
   if (i >= 0)
     {
-      const int n = dict->val.l.count;
+      const int last = dict->val.l.count - 1;
+
       tr_variantFree (&dict->val.l.vals[i]);
-      tr_variantFree (&dict->val.l.vals[i + 1]);
-      if (i + 2 < n)
-        {
-          dict->val.l.vals[i]   = dict->val.l.vals[n - 2];
-          dict->val.l.vals[i + 1] = dict->val.l.vals[n - 1];
-        }
-      dict->val.l.count -= 2;
-    }
-
-  return i >= 0; /* return true if found */
+
+      if (i != last)
+        dict->val.l.vals[i] = dict->val.l.vals[last];
+
+      --dict->val.l.count;
+
+       removed = true;
+    }
+
+  return removed;
 }
 
@@ -765 +729 @@
 struct KeyIndex
 {
-  const char *  key;
-  int           index;
+  const char * keystr;
+  tr_variant * val;
 };
 
@@ -775 +739 @@
   const struct KeyIndex * b = vb;
 
-  return strcmp (a->key, b->key);
+  return strcmp (a->keystr, b->keystr);
 }
 
 struct SaveNode
 {
-  const tr_variant * val;
-  int valIsVisited;
-  int childCount;
-  int childIndex;
-  int * children;
+  const tr_variant * v;
+  tr_variant sorted;
+  size_t childIndex;
+  bool isVisited;
 };
 
 static void
-nodeInitDict (struct SaveNode   * node,
-              const tr_variant  * val,
-              bool                sort_dicts)
-{
-  const int n = val->val.l.count;
-  const int nKeys = n / 2;
-
-  assert (tr_variantIsDict (val));
-
-  node->val = val;
-  node->children = tr_new0 (int, n);
-
-  if (sort_dicts)
-    {
-      int i, j;
-      struct KeyIndex * indices = tr_new (struct KeyIndex, nKeys);
-
-      for (i=j=0; i<n; i+=2, ++j)
+nodeConstruct (struct SaveNode   * node,
+               const tr_variant  * v,
+               bool                sort_dicts)
+{
+  node->isVisited = false;
+  node->childIndex = 0;
+
+  if (sort_dicts && tr_variantIsDict(v))
+    {
+      /* make node->sorted a sorted version of this dictionary */
+
+      size_t i;
+      const size_t n = v->val.l.count;
+      struct KeyIndex * tmp = tr_new (struct KeyIndex, n);
+
+      for (i=0; i<n; i++)
         {
-          indices[j].key = getStr (&val->val.l.vals[i]);
-          indices[j].index = i;
+          tmp[i].val = v->val.l.vals+i;
+          tmp[i].keystr = tr_quark_get_string (tmp[i].val->key, NULL);
         }
 
-      qsort (indices, j, sizeof (struct KeyIndex), compareKeyIndex);
-
-      for (i=0; i<j; ++i)
-        {
-          const int index = indices[i].index;
-          node->children[node->childCount++] = index;
-          node->children[node->childCount++] = index + 1;
-        }
-
-      tr_free (indices);
+      qsort (tmp, n, sizeof (struct KeyIndex), compareKeyIndex);
+
+      tr_variantInitDict (&node->sorted, n);
+      for (i=0; i<n; ++i)
+        node->sorted.val.l.vals[i] = *tmp[i].val;
+      node->sorted.val.l.count = n;
+
+      tr_free (tmp);
+
+      node->v = &node->sorted;
     }
   else
     {
-      int i;
-
-      for (i=0; i<n; ++i)
-        node->children[node->childCount++] = i;
-    }
-
-  assert (node->childCount == n);
+      node->v = v;
+    }
 }
 
 static void
-nodeInitList (struct SaveNode   * node,
-              const tr_variant  * val)
-{
-  int i;
-  int n;
-
-  assert (tr_variantIsList (val));
-
-  n = val->val.l.count;
-  node->val = val;
-  node->childCount = n;
-  node->children = tr_new0 (int, n);
-  for (i=0; i<n; ++i) /* a list's children don't need to be reordered */
-    node->children[i] = i;
-}
-
-static void
-nodeInitLeaf (struct SaveNode   * node,
-              const tr_variant  * variant)
-{
-  assert (!tr_variantIsContainer (variant));
-
-  node->val = variant;
-}
-
-static void
-nodeInit (struct SaveNode   * node,
-          const tr_variant  * variant,
-          bool                sort_dicts)
-{
-  static const struct SaveNode INIT_NODE = { NULL, 0, 0, 0, NULL };
-
-  *node = INIT_NODE;
-
-  if (tr_variantIsList (variant))
-    nodeInitList (node, variant);
-  else if (tr_variantIsDict (variant))
-    nodeInitDict (node, variant, sort_dicts);
-  else
-    nodeInitLeaf (node, variant);
+nodeDestruct (struct SaveNode * node)
+{
+  if (node->v == &node->sorted)
+    tr_free (node->sorted.val.l.vals);
 }
 
@@ -882 +802 @@
  */
 void
-tr_variantWalk (const tr_variant               * top,
+tr_variantWalk (const tr_variant               * v,
                 const struct VariantWalkFuncs  * walkFuncs,
                 void                           * user_data,
@@ -889 +809 @@
   int stackSize = 0;
   int stackAlloc = 64;
+  char lc_numeric[128];
   struct SaveNode * stack = tr_new (struct SaveNode, stackAlloc);
 
-  nodeInit (&stack[stackSize++], top, sort_dicts);
+  /* always use a '.' decimal point s.t. locale-hopping doesn't bite us */
+  tr_strlcpy (lc_numeric, setlocale (LC_NUMERIC, NULL), sizeof (lc_numeric));
+  setlocale (LC_NUMERIC, "POSIX");
+
+  nodeConstruct (&stack[stackSize++], v, sort_dicts);
 
   while (stackSize > 0)
     {
       struct SaveNode * node = &stack[stackSize-1];
-      const tr_variant * val;
-
-      if (!node->valIsVisited)
+      const tr_variant * v;
+
+      if (!node->isVisited)
         {
-            val = node->val;
-            node->valIsVisited = true;
+          v = node->v;
+          node->isVisited = true;
         }
-      else if (node->childIndex < node->childCount)
+      else if (tr_variantIsContainer(node->v) && (node->childIndex < node->v->val.l.count))
         {
-            const int index = node->children[node->childIndex++];
-            val = node->val->val.l.vals +  index;
+          const int index = node->childIndex++;
+          v = node->v->val.l.vals + index;
+
+          if (tr_variantIsDict (node->v))
+            {
+              tr_variant tmp;
+              tr_variantInitQuark (&tmp, v->key);
+              walkFuncs->stringFunc (&tmp, user_data);
+            }
         }
       else /* done with this node */
         {
-            if (tr_variantIsContainer (node->val))
-                walkFuncs->containerEndFunc (node->val, user_data);
-            --stackSize;
-            tr_free (node->children);
-            continue;
+          if (tr_variantIsContainer (node->v))
+            walkFuncs->containerEndFunc (node->v, user_data);
+          --stackSize;
+          nodeDestruct (node);
+          continue;
         }
 
-      if (val) switch (val->type)
+      if (v) switch (v->type)
         {
           case TR_VARIANT_TYPE_INT:
-            walkFuncs->intFunc (val, user_data);
+            walkFuncs->intFunc (v, user_data);
             break;
 
           case TR_VARIANT_TYPE_BOOL:
-            walkFuncs->boolFunc (val, user_data);
+            walkFuncs->boolFunc (v, user_data);
             break;
 
           case TR_VARIANT_TYPE_REAL:
-            walkFuncs->realFunc (val, user_data);
+            walkFuncs->realFunc (v, user_data);
             break;
 
           case TR_VARIANT_TYPE_STR:
-            walkFuncs->stringFunc (val, user_data);
+            walkFuncs->stringFunc (v, user_data);
             break;
 
           case TR_VARIANT_TYPE_LIST:
-            if (val == node->val)
+            if (v == node->v)
               {
-                walkFuncs->listBeginFunc (val, user_data);
+                walkFuncs->listBeginFunc (v, user_data);
               }
             else
@@ -947 +879 @@
                     stack = tr_renew (struct SaveNode, stack, stackAlloc);
                   }
-                nodeInit (&stack[stackSize++], val, sort_dicts);
+                nodeConstruct (&stack[stackSize++], v, sort_dicts);
               }
             break;
 
           case TR_VARIANT_TYPE_DICT:
-            if (val == node->val)
+            if (v == node->v)
               {
-                walkFuncs->dictBeginFunc (val, user_data);
+                walkFuncs->dictBeginFunc (v, user_data);
               }
             else
@@ -963 +895 @@
                     stack = tr_renew (struct SaveNode, stack, stackAlloc);
                   }
-                nodeInit (&stack[stackSize++], val, sort_dicts);
+                nodeConstruct (&stack[stackSize++], v, sort_dicts);
               }
             break;
@@ -973 +905 @@
         }
     }
+
+  /* restore the locale... */
+  setlocale (LC_NUMERIC, lc_numeric);
 
   tr_free (stack);
@@ -1067 +1002 @@
 tr_variantDictSize (const tr_variant * dict)
 {
-  size_t count = 0;
-
-  if (tr_variantIsDict (dict))
-    count = dict->val.l.count / 2;
-
-  return count;
+  return tr_variantIsDict (dict) ? dict->val.l.count : 0;
 }
 
@@ -1085 +1015 @@
   assert (tr_variantIsDict (dict));
 
-  if (tr_variantIsDict (dict) && (n*2)+1 <= dict->val.l.count)
-    {
-      tr_variant * k = dict->val.l.vals + (n*2);
-      tr_variant * v = dict->val.l.vals + (n*2) + 1;
-      if ((k->val.s.type == TR_STRING_TYPE_QUARK) && tr_variantIsSomething (v))
-        {
-          *key = k->val.s.quark;
-          *val = v;
-          success = true;
-        }
+  if (tr_variantIsDict (dict) && (n<dict->val.l.count))
+    {
+      *key = dict->val.l.vals[n].key;
+      *val = dict->val.l.vals+n;
+      success = true;
     }
 
@@ -1176 +1101 @@
 
 struct evbuffer *
-tr_variantToBuf (const tr_variant * top, tr_variant_fmt fmt)
-{
-  struct evbuffer * buf = evbuffer_new ();
+tr_variantToBuf (const tr_variant * v, tr_variant_fmt fmt)
+{
+  struct evbuffer * buf = evbuffer_new();
 
   evbuffer_expand (buf, 4096); /* alloc a little memory to start off with */
@@ -1185 +1110 @@
     {
       case TR_VARIANT_FMT_BENC:
-        tr_variantToBufBenc (top, buf);
+        tr_variantToBufBenc (v, buf);
         break;
 
       case TR_VARIANT_FMT_JSON:
-        tr_variantToBufJson (top, buf, false);
+        tr_variantToBufJson (v, buf, false);
         break;
 
       case TR_VARIANT_FMT_JSON_LEAN:
-        tr_variantToBufJson (top, buf, true);
+        tr_variantToBufJson (v, buf, true);
         break;
     }
@@ -1201 +1126 @@
 
 char*
-tr_variantToStr (const tr_variant * top, tr_variant_fmt fmt, int * len)
-{
-  struct evbuffer * buf = tr_variantToBuf (top, fmt);
+tr_variantToStr (const tr_variant * v, tr_variant_fmt fmt, int * len)
+{
+  struct evbuffer * buf = tr_variantToBuf (v, fmt);
   const size_t n = evbuffer_get_length (buf);
   char * ret = evbuffer_free_to_str (buf);
@@ -1211 +1136 @@
 }
 
-/* portability wrapper for mkstemp (). */
+/* portability wrapper for mkstemp(). */
 static int
 tr_mkstemp (char * template)
@@ -1226 +1151 @@
 
 int
-tr_variantToFile (const tr_variant  * top,
+tr_variantToFile (const tr_variant  * v,
                   tr_variant_fmt      fmt,
                   const char        * filename)
@@ -1236 +1161 @@
 
   /* follow symlinks to find the "real" file, to make sure the temporary
-   * we build with tr_mkstemp () is created on the right partition */
+   * we build with tr_mkstemp() is created on the right partition */
   if (tr_realpath (filename, buf) != NULL)
     filename = buf;
@@ -1250 +1175 @@
       /* save the variant to a temporary file */
       {
-        struct evbuffer * buf = tr_variantToBuf (top, fmt);
+        struct evbuffer * buf = tr_variantToBuf (v, fmt);
         const char * walk = (const char *) evbuffer_pullup (buf, -1);
         nleft = evbuffer_get_length (buf);

trunk/libtransmission/variant.h

@@ -75 +75 @@
   char type;
 
+  tr_quark key;
+
   union
     {
@@ -87 +89 @@
       struct
         {
-          struct tr_variant * vals; /* nodes */
-          size_t alloc; /* nodes allocated */
-          size_t count; /* nodes used */
+          size_t alloc;
+          size_t count;
+          struct tr_variant * vals;
         } l;
     }
@@ -276 +278 @@
 }
 
-int          tr_variantInitList        (tr_variant       * list,
-                                        size_t             reserve_count);
-
-int          tr_variantListReserve     (tr_variant       * list,
+void         tr_variantInitList        (tr_variant       * list,
+                                        size_t             reserve_count);
+
+void         tr_variantListReserve     (tr_variant       * list,
                                         size_t             reserve_count);
 
@@ -312 +314 @@
                                         size_t             pos);
 
-int          tr_variantListRemove      (tr_variant       * list,
+bool         tr_variantListRemove      (tr_variant       * list,
                                         size_t             pos);
 
@@ -328 +330 @@
 }
 
-int          tr_variantInitDict        (tr_variant       * initme,
-                                        size_t             reserve_count);
-
-int          tr_variantDictReserve     (tr_variant       * dict,
-                                        size_t             reserve_count);
-
-int          tr_variantDictRemove      (tr_variant       * dict,
+void         tr_variantInitDict        (tr_variant       * initme,
+                                        size_t             reserve_count);
+
+void         tr_variantDictReserve     (tr_variant       * dict,
+                                        size_t             reserve_count);
+
+bool         tr_variantDictRemove      (tr_variant       * dict,
                                         const tr_quark     key);
 

trunk/qt/my-valgrind.sh

@@ -1 +1 @@
 #/bin/sh
-valgrind --tool=cachegrind ./transmission-qt
+valgrind --tool=cachegrind ./transmission-qt 2>&1 | tee runlog
+#valgrind --tool=memcheck --leak-check=full --leak-resolution=high --num-callers=48 --log-file=x-valgrind --show-reachable=no ./transmission-qt 2>&1 | tee runlog