node64s.go

package iptree8

// !!!DON'T EDIT!!! Generated by infobloxopen/go-trees/etc from <name>tree{{.bits}} with etc -s uint8 -d uintX.yaml -t ./<name>tree\{\{.bits\}\}

import (
	"fmt"
	"math/bits"
)

// node64s is an element of radix tree with 64-bit unsigned integer as a key.
type node64s struct {
	// key stores key for current node.
	key uint64
	// bits is a number of significant bits in key.
	bits uint8
	// leaf indicates if the node is leaf node and contains any data in value.
	leaf bool
	// value contains data associated with key.
	value *node64

	chld [2]*node64s
}

// Dot dumps tree to Graphviz .dot format
func (n *node64s) Dot() string {
	body := ""

	i := 0
	queue := []*node64s{n}
	for len(queue) > 0 {
		c := queue[0]
		body += fmt.Sprintf("N%d %s\n", i, c.dotString())

		if c != nil && (c.chld[0] != nil || c.chld[1] != nil) {
			body += fmt.Sprintf("N%d -> { N%d N%d }\n", i, i+len(queue), i+len(queue)+1)
			queue = append(append(queue, c.chld[0]), c.chld[1])
		}

		queue = queue[1:]
		i++
	}

	return "digraph d {\n" + body + "}\n"
}

// Insert puts new leaf to radix tree and returns pointer to new root. The method uses copy on write strategy so old root doesn't see the change.
func (n *node64s) Insert(key uint64, bits int, value *node64) *node64s {
	if bits < 0 {
		bits = 0
	} else if bits > key64BitSize {
		bits = key64BitSize
	}

	return n.insert(newNode64s(key, uint8(bits), true, value))
}

// InplaceInsert puts new leaf to radix tree (or replaces value in existing one). The method inserts data directly to current tree so make sure you have exclusive access to it.
func (n *node64s) InplaceInsert(key uint64, bits int, value *node64) *node64s {
	// Adjust bits.
	if bits < 0 {
		bits = 0
	} else if bits > key64BitSize {
		bits = key64BitSize
	}

	return n.inplaceInsert(key, uint8(bits), value)
}

// Enumerate returns channel which is populated by nodes in order of their keys.
func (n *node64s) Enumerate() chan *node64s {
	ch := make(chan *node64s)

	go func() {
		defer close(ch)

		if n == nil {
			return
		}

		n.enumerate(ch)
	}()

	return ch
}

// Match locates node which key is equal to or "contains" the key passed as argument.
func (n *node64s) Match(key uint64, bits int) (*node64, bool) {
	if n == nil {
		return nil, false
	}

	if bits < 0 {
		bits = 0
	} else if bits > key64BitSize {
		bits = key64BitSize
	}

	r := n.match(key, uint8(bits))
	if r == nil {
		return nil, false
	}

	return r.value, true
}

// ExactMatch locates node which exactly matches given key.
func (n *node64s) ExactMatch(key uint64, bits int) (*node64, bool) {
	if n == nil {
		return nil, false
	}

	if bits < 0 {
		bits = 0
	} else if bits > key64BitSize {
		bits = key64BitSize
	}

	r := n.exactMatch(key, uint8(bits))
	if r == nil {
		return nil, false
	}

	return r.value, true
}

// Delete removes subtree which is contained by given key. The method uses copy on write strategy.
func (n *node64s) Delete(key uint64, bits int) (*node64s, bool) {
	if n == nil {
		return n, false
	}

	if bits < 0 {
		bits = 0
	} else if bits > key64BitSize {
		bits = key64BitSize
	}

	return n.del(key, uint8(bits))
}

func (n *node64s) dotString() string {
	if n == nil {
		return "[label=\"nil\"]"
	}

	if n.leaf {
		return fmt.Sprintf("[label=\"k: %016x, b: %d, v: \\\"%p\\\"\"]", n.key, n.bits, n.value)
	}

	return fmt.Sprintf("[label=\"k: %016x, b: %d\"]", n.key, n.bits)
}

func (n *node64s) insert(c *node64s) *node64s {
	if n == nil {
		return c
	}

	bits := uint8(bits.LeadingZeros64((n.key ^ c.key) | ^masks64[n.bits] | ^masks64[c.bits]))
	if bits < n.bits {
		branch := (n.key >> (key64BitSize - 1 - bits)) & 1
		if bits == c.bits {
			c.chld[branch] = n
			return c
		}

		m := newNode64s(c.key&masks64[bits], bits, false, nil)
		m.chld[branch] = n
		m.chld[1-branch] = c

		return m
	}

	if c.bits == n.bits {
		c.chld = n.chld
		return c
	}

	m := newNode64s(n.key, n.bits, n.leaf, n.value)
	m.chld = n.chld

	branch := (c.key >> (key64BitSize - 1 - bits)) & 1
	m.chld[branch] = m.chld[branch].insert(c)

	return m
}

func (n *node64s) inplaceInsert(key uint64, sbits uint8, value *node64) *node64s {
	var (
		p      *node64s
		branch uint64
	)

	r := n

	for n != nil {
		cbits := uint8(bits.LeadingZeros64((n.key ^ key) | ^masks64[n.bits] | ^masks64[sbits]))
		if cbits < n.bits {
			pBranch := branch
			branch = (n.key >> (key64BitSize - 1 - cbits)) & 1

			var m *node64s

			if cbits == sbits {
				m = newNode64s(key, sbits, true, value)
				m.chld[branch] = n
			} else {
				m = newNode64s(key&masks64[cbits], cbits, false, nil)
				m.chld[1-branch] = newNode64s(key, sbits, true, value)
			}

			m.chld[branch] = n
			if p == nil {
				r = m
			} else {
				p.chld[pBranch] = m
			}

			return r
		}

		if sbits == n.bits {
			n.key = key
			n.leaf = true
			n.value = value
			return r
		}

		p = n
		branch = (key >> (key64BitSize - 1 - cbits)) & 1
		n = n.chld[branch]
	}

	n = newNode64s(key, sbits, true, value)
	if p == nil {
		return n
	}

	p.chld[branch] = n
	return r
}

func (n *node64s) enumerate(ch chan *node64s) {
	if n.leaf {
		ch <- n
	}

	if n.chld[0] != nil {
		n.chld[0].enumerate(ch)
	}

	if n.chld[1] != nil {
		n.chld[1].enumerate(ch)
	}
}

func (n *node64s) match(key uint64, bits uint8) *node64s {
	if n.bits > bits {
		return nil
	}

	if n.bits == bits {
		if n.leaf && (n.key^key)&masks64[n.bits] == 0 {
			return n
		}

		return nil
	}

	if (n.key^key)&masks64[n.bits] != 0 {
		return nil
	}

	c := n.chld[(key>>(key64BitSize-1-n.bits))&1]
	if c != nil {
		r := c.match(key, bits)
		if r != nil {
			return r
		}
	}

	if n.leaf {
		return n
	}

	return nil
}

func (n *node64s) exactMatch(key uint64, bits uint8) *node64s {
	if n.bits > bits {
		return nil
	}

	if n.bits == bits {
		if n.leaf && (n.key^key)&masks64[n.bits] == 0 {
			return n
		}

		return nil
	}

	if (n.key^key)&masks64[n.bits] != 0 {
		return nil
	}

	c := n.chld[(key>>(key64BitSize-1-n.bits))&1]
	if c != nil {
		r := c.exactMatch(key, bits)
		if r != nil {
			return r
		}
	}

	return nil
}

func (n *node64s) del(key uint64, bits uint8) (*node64s, bool) {
	if bits <= n.bits {
		if (n.key^key)&masks64[bits] == 0 {
			return nil, true
		}

		return n, false
	}

	if (n.key^key)&masks64[n.bits] != 0 {
		return n, false
	}

	branch := (key >> (key64BitSize - 1 - n.bits)) & 1
	c := n.chld[branch]
	if c == nil {
		return n, false
	}

	c, ok := c.del(key, bits)
	if !ok {
		return n, false
	}

	if c == nil && !n.leaf {
		return n.chld[1-branch], true
	}

	m := newNode64s(n.key, n.bits, n.leaf, n.value)
	m.chld = n.chld

	m.chld[branch] = c
	return m, true
}

func newNode64s(key uint64, bits uint8, leaf bool, value *node64) *node64s {
	return &node64s{
		key:   key,
		bits:  bits,
		leaf:  leaf,
		value: value}
}