Recolección de basura

(Todos estos ejemplos asumen alguna forma de marcar un nodo como "muerto" sin eliminarlo inmediatamente).

Una posibilidad es, durante cada transacción "normal", eliminar solo los nodos necesarios para maximizar el reembolso. Por lo tanto, el uso normal eliminará lentamente la hinchazón del estado. Tendría que calcular la cantidad, y probablemente no sea exacta (incluso si lo fuera, existe la posibilidad de que cambien los precios de la gasolina en el futuro).

Otra posibilidad es la misma, excepto que usa la interfaz para calcular qué nodos eliminar. Esto podría complicar un poco su código, pero sería más eficiente.

Otro (y esto puede ser más simple) es realizar un seguimiento de los nodos muertos en una lista y luego reutilizarlos. Específicamente, cuando ya no necesite un nodo, insértelo en la lista muerta. Cuando necesite un nuevo nodo, primero verifique la lista muerta y luego intente sobrescribirla. Puede manejar a los niños ahora huérfanos empujándolos también a la lista de muertos. Esencialmente, elimina recursivamente con el tiempo, en lugar de todo a la vez.

Cualquier proceso iterativo implicará un límite al ancho del árbol. De manera similar, cualquier proceso recursivo implicará un límite a la profundidad del árbol. La mayoría de los algoritmos implicarán un poco de ambos. Si dicha lógica se incluye en el contrato, será difícil estimar qué tan grande puede ser el árbol antes de que comiencen los problemas. Pero, estaremos seguros de que el costo de transacción aumenta con la escala. En el límite de gas del bloque y/o el límite de la pila, los procesos importantes no funcionarán en absoluto.

También vale la pena señalar que realmente no hay forma de eliminar información de la cadena de bloques, por lo que no me detendría en la destrucción real de las hojas y ramas que se podan. Es suficiente (y más o menos lo mismo) eliminarlos lógicamente.

En el siguiente código, los nodos incluyen algunas estructuras simples:

1. Cada nodo tiene un padre.
2. Cada nodo tiene una lista desordenada de los hijos.

Podemos agregar nuevos nodos dondequiera que pertenezcan. Un cliente puede obtener la longitud de la lista de niños e iterar sobre los niños. Eso hace posible explorar el árbol.

Eliminar es un poco complicado.

El principio básico es que una rama podada no tiene padre. Ignoramos lo que hay debajo de la rama podada, ya que una exploración de arriba hacia abajo no conducirá a nodos podados.

Para facilitar la eliminación, los hijos obtienen un puntero adicional; su posición en la lista de hijos en el padre. Notamos que a medida que agregamos nodos.

Para eliminar un nodo,

1. Mueva el último hijo de los padres a la fila para eliminar en la lista de hijos.
2. Actualice el puntero de posición principal en el elemento secundario que se movió.
3. Acorte la lista de niños en uno.

Entonces, si el padre tiene hijos:

• A B C D E F

y queremos eliminar D.

• Mueva F a la cuarta posición, donde está D.

Facilitamos la ubicación de la posición de D con otro puntero:

en D:

• padre es X
• parentIndex es 3 (posición en la lista de padres)

Habiendo hecho eso, la lista de los padres dice:

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

Haga la lista una fila más corta con --.

• No olvide actualizar el puntero parentIndex de F. Tenía 5. Ahora 3, porque se movió.
• Ponga a cero los punteros principales de los nodos eliminados.

Se puede ver que cualquier nodo está adjunto a la raíz siguiendo su ascendencia hasta la raíz del árbol. Debe ser una cadena ininterrumpida de padres. Si se encuentra un padre 0 antes de treeRoot, entonces el nodo vive en una rama podada. Eliminado lógicamente.

Incluí un proceso recursivo para mostrar la simplicidad de la lógica, pero es mejor hacer ese proceso del lado del cliente porque es recursivo.

Un cliente deshonesto puede perder el tiempo en las ramas podadas cuando el control recursivo está ausente. Si los valores establecidos tienen alguna consecuencia, entonces es mejor barrer los cambios "pendientes" con un cliente de confianza mediante un proceso restringido de "solo propietario". Un cliente puede arrastrarse a lo ancho y a lo profundo, arriba y abajo sin quedarse nunca sin combustible porque llamará a funciones diminutas a medida que avanza. Las funciones de contrato que cambian de estado siempre deben ponerse a cero pendientes para que se mantenga la integridad del estado en cada paso atómico.

Un front-end honesto podrá proporcionar una navegación de árbol confiable a cualquier escala.

Esbozado rápidamente con pruebas mínimas. Espero eso ayude:

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];
}


}