IndexBranchNode


1   // You can redistribute this software and/or modify it under the terms of
2   // the Ozone Core License version 1 published by ozone-db.org.
3   //
4   // Copyright (C) 2003-@year@, Leo Mekenkamp. All rights reserved.
5   //
6   // $Id: IndexBranchNode.java,v 1.4 2004/02/01 20:55:47 leomekenkamp Exp $
7   
8   package org.ozoneDB.core.storage.gammaStore;
9   
10  import java.io.IOException  ;
11  import java.io.ObjectInputStream  ;
12  import java.io.ObjectOutputStream  ;
13  import java.util.Iterator  ;
14  import java.util.NoSuchElementException  ;
15  import java.util.SortedMap  ;
16  import java.util.TreeMap  ;
17  import java.util.logging.Level  ;
18  import org.ozoneDB.ObjectNotFoundException;
19  import org.ozoneDB.OzoneInternalException;
20  
21  /**
22   * @author <a HREF="mailto:leoATmekenkampD0Tcom">Leo Mekenkamp (mind the anti sp@m)</a>
23   * @version $Id: IndexBranchNode.java,v 1.4 2004/02/01 20:55:47 leomekenkamp Exp $
24   */
25  final class IndexBranchNode extends IndexNode {
26      
27      private static final long serialVersionUID = 0L;
28  
29      // key: long minimum object id; value: long node id
30      private NodeIdLoc nodeIdLoc;
31      
32      /**
33       * Creates a branch node; created node places itself in the index managers
34       * cache, but is not yet connected to any other nodes.
35       */
36      IndexBranchNode(IndexManager indexManager) {
37          super(indexManager);
38          setMaxSize(indexManager.getMaxBranchNodeSize());
39          nodeIdLoc = new NodeIdLoc(getMaxSize(), 0);
40          setIndexManager(indexManager);
41      }
42   
43      // private so it can be inlined
44      private NodeIdLoc getNodeIdLoc() {
45          return nodeIdLoc;
46      }
47      
48      /**
49       * Returns the id of a child node of this node, containing the specified
50       * object id. If the specified object id does not exist in any child node,
51       * this method returns the most appropriate child node.
52       */
53      long getChildNodeId(long objectId) {
54          int pos = getNodeIdLoc().getKeyPosOrNearestSmaller(objectId);
55          if (pos < 0) {
56              pos = getNodeIdLoc().getKeyPosOrNearestGreater(objectId);
57              if (pos < 0) {
58                  throw new OzoneInternalException("BUG: no smaller AND no greater for " + objectId);
59              }
60          }
61          return getNodeIdLoc().getNodeId(pos);
62      }
63  
64      /**
65       * Adds a child node in this node. Does not do any merging or
66       * splitting, but does inform parent if changed because of this action.
67       *
68       * @throws IndexOutOfBoundsException maximum size has already been reached
69       */
70      private void rawPutChildNode(IndexNode childNode) {
71          // compiler tells us we must initialize; not very smart compiler
72          long oldMinObjectId = LONGNULL;
73          if (getParentNodeId() != LONGNULL) {
74              oldMinObjectId = getMinObjectId();
75          }
76  
77          int pos = getNodeIdLoc().putKey(childNode.getMinObjectId());
78          getNodeIdLoc().putNodeId(pos, childNode.getNodeId());
79          childNode.setParentNode(this);
80          setDirty();
81  
82          if (getParentNodeId() != LONGNULL && getMinObjectId() != oldMinObjectId) {
83              IndexBranchNode p = getParentNode();
84              p.childMinObjectIdChanged(this, oldMinObjectId);
85              p.endInvoke();
86          }
87      }
88  
89      void putChildNode(IndexNode childNode) {
90  //if (childNode.getNodeId() == 2 || childNode.getMinObjectId() < -1000000) {
91  //    log.severe("putting " + childNode.getNodeId() + " into " + this);
92  //}
93          if (log.isLoggable(Level.FINE)) log.fine("putting " + childNode.getNodeId() + " on key " + childNode.getMinObjectId() + " in " + getNodeId());
94          if (!isFull()) {
95              
96              rawPutChildNode(childNode);
97          } else {
98              if (log.isLoggable(Level.FINER)) log.fine(getNodeId() + " is full");
99              if (getParentNodeId() == LONGNULL) {
100 
101                 // we are the root and we are full; it is time to create a
102                 // new root and make it our parent
103                 IndexBranchNode newRoot = new IndexBranchNode(getIndexManager());
104                 newRoot.putChildNode(this);
105                 getIndexManager().setRootNode(newRoot);
106                 newRoot.endInvoke();
107 
108                 // after we have created a new root we can now simply split
109             }
110             split(childNode);
111         }
112 //if (childNode.getNodeId() == 2) {
113 //    log.severe("ready putting " + childNode.getNodeId() + " into " + this);
114 //}
115     }
116     
117     /**
118      * Removes a child node from this node. Does not do any merging or
119      * splitting, but does inform parent if changing because of this action.
120      * Also removes itself from the tree if empty after the remove.
121      *
122      */
123     private void rawRemoveChildNode(IndexNode childNode) {
124         int pos = getNodeIdLoc().getKeyPos(childNode.getMinObjectId());
125         if (pos < 0) {
126             throw new OzoneInternalException("no such child node with minObjectId: " + childNode.getMinObjectId());
127         }
128         if (size() == 1) {
129             if (getNextNodeId() != LONGNULL) {
130                 IndexNode n = getNextNode();
131                 n.setPrevNodeId(getPrevNodeId());
132                 n.endInvoke();
133             }
134             
135             if (getPrevNodeId() != LONGNULL) {
136                 IndexNode p = getPrevNode();
137                 p.setNextNodeId(getNextNodeId());
138                 p.endInvoke();
139             }
140             // we only remove ourselves if we are not the root
141             if (getParentNodeId() != LONGNULL) {
142                 IndexBranchNode p = getParentNode();
143                 p.removeChildNode(this);
144                 p.endInvoke();
145                 
146                 // removes us from the index manager cache
147                 setIndexManager(null);
148             }
149         }
150         
151         long oldMinObjectId = getMinObjectId();
152         getNodeIdLoc().removePos(pos);
153         childNode.setParentNode(null);
154         setDirty();
155         
156         if (getParentNodeId() != LONGNULL) {
157             long newMinObjectId = getMinObjectId();
158             if (oldMinObjectId != newMinObjectId) {
159                 IndexBranchNode p = getParentNode();
160                 p.childMinObjectIdChanged(this, oldMinObjectId);
161                 p.endInvoke();
162             }
163         }
164     }
165 
166     /**
167      * @throws OzoneInternalException when given node not found
168      */
169     void removeChildNode(IndexNode childNode) {
170 //if (childNode.getNodeId() == 8) {
171 //    log.severe("removing childNode " + childNode + "\nfrom " + this);
172 //}
173         if (log.isLoggable(Level.FINE)) log.fine("removing on key " + childNode.getMinObjectId() + " from " + getNodeId());
174 
175         rawRemoveChildNode(childNode);
176 
177         // remove ourselves if we have only one child and no siblings, move our
178         // child over to our parent
179         if (size() == 1 && getNextNodeId() == LONGNULL && getPrevNodeId() == LONGNULL) {
180             long moveUpId = getNodeIdLoc().getNodeId(getNodeIdLoc().getMinPos());
181             IndexNode moveUp = getIndexManager().getNode(moveUpId);
182             if (getParentNodeId() == LONGNULL) {
183                 if (moveUp instanceof IndexLeafNode) {
184                     // we do absolutely nothing here, since the indexmanager
185                     // must always have a root node (branch) and (at least) one
186                     // leaf node as its child
187                 } else {
188                     if (log.isLoggable(Level.FINE)) log.fine("root node " + getNodeId() + " has one (branch) child (" + moveUp.getNodeId() + ") and no siblings, so making that new root node");
189                     getIndexManager().setRootNode((IndexBranchNode) moveUp);
190                     removeChildNode(moveUp);
191                     
192                     // removes ourselves from cache and storage
193                     setIndexManager(null);
194                 }
195             } else {
196                 if (log.isLoggable(Level.FINE)) log.fine("branch node " + getNodeId() + " has one child (" + moveUp.getNodeId() + ") and no siblings, so child is taking branchnodes place");
197                 IndexBranchNode p = getParentNode();
198                 
199                 // next statement effectively overwrites 'our' entry in the
200                 // parent, because our minObjId == moveUps minObjId, since
201                 // moveUp is our only child
202                 p.rawPutChildNode(moveUp);
203                 p.endInvoke();
204                 
205                 // removes ourselves from cache and storage
206                 setIndexManager(null);
207             }
208             moveUp.endInvoke();
209         }
210         
211 //if (childNode.getNodeId() == 8) {
212 //    log.severe("ready removing childNode " + childNode + "\nfrom " + this);
213 //}
214     }
215     
216     protected final int size() {
217         return getNodeIdLoc().size();
218     }
219     
220     void childMinObjectIdChanged(IndexNode childNode, long childOldMinObjectId) {
221 //if (getNodeId() == 5) {
222 //    log.severe("child node changed, oldMin: " + childOldMinObjectId + ", child: " + childNode + ", parent: " + this);
223 //}
224         if (log.isLoggable(Level.FINE)) log.fine("child changed, oldId " + childOldMinObjectId + "; node " + childNode + "\nthis: " + this);
225         long oldMinObjectId = getMinObjectId();
226             
227         if (getNodeIdLoc().removeKey(childOldMinObjectId) < 0) {
228             throw new OzoneInternalException("could not find " + childOldMinObjectId + " in " + this + "; child: " + childNode);
229         }
230         int pos = getNodeIdLoc().putKey(childNode.getMinObjectId());
231         getNodeIdLoc().putNodeId(pos, childNode.getNodeId());
232 
233         setDirty();
234         if (getMinObjectId() != oldMinObjectId && getParentNodeId() != LONGNULL) {
235             IndexBranchNode p = getParentNode();
236             p.childMinObjectIdChanged(this, oldMinObjectId);
237             p.endInvoke();
238         }
239     }
240     
241     long getMaxObjectId() {
242         long result;
243         if (size() == 0) {
244             result = MINOBJECTID;
245         } else {
246             result = getNodeIdLoc().getMaxKey();
247         }
248         return result;
249     }
250     
251     long getMinObjectId() {
252         long result;
253         if (size() == 0) {
254             result = MINOBJECTID;
255         } else {
256             result = getNodeIdLoc().getMinKey();
257         }
258         return result;
259     }
260     
261     
262     /**
263      * Splits this instance into two nodes; the specified id is used to find
264      * out which child nodes should remain in this instance, and which
265      * should be put in the other one. Say we have a full node with sub node
266      * ids [10, 20, 30, 40, 50] and we are adding 35, then we would split into
267      * [10, 20, 30] and [40, 50].
268      */
269     private void split(IndexNode indexNode) {
270         if (log.isLoggable(Level.FINE)) log.fine("split around " + indexNode.getMinObjectId() + " for indexBranchNode " + getNodeId());
271 
272         // since we are about to create a new node, we wait a little if the
273         // serializer has too much still to do
274         getIndexManager().checkSerializerSize();
275         IndexBranchNode result = new IndexBranchNode(getIndexManager());
276         if (log.isLoggable(Level.FINE)) log.fine("split created " + result.getNodeId());
277         
278         // Must test if new node is not full, because the maximum size may
279         // change at runtime. If we don't, the new node may split itself also,
280         // and since the new node does not know its parent yet we will then have
281         // a problem...
282         while (!result.isFull(1) && size() > 1) {
283             int pos = getNodeIdLoc().getMaxPos();
284             if (getNodeIdLoc().getKey(pos) < indexNode.getMaxObjectId()) {
285                 break;
286             }
287             long childNodeId = getNodeIdLoc().getNodeId(pos);
288             IndexNode childNode = getIndexManager().getNode(childNodeId);
289             rawRemoveChildNode(childNode);
290             result.rawPutChildNode(childNode);
291             childNode.endInvoke();
292         }
293         
294         if (indexNode.getMaxObjectId() > getNodeIdLoc().getMaxKey()) {
295             result.putChildNode(indexNode);
296         } else {
297             rawPutChildNode(indexNode);
298         }
299         
300         // make new node known to our peers
301         result.setPrevNode(this);
302         if (getNextNodeId() != LONGNULL) {
303             result.setNextNodeId(getNextNodeId());
304             IndexNode n = getNextNode();
305             n.setPrevNode(result);
306             n.endInvoke();
307         }
308         setNextNode(result);
309         
310         // make new node known to our parent
311         IndexBranchNode p = getParentNode();
312         p.putChildNode(result);
313         p.endInvoke();
314         result.endInvoke();
315     }
316     
317     public String   toString() {
318         return super.toString() + " " + getNodeIdLoc();
319     }
320     
321 }
322
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags