天天看點
傳回

libmxml資料結構（源碼分析）

　　libmxml是一個開源、小巧的C語言xml庫。這裡簡單分析一下它是用什麼樣的資料結構來儲存分析過的xml文檔。

　　mxml關鍵的結構體mxml_node_t是這樣的實作的：

struct mxml_node_s            /**** An XML node. @private@ ****/
{
  mxml_type_t        type;        /* Node type */
  struct mxml_node_s    *next;        /* Next node under same parent */
  struct mxml_node_s    *prev;        /* Previous node under same parent */
  struct mxml_node_s    *parent;    /* Parent node */
  struct mxml_node_s    *child;        /* First child node */
  struct mxml_node_s    *last_child;    /* Last child node */
  mxml_value_t        value;        /* Node value */
  int            ref_count;    /* Use count */
  void            *user_data;    /* User data */
};

typedef struct mxml_node_s mxml_node_t;    /**** An XML node. ****/

　　

 　　它使用左孩子右兄弟的樹形結構來描述xml封包：即下層節點登記在child連結清單，兄弟節點登記在next連結清單。 如果某個節點下面有N個子節點，則child指向第一個子節點，該子節點的next指向下一個同父節點的子節點。  比較特殊的是，mxml把xml節點值也認為是一個子節點。例如<group>value</group>， 其中value(type是MXML_OPAQUE)是一個獨立的子節點，挂載在group節點(type是MXML_ELEMENT)下面。  另外，空白符（空格，回車換行，制表符）和注釋，雖然對xml封包無實質意義，但mxml還是把它們做為一個節點存儲起來。

　　由于mxml隻是使用簡單的連結清單存儲xml元素，是以元素節點個數比較多時，mxml查找元素效率是比較低的。是以libmxml提供了一個索引查找的函數，它需要先周遊xml元素樹，生成一個排序過的數組，加快查找速度。

 　　為了友善大家了解，我寫了一個函數列印xml結構體。

void printNode(mxml_node_t *node, int nNodeSn, int level)
{
    static int currNodeSn = 0;
    if (node == NULL)
    {
        return;
    }

    ++currNodeSn; //每遇到一個新節點 則将節點序号遞增，做為本節點序号
    printf("[%- 3d -> %- 3d] ", currNodeSn, nNodeSn);

    switch (node->type)
    {
    case MXML_ELEMENT:
        {
            int i;
            printf("level %d MXML_ELEMENT [%s]", level, node->value.element.name);
            for (i = 0; i < node->value.element.num_attrs; ++i)
            {
                printf(" %s=%s", node->value.element.attrs[i].name, node->value.element.attrs[i].value);
            }
            printf("\n");
        }
        break;
    case MXML_INTEGER:
        printf("level %d MXML_INTEGER %d\n", level, node->value.integer);
        break;
    case MXML_OPAQUE:
        printf("level %d MXML_OPAQUE [%s]\n", level, node->value.opaque);
        break;
    case MXML_REAL:
        printf("level %d MXML_REAL %lf\n", level, node->value.real);
        break;
    case MXML_TEXT:
        printf("level %d MXML_TEXT [%s]\n", level, node->value.text.string);
        break;
    case MXML_CUSTOM:
        printf("level %d MXML_CUSTOM\n", level);
        break;
    default:
        printf("unknown node type %d\n", node->type);
    }

    //深度優先周遊
    if (node->child)
    {
        //通路子節點時把本節點序号做為父節點序号 層級加1
        printNode(node->child, currNodeSn, level + 1);
    }

    if (node->next)
    {
        //通路兄弟節點，直接傳父節點序号即可 層級也不用加1
        printNode(node->next, nNodeSn, level);
    }
}

　　運作示例如下：

　　xml源如下：

<?xml version="1.0" encoding="GBK" ?>
<group>
    <option>122334 我們
        <string>我們</string>45677
        <keyword type="opaque">InputSlot</keyword>
        <default type="opaque">Auto</default>
        <text>Media Source</text>
        <order type="real">10.000000</order>
        <choice>
            <keyword type="opaque">Auto</keyword>
            <text>Auto Tray Selection</text>
            <code type="opaque" />
        </choice>
        <choice>
            <keyword type="opaque">Upper</keyword>
            <text>Tray 1</text>
            <code type="opaque">&lt;&lt;/MediaPosition 0&gt;&gt;setpagedevice</code>
        </choice>
        <choice>
            <keyword type="opaque">Lower</keyword>
            <text>Tray 2</text>
            <code type="opaque">&lt;&lt;/MediaPosition 1&gt;&gt;setpagedevice</code>
        </choice>
    </option> 我 12334545 050504550
    <integer>123</integer>
    <string>Now is the time for all good men to come to the aid of their
country.</string>
    <!-- this is a comment -->
    <![CDATA[this is CDATA 0123456789ABCDEF]]>
</group>

　　用我這個printNode分析結果如下：

說明：[ 1  ->  0 ]，代表本節點序号是1，其父節點序号是0，level 0代表本節點是最頂層節點。

[ 1  ->  0 ] level 0 MXML_ELEMENT [?xml version="1.0" encoding="GBK" ?]
[ 2  ->  1 ] level 1 MXML_OPAQUE [
]
[ 3  ->  1 ] level 1 MXML_ELEMENT [group]
[ 4  ->  3 ] level 2 MXML_OPAQUE [
        ]
[ 5  ->  3 ] level 2 MXML_ELEMENT [option]
[ 6  ->  5 ] level 3 MXML_OPAQUE [122334 我們
                ]
[ 7  ->  5 ] level 3 MXML_ELEMENT [string]
[ 8  ->  7 ] level 4 MXML_OPAQUE [我們]
[ 9  ->  5 ] level 3 MXML_OPAQUE [45677
                ]
[ 10 ->  5 ] level 3 MXML_ELEMENT [keyword] type=opaque
[ 11 ->  10] level 4 MXML_OPAQUE [InputSlot]
[ 12 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 13 ->  5 ] level 3 MXML_ELEMENT [default] type=opaque
[ 14 ->  13] level 4 MXML_OPAQUE [Auto]
[ 15 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 16 ->  5 ] level 3 MXML_ELEMENT [text]
[ 17 ->  16] level 4 MXML_OPAQUE [Media Source]
[ 18 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 19 ->  5 ] level 3 MXML_ELEMENT [order] type=real
[ 20 ->  19] level 4 MXML_OPAQUE [10.000000]
[ 21 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 22 ->  5 ] level 3 MXML_ELEMENT [choice]
[ 23 ->  22] level 4 MXML_OPAQUE [
                        ]
[ 24 ->  22] level 4 MXML_ELEMENT [keyword] type=opaque
[ 25 ->  24] level 5 MXML_OPAQUE [Auto]
[ 26 ->  22] level 4 MXML_OPAQUE [
                        ]
[ 27 ->  22] level 4 MXML_ELEMENT [text]
[ 28 ->  27] level 5 MXML_OPAQUE [Auto Tray Selection]
[ 29 ->  22] level 4 MXML_OPAQUE [
                        ]
[ 30 ->  22] level 4 MXML_ELEMENT [code] type=opaque
[ 31 ->  22] level 4 MXML_OPAQUE [
                ]
[ 32 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 33 ->  5 ] level 3 MXML_ELEMENT [choice]
[ 34 ->  33] level 4 MXML_OPAQUE [
                        ]
[ 35 ->  33] level 4 MXML_ELEMENT [keyword] type=opaque
[ 36 ->  35] level 5 MXML_OPAQUE [Upper]
[ 37 ->  33] level 4 MXML_OPAQUE [
                        ]
[ 38 ->  33] level 4 MXML_ELEMENT [text]
[ 39 ->  38] level 5 MXML_OPAQUE [Tray 1]
[ 40 ->  33] level 4 MXML_OPAQUE [
                        ]
[ 41 ->  33] level 4 MXML_ELEMENT [code] type=opaque
[ 42 ->  41] level 5 MXML_OPAQUE [<</MediaPosition 0>>setpagedevice]
[ 43 ->  33] level 4 MXML_OPAQUE [
                ]
[ 44 ->  5 ] level 3 MXML_OPAQUE [
                ]
[ 45 ->  5 ] level 3 MXML_ELEMENT [choice]
[ 46 ->  45] level 4 MXML_OPAQUE [
                        ]
[ 47 ->  45] level 4 MXML_ELEMENT [keyword] type=opaque
[ 48 ->  47] level 5 MXML_OPAQUE [Lower]
[ 49 ->  45] level 4 MXML_OPAQUE [
                        ]
[ 50 ->  45] level 4 MXML_ELEMENT [text]
[ 51 ->  50] level 5 MXML_OPAQUE [Tray 2]
[ 52 ->  45] level 4 MXML_OPAQUE [
                        ]
[ 53 ->  45] level 4 MXML_ELEMENT [code] type=opaque
[ 54 ->  53] level 5 MXML_OPAQUE [<</MediaPosition 1>>setpagedevice]
[ 55 ->  45] level 4 MXML_OPAQUE [
                ]
[ 56 ->  5 ] level 3 MXML_OPAQUE [
        ]
[ 57 ->  3 ] level 2 MXML_OPAQUE [ 我12334545 050504550
        ]
[ 58 ->  3 ] level 2 MXML_ELEMENT [integer]
[ 59 ->  58] level 3 MXML_OPAQUE [123]
[ 60 ->  3 ] level 2 MXML_OPAQUE [
        ]
[ 61 ->  3 ] level 2 MXML_ELEMENT [string]
[ 62 ->  61] level 3 MXML_OPAQUE [Now is the time for all good men to come to the aid of their
country.]
[ 63 ->  3 ] level 2 MXML_OPAQUE [
        ]
[ 64 ->  3 ] level 2 MXML_ELEMENT [!-- this is a comment --]
[ 65 ->  3 ] level 2 MXML_OPAQUE [
        ]
[ 66 ->  3 ] level 2 MXML_ELEMENT [![CDATA[this is CDATA 0123456789ABCDEF]]]
[ 67 ->  3 ] level 2 MXML_OPAQUE [
]      
xml封包與結構體轉換優化

    項目中每個交易都有一個必須的步驟：把請求封包的内容轉換到流水結構體。目前的做法是對于流水結構裡面的字段，逐個到xml封包（調用XmlGetTextByPath），根據路徑在xml封包裡面找出對應的值。
    根據callgrind分析，此類操作在占用了交易的30%以上cpu時間，值得優化。為此我提出另一個做法：
開發新的函數，XmlGetTextByPathMutiple。改變目前每取一個字段就周遊一次xml的操作，一次性将所有需要取出的字段對應的xml路徑傳給新函數。在周遊過程中檢查所需路徑是否存在，如果存在則取出。
    如果周遊完成後還沒有遇到的路徑，則視為不存在。
    由于目前我們的請求xml封包都相對比較小，周遊xml開銷不大。并且現在每個交易需要從請求xml擷取的字段至少十幾個以上，新函數理論上可以比原函數更節約時間與資源。
    為加快周遊過程中檢查xml路徑是否存在的過程，需要在函數開始前先對所有字段的xml路徑做哈希計算。然後把哈希結果放到C99變長數組，再進行排序。
    數組元素結構說明如下：
    typedef struct tagMemInfo
    {
        const char *xmlPath; //字段對應的xml路徑
        void *destBuf; //結果存放區
        size_t destBufLen; //存放區長度
        int destType; //結果類型，目前隻支援char數組和double
        int isNullAble; //是否可為空
    }MemInfo;

    typedef struct tagXmlGetInfo
    {
        int pathHashCode; //xml路徑對應的哈希值
        const char *xmlPath; //字段對應的xml路徑
        int isNullFlag; //是否為空，初始化都是1
        MemInfo *memInfo;
    }XmlGetInfo;
    周遊過程中，對于每個xml節點，我們先計算其路徑的哈希值。根據哈希值二分查找數組，看是否有與該值相同的目标字段。
    如果找到哈希值相同，并且路徑也相同的，則把xml節點值取出來放到指定的緩沖區。

    計算哈希的函數推薦使用glib的g_str_hash，其使用的是DJB算法。這樣我們在周遊子路徑可以在父節點的哈希值基礎上做增量計算，減少哈希值計算的開銷。

    //僞代碼如下：
    //parentHashCode：外部調用統一傳5381，遞歸調用傳本節點哈希值
    void XmlGetTextByPathMutipleInternal(const XmlGetInfo *xmlGetArr,  size_t arrLen,
    mxml_t *currNode, int parentHashCode);
    {
        int nHashCode = parentHashCode;
        根據parentHashCode及本節點名稱計算nHashCode
        使用nHashCode在xmlGetArr裡面二分查找
        如果找到符合要求的路徑，則将本節點值取出來（即第一個孩子節點）

        for (第一個孩子節點; 兄弟節點 != NULL; 取出兄弟節點)
        {
            如果發現該節點是xml路徑節點 //可能是文本節點
            則調用函數XmlGetTextByPathMutipleInternal
        }
    }
    

    int XmlGetTextByPathMutipleRel(const XmlGetInfo *xmlGetArr,  size_t arrLen,
    mxml_t *rootNode)
    {
        int nHashCode = 5381;
        for (第一個孩子節點; 兄弟節點 != NULL; 取出兄弟節點)
        {
            如果發現該節點是xml路徑節點 //可能是文本節點
            則調用函數XmlGetTextByPathMutipleInternal
        }
        
        檢查xmlGetArr所有不允許為空的成員是否找到對應的路徑
    }

    對于組裝封包，我們也可以做類似優化：先将需要修改的xml封包路徑及其對應的值緩存起來，
等到把xml封包值設定好後再統一周遊一次xml封包，根據緩存資訊，進行實際的xml封包修改。
    修改邏輯如下：對緩存以xml路徑進行排序，排序後順序處理。由于路徑相似的xml路徑排序後肯定在一起，
可以減少修改過程中對于xml封包的查找。（可以根據待修改值的數量決定是否對目前xml節點建構索引，為保持與之前代碼相容性，建索引時可以考慮使用歸并排序，或者使用冒泡法即可）

    相關函數設計：
    XmlSetTextByPathCopy //xml封包值是存在臨時變量，需要把值複制出來，暫存。
    XmlSetTextByPathNoCopy //xml封包值是存在非臨時變量
    XmlSetTextByPathDual //真正對xml封包進行修改

　　 

~~積土成山，風雨興焉；積水成淵，蛟龍生焉；~~~

上一篇: 分布式設計與開發（二）------幾種必須了解的分布式算法
下一篇: windows和cygwin下hadoop安裝配置