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