From: Robert Varga Date: Thu, 12 Feb 2015 14:09:54 +0000 (+0100) Subject: Sharded implementation of DOMDataTreeService X-Git-Tag: release/lithium~473^2~6^2 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=5199c0527719d0410ae67bba2365e2a7ed2a9e91 Sharded implementation of DOMDataTreeService This patch adds a simplistic implementation of a DOMDataTreeService and a DOMDataTreeShardingService. Change-Id: Ibb76c99d0fa842b1034a2b747c4ec57816f99c7d Signed-off-by: Robert Varga --- diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java new file mode 100644 index 0000000000..9a71089946 --- /dev/null +++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java @@ -0,0 +1,33 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.md.sal.dom.broker.impl; + +import com.google.common.base.Preconditions; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard; +import org.opendaylight.yangtools.concepts.AbstractListenerRegistration; + +final class ShardRegistration extends AbstractListenerRegistration { + private final DOMDataTreeIdentifier prefix; + private final ShardedDOMDataTree tree; + + protected ShardRegistration(final ShardedDOMDataTree tree, final DOMDataTreeIdentifier prefix, final T shard) { + super(shard); + this.tree = Preconditions.checkNotNull(tree); + this.prefix = Preconditions.checkNotNull(prefix); + } + + DOMDataTreeIdentifier getPrefix() { + return prefix; + } + + @Override + protected void removeRegistration() { + tree.removeShard(this); + } +} diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java new file mode 100644 index 0000000000..11eae5d833 --- /dev/null +++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java @@ -0,0 +1,181 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.md.sal.dom.broker.impl; + +import com.google.common.base.Preconditions; +import java.util.Collection; +import java.util.EnumMap; +import java.util.HashMap; +import java.util.Map; +import java.util.Map.Entry; +import java.util.TreeMap; +import javax.annotation.concurrent.GuardedBy; +import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeListener; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducer; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeService; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShardingConflictException; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShardingService; +import org.opendaylight.yangtools.concepts.ListenerRegistration; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +public final class ShardedDOMDataTree implements DOMDataTreeService, DOMDataTreeShardingService { + private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataTree.class); + private final Map shardingTables = new EnumMap<>(LogicalDatastoreType.class); + @GuardedBy("this") + private final Map idToProducer = new TreeMap<>(); + + @GuardedBy("this") + private ShardingTableEntry lookupShard(final DOMDataTreeIdentifier prefix) { + final ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType()); + if (t == null) { + return null; + } + + return t.lookup(prefix.getRootIdentifier()); + } + + @GuardedBy("this") + private void storeShard(final DOMDataTreeIdentifier prefix, final ShardRegistration reg) { + ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType()); + if (t == null) { + t = new ShardingTableEntry(); + shardingTables.put(prefix.getDatastoreType(), t); + } + + t.store(prefix.getRootIdentifier(), reg); + } + + void removeShard(final ShardRegistration reg) { + final DOMDataTreeIdentifier prefix = reg.getPrefix(); + final ShardRegistration parentReg; + + synchronized (this) { + final ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType()); + if (t == null) { + LOG.warn("Shard registration {} points to non-existent table", reg); + return; + } + + t.remove(prefix.getRootIdentifier()); + parentReg = lookupShard(prefix).getRegistration(); + + /* + * FIXME: adjust all producers. This is tricky, as we need different locking strategy, + * simply because we risk AB/BA deadlock with a producer being split off from + * a producer. + * + */ + } + + if (parentReg != null) { + parentReg.getInstance().onChildDetached(prefix, reg.getInstance()); + } + } + + @Override + public ListenerRegistration registerDataTreeShard(final DOMDataTreeIdentifier prefix, final T shard) throws DOMDataTreeShardingConflictException { + final ShardRegistration reg; + final ShardRegistration parentReg; + + synchronized (this) { + /* + * Lookup the parent shard (e.g. the one which currently matches the prefix), + * and if it exists, check if its registration prefix does not collide with + * this registration. + */ + final ShardingTableEntry parent = lookupShard(prefix); + parentReg = parent.getRegistration(); + if (parentReg != null && prefix.equals(parentReg.getPrefix())) { + throw new DOMDataTreeShardingConflictException(String.format("Prefix %s is already occupied by shard {}", prefix, parentReg.getInstance())); + } + + // FIXME: wrap the shard in a proper adaptor based on implemented interface + + reg = new ShardRegistration(this, prefix, shard); + + storeShard(prefix, reg); + + // FIXME: update any producers/registrations + } + + // Notify the parent shard + if (parentReg != null) { + parentReg.getInstance().onChildAttached(prefix, shard); + } + + return reg; + } + + @GuardedBy("this") + private DOMDataTreeProducer findProducer(final DOMDataTreeIdentifier subtree) { + for (Entry e : idToProducer.entrySet()) { + if (e.getKey().contains(subtree)) { + return e.getValue(); + } + } + + return null; + } + + synchronized void destroyProducer(final ShardedDOMDataTreeProducer producer) { + for (DOMDataTreeIdentifier s : producer.getSubtrees()) { + DOMDataTreeProducer r = idToProducer.remove(s); + if (!producer.equals(r)) { + LOG.error("Removed producer %s on subtree %s while removing %s", r, s, producer); + } + } + } + + @GuardedBy("this") + private DOMDataTreeProducer createProducer(final Map shardMap) { + // Record the producer's attachment points + final DOMDataTreeProducer ret = ShardedDOMDataTreeProducer.create(this, shardMap); + for (DOMDataTreeIdentifier s : shardMap.keySet()) { + idToProducer.put(s, ret); + } + + return ret; + } + + @Override + public synchronized DOMDataTreeProducer createProducer(final Collection subtrees) { + Preconditions.checkArgument(!subtrees.isEmpty(), "Subtrees may not be empty"); + + final Map shardMap = new HashMap<>(); + for (DOMDataTreeIdentifier s : subtrees) { + // Attempting to create a disconnected producer -- all subtrees have to be unclaimed + final DOMDataTreeProducer producer = findProducer(s); + Preconditions.checkArgument(producer == null, "Subtree %s is attached to producer %s", s, producer); + + shardMap.put(s, lookupShard(s).getRegistration().getInstance()); + } + + return createProducer(shardMap); + } + + synchronized DOMDataTreeProducer createProducer(final ShardedDOMDataTreeProducer parent, final Collection subtrees) { + Preconditions.checkNotNull(parent); + + final Map shardMap = new HashMap<>(); + for (DOMDataTreeIdentifier s : subtrees) { + shardMap.put(s, lookupShard(s).getRegistration().getInstance()); + } + + return createProducer(shardMap); + } + + @Override + public synchronized ListenerRegistration registerListener(final T listener, final Collection subtrees, final boolean allowRxMerges, final Collection producers) { + // TODO Auto-generated method stub + return null; + } +} diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java new file mode 100644 index 0000000000..9712b25ac9 --- /dev/null +++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java @@ -0,0 +1,210 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.md.sal.dom.broker.impl; + +import com.google.common.base.Preconditions; +import com.google.common.collect.BiMap; +import com.google.common.collect.ImmutableBiMap; +import com.google.common.collect.ImmutableBiMap.Builder; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSet; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Queue; +import java.util.Set; +import javax.annotation.concurrent.GuardedBy; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducer; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducerBusyException; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducerException; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard; +import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction; +import org.opendaylight.controller.sal.core.spi.data.DOMStore; +import org.opendaylight.controller.sal.core.spi.data.DOMStoreTransactionChain; +import org.opendaylight.controller.sal.core.spi.data.DOMStoreWriteTransaction; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +final class ShardedDOMDataTreeProducer implements DOMDataTreeProducer { + private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataTreeProducer.class); + private final BiMap shardToChain; + private final Map idToShard; + private final ShardedDOMDataTree dataTree; + + @GuardedBy("this") + private Map children = Collections.emptyMap(); + @GuardedBy("this") + private DOMDataWriteTransaction openTx; + @GuardedBy("this") + private boolean closed; + + ShardedDOMDataTreeProducer(final ShardedDOMDataTree dataTree, final Map shardMap, final Set shards) { + this.dataTree = Preconditions.checkNotNull(dataTree); + + // Create shard -> chain map + final Builder cb = ImmutableBiMap.builder(); + final Queue es = new LinkedList<>(); + + for (DOMDataTreeShard s : shards) { + if (s instanceof DOMStore) { + try { + final DOMStoreTransactionChain c = ((DOMStore)s).createTransactionChain(); + LOG.trace("Using DOMStore chain {} to access shard {}", c, s); + cb.put(s, c); + } catch (Exception e) { + LOG.error("Failed to instantiate chain for shard {}", s, e); + es.add(e); + } + } else { + LOG.error("Unhandled shard instance type {}", s.getClass()); + } + } + this.shardToChain = cb.build(); + + // An error was encountered, close chains and report the error + if (shardToChain.size() != shards.size()) { + for (DOMStoreTransactionChain c : shardToChain.values()) { + try { + c.close(); + } catch (Exception e) { + LOG.warn("Exception raised while closing chain %s", c, e); + } + } + + final IllegalStateException e = new IllegalStateException("Failed to completely allocate contexts", es.poll()); + while (!es.isEmpty()) { + e.addSuppressed(es.poll()); + } + + throw e; + } + + idToShard = ImmutableMap.copyOf(shardMap); + } + + @Override + public synchronized DOMDataWriteTransaction createTransaction(final boolean isolated) { + Preconditions.checkState(!closed, "Producer is already closed"); + Preconditions.checkState(openTx == null, "Transaction %s is still open", openTx); + + // Allocate backing transactions + final Map shardToTx = new HashMap<>(); + for (Entry e : shardToChain.entrySet()) { + shardToTx.put(e.getKey(), e.getValue().newWriteOnlyTransaction()); + } + + // Create the ID->transaction map + final ImmutableMap.Builder b = ImmutableMap.builder(); + for (Entry e : idToShard.entrySet()) { + b.put(e.getKey(), shardToTx.get(e.getValue())); + } + + final ShardedDOMDataWriteTransaction ret = new ShardedDOMDataWriteTransaction(this, b.build()); + openTx = ret; + return ret; + } + + @GuardedBy("this") + private boolean haveSubtree(final DOMDataTreeIdentifier subtree) { + for (DOMDataTreeIdentifier i : idToShard.keySet()) { + if (i.contains(subtree)) { + return true; + } + } + + return false; + } + + @GuardedBy("this") + private DOMDataTreeProducer lookupChild(final DOMDataTreeIdentifier s) { + for (Entry e : children.entrySet()) { + if (e.getKey().contains(s)) { + return e.getValue(); + } + } + + return null; + } + + @Override + public synchronized DOMDataTreeProducer createProducer(final Collection subtrees) { + Preconditions.checkState(!closed, "Producer is already closed"); + Preconditions.checkState(openTx == null, "Transaction %s is still open", openTx); + + for (DOMDataTreeIdentifier s : subtrees) { + // Check if the subtree was visible at any time + if (!haveSubtree(s)) { + throw new IllegalArgumentException(String.format("Subtree %s was never available in producer %s", s, this)); + } + + // Check if the subtree has not been delegated to a child + final DOMDataTreeProducer child = lookupChild(s); + Preconditions.checkArgument(child == null, "Subtree %s is delegated to child producer %s", s, child); + + // Check if part of the requested subtree is not delegated to a child. + for (DOMDataTreeIdentifier c : children.keySet()) { + if (s.contains(c)) { + throw new IllegalArgumentException(String.format("Subtree %s cannot be delegated as it is superset of already-delegated %s", s, c)); + } + } + } + + final DOMDataTreeProducer ret = dataTree.createProducer(this, subtrees); + final ImmutableMap.Builder cb = ImmutableMap.builder(); + cb.putAll(children); + for (DOMDataTreeIdentifier s : subtrees) { + cb.put(s, ret); + } + + children = cb.build(); + return ret; + } + + @Override + public synchronized void close() throws DOMDataTreeProducerException { + if (!closed) { + if (openTx != null) { + throw new DOMDataTreeProducerBusyException(String.format("Transaction %s is still open", openTx)); + } + + closed = true; + dataTree.destroyProducer(this); + } + } + + static DOMDataTreeProducer create(final ShardedDOMDataTree dataTree, final Map shardMap) { + /* + * FIXME: we do not allow multiple multiple shards in a producer because we do not implement the + * synchronization primitives yet + */ + final Set shards = ImmutableSet.copyOf(shardMap.values()); + if (shards.size() > 1) { + throw new UnsupportedOperationException("Cross-shard producers are not supported yet"); + } + + return new ShardedDOMDataTreeProducer(dataTree, shardMap, shards); + } + + Set getSubtrees() { + return idToShard.keySet(); + } + + synchronized void cancelTransaction(final ShardedDOMDataWriteTransaction transaction) { + if (!openTx.equals(transaction)) { + LOG.warn("Transaction {} is not open in producer {}", transaction, this); + return; + } + + LOG.debug("Transaction {} cancelled", transaction); + openTx = null; + } +} diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java new file mode 100644 index 0000000000..33f15e3f67 --- /dev/null +++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java @@ -0,0 +1,125 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.md.sal.dom.broker.impl; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableSet; +import com.google.common.util.concurrent.CheckedFuture; +import com.google.common.util.concurrent.Futures; +import com.google.common.util.concurrent.ListenableFuture; +import java.util.ArrayList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import java.util.concurrent.atomic.AtomicLong; +import javax.annotation.concurrent.GuardedBy; +import javax.annotation.concurrent.NotThreadSafe; +import org.opendaylight.controller.md.sal.common.api.TransactionStatus; +import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType; +import org.opendaylight.controller.md.sal.common.api.data.TransactionCommitFailedException; +import org.opendaylight.controller.md.sal.common.impl.service.AbstractDataTransaction; +import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier; +import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction; +import org.opendaylight.controller.sal.core.spi.data.DOMStoreThreePhaseCommitCohort; +import org.opendaylight.controller.sal.core.spi.data.DOMStoreWriteTransaction; +import org.opendaylight.yangtools.yang.common.RpcResult; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; +import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +@NotThreadSafe +final class ShardedDOMDataWriteTransaction implements DOMDataWriteTransaction { + private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataWriteTransaction.class); + private static final AtomicLong COUNTER = new AtomicLong(); + private final Map idToTransaction; + private final ShardedDOMDataTreeProducer producer; + private final String identifier; + @GuardedBy("this") + private boolean closed = false; + + ShardedDOMDataWriteTransaction(final ShardedDOMDataTreeProducer producer, final Map idToTransaction) { + this.producer = Preconditions.checkNotNull(producer); + this.idToTransaction = Preconditions.checkNotNull(idToTransaction); + this.identifier = "SHARDED-DOM-" + COUNTER.getAndIncrement(); + } + + // FIXME: use atomic operations + @GuardedBy("this") + private DOMStoreWriteTransaction lookup(final LogicalDatastoreType store, final YangInstanceIdentifier path) { + final DOMDataTreeIdentifier id = new DOMDataTreeIdentifier(store, path); + + for (Entry e : idToTransaction.entrySet()) { + if (e.getKey().contains(id)) { + return e.getValue(); + } + } + + throw new IllegalArgumentException(String.format("Path %s is not acessible from transaction %s", id, this)); + } + + @Override + public String getIdentifier() { + return identifier; + } + + @Override + public synchronized boolean cancel() { + if (closed) { + return false; + } + + LOG.debug("Cancelling transaction {}", identifier); + for (DOMStoreWriteTransaction tx : ImmutableSet.copyOf(idToTransaction.values())) { + tx.close(); + } + + closed = true; + producer.cancelTransaction(this); + return true; + } + + @Override + public synchronized CheckedFuture submit() { + Preconditions.checkState(!closed, "Transaction %s is already closed", identifier); + + final Set txns = ImmutableSet.copyOf(idToTransaction.values()); + final List cohorts = new ArrayList<>(txns.size()); + for (DOMStoreWriteTransaction tx : txns) { + cohorts.add(tx.ready()); + } + + try { + return Futures.immediateCheckedFuture(new CommitCoordinationTask(this, cohorts, null).call()); + } catch (TransactionCommitFailedException e) { + return Futures.immediateFailedCheckedFuture(e); + } + } + + @Override + @Deprecated + public ListenableFuture> commit() { + return AbstractDataTransaction.convertToLegacyCommitFuture(submit()); + } + + @Override + public synchronized void delete(final LogicalDatastoreType store, final YangInstanceIdentifier path) { + lookup(store, path).delete(path); + } + + @Override + public synchronized void put(final LogicalDatastoreType store, final YangInstanceIdentifier path, final NormalizedNode data) { + lookup(store, path).write(path, data); + } + + @Override + public synchronized void merge(final LogicalDatastoreType store, final YangInstanceIdentifier path, final NormalizedNode data) { + lookup(store, path).merge(path, data); + } +} diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java new file mode 100644 index 0000000000..fcd0ebdca0 --- /dev/null +++ b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.md.sal.dom.broker.impl; + +import com.google.common.base.Preconditions; +import java.util.Collections; +import java.util.Iterator; +import java.util.Map; +import org.opendaylight.yangtools.concepts.Identifiable; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier; +import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +final class ShardingTableEntry implements Identifiable { + private static final Logger LOG = LoggerFactory.getLogger(ShardingTableEntry.class); + private final Map children = Collections.emptyMap(); + private final PathArgument identifier; + private ShardRegistration registration; + + ShardingTableEntry() { + identifier = null; + } + + ShardingTableEntry(final PathArgument identifier) { + this.identifier = Preconditions.checkNotNull(identifier); + } + + @Override + public PathArgument getIdentifier() { + return identifier; + } + + public ShardRegistration getRegistration() { + return registration; + } + + ShardingTableEntry lookup(final YangInstanceIdentifier id) { + final Iterator it = id.getPathArguments().iterator(); + ShardingTableEntry entry = this; + + while (it.hasNext()) { + final PathArgument a = it.next(); + final ShardingTableEntry child = entry.children.get(a); + if (child == null) { + LOG.debug("Lookup of {} stopped at {}", id, a); + break; + } + + entry = child; + } + + return entry; + } + + void store(final YangInstanceIdentifier id, final ShardRegistration reg) { + final Iterator it = id.getPathArguments().iterator(); + ShardingTableEntry entry = this; + + while (it.hasNext()) { + final PathArgument a = it.next(); + ShardingTableEntry child = entry.children.get(a); + if (child == null) { + child = new ShardingTableEntry(a); + entry.children.put(a, child); + } + } + + Preconditions.checkState(entry.registration == null); + entry.registration = reg; + } + + private boolean remove(final Iterator it) { + if (it.hasNext()) { + final PathArgument arg = it.next(); + final ShardingTableEntry child = children.get(arg); + if (child != null) { + if (child.remove(it)) { + children.remove(arg); + } + } else { + LOG.warn("Cannot remove non-existent child {}", arg); + } + } + + return registration == null && children.isEmpty(); + } + + void remove(final YangInstanceIdentifier id) { + this.remove(id.getPathArguments().iterator()); + } +}