1// SPDX-License-Identifier: ISC
2// Copyright (c) 2014-2020 Bitmark Inc.
3// Use of this source code is governed by an ISC
4// license that can be found in the LICENSE file.
5
6package avl
7
8import (
9	"sync"
10)
11
12// Item - a key item must implement the Compare function
13type Item interface {
14	Compare(interface{}) int // for left/right ordering of items
15}
16
17// Node - a node in the tree
18type Node struct {
19	left       *Node       // left sub-tree
20	right      *Node       // right sub-tree
21	up         *Node       // points to parent node
22	key        Item        // key part for ordering
23	value      interface{} // value part for data storage
24	leftNodes  int         // node count
25	rightNodes int         // node count
26	balance    int         // -1, 0, +1
27}
28
29// global data for allocator
30var m sync.Mutex   // to keep values in sync
31var pool *Node     // linked list of reclaimed nodes
32var totalNodes int // total nodes created
33var freeNodes int  // number of nodes in the pool
34
35// allocate a new node, reuses reclaimed nodes if any are available
36func newNode(key Item, value interface{}) *Node {
37	m.Lock()
38	if nil == pool {
39		if 0 != freeNodes {
40			panic("pool corrupt")
41		}
42		totalNodes += 1
43		m.Unlock()
44		return &Node{
45			key:     key,
46			value:   value,
47			balance: 0,
48		}
49	}
50	p := pool
51	pool = p.up
52	p.key = key
53	p.value = value
54	p.balance = 0
55	p.leftNodes = 0
56	p.rightNodes = 0
57	p.left = nil
58	p.right = nil
59	p.up = nil // ensure freelist pointer is cleared
60	freeNodes -= 1
61	m.Unlock()
62	return p
63}
64
65// reclaim a node and keep it in a pool
66func freeNode(node *Node) {
67	m.Lock()
68	node.up = pool // use as free list pointer
69
70	node.left = nil
71	node.right = nil
72	node.key = nil
73	node.value = nil
74	node.balance = 0
75	node.leftNodes = 0
76	node.rightNodes = 0
77	freeNodes += 1
78
79	pool = node
80	m.Unlock()
81}
82