Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to use go's amt array algorithm". In daily operation, I believe many people have doubts about how to use go's amt array algorithm. Xiaobian consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "how to use go's amt array algorithm". Next, please follow the editor to study!

Amttype Node struct {Bmap [] byte / / whether to set the value to swim only the first byte. Eight bits represent the existence of Links [] cid.Cid / / slave node Values [] * cbg.Deferred / / Flush set expVals to the child node value of expLinks [] cid.Cid / / set on Values [] * cbg.Deferred / / value cache [] * Node / / child node cache} basic structure

The amt data structure is an octree, and all data nodes are stored on leaf nodes. The array shape is shown on the leaves, and the lowest nodes of the whole tree are put together in order to form the amt array. Index nodes that do not have data are cut down, saving the required data space.

Set up data

Determine the location of leaf nodes by id

If the index node where the leaf node is located has data, then you can set this data directly.

If the leaf node is within the capacity of the current tree, but the path data does not exist, you need to create a new index path and mount the data.

If the data location set exceeds the current octree capacity, the current octree depth should be expanded first, and the original data should be used as the left subtree of the new tree. New node create a new path hang the written leaf node

/ / growth layers for I > = nodesForHeight (width, int (r.Height) + 1) {if! r.Node.empty () {if err: = r.Node.Flush (ctx, r.store, int (r.Height)) Err! = nil {return err} c, err: = r.store.Put (ctx & r.Node) if err! = nil {return err} r.Node = Node {Bmap: [] byte {0x01}, Links: [] cid.Cid {c} }} r.Heightweights +} / / set the value addVal, err: = r.Node.set (ctx, r.store, int (r.Height), I & cbg.Deferred {Raw: B}) if err! = nil {return err} if addVal {r.Countters +} find data

When adding data, first determine the number of the last layer through the height, determine the index node of the first layer through the array index, and then recursively determine the index node of the second layer through the data width of the penultimate layer, so as to find the leaf node data layer by layer.

Func (n * Node) get (ctx context.Context, bs cbor.IpldStore, height int, I uint64, out interface {}) error {subi: = I / nodesForHeight (width, height) set _: = n.getBit (subi) if! set {return & ErrNotFound {I}} if height = 0 {/ / find from node n.expandValues () d: = n.expVals [I] if um, ok: = out. (cbg.CBORUnmarshaler) Ok {return um.UnmarshalCBOR (bytes.NewReader (d.Raw))} else {return cbor.DecodeInto (d.Raw, out)}} subn, err: = n.loadNode (ctx, bs, subi) False) if err! = nil {return err} return subn.get (ctx, bs, height-1, i%nodesForHeight (width, height), out) / / Recursive Down from Node} Delete data

Delete data and find the data location and path first.

If there is other data on the index node where the data is located, clear the data directly and set the identity.

After deleting the data, check the index node layer by layer, and if the index node is empty, delete the empty node. This reduces the size of the tree to prevent waste of space.

If after clearing the subtree, it is found that there is only one self node with the node, then the size of the whole tree can be reduced, the height can be reduced, and the amount of data stored and the number of nodes indexed can be further reduced.

Func (n * Node) delete (ctx context.Context, bs cbor.IpldStore, height int, I uint64) error {subi: = I / nodesForHeight (width, height) set, _: = n.getBit (subi) if! set {return & ErrNotFound {I}} if height = 0 {/ / find the node Clean up the node n.expandValues () n.expVals [I] = nil n.clearBit (I) return nil} subn, err: = n.loadNode (ctx, bs, subi, false) if err! = nil {return err} / / Recursively look down if err: = subn.delete (ctx Bs, height-1, i%nodesForHeight (width, height)) Err! = nil {return err} if subn.empty () {/ / Clean empty branch n.clearBit (subi) n.cache [subi] = nil n.expLinks [subi] = cid.Undef} return nil} at this point, the study of "how to use go's amt array algorithm" ends. I hope I can solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.