# HG changeset patch # User shoshi # Date 1306910150 -32400 # Node ID 084de69094513ba9206fcf1db168eea3249e75b3 # Parent 019ca5abb1f07bdf8e02b7c32d1199ca4623ae28 commit diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/Forest.java --- a/src/treecms/api/Forest.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/api/Forest.java Wed Jun 01 15:35:50 2011 +0900 @@ -1,60 +1,9 @@ package treecms.api; -import treecms.tree.util.NodeData; - -/** - * ForestはNodeの集合で、集合に対するアクセスを提供します．クライアントはNodeIDを用いてNodeの取得や作成を行うことが出来ます． - * @author shoshi - */ public interface Forest { - /** - * NodeIDで示されるNodeを取得します． - * @param _id Nodeを示すNodeID． - * @return NodeIDと一致するNodeがある場合は，Nodeのインスタンスを返し，見つからない場合はnullを返します． - */ - SingleNode get(NodeID _id); - - /** - * 同じUUIDを持つNode中で最新のNodeを取得します． - * @param _uuid NodeIDのUUID - * @return UUIDと一致するNodeが見つからない場合はnullを返します． - */ - SingleNode getTip(String _uuid); - - /** - * 新しいNodeを作成します．このメソッドで作成されるNodeは新しいUUIDを持ちます． - * @return 新しいNode - */ - SingleNode create(); - - /** - * あるNodeを木として返します - * @param _root - * @return Tree あるNodeをルートとした木 - */ - Tree getTree(SingleNode _root); - - /** - * 木を非破壊的に編集するMonotonicTreeを取得します - * @param _tree 対象 - * @return TreeEditor - */ - MonotonicTree getMonotonicTree(Tree _tree); - - /** - * NodeDataを保持する新しいNodeを作成します．このメソッドで作成されるNodeは新しいUUIDを持ちます． - * このメソッドはNodeDataをNodeに割り当てるとき防御的コピーを行います． - * @param _data 新しいNodeが保持するNodeData - * @return NodeDataを保持した新しいNode - */ - SingleNode create(NodeData _data); - - /** - * このForestの現在の最新のMainTreeを取得します - * @return このForestのMainTree、最新版 - */ - Tree getMainTree(); - - SingleNode create(NodeID _id,NodeData _data); + MonotonicTree get(NodeID _id); + MonotonicTree getTip(String _uuid); + MonotonicTree create(); + MonotonicTree getMainTree(); } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/MonotonicTree.java --- a/src/treecms/api/MonotonicTree.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/api/MonotonicTree.java Wed Jun 01 15:35:50 2011 +0900 @@ -8,36 +8,9 @@ */ public interface MonotonicTree { - /** - * 非破壊的に更新した木構造を適用します． - * 更新する際に他の方法により木構造がすでに更新されていた場合，commitは失敗します。_forceがtrueの場合，強制的に置き換えます． - * @param _force 強制コミットフラグ - * @return 成功した場合true，失敗した場合false - */ public boolean commit(boolean _force); - - /** - * 監視している木構造をEditorにキャッシュします． - * @return キャッシュが成功した場合はtrue，失敗した場合はfalse - */ public boolean pull(); - - /** - * 監視されている木構造が更新されていないかチェックします． - * @return 更新されていた場合はture，されていない場合はfalse - */ public boolean check(); - - /** - * 監視している木構造をキャッシュにマージします． - */ public void merge(); - - /** - * この木構造のルートNodeを返します。 - * @return この木構造のルートNode - */ public MonotonicTreeNode getRoot(); - - public Tree getTree(); } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/MonotonicTreeNode.java --- a/src/treecms/api/MonotonicTreeNode.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/api/MonotonicTreeNode.java Wed Jun 01 15:35:50 2011 +0900 @@ -5,8 +5,7 @@ * TreeNodeとは違い、この実装は木を非破壊的に編集します． * @author shoshi */ -public interface MonotonicTreeNode extends Node +public interface MonotonicTreeNode extends NodeContext , NodeAttributes , NodeChildren { public MonotonicTreeNode getParent(); - public SingleNode getNode(); } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/Node.java --- a/src/treecms/api/Node.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -package treecms.api; - -public interface Node> extends NodeContext , NodeAttributes , NodeChildren -{ -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/NodeChildren.java --- a/src/treecms/api/NodeChildren.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/api/NodeChildren.java Wed Jun 01 15:35:50 2011 +0900 @@ -3,18 +3,22 @@ import java.util.List; import java.util.Set; -public interface NodeChildren> +public interface NodeChildren> { public List getList(); - public Set getUUIDSet(); + public boolean add(T _child); - public boolean addAll(NodeChildren _children); + public boolean addAll(NodeChildren _list); + public Set getFamilyIDSet(); + public T get(String _uuid); public T get(int _index); public T remove(String _uuid); public T remove(int _index); - public T replace(T _newChild); - public boolean contains(String _id); - public boolean swap(String _uuid1,String _uuid2); + public T replace(T _new); + + public boolean contains(NodeID _id); + public boolean swap(String _uuid,String _uuid2); + public void clearChildren(); } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/NodeID.java --- a/src/treecms/api/NodeID.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/api/NodeID.java Wed Jun 01 15:35:50 2011 +0900 @@ -1,30 +1,30 @@ package treecms.api; /** - * Nodeに対応するNodeIDです．NodeIDはUUIDとバージョンから構成されており，同じUUIDを持つNodeIDはファミリーと定義します． - * 木構造で同じUUIDを持つNodeは同一のNodeと判断されます．また，一つの木構造に同じUUIDを持つNodeは存在しません． - * ファイルのバージョン管理と同じようなものと考えてください．その場合，UUIDがファイルのパスで，バージョンがファイルの更新日時です． + * Nodeに対応するNodeIDです．NodeIDはFamilyとVersionから構成されており，同じFamilyを持つNodeIDはファミリーと定義します． + * 木構造で同じFamilyを持つNodeは同一のNodeと判断されます．また，一つの木構造に同じFamilyを持つNodeは存在しません． + * ファイルのバージョン管理と同じようなものと考えてください．その場合，Familyがファイルのパスで，Versionがファイルの更新日時です． * @author shoshi */ public interface NodeID { /** - * 新しいNodeIDを作成します．新しいNodeIDは異なるUUIDを持ちます． - * @return 新しいUUIDを持つNodeID + * 新しいNodeIDを作成します．新しいNodeIDは異なるFamilyを持ちます． + * @return 新しいFamilyを持つNodeID */ public NodeID create(); /** - * このNodeIDが保持するUUIDを継承した，自分とバージョンの異なるNodeIDを生成します． - * @return UUIDを継承した新しいNodeID + * このNodeIDが保持するFamilyを継承した，自分とバージョンの異なるNodeIDを生成します． + * @return Familyを継承した新しいNodeID */ public NodeID update(); /** - * UUIDを取得します． - * @return NodeIDが保持しているUUID + * Familyを取得します． + * @return NodeIDが保持しているFamily */ - public String getUUID(); + public String getFamilyID(); /** * このNodeIDのバージョンを取得します． @@ -33,7 +33,7 @@ public String getVersion(); /** - * このNodeIDが同一なUUIDを保持しているか比較します． + * このNodeIDが同一なFamilyを保持しているか比較します． * @param _id * @return 同一な場合はtrue，異なる場合はfalse */ @@ -41,7 +41,7 @@ /** * このNodeIDの文字列表現を返します． - * このメソッドを実装する際に，文字列の表現方法はUUID＠Versionを採用してください． + * このメソッドを実装する際に，文字列の表現方法はFamily＠Versionを採用してください． * @return */ public String toString(); diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/SingleNode.java --- a/src/treecms/api/SingleNode.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -package treecms.api; - -public interface SingleNode extends Node -{ -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/Tree.java --- a/src/treecms/api/Tree.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,14 +0,0 @@ -package treecms.api; - -/** - * 木構造を表します． - * @author shoshi - */ -public interface Tree -{ - /** - * この木構造のルートNodeを取得します． - * @return ルートNode - */ - TreeNode getRoot(); -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/api/TreeNode.java --- a/src/treecms/api/TreeNode.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ -package treecms.api; - -/** - * DoubleLinkedなNodeの実装です．SingleLinkedなNodeの実装と違い，親の情報を保持します． - * 非破壊的木構造の実装では，Nodeは子どもの情報しか持っていません．これは，一つのNodeに対して複数の親が存在するためです． - * 木構造内のあるNodeへのRootNodeからのパスを検索する手間を省くことが出来ます． - * - * なのでSingleLinkedとDoubleLinkedを分けて，DoubleLinkedはSingleLinkedを内包した形で実装します． - * TreeNodeがNodeのインターフェイスを継承していないのは，継承するとSingleLinkedなNodeに子供として追加できるようになるからです． - * - * また，TreeNodeを編集したときは非破壊的に編集されず、破壊的に編集されます． - * @author shoshi - */ -public interface TreeNode extends Node -{ - public TreeNode getParent(); - public SingleNode getNode(); -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/memory/OnMemoryForest.java --- a/src/treecms/memory/OnMemoryForest.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/memory/OnMemoryForest.java Wed Jun 01 15:35:50 2011 +0900 @@ -5,9 +5,8 @@ import java.util.UUID; import java.util.concurrent.ConcurrentHashMap; import treecms.api.Forest; +import treecms.api.MonotonicTreeNode; import treecms.api.NodeID; -import treecms.api.SingleNode; -import treecms.api.Tree; import treecms.api.MonotonicTree; import treecms.tree.id.AbstractRandomNodeID; import treecms.tree.util.NodeData; @@ -19,12 +18,12 @@ public class OnMemoryForest implements Forest { //Nodeのマップ - Map m_table; + private final Map m_table; //最新版Nodeのマップ - Map m_tipTable; + private final Map m_tipTable; //MainTreeのUUID - String m_mainID; + private final String m_mainID; /** * コンストラクタ @@ -34,7 +33,7 @@ m_table = new ConcurrentHashMap(); m_tipTable = new ConcurrentHashMap(); - m_mainID = createNode(null,null).getID().getUUID(); + m_mainID = createNode(null,null).getID().getFamilyID(); } /** @@ -43,17 +42,17 @@ * @param _newData Nodeが保持するNodeData * @return 作成されたOnMemoryNode */ - public OnMemoryNode createNode(NodeID _id,NodeData _newData) + public OnMemoryNode createNode(NodeID _id,NodeData _newData) { NodeID newID = (_id != null) ? _id : createID(); - NodeData newData = (_newData != null) ? _newData : new NodeData(); + NodeData newData = (_newData != null) ? _newData : new NodeData(); //newIDとnewDataを元にOnMemoryNodeを生成する． OnMemoryNode newNode = new OnMemoryNode(this,newID,newData); //登録 m_table.put(newID,newNode); - m_tipTable.put(newID.getUUID(),newNode); + m_tipTable.put(newID.getFamilyID(),newNode); return newNode; } @@ -72,49 +71,17 @@ * @return NodeIDに対応するNode */ @Override - public SingleNode get(NodeID _id) + public MonotonicTree get(NodeID _id) { return m_table.get(_id); } /** - * あるNodeをルートとしてTreeのオブジェクトを取得します。 - * @param _id 木のルートとなるNodeのNodeID - * @return Tree - */ - @Override - public Tree getTree(SingleNode _node) - { - Forest forest = _node.getForest(); - if(forest != this){ - throw new IllegalArgumentException(); - } - - return new OnMemoryTree((OnMemoryNode)_node); - } - - /** - * あるNodeをルートとしたTreeを非破壊的に編集するTreeEditorを取得します。 - * @param _id 木のルートとなるNodeのNodeID - * @return TreeEditor - */ - @Override - public MonotonicTree getMonotonicTree(Tree _tree) - { - Forest forest = _tree.getRoot().getForest(); - if(forest != this || !(_tree instanceof OnMemoryTree)){ - throw new IllegalArgumentException(); - } - - return new OnMemoryMonotonicTree((OnMemoryTree)_tree); - } - - /** * 新しくNodeを作成します． * @return 新しいNode */ @Override - public SingleNode create() + public MonotonicTree create() { return createNode(null,null); } @@ -144,7 +111,7 @@ * @return このForestのMainTree */ @Override - public Tree getMainTree() + public MonotonicTree getMainTree() { return new OnMemoryTree(m_tipTable.get(m_mainID)); } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/memory/OnMemoryMonotonicTreeNode.java --- a/src/treecms/memory/OnMemoryMonotonicTreeNode.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/memory/OnMemoryMonotonicTreeNode.java Wed Jun 01 15:35:50 2011 +0900 @@ -6,12 +6,14 @@ import java.util.List; import java.util.Map; import java.util.Set; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; + import treecms.api.Forest; import treecms.api.MonotonicTreeNode; import treecms.api.NodeAttributes; import treecms.api.NodeChildren; import treecms.api.NodeID; -import treecms.api.SingleNode; import treecms.tree.util.NodeChildrenImpl; import treecms.tree.util.NodeData; @@ -22,18 +24,19 @@ public class OnMemoryMonotonicTreeNode implements MonotonicTreeNode { private OnMemoryNode m_node; + + private static final AtomicReferenceFieldUpdater m_parentUpdater + = AtomicReferenceFieldUpdater.newUpdater(OnMemoryMonotonicTreeNode.class,OnMemoryMonotonicTreeNode.class,"m_parent"); + private OnMemoryMonotonicTreeNode m_parent; - /** - * コンストラクタです． - * @param _target 対象となるSingleLinked Node - * @param _parent このDoubleLinked Nodeの親，RootNodeならnull - * @param _tree このNodeがRootNodeなら，nullではいけない． - */ + private final Map m_cache; + public OnMemoryMonotonicTreeNode(OnMemoryNode _target,OnMemoryMonotonicTreeNode _parent) { m_node = _target; m_parent = _parent; + m_cache = new ConcurrentHashMap(); } @Override @@ -53,16 +56,6 @@ { return m_parent; } - - @Override - public SingleNode getNode() - { - return m_node; - } - - /* - * 属性関連のメソッド - */ @Override public ByteBuffer get(ByteBuffer _key) @@ -77,51 +70,51 @@ } @Override - public void put(ByteBuffer _key, ByteBuffer _value) + public synchronized void put(ByteBuffer _key, ByteBuffer _value) { - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); d.put(_key,_value); cloneAndTransmit(d); } @Override - public void putAll(NodeAttributes _map) + public synchronized void putAll(NodeAttributes _map) { - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); d.putAll(_map); cloneAndTransmit(d); } @Override - public void remove(ByteBuffer _key) + public synchronized void remove(ByteBuffer _key) { - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); d.remove(_key); cloneAndTransmit(d); } @Override - public void removeAll(Set _keys) + public synchronized void removeAll(Set _keys) { - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); d.removeAll(_keys); cloneAndTransmit(d); } @Override - public void clearAttributes() + public synchronized void clearAttributes() { - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); d.clearAttributes(); cloneAndTransmit(d); } - public void cloneAndTransmit(NodeData _d) + public synchronized void cloneAndTransmit(NodeData _d) { OnMemoryForest f = (OnMemoryForest)m_node.getForest(); OnMemoryNode clone = f.createNode(m_node.getID().update(),_d); @@ -140,7 +133,7 @@ * _fromがnullの場合は，自身が編集元であることを示します． * @param _from 編集元のOnMemoryMonotonicTreeNode */ - public void transmit(OnMemoryNode _orig,OnMemoryNode _edit) + public synchronized void transmit(OnMemoryNode _orig,OnMemoryNode _edit) { OnMemoryForest f = (OnMemoryForest)m_node.getForest(); OnMemoryNode clone = f.createNode(m_node.getID().update(),null); @@ -152,27 +145,39 @@ } } - /* - * 子供関連のメソッド - */ + private synchronized OnMemoryMonotonicTreeNode getCache(OnMemoryNode _node) + { + NodeID id = _node.getID(); + OnMemoryMonotonicTreeNode mono; + synchronized(m_cache){ + mono = m_cache.get(id); + if(mono == null){ + //cache not found . create it + mono = new OnMemoryMonotonicTreeNode(_node,this); + } + } + return mono; + } + @Override - public List getList() + public synchronized List getList() { //NodeのリストよりMonotonicTreeNodeのリストを作成する． NodeChildren res = new NodeChildrenImpl(); - for(Iterator it = m_node.getList().iterator();it.hasNext();){ + for(Iterator it = m_node.getList().iterator();it.hasNext();){ OnMemoryNode n = (OnMemoryNode)it.next(); - res.add(new OnMemoryMonotonicTreeNode(n,this)); + res.add(getCache(n)); } return res.getList(); } @Override - public boolean add(MonotonicTreeNode _n) + public synchronized boolean add(MonotonicTreeNode _n) { - NodeData d = new NodeData(m_node); - boolean ret = d.add(_n.getNode()); + OnMemoryMonotonicTreeNode mono = (OnMemoryMonotonicTreeNode)_n; + NodeData d = new NodeData(m_node); + boolean ret = d.add(mono.m_node); if(ret){ cloneAndTransmit(d); } @@ -181,16 +186,16 @@ } @Override - public boolean addAll(NodeChildren _list) + public synchronized boolean addAll(NodeChildren _list) { //MotonicTreeNodeのリストからNodeのリストを作成する． - NodeChildren c = new NodeChildrenImpl(); + NodeChildren c = new NodeChildrenImpl(); for(Iterator it = _list.getList().iterator();it.hasNext();){ - MonotonicTreeNode mono = (MonotonicTreeNode)it.next(); - c.add(mono.getNode()); + OnMemoryMonotonicTreeNode mono = (OnMemoryMonotonicTreeNode)it.next(); + c.add(mono.m_node); } - NodeData d = new NodeData(m_node); + NodeData d = new NodeData(m_node); boolean ret = d.addAll(c); if(ret){ cloneAndTransmit(d); @@ -200,10 +205,10 @@ } @Override - public MonotonicTreeNode remove(String _uuid) + public synchronized MonotonicTreeNode remove(int _index) { - NodeData d = new NodeData(m_node); - SingleNode n = d.remove(_uuid); + NodeData d = new NodeData(m_node); + OnMemoryNode n = d.remove(_index); if(n != null){ cloneAndTransmit(d); return new OnMemoryMonotonicTreeNode((OnMemoryNode)n,null); @@ -213,23 +218,11 @@ } @Override - public MonotonicTreeNode remove(int _index) + public synchronized void clearChildren() { - NodeData d = new NodeData(m_node); - SingleNode n = d.remove(_index); - if(n != null){ - cloneAndTransmit(d); - return new OnMemoryMonotonicTreeNode((OnMemoryNode)n,null); - } + NodeData d = new NodeData(m_node); + d.clearChildren(); - return null; - } - - @Override - public void clearChildren() - { - NodeData d = new NodeData(m_node); - d.clearChildren(); cloneAndTransmit(d); } @@ -246,47 +239,62 @@ } @Override - public Set getUUIDSet() + public synchronized MonotonicTreeNode get(int _index) { - return m_node.getUUIDSet(); - } - - @Override - public MonotonicTreeNode get(String _uuid) - { - SingleNode n = m_node.get(_uuid); - return new OnMemoryMonotonicTreeNode((OnMemoryNode)n,this); + OnMemoryNode n = m_node.get(_index); + return getCache(n); } @Override - public MonotonicTreeNode get(int _index) + public synchronized MonotonicTreeNode replace(MonotonicTreeNode _newChild) { - SingleNode n = m_node.get(_index); - return new OnMemoryMonotonicTreeNode((OnMemoryNode)n,this); - } - - @Override - public MonotonicTreeNode replace(MonotonicTreeNode _newChild) - { - NodeData d = new NodeData(m_node); - SingleNode n = d.replace(_newChild.getNode()); + OnMemoryMonotonicTreeNode mono = (OnMemoryMonotonicTreeNode)_newChild; + NodeData d = new NodeData(m_node); + OnMemoryNode n = d.replace(mono.m_node); + if(n != null){ cloneAndTransmit(d); - return new OnMemoryMonotonicTreeNode((OnMemoryNode)n,(OnMemoryMonotonicTreeNode)null); + return new OnMemoryMonotonicTreeNode(n,null); } return null; } @Override - public boolean contains(String _id) + public boolean contains(NodeID _id) { return m_node.contains(_id); } @Override - public boolean swap(String _uuid1, String _uuid2) + public boolean swap(String _fid1,String _fid2) + { + return m_node.swap(_fid1,_fid2); + } + + @Override + public Set getFamilyIDSet() + { + return m_node.getFamilyIDSet(); + } + + @Override + public synchronized MonotonicTreeNode get(String _fid) { - return m_node.swap(_uuid1,_uuid2); + OnMemoryNode n = m_node.get(_fid); + OnMemoryMonotonicTreeNode mono = getCache(n); + + return mono; + } + + @Override + public synchronized MonotonicTreeNode remove(String _fid) + { + NodeData d = new NodeData(m_node); + OnMemoryNode n = d.remove(_fid); + + cloneAndTransmit(d); + + return new OnMemoryMonotonicTreeNode(n,null); } } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/memory/OnMemoryNode.java --- a/src/treecms/memory/OnMemoryNode.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,41 +0,0 @@ -package treecms.memory; - -import treecms.api.Forest; -import treecms.api.NodeID; -import treecms.api.SingleNode; -import treecms.tree.util.NodeData; - -/** - * オンメモリ上でのNodeの実装です。 - * @author shoshi - */ -class OnMemoryNode extends NodeData implements SingleNode -{ - private OnMemoryForest m_forest; - private NodeID m_id; - - /** - * コンストラクタ - * @param _forest このNodeが属するForestです． - * @param _id このNodeのNodeIDです． - * @param _newData このNodeに割り当てるNodeDataです．防御的にコピーします． - */ - public OnMemoryNode(OnMemoryForest _forest,NodeID _id,NodeData _newData) - { - super(_newData); - m_id = _id; - m_forest = _forest; - } - - @Override - public NodeID getID() - { - return m_id; - } - - @Override - public Forest getForest() - { - return m_forest; - } -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/memory/OnMemoryTree.java --- a/src/treecms/memory/OnMemoryTree.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,51 +0,0 @@ -package treecms.memory; - -import java.util.concurrent.atomic.AtomicReferenceFieldUpdater; -import treecms.api.Tree; -import treecms.api.TreeNode; - -/** - * オンメモリのTree実装です。 - * 木構造のルートとなるNodeをメンバーとして持ち、操作はすべて転送します。 - * @author shoshi - */ -public class OnMemoryTree implements Tree -{ - private static final AtomicReferenceFieldUpdater m_refUpdater = AtomicReferenceFieldUpdater.newUpdater(OnMemoryTree.class,OnMemoryNode.class,"m_root"); - private volatile OnMemoryNode m_root; - - /** - * コンストラクタです。 - * @param _newRoot 木構造のルートノードです。 - */ - public OnMemoryTree(OnMemoryNode _newRoot) - { - m_root = _newRoot; - } - - /** - * この木構造のルートNodeを取得します． - * @return ルートNode - */ - @Override - public TreeNode getRoot() - { - return new OnMemoryTreeNode(m_root,null); - } - - /** - * ルートNodeを比較して置き換えます． - * @param _except 比較する対象 - * @param _newRoot 一致した場合置き換える対象 - */ - public boolean compareAndSwapRootNode(OnMemoryNode _expect,OnMemoryNode _newRoot,boolean _force) - { - if(_force){ - m_root = _newRoot; - } - - m_refUpdater.compareAndSet(this,_expect,_newRoot); - return true; - } - -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/memory/OnMemoryTreeNode.java --- a/src/treecms/memory/OnMemoryTreeNode.java Tue May 31 15:55:28 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,225 +0,0 @@ -package treecms.memory; - -import java.nio.ByteBuffer; -import java.util.Collections; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.Map; -import java.util.Set; -import treecms.api.Forest; -import treecms.api.NodeAttributes; -import treecms.api.NodeChildren; -import treecms.api.NodeID; -import treecms.api.SingleNode; -import treecms.api.TreeNode; -import treecms.tree.util.NodeChildrenImpl; - -/** - * DoubleLinkedなNodeであるTreeNodeのOnMemory実装です． - * @author shoshi - */ -public class OnMemoryTreeNode implements TreeNode -{ - public OnMemoryTreeNode m_parent; - public OnMemoryNode m_node; - - /** - * コンストラクタです． - * @param _node 対象となるSingleLinkedなNode - * @param _parent 親のOnMemoryTreeNode - */ - public OnMemoryTreeNode(OnMemoryNode _node,OnMemoryTreeNode _parent) - { - //とりあえず、チェック - if(_node == null){ - throw new NullPointerException(); - } - - m_node = _node; - - //このノードがルートの場合、親はnullで構わない． - m_parent = _parent; - } - - /* - * 親関連のメソッド - */ - - @Override - public NodeID getID() - { - return m_node.getID(); - } - - @Override - public SingleNode getNode() - { - return m_node; - } - - @Override - public TreeNode getParent() - { - return m_parent; - } - - @Override - public Forest getForest() - { - return m_node.getForest(); - } - - /* - * 子供関連のメソッド - */ - - @Override - public List getList() - { - /* - * m_node（対象ノード）のリストにはNodeが格納されており、TreeNodeのリストを取得するためにはTreeNodeで要素を構成する必要がある． - */ - LinkedList ret = new LinkedList(); - for(Iterator it = m_node.getList().iterator();it.hasNext();){ - OnMemoryNode n = (OnMemoryNode)it.next(); - ret.add(new OnMemoryTreeNode(n,this)); - } - - return Collections.unmodifiableList(ret); - } - - @Override - public boolean add(TreeNode _child) - { - return m_node.add(_child.getNode()); - } - - @Override - public boolean addAll(NodeChildren _children) - { - /* - * TreeNodeのリストからNodeのリストへ変換する - */ - NodeChildren res = new NodeChildrenImpl(); - for(Iterator it = _children.getList().iterator();it.hasNext();){ - TreeNode tn = it.next(); - res.add(tn.getNode()); - } - - return m_node.addAll(res); - } - - @Override - public TreeNode remove(String _uuid) - { - SingleNode n = m_node.remove(_uuid); - return new OnMemoryTreeNode((OnMemoryNode)n,this); - } - - @Override - public TreeNode remove(int _index) - { - SingleNode n = m_node.remove(_index); - return new OnMemoryTreeNode((OnMemoryNode)n,this); - } - - @Override - public void clearChildren() - { - m_node.clearChildren(); - } - - @Override - public ByteBuffer get(ByteBuffer _key) - { - return m_node.get(_key); - } - - @Override - public NodeAttributes getAll() - { - return m_node.getAll(); - } - - @Override - public void put(ByteBuffer _key,ByteBuffer _value) - { - m_node.put(_key,_value); - } - - @Override - public void putAll(NodeAttributes _map) - { - m_node.putAll(_map); - } - - @Override - public void remove(ByteBuffer _key) - { - m_node.remove(_key); - } - - @Override - public void removeAll(Set _keySet) - { - m_node.removeAll(_keySet); - } - - @Override - public void clearAttributes() - { - m_node.clearAttributes(); - } - - @Override - public Map asMap() - { - return m_node.asMap(); - } - - @Override - public Set getKeySet() - { - return m_node.getKeySet(); - } - - @Override - public Set getUUIDSet() - { - return m_node.getUUIDSet(); - } - - @Override - public TreeNode get(String _uuid) - { - SingleNode n = m_node.get(_uuid); - return new OnMemoryTreeNode((OnMemoryNode)n,this); - } - - @Override - public TreeNode get(int _index) - { - SingleNode n = m_node.get(_index); - return new OnMemoryTreeNode((OnMemoryNode)n,this); - } - - @Override - public TreeNode replace(TreeNode _newChild) - { - SingleNode n = m_node.replace(_newChild.getNode()); - return new OnMemoryTreeNode((OnMemoryNode)n,this); - } - - @Override - public boolean contains(String _id) - { - return m_node.contains(_id); - } - - @Override - public boolean swap(String _uuid1, String _uuid2) - { - return m_node.swap(_uuid1,_uuid2); - } -} diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/tree/id/AbstractRandomNodeID.java --- a/src/treecms/tree/id/AbstractRandomNodeID.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/tree/id/AbstractRandomNodeID.java Wed Jun 01 15:35:50 2011 +0900 @@ -5,12 +5,12 @@ public abstract class AbstractRandomNodeID extends AbstractNodeID { public abstract NodeID create(); - public abstract String getUUID(); + public abstract String getFamilyID(); public abstract String getVersion(); public abstract NodeID update(); public boolean isFamily(NodeID _id) { - return (_id instanceof AbstractNodeID) ? getUUID().equals(_id.getUUID()) : false; + return (_id instanceof AbstractNodeID) ? getFamilyID().equals(_id.getFamilyID()) : false; } } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/tree/util/NodeAttributesImpl.java --- a/src/treecms/tree/util/NodeAttributesImpl.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/tree/util/NodeAttributesImpl.java Wed Jun 01 15:35:50 2011 +0900 @@ -2,10 +2,9 @@ import java.nio.ByteBuffer; import java.util.Collections; -import java.util.HashMap; import java.util.Map; import java.util.Set; - +import java.util.concurrent.ConcurrentHashMap; import treecms.api.NodeAttributes; public class NodeAttributesImpl implements NodeAttributes @@ -14,7 +13,7 @@ public NodeAttributesImpl() { - m_attrs = new HashMap(); + m_attrs = new ConcurrentHashMap(); } public NodeAttributesImpl(Map _map) diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/tree/util/NodeChildrenImpl.java --- a/src/treecms/tree/util/NodeChildrenImpl.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/tree/util/NodeChildrenImpl.java Wed Jun 01 15:35:50 2011 +0900 @@ -1,35 +1,37 @@ package treecms.tree.util; -import java.util.ArrayList; import java.util.Collections; -import java.util.HashSet; +import java.util.HashMap; +import java.util.List; +import java.util.Map; import java.util.Set; -import java.util.List; -import treecms.api.Node; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.CopyOnWriteArrayList; import treecms.api.NodeChildren; +import treecms.api.NodeContext; +import treecms.api.NodeID; -/** - * 子供ノードを格納するため専用のリストです．java.util.Listは継承しておりません． - * 子供ノードのリストには　リスト内に同じUUIDを持つNodeが存在　してはいけません． - * @author shoshi - */ -public class NodeChildrenImpl> implements NodeChildren +public class NodeChildrenImpl> implements NodeChildren { - private List m_list; - private Set m_set; + private final Map m_map; + private final List m_list; + private final List m_readOnlyList; public NodeChildrenImpl() { - m_list = new ArrayList(); - m_set = new HashSet(); + m_map = new ConcurrentHashMap(); + m_list = new CopyOnWriteArrayList(); + m_readOnlyList = Collections.unmodifiableList(m_list); } public NodeChildrenImpl(T... _args) { this(); for(T i : _args){ - if(!add(i)){ - throw new IllegalArgumentException("duplicate Node UUID at "+i.getID().getUUID()); + String fid = i.getID().getFamilyID(); + if(!m_map.containsKey(fid)){ + m_map.put(fid,i); + m_list.add(i); } } } @@ -40,197 +42,160 @@ if(_list != null){ addAll(_list); + }else{ + throw new NullPointerException("_list is null"); } } - public List getList() + @Override + public synchronized List getList() { - return Collections.unmodifiableList(m_list); - } - - public Set getUUIDSet() - { - return Collections.unmodifiableSet(m_set); + return m_readOnlyList; } @Override - public T replace(T _newChild) + public synchronized T replace(T _node) { - String uuid = _newChild.getID().getUUID(); - int size = m_list.size(); - for(int i = 0;i < size;i ++){ - T n = m_list.get(i); - if(uuid.equals(n.getID().getUUID())){ - //_newChildと同一なUUIDを見つけた - return m_list.set(i,_newChild); + String fid = _node.getID().getFamilyID(); + + T old = m_map.get(fid); + + if(old != null){ + m_map.put(fid,_node); + + //find index of _node , better put index with node in the map? + int size = m_list.size(); + for(int i = 0;i < size;i ++){ + T n = m_list.get(i); + NodeID nid = n.getID(); + if(nid.isFamily(nid)){ + m_list.set(i,_node); + return old; + } } + + throw new IllegalStateException("FamilyID is found on the map but not found on the list"); } - //見つからなかった return null; } - /** - * このリストに新しく子供を追加します． - * @param _n - * @return 追加に成功した場合true - */ - public boolean add(T _n) + @Override + public synchronized boolean add(T _n) { - if(m_set.contains(_n.getID().getUUID())){ - return false; - } - - m_set.add(_n.getID().getUUID()); - m_list.add(_n); - return true; - } - - /** - * _listに含まれている子供がすべてこのリストに含まれない場合にのみ、要素をすべて追加します。 - * @param _list - * @return 追加に成功した場合true - */ - public boolean addAll(NodeChildren _list) - { - if(Collections.disjoint(m_set,_list.getUUIDSet())){ - //共通要素がない - m_set.addAll(_list.getUUIDSet()); - m_list.addAll(_list.getList()); - return true; + if(!m_map.containsKey(_n.getID().getFamilyID())){ + m_map.put(_n.getID().getFamilyID(),_n); + return m_list.add(_n); } return false; } - /** - * 指定されたNodeID - * @param _id - * @return 子供ノード - */ - public T get(String _uuid) + @Override + public synchronized boolean addAll(NodeChildren _list) { - for(T n : m_list){ - String uuid = n.getID().getUUID(); - if(uuid.equals(_uuid)){ - return n; + if(Collections.disjoint(getFamilyIDSet(),_list.getFamilyIDSet())){ + + HashMap map = new HashMap(); + for(T item : _list.getList()){ + NodeID id = item.getID(); + map.put(id.getFamilyID(),item); } + + return m_list.addAll(_list.getList()); } - - return null; + return false; } - /** - * 指定された_indexの場所に位置する子供を削除します - * @param _index - * @return 消される子供ノード - */ - public T get(int _index) + @Override + public synchronized T get(int _index) { return m_list.get(_index); } - /** - * 指定されたUUIDを持つ子どもを削除します - * @param _id - * @return 削除される子供ノード - */ - public T remove(String _uuid) + @Override + public synchronized T get(String _familyID) { - int size = m_list.size(); - - for(int i = 0;i < size;i ++){ - String uuid = m_list.get(i).getID().getUUID(); - if(uuid.equals(_uuid)){ - //NodeIDのUUIDが一致した - return m_list.remove(i); - } - } - - return null; - } - - /** - * 指定された場所の子供ノードを削除します - * @param _index - * @return 削除された子供ノード - */ - public T remove(int _index) - { - return m_list.remove(_index); - } - - /** - * このリストに指定されたUUIDを持つNodeがあるか確認します - * @param _id - * @return 存在する場合true - */ - public boolean contains(String _uuid) - { - return m_set.contains(_uuid); + return m_map.get(_familyID); } - /** - * 指定された二つのUUID(_uuid1,_uuid2)がリスト上に存在する場合、その二つの順番を入れ替えます - * @param _uuid1 String - * @param _uuid2 String - * @return 成功した場合はtrue,NodeIDが見つからなかった場合はfalse - */ - public boolean swap(String _uuid1,String _uuid2) + @Override + public synchronized T remove(int _index) { - /* - * 二つのNodeIDの位置を求める - */ - int index1 = -1; - int index2 = -1; - - int size = m_list.size(); - for(int i = 0;i < size && (index1 == -1 || index2 == 1);i ++){ - String uuid = m_list.get(i).getID().getUUID(); - if(uuid.equals(_uuid1)){ - index1 = i; - continue; - } - - if(uuid.equals(_uuid2)){ - index2 = i; - continue; - } + T n = m_list.remove(_index); + NodeID id = n.getID(); + if(m_map.remove(id.getFamilyID()) != null){ + return n; } - /* - * Collection.swapを使って入れ替える - */ - if(index1 != -1 && index2 != -1){ - Collections.swap(m_list,index1,index2); - return true; - } - - //NodeIDがリスト上になかった - return false; + throw new IllegalStateException(""); } - /** - * 子供ノードのリストをクリアします - */ - public void clearChildren() + @Override + public synchronized boolean contains(NodeID _id) { - m_set.clear(); + T n = m_map.get(_id); + NodeID id = n.getID(); + return id.equals(_id); + } + + @Override + public synchronized void clearChildren() + { + m_map.clear(); m_list.clear(); } @SuppressWarnings("unchecked") @Override - public boolean equals(Object _o) + public synchronized boolean equals(Object _o) { NodeChildrenImpl list = (NodeChildrenImpl)_o; return m_list.equals(list.m_list); } @Override - public int hashCode() + public synchronized int hashCode() { int result = 17; result = 37*result + m_list.hashCode(); - result = 37*result + m_set.hashCode(); + result = 37*result + m_map.hashCode(); return result; } + + @Override + public synchronized Set getFamilyIDSet() + { + return m_map.keySet(); + } + + @Override + public synchronized T remove(String _fid) + { + return m_map.remove(_fid); + } + + @Override + public synchronized boolean swap(String _fid1, String _fid2) + { + if(m_map.containsKey(_fid1) && m_map.containsKey(_fid2)){ + int index1,index2; + index1 = index2 = -1; + int size = m_list.size(); + for(int i = 0;i < size;i ++){ + T n = m_list.get(i); + String fid = n.getID().getFamilyID(); + + if(fid.equals(_fid1)){ + index1 = i; + }else if(fid.equals(_fid2)){ + index2 = i; + } + + if(index1 != -1 && index2 != -1){ + Collections.swap(m_list, index1, index2); + return true; + } + } + } + return false; + } } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/tree/util/NodeData.java --- a/src/treecms/tree/util/NodeData.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/tree/util/NodeData.java Wed Jun 01 15:35:50 2011 +0900 @@ -4,24 +4,15 @@ import java.util.List; import java.util.Map; import java.util.Set; - -import treecms.api.Node; import treecms.api.NodeAttributes; import treecms.api.NodeChildren; +import treecms.api.NodeContext; +import treecms.api.NodeID; -/** - * Node が保持するデータのスナップショットです．Node を大きく変更するときや新しく作成される場合に使用されます． - * 通常このクラスのインスタンスを Node から取得した場合，NodeData インスタンスに変更（set,add）を加えても元の Node に変更は反映されません． - * その様に実装してください． - * - * このクラスは Node が保持するデータのうち　子供ノードのリスト・属性のマップ　のみ保持しています．つまり，ノードが持っているはずの ID は保持していません． - * getID,getForest を呼び出すと UnsupportedOperationException をスローします． - * @author shoshi - */ -public class NodeData> implements NodeAttributes , NodeChildren +public class NodeData> implements NodeAttributes , NodeChildren { - private NodeChildrenImpl m_children; - private NodeAttributesImpl m_attrs; + private final NodeChildrenImpl m_children; + private final NodeAttributesImpl m_attrs; public NodeData() { @@ -46,12 +37,6 @@ } @Override - public Set getUUIDSet() - { - return m_children.getUUIDSet(); - } - - @Override public boolean add(T _child) { return m_children.add(_child); @@ -64,48 +49,30 @@ } @Override - public T get(String _uuid) - { - return m_children.get(_uuid); - } - - @Override public T get(int _index) { return m_children.get(_index); } @Override - public T remove(String _uuid) + public T remove(int _uuid) { return m_children.remove(_uuid); } @Override - public T remove(int _index) - { - return m_children.remove(_index); - } - - @Override public T replace(T _newChild) { return m_children.replace(_newChild); } @Override - public boolean contains(String _id) + public boolean contains(NodeID _id) { return m_children.contains(_id); } @Override - public boolean swap(String _uuid1, String _uuid2) - { - return m_children.swap(_uuid1, _uuid2); - } - - @Override public void clearChildren() { m_children.clearChildren(); @@ -164,4 +131,28 @@ { m_attrs.clearAttributes(); } + + @Override + public Set getFamilyIDSet() + { + return m_children.getFamilyIDSet(); + } + + @Override + public T get(String _familyID) + { + return m_children.get(_familyID); + } + + @Override + public T remove(String _familyID) + { + return m_children.get(_familyID); + } + + @Override + public boolean swap(String _fid1, String _fid2) + { + return m_children.swap(_fid1,_fid2); + } } diff -r 019ca5abb1f0 -r 084de6909451 src/treecms/tree/util/NodeFinder.java --- a/src/treecms/tree/util/NodeFinder.java Tue May 31 15:55:28 2011 +0900 +++ b/src/treecms/tree/util/NodeFinder.java Wed Jun 01 15:35:50 2011 +0900 @@ -1,9 +1,10 @@ package treecms.tree.util; -import treecms.api.Node; +import treecms.api.NodeChildren; +import treecms.api.NodeContext; import treecms.api.NodeID; -public class NodeFinder> +public class NodeFinder> { private T m_root; public NodeFinder(T _root) @@ -18,7 +19,7 @@ @Override public boolean evaluate(T _target) { - if(_target.getID().getUUID().equals(_uuid)){ + if(_target.getID().getFamilyID().equals(_uuid)){ m_res = _target; return true; }