密鑰生成

Question

我使用AVL樹爲IP地址的快速搜索一個大系統：

struct avl_node 
{ 
    struct avl_node *left; 
    struct avl_node *right; 
    ... 
    void *info; /* point to nhlfe_entry describing nexthop */ 
} 

struct nhlfe_entry 
{ 
    u_int32_t nhlfe_ix; 
    u_char opcode; 
    ... 
    struct nhlfe_key key; 
} 

/* defines a search key. */ 
struct nhlfe_key 
{ 
    struct in_addr nh_addr; 
    u_int32_t oif_ix; 
    u_int32_t out_label; 
} 

所以搜索是基於「結構nhlfe_key」，即比較功能 AVL樹的樣子這樣的：

static int 
mpls_cmp_nhlfe_ipv4_key (void *data1, void* data2) 
{ 
    struct nhlfe_entry *nh1, *nh2; 
    struct nhlfe_key *key1, *key2; 
    int ret; 

    nh1 = (struct nhlfe_entry *) data1; 
    nh2 = (struct nhlfe_entry *) data2; 

    key1 = (struct nhlfe_key *) nh1->nkey; 
    key2 = (struct nhlfe_key *) nh2->nkey; 

    ret = memcmp (&key1->nh_addr, &key2->nh_addr, sizeof (struct in_addr)); 
    if (ret != 0) 
    return ret; 

    if (key1->oif_ix > key2->oif_ix) 
    return 1; 
    else if (key1->oif_ix < key2->oif_ix) 
    return -1; 

    if (key1->out_label > key2->out_label) 
    return 1; 
    else if (key1->out_label < key2->out_label) 
    return -1; 

    return 0; 
} 

現在，我想要做的是增加對多個下一跳的支持，這是 我nhlfe_entry添加一個鏈接列表：

struct nhlfe_entry 
{ 
    u_int32_t nhlfe_ix; 
    u_char opcode; 
    ... 
    struct list *nhkey_list; 
} 

每個'struct list'是struct listnode，它將'void * data'指針嵌入到 調用者的私有數據中，這是'struct nhlfe_key'。

所以我的問題是 - 如何根據從 列表中的多個元素用於存儲/檢索樹中的節點生成密鑰（否則現在 引進名單後，就不可能有鑰匙僅基於一個 下一跳地址）。此外，他們同樣的問題 適用於搜索。

此外，在列表中添加新節點後，是否需要重新構建樹 ，因爲我認爲此操作將更改密鑰，因此樹可能會變得不平衡？ （或自然正確實施的AVL樹 不需要重建？）

我正在考慮在每個listnode上生成CRC，然後總結。這可以保證鑰匙的唯一性嗎？ （缺點是，無論何時添加/刪除listnode，我都必須重新生成密鑰，從tre刪除節點並用新密鑰重新添加）。

謝謝！

Answer 1

我使用AVL樹爲IP地址的快速搜索一個大系統：

對於大量的IP地址通常要基數樹。二叉樹可以工作，但是你沒有任何能力使用它們的前綴存儲地址範圍，例如， 10.*。如果你沒有使用這種類似於路由的任何東西，或者你不需要節省將整個子網映射到某個東西的空間。

所以我的問題是 - 如何根據從列表中選擇多個元素用於存儲生成密鑰樹（搜索節點，因爲否則現在引進名單後，就不可能有一個基於密鑰/只有一個下一跳地址）。此外，他們同樣的問題適用於搜索。

您的mpls_cmp_nhlfe_ipv4_key函數只需要比較可能是地址列表的鍵。顯然(1 2 3)相當於(1 2 3)。此外，(1 2 3)比較大於(1 2)，但小於(1 3)或(1 2 4)。

此外，在列表中添加一個新的節點後，我是否需要重新編譯樹...

如果要更新平衡搜索樹中的節點以便更改密鑰，最好的辦法可能是刪除它並重新插入它。

可能有方法來優化它。例如，假設一個關鍵字發生了變化，但是這樣一來，它仍然在樹中具有完全相同的後繼者和前驅者。在這種情況下，它可以完成。或者一個密鑰可以改變，只需要一個節點與前任或繼任者交換。在嘗試這樣的技巧之前，我會做好。

[CRC]可以保證密鑰的唯一性嗎？

不，CRC是一種哈希函數。它的位數比被哈希的對象少，因此多個對象可以哈希到相同的CRC。 （當一組元素找到「完美哈希函數」時，例外情況是這樣，但動態數據很少出現這種情況：對於某些靜態數據集合，完美哈希函數是有效的）。使用哈希方法，您可能會以及使用哈希表。 CRC的排序關係可能沒有意義。當集合必須通過關鍵字的排序關係進行排序時，使用二元搜索樹。