Müllabfuhr

(Alle diese Beispiele gehen von einer Möglichkeit aus, einen Knoten als "tot" zu markieren, ohne ihn sofort zu löschen.)

Eine Möglichkeit besteht darin, bei jeder "normalen" Transaktion gerade genug Knoten zu löschen, um die Rückerstattung zu maximieren. Daher wird die normale Verwendung das Aufblähen langsam aus dem Zustand entfernen. Sie müssten den Betrag berechnen, und er wird wahrscheinlich nicht genau sein (selbst wenn es so wäre, besteht die Möglichkeit, dass sich die Gaspreise in Zukunft ändern.)

Eine andere Möglichkeit ist die gleiche, außer dass Sie das Frontend verwenden, um zu berechnen, welche Knoten gelöscht werden sollen. Dies könnte Ihren Code etwas verkomplizieren, wäre aber effizienter.

Noch eine andere (und dies könnte die einfachste sein) besteht darin, tote Knoten auf einer Liste zu verfolgen und sie dann wiederzuverwenden. Insbesondere wenn Sie einen Knoten nicht mehr benötigen, schieben Sie ihn auf die Liste der toten Knoten. Wenn Sie einen neuen Knoten benötigen, überprüfen Sie zuerst die Liste der toten Knoten und versuchen Sie dann, sie zu überschreiben. Sie können mit jetzt verwaisten Kindern umgehen, indem Sie sie auch auf die Todesliste setzen. Im Wesentlichen löschen Sie rekursiv im Laufe der Zeit und nicht auf einmal.

Jeder iterative Prozess impliziert eine Begrenzung der Baumbreite. Ebenso impliziert jeder rekursive Prozess eine Begrenzung der Baumtiefe. Die meisten Algos beinhalten ein bisschen von beidem. Wenn eine solche Logik in den Vertrag aufgenommen wird, ist es schwierig abzuschätzen, wie groß der Baum sein kann, bevor es zu Problemen kommt. Wir sind uns jedoch sicher, dass die Transaktionskosten mit der Skalierung steigen. An der Blockgasgrenze und/oder Stackgrenze funktionieren wichtige Prozesse überhaupt nicht.

Es ist auch erwähnenswert, dass es wirklich keine Möglichkeit gibt, Informationen aus der Blockchain zu löschen, daher würde ich nicht auf die tatsächliche Zerstörung von Blättern und Zweigen eingehen, die weggeschnitten werden. Es ist ausreichend (und ungefähr gleich), sie logisch zu entfernen.

Im folgenden Code enthalten die Knoten einige einfache Strukturen:

1. Jeder Knoten hat einen Elternknoten.
2. Jeder Knoten hat eine ungeordnete Liste der Kinder.

Wir können neue Knoten hinzufügen, wo immer sie hingehören. Ein Client kann die Länge der Kinderliste erhalten und über die Kinder iterieren. Das macht das Erkunden des Baumes möglich.

Das Löschen ist etwas fummelig.

Das Grundprinzip ist, dass ein beschnittener Zweig keinen Elternteil hat. Wir ignorieren, was sich unter dem beschnittenen Zweig befindet, da eine Erkundung von oben nach unten nicht zu beschnittenen Knoten führt.

Um das Löschen zu erleichtern, erhalten die Kinder einen zusätzlichen Zeiger; ihre Position in der Liste der untergeordneten Elemente im übergeordneten Element. Wir bemerken dies, wenn wir Knoten hinzufügen.

Um einen Knoten zu löschen,

1. Verschieben Sie das letzte Kind der Eltern in die zu löschende Zeile in der Liste der Kinder.
2. Aktualisieren Sie den Positionszeiger des übergeordneten Elements in dem verschobenen untergeordneten Element.
3. Kürzen Sie die Kinderliste um eins.

Also, wenn der Elternteil Kinder hat:

• A, B, C, D, E, F

und wir wollen D löschen.

• Bewegen Sie F an die 4. Position, wo D ist.

Wir machen es einfach, die Position von D mit einem anderen Zeiger zu lokalisieren:

In D:

• Elternteil ist X
• parentIndex ist 3 (Position in der Liste der Eltern)

Danach lautet die Liste der Eltern:

• A, B, C, F, E, F

Machen Sie die Liste mit -- um eine Zeile kürzer.

• Vergessen Sie nicht, den parentIndex-Zeiger von F zu aktualisieren. War 5. Jetzt 3, weil es sich bewegt hat.
• Setzen Sie die übergeordneten Zeiger der gelöschten Knoten auf Null.

Jeder Knoten kann als mit der Wurzel verbunden angesehen werden, indem er seinem Vorfahren bis zur Baumwurzel folgt. Es sollte eine ununterbrochene Kette von Eltern sein. Wenn ein 0-Elternteil vor der Baumwurzel angetroffen wird, lebt der Knoten in einem beschnittenen Zweig. Logisch gelöscht.

Ich habe einen rekursiven Prozess eingefügt, um die Einfachheit der Logik zu zeigen, aber es ist besser, diesen Prozess clientseitig durchzuführen, da er rekursiv ist.

Ein unehrlicher Client kann möglicherweise in beschnittenen Zweigen herumspielen, wenn die rekursive Prüfung fehlt. Wenn die festgelegten Werte von Bedeutung sind, ist es besser, "ausstehende" Änderungen mit einem vertrauenswürdigen Client unter Verwendung eines eingeschränkten "onlyOwner"-Prozesses zu beheben. Ein Client kann weit und tief, rauf und runter kriechen, ohne dass ihm jemals das Benzin ausgeht, weil er im Laufe der Zeit winzige Funktionen aufruft. Die Vertragsfunktionen, die den Zustand ändern, sollten immer auf Null gesetzt werden, damit die Zustandsintegrität bei jedem atomaren Schritt aufrechterhalten wird.

Ein ehrliches Front-End wird in der Lage sein, eine zuverlässige Baumnavigation in jeder Größenordnung bereitzustellen.

Mit minimalem Testaufwand schnell skizziert. Ich hoffe es hilft:

pragma solidity ^0.4.6;

contract ObjectTree {

bytes32 public treeRoot;

struct NodeStruct {
    bytes32 parent; // the id of the parent node
    uint parentIndex; // the position of this node in the Parent's children list
    bytes32[] children; // unordered list of children below this node
    // add useful node properties here
}

mapping(bytes32 => NodeStruct) nodeStructs;

event LogNewNode(bytes32 nodeId, bytes32 parentId);
event LogDelNode(bytes32 nodeId);

function ObjectTree() {
    treeRoot = newNode(0);
}

function newNode(bytes32 parent) 
    public
    returns(bytes32 newNodeId)
{
    // very tempting to call isActiveNode(parent) here
    // to prevent insertion in pruned branches. Not scalable. 

    newNodeId = sha3(parent, msg.sender, block.number);
    NodeStruct memory node;
    node.parent = parent;
    if(parent>0) {
        node.parentIndex = registerChild(parent,newNodeId);
    }
    nodeStructs[newNodeId] = node;
    LogNewNode(newNodeId, parent);
    return newNodeId;
}

function registerChild(bytes32 parentId, bytes32 childId)
    private
    returns(uint index)
{
    return nodeStructs[parentId].children.push(childId) - 1;
}

// to remove a node, 
// we'll zero the parent and parent index.
// we'll remove the node from the parent's children list
// To do that, we'll 
// 1. move the list child into the row to delete
// 2. update the index of the node that moved
// 3. shorten the parent's children list by one

function pruneBranch(bytes32 nodeId)
    public
    returns(bool success)
{
    bytes32 parent = nodeStructs[nodeId].parent;
    uint rowToDelete = nodeStructs[nodeId].parentIndex;
    uint rowToMove = nodeStructs[parent].children.length-1; // last child in the list
    // move the last child into the row to delete
    nodeStructs[parent].children[rowToDelete] = nodeStructs[parent].children[rowToMove];
    // maintain pointer integrity ... pointer in the child that moved
    nodeStructs[nodeStructs[parent].children[rowToMove]].parentIndex = rowToMove;
    // parent has one less children now
    nodeStructs[parent].children.length--;
    // zero out the node that was pruned
    nodeStructs[nodeId].parent=0;
    nodeStructs[nodeId].parentIndex=0;
    LogDelNode(nodeId);
    return true;
}

// This following recursive process puts an upper bound on the tree depth the contract can handle. 
// Therefore, better to implement similar logic on the client side and recursively call nodeStructs
// until a node can be confirmed attached to the treeRoot in an unbroken chain. 
// Shown here for illustration only since it won't scale infinately.

function isActiveNode(bytes32 nodeId)
    public
    constant
    returns(bool isIndeed)
{
    if(nodeId==treeRoot) return true;
    if(nodeStructs[nodeId].parent==0) return false;
    return isActiveNode(nodeStructs[nodeId].parent);
}

function getNodeChildCount(bytes32 nodeId)
    public
    constant
    returns(uint childCount)
{
    return(nodeStructs[nodeId].children.length);
}

function getNodeChildAtIndex(bytes32 nodeId, uint index) 
    public 
    constant
    returns(bytes32 childId)
{
    return nodeStructs[nodeId].children[index];
}


}