type Item … const DefaultFreeListSize … var nilItems … var nilChildren … type FreeList … // NewFreeList creates a new free list. // size is the maximum size of the returned free list. func NewFreeList(size int) *FreeList { … } func (f *FreeList) newNode() (n *node) { … } // freeNode adds the given node to the list, returning true if it was added // and false if it was discarded. func (f *FreeList) freeNode(n *node) (out bool) { … } type ItemIterator … // New creates a new B-Tree with the given degree. // // New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items // and 2-4 children). func New(degree int) *BTree { … } // NewWithFreeList creates a new B-Tree that uses the given node free list. func NewWithFreeList(degree int, f *FreeList) *BTree { … } type items … // insertAt inserts a value into the given index, pushing all subsequent values // forward. func (s *items) insertAt(index int, item Item) { … } // removeAt removes a value at a given index, pulling all subsequent values // back. func (s *items) removeAt(index int) Item { … } // pop removes and returns the last element in the list. func (s *items) pop() (out Item) { … } // truncate truncates this instance at index so that it contains only the // first index items. index must be less than or equal to length. func (s *items) truncate(index int) { … } // find returns the index where the given item should be inserted into this // list. 'found' is true if the item already exists in the list at the given // index. func (s items) find(item Item) (index int, found bool) { … } type children … // insertAt inserts a value into the given index, pushing all subsequent values // forward. func (s *children) insertAt(index int, n *node) { … } // removeAt removes a value at a given index, pulling all subsequent values // back. func (s *children) removeAt(index int) *node { … } // pop removes and returns the last element in the list. func (s *children) pop() (out *node) { … } // truncate truncates this instance at index so that it contains only the // first index children. index must be less than or equal to length. func (s *children) truncate(index int) { … } type node … func (n *node) mutableFor(cow *copyOnWriteContext) *node { … } func (n *node) mutableChild(i int) *node { … } // split splits the given node at the given index. The current node shrinks, // and this function returns the item that existed at that index and a new node // containing all items/children after it. func (n *node) split(i int) (Item, *node) { … } // maybeSplitChild checks if a child should be split, and if so splits it. // Returns whether or not a split occurred. func (n *node) maybeSplitChild(i, maxItems int) bool { … } // insert inserts an item into the subtree rooted at this node, making sure // no nodes in the subtree exceed maxItems items. Should an equivalent item be // be found/replaced by insert, it will be returned. func (n *node) insert(item Item, maxItems int) Item { … } // get finds the given key in the subtree and returns it. func (n *node) get(key Item) Item { … } // min returns the first item in the subtree. func min(n *node) Item { … } // max returns the last item in the subtree. func max(n *node) Item { … } type toRemove … const removeItem … const removeMin … const removeMax … // remove removes an item from the subtree rooted at this node. func (n *node) remove(item Item, minItems int, typ toRemove) Item { … } // growChildAndRemove grows child 'i' to make sure it's possible to remove an // item from it while keeping it at minItems, then calls remove to actually // remove it. // // Most documentation says we have to do two sets of special casing: // 1) item is in this node // 2) item is in child // In both cases, we need to handle the two subcases: // A) node has enough values that it can spare one // B) node doesn't have enough values // For the latter, we have to check: // a) left sibling has node to spare // b) right sibling has node to spare // c) we must merge // To simplify our code here, we handle cases #1 and #2 the same: // If a node doesn't have enough items, we make sure it does (using a,b,c). // We then simply redo our remove call, and the second time (regardless of // whether we're in case 1 or 2), we'll have enough items and can guarantee // that we hit case A. func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item { … } type direction … const descend … const ascend … // iterate provides a simple method for iterating over elements in the tree. // // When ascending, the 'start' should be less than 'stop' and when descending, // the 'start' should be greater than 'stop'. Setting 'includeStart' to true // will force the iterator to include the first item when it equals 'start', // thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a // "greaterThan" or "lessThan" queries. func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) { … } // Used for testing/debugging purposes. func (n *node) print(w io.Writer, level int) { … } type BTree … type copyOnWriteContext … // Clone clones the btree, lazily. Clone should not be called concurrently, // but the original tree (t) and the new tree (t2) can be used concurrently // once the Clone call completes. // // The internal tree structure of b is marked read-only and shared between t and // t2. Writes to both t and t2 use copy-on-write logic, creating new nodes // whenever one of b's original nodes would have been modified. Read operations // should have no performance degredation. Write operations for both t and t2 // will initially experience minor slow-downs caused by additional allocs and // copies due to the aforementioned copy-on-write logic, but should converge to // the original performance characteristics of the original tree. func (t *BTree) Clone() (t2 *BTree) { … } // maxItems returns the max number of items to allow per node. func (t *BTree) maxItems() int { … } // minItems returns the min number of items to allow per node (ignored for the // root node). func (t *BTree) minItems() int { … } func (c *copyOnWriteContext) newNode() (n *node) { … } type freeType … const ftFreelistFull … const ftStored … const ftNotOwned … // freeNode frees a node within a given COW context, if it's owned by that // context. It returns what happened to the node (see freeType const // documentation). func (c *copyOnWriteContext) freeNode(n *node) freeType { … } // ReplaceOrInsert adds the given item to the tree. If an item in the tree // already equals the given one, it is removed from the tree and returned. // Otherwise, nil is returned. // // nil cannot be added to the tree (will panic). func (t *BTree) ReplaceOrInsert(item Item) Item { … } // Delete removes an item equal to the passed in item from the tree, returning // it. If no such item exists, returns nil. func (t *BTree) Delete(item Item) Item { … } // DeleteMin removes the smallest item in the tree and returns it. // If no such item exists, returns nil. func (t *BTree) DeleteMin() Item { … } // DeleteMax removes the largest item in the tree and returns it. // If no such item exists, returns nil. func (t *BTree) DeleteMax() Item { … } func (t *BTree) deleteItem(item Item, typ toRemove) Item { … } // AscendRange calls the iterator for every value in the tree within the range // [greaterOrEqual, lessThan), until iterator returns false. func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) { … } // AscendLessThan calls the iterator for every value in the tree within the range // [first, pivot), until iterator returns false. func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) { … } // AscendGreaterOrEqual calls the iterator for every value in the tree within // the range [pivot, last], until iterator returns false. func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) { … } // Ascend calls the iterator for every value in the tree within the range // [first, last], until iterator returns false. func (t *BTree) Ascend(iterator ItemIterator) { … } // DescendRange calls the iterator for every value in the tree within the range // [lessOrEqual, greaterThan), until iterator returns false. func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) { … } // DescendLessOrEqual calls the iterator for every value in the tree within the range // [pivot, first], until iterator returns false. func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) { … } // DescendGreaterThan calls the iterator for every value in the tree within // the range [last, pivot), until iterator returns false. func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) { … } // Descend calls the iterator for every value in the tree within the range // [last, first], until iterator returns false. func (t *BTree) Descend(iterator ItemIterator) { … } // Get looks for the key item in the tree, returning it. It returns nil if // unable to find that item. func (t *BTree) Get(key Item) Item { … } // Min returns the smallest item in the tree, or nil if the tree is empty. func (t *BTree) Min() Item { … } // Max returns the largest item in the tree, or nil if the tree is empty. func (t *BTree) Max() Item { … } // Has returns true if the given key is in the tree. func (t *BTree) Has(key Item) bool { … } // Len returns the number of items currently in the tree. func (t *BTree) Len() int { … } // Clear removes all items from the btree. If addNodesToFreelist is true, // t's nodes are added to its freelist as part of this call, until the freelist // is full. Otherwise, the root node is simply dereferenced and the subtree // left to Go's normal GC processes. // // This can be much faster // than calling Delete on all elements, because that requires finding/removing // each element in the tree and updating the tree accordingly. It also is // somewhat faster than creating a new tree to replace the old one, because // nodes from the old tree are reclaimed into the freelist for use by the new // one, instead of being lost to the garbage collector. // // This call takes: // O(1): when addNodesToFreelist is false, this is a single operation. // O(1): when the freelist is already full, it breaks out immediately // O(freelist size): when the freelist is empty and the nodes are all owned // by this tree, nodes are added to the freelist until full. // O(tree size): when all nodes are owned by another tree, all nodes are // iterated over looking for nodes to add to the freelist, and due to // ownership, none are. func (t *BTree) Clear(addNodesToFreelist bool) { … } // reset returns a subtree to the freelist. It breaks out immediately if the // freelist is full, since the only benefit of iterating is to fill that // freelist up. Returns true if parent reset call should continue. func (n *node) reset(c *copyOnWriteContext) bool { … } type Int … // Less returns true if int(a) < int(b). func (a Int) Less(b Item) bool { … }
Codebase Browser
kubernetes