优化 cJSON 库的 array 插入速度

和参考资料一样,我在我的项目中应用 cJSON 数组功能,发现在创建 array 的时候耗时很厉害(作为嵌入式 CPU,几十个 array 项的插入,居然花了 300ms)。搜了一下,网上已经有人遇到过了,就是参考资料的那篇。本文解释一下优化的思路和方法。

Reference

cJSON 库的使用和优化

优化 cJSON 库的 array 插入速度

修改方法

下面左边是原版的 cJSON 代码,右边是修改后的,可以自己看看:

void cJSON_AddItemToArray (cJSON *array, cJSON *item) |  void cJSON_AddItemToArray (cJSON *array, cJSON *item)
{                                                     |  {
    cJSON *c = array->child;                          |      cJSON *c = array->child;
    if (!item)                                        |      if (!item) 
        return;                                       |          return;
                                                      | 
    if (!c) {                                         |      if (!c) {
        array->child=item;                            |          array->child=item;
                                                      |          array->child->prev = item;
    }                                                 |      }
    else {                                            |      else {
        while (c && c->next)                          |          item->prev = array->child->prev;
            c=c->next;                                |          array->child->prev->next = item;    /* MARK */
        suffix_object(c,item);                        |          array->child->prev = item; 
                                                      |          item->next = NULL;
    }                                                 |      }
                                                      |
}                                                     |  }

如果只单纯改上面这个函数的话(参考资料就只改了这点),实际上是会有 bug 的,那就是如果对一个使用 cJSON_Parse() 得到的对象进行 addObject 操作的话,程序会崩溃,原因是上述标记的 “MARK” 的语句的prev成员为空,因而出现内存越界。
  我现在做的实际上的函数是这样的:

void cJSON_AddItemToArray(cJSON *array, cJSON *item)
{
    cJSON *c = array->child;
    if (!item) {
        return;
    }
    if (!c) {
        /* list is empty, start new one */
        array->child = item;
        array->child->prev = item;
    }
    else {
        /* append to the end */
        if (array->child->prev) {
            item->prev = array->child->prev;
            array->child->prev->next = item;
            array->child->prev = item;
            item->next = NULL;
        }
        else {
            while (c->next)
                c = c->next;
            suffix_object(c, item);
            array->child->prev = item;
        }
    }
}

优化 cJSON 库的 array 插入速度

修改思路

原文提到两种修改方法,其实本质上是一模一样的。
  我们先看原来 cJSON 的代码思路:每次添加数组成员时,都会遍历链表以找到最后一个数组成员,然后在这个成员的next上加上新数组成员。
  那么修改思路自然是:每次插入新成员时,都把这个 “最后一个数组成员” 缓存下来就好了嘛。
  这里我们注意到一个很重要的点:对于 cJSON 数组成员的第一项,它的 “prev” 成员永远是 NULL,也就是压根没用上!所以,原文的修改思路就是:复用没用到的第一个成员的 prev 变量,用来保存 last 值。实际上,原文这么做,也同时把 cJSON array 的单向链表变成了一个循环链表~~

THE END——实在是一个很不错的修改。我的操作时间从几百毫秒变成了30毫秒了。
WARNING:这个修改没有经过经过完整用例的测试,也没有与作者本人 Dave Gamble 确认过,所以请各位谨慎食用。

相关推荐