2017-03-05 75 views
1

我想克隆/复制一个html Node,以便我可以修改/复制它,然后将其注入到主文档中。问题是我得到堆栈溢出[2]。我假设有一个竞赛条件。它看起来像是由于ParentPrevSibling字段(基于我的盲目测试)。任何想法为什么是这样的,我怎样才能完全克隆它(以便它可以测试正面反映.DeepEqual)?克隆节点[golang.org/x/net/html]:堆栈溢出

func clone(src *html.Node) *html.Node { 
    if src == nil { 
     return nil 
    } 
    n := html.Node{ 
     Parent:  clone(src.Parent), 
     FirstChild: clone(src.FirstChild), 
     LastChild: clone(src.LastChild), 
     PrevSibling: clone(src.PrevSibling), 
     NextSibling: clone(src.NextSibling), 

     Type:  src.Type, 
     DataAtom: src.DataAtom, 
     Data:  src.Data, 
     Namespace: src.Namespace, 
    } 
    for _, v := range n.Attr { 
     n.Attr = append(n.Attr, v) 
    } 
    return &n 
} 

[2]

runtime: goroutine stack exceeds 1000000000-byte limit 
fatal error: stack overflow 

runtime stack: 
runtime.throw(0x3495b9, 0xe) 
    /Users/x/gosrc/src/runtime/panic.go:566 +0x95 
runtime.newstack() 
    /Users/x/gosrc/src/runtime/stack.go:1061 +0x416 
runtime.morestack() 
    /Users/x/gosrc/src/runtime/asm_amd64.s:366 +0x7f 

goroutine 7 [running]: 
runtime.heapBitsSetType(0xc42a0ae5b0, 0x70, 0x68, 0x32e420) 
    /Users/x/gosrc/src/runtime/mbitmap.go:867 fp=0xc4402002a8 sp=0xc4402002a0 
runtime.mallocgc(0x70, 0x32e420, 0x1, 0x0) 
    /Users/x/gosrc/src/runtime/malloc.go:690 +0x5ba fp=0xc440200348 sp=0xc4402002a8 
runtime.newobject(0x32e420, 0x0) 
    /Users/x/gosrc/src/runtime/malloc.go:785 +0x38 fp=0xc440200378 sp=0xc440200348 
bitbucket.org/x/y/client.clone(0xc420138d20, 0x0) 

回答

0

当深克隆包含指针不是你需要一个更复杂的方法树的数据结构;如果调用

n := Node{... 
      next:clone(src.next), 
      prev:clone(src.prev), 
      ...} 

,你的结构有哪怕只是姐弟两个节点n1n2其中n1.next&n2n2.prev&n1代码将堆栈溢出(克隆n1将调用clone(n2)next指针将依次调用clone(n1)prev指针,永远循环来回直到调用堆栈爆炸)。

解决方案是在克隆节点时保留一个“缓存”,您将存储关联src→cloned,因此克隆过程将能够在递归结构的情况下返回节点。

下面是一个完整的小例子:

package main 

import "fmt" 

type Node struct { 
    value  int 
    prev, next *Node 
} 

func clone(n *Node, cache map[*Node]*Node) *Node { 
    if n == nil { 
     return nil 
    } 

    if val, ok := cache[n]; ok { 
     return val 
    } 

    val := &Node{} 
    cache[n] = val 
    val.value = n.value 
    val.prev = clone(n.prev, cache) 
    val.next = clone(n.next, cache) 

    return val 
} 

func printlist(n *Node) { 
    for n != nil { 
     println(fmt.Sprintf("address=%p, value=%v, prev=%p, next=%p", 
      n, n.value, n.prev, n.next)) 
     n = n.next 
    } 
} 

func main() { 
    n1 := &Node{} 
    n2 := &Node{} 
    n3 := &Node{} 
    n1.value = 100 
    n2.value = 200 
    n3.value = 300 
    n1.next = n2 
    n2.prev = n1 
    n2.next = n3 
    n3.prev = n2 

    printlist(n1) 

    println("Cloning list") 
    c1 := clone(n1, make(map[*Node]*Node)) 
    printlist(c1) 
} 

我的机器上运行这个程序,我得到

~/x$ go run recstruct.go 
address=0xc42000e540, value=100, prev=0x0, next=0xc42000e560 
address=0xc42000e560, value=200, prev=0xc42000e540, next=0xc42000e580 
address=0xc42000e580, value=300, prev=0xc42000e560, next=0x0 
Cloning list 
address=0xc42000e5c0, value=100, prev=0x0, next=0xc42000e5e0 
address=0xc42000e5e0, value=200, prev=0xc42000e5c0, next=0xc42000e600 
address=0xc42000e600, value=300, prev=0xc42000e5e0, next=0x0 
~/x$ 

在这里你可以看到三个节点已经被正确地克隆和上一页/下一页在克隆的结构列表中互相指向。

+0

有意义。我假设* map [* Node] *节点是错误的,对吗? (地图[*节点] *节点将工作得很好) – mike

+0

@mike:谢谢,修正。 – 6502