BTreeNode


1   package com.daffodilwoods.daffodildb.server.datasystem.btree;
2   
3   import com.daffodilwoods.daffodildb.server.datasystem.indexsystem.*;
4   import com.daffodilwoods.daffodildb.server.datasystem.interfaces.*;
5   import com.daffodilwoods.daffodildb.utils.byteconverter.*;
6   import com.daffodilwoods.daffodildb.utils.comparator.*;
7   import com.daffodilwoods.database.resource.*;
8   import com.daffodilwoods.database.utility.P;
9   
10  /**
11   *
12   * <p>Title: BTreeNode</p>
13   * <p>Description: BTreeNode : BTreeNode represents a single node of Balanced Tree.A Btree can have any
14   * number of nodes.Node Size of a BTree is constant which is decided at the time of database creation.
15   * All the nodes are managed by the BTree with which they are related.
16   *
17   * Must Know :
18   * 1.   Every Node can contain 2^n-1 elements ( Optimized result ) at most.
19   * 2.   Every node except root node has a parent node and a parent element.
20   * 3.   Every node has a dummy element which is the very first element of the node.
21   * 4.   Node can not have any left or right child.</p>
22   */
23  
24  public class BTreeNode {
25  
26  
27      private _Index btree ;
28  
29      /**
30       * memory node or file Node
31       */
32  
33      private _Node node ;
34  
35      private _NodeManager nodeManager;
36      private BTreeElement parentElement;
37      private boolean isNodeRemovedFromMap = false;
38  
39      public BTreeNode(_Index btree,_Node node1) throws DException {
40          this.btree = btree;
41          node = node1;
42          nodeManager = ((BTree)btree).getNodeManager();
43      }
44  
45  
46     public void insertDummyElement(BTreeElement element) throws DException{
47          element.setPosition(0);
48          node.insertDummyElement(element);
49      }
50  
51      /**
52       * insert key,value pair in this node at the proper position.
53       */
54  
55     public int insert(_DatabaseUser user,Object   key,Object   value,int pos) throws DException {
56          try{
57              int position = pos == -1 ? binarySearch(key) : pos;
58              if(position < 0)
59                  position = Math.abs(position);
60              position++;
61              node.updateNode(position,false);
62              BTreeElement btreeElement = createBTreeElement(user,key,value,null,null);
63              btreeElement.setCurrentNode(this);
64              btreeElement.setPosition(position);
65              node.insert(position,btreeElement,true);
66              node.updateElementCount(true);
67              return position;
68          }
69          catch(DException de){
70              if(de.getDseCode().equals("DSE2044")){
71                  return -1;
72              }
73              throw de;
74          }
75      }
76  
77  
78      Object   getKey(){
79          return this;
80      }
81  
82     public void delete(_DatabaseUser user,int position) throws DException {
83          node.delete(position);
84      }
85  
86     public void update(_DatabaseUser user,BTreeKey btreekey,Object   newKey,Object   newValue) throws DException {
87       node.updateBtree(btreekey,newKey,newValue);
88      }
89  
90      /**
91       * Returns parentNode of this node
92       */
93  
94     public BTreeNode getParentNode(_DatabaseUser user) throws DException{
95          Object   nodeKey = node.getParentNode(user);
96          return nodeKey == null ? null : nodeManager.getNode(user,nodeKey);
97      }
98  
99  
100     /**
101      * Returns element at required position of Node
102      *
103      * @param index Position on which element From node is required
104      * @return element at required position of Node
105      */
106 
107     public BTreeElement getElement(int index,_DatabaseUser user) throws DException{
108         BTreeElement ele = node.getElement(index);
109         ele.setCurrentNode(this);
110         ele.setPosition(index);
111         return ele;
112     }
113 
114    public int binarySearch(Object   key)throws DException{
115         return binarySearch(key, 1,node.getElementCount()-1);
116     }
117 
118     private int binarySearch(Object   key,int low,int high)throws DException{
119         int position = -1;
120         SuperComparator comparator = btree.getComparator();
121         while (low <= high) {
122             int mid =(low + high)/2;
123             int cmp;
124             cmp = comparator.compare(getKey(mid),key);
125             if (cmp < 0)
126                 low = mid + 1;
127             else if (cmp > 0)
128                 high = mid-1 ;
129             else{
130                 position = mid;
131                 if(!btree.getDuplicateAllowed() )
132                   break;
133                 low = mid + 1;
134             }
135         }
136         return position == -1 ? -(low-1) : position;
137     }
138 
139     public String   toString(){
140          try {
141              int count = getElementCount();
142              String   str = getNodeKey()+" ISLEAF NODE :: "+isLeaf()+" Element Count "+count ;//+ "free sapce is " + ((FileNode)node).getFreespace();"NODE ADDRESS : "+node.getNodeKey()+
143              for (int i = 0; i < count; i++) {
144                  BTreeElement element = getElement(i,null);
145                  str += "["+element +"]";
146              }
147              str+=" prev node :: " +  (getPreviousNode(null) == null ? null : getPreviousNode(null).getNodeKey());
148              str+=" next node :: " +  (getNextNode(null) == null ? null : getNextNode(null).getNodeKey());
149              return str;
150          }
151          catch (DException ex) {
152          }
153          return null;
154      }
155 
156 
157     SuperComparator getComparator() {
158         return btree.getComparator();
159     }
160 
161 
162   public  short getLevel() {
163         return node.getLevel();
164     }
165 
166    public void setLevel(short level0)throws DException{
167         node.setLevel(level0);
168     }
169 
170     BTreeElement createBTreeElement(_DatabaseUser user, Object   key,Object   value,BTreeNode leftNode,BTreeNode rightNode ) throws DException {
171         return node.createElement(node.isLeafNode(),user,key,value,leftNode,rightNode);
172     }
173 
174     public int getElementCount() throws DException{
175         return node.getElementCount();
176     }
177 
178    public int getSplitPoint() throws DException{
179         return node.getSplitPoint();
180     }
181 
182   public  void insertRange(Object   elements,int startPosition,int endPosition)throws DException{
183         node.insertRange(elements,startPosition,endPosition);
184     }
185 
186    public void deleteRange(int startPosition,int endPosition)throws DException{
187         node.deleteRange(startPosition,endPosition);
188     }
189 
190    public Object   getElements()throws DException{
191         return node.getElements();
192     }
193 
194   public  int getFirstValidPosition() throws DException{
195         if(node.getElementCount() > 1)
196             return 1;
197         else
198             throw StaticExceptions.NO_VALID_KEY;
199     }
200 
201     /**
202      * returns next valid position in this node from given position if this node does not have any valid
203      * position after given position then it throws an Exception.
204      * @param position after which next valid position from node has to give
205      * @return next valid position in node from given position
206      * @throws DException if no valid position exists after given position
207      */
208 
209     public int getNextValidPosition(int position)throws DException{
210         int nextvalidPosition = position + 1;
211         if(nextvalidPosition < node.getElementCount())
212             return nextvalidPosition;
213         else
214             throw StaticExceptions.NO_VALID_KEY;
215     }
216 
217     /**
218      * Returns last valid position in this node, if there is no element in node then it throws DException
219      * @return last valid position in this node
220      * @throws DException there is no valid position if there is no element in node
221      */
222    public int getLastValidPosition()throws DException{
223         int elementCount = node.getElementCount();
224         if(elementCount > 1)
225             return elementCount -1;
226         else
227             throw StaticExceptions.NO_VALID_KEY;
228     }
229 
230     /**
231      * returns previous valid position in this node from given position if this node does not have any
232      * valid position before given position then it throws an Exception.
233      *
234      * @param position after which previous valid position from node has to give
235      * @return previous valid position in node from given position
236      * @throws DException if no valid position exists before given position
237      */
238   public  int getPreviousValidPosition(int position)throws DException{
239         int previousPosition = position - 1;
240         if(previousPosition > 0)
241             return previousPosition;
242         else
243             throw StaticExceptions.NO_VALID_KEY;
244     }
245 
246     /**
247      * returns next node of this node if exists otherwise returns false
248      * @param user
249      * @return next node of this node if exists otherwise returns false
250      */
251 
252    public BTreeNode getNextNode(_DatabaseUser user) throws DException{
253         Object   nextNode = node.getNextNode(user);
254         return  nextNode == null ? null : nodeManager.getNode(user,nextNode);
255     }
256 
257     /**
258      * returns previous node of this node if exists otherwise returns false
259      * @param user
260      * @return previous node of this node if exists otherwise returns false
261      */
262 
263    public BTreeNode getPreviousNode(_DatabaseUser user) throws DException{
264         Object   nodeKey =  node.getPreviousNode(user);
265         return nodeKey == null ? null :  nodeManager.getNode(user,nodeKey);
266     }
267 
268     public Object   getNodeKey() throws DException{
269         return node.getNodeKey();
270     }
271 
272   public  void setNextNode(BTreeNode node0)throws DException {
273         node.setNextNode(node0);
274     }
275 
276    public void setPreviousNode(BTreeNode node0)throws DException {
277         node.setPreviousNode(node0);
278     }
279 
280    public void setLeafNode(boolean flag)throws DException{
281         node.setLeafNode(flag);
282     }
283 
284     public boolean isLeaf() throws DException {
285         return node.isLeafNode();
286     }
287 
288    public void setParentNode(BTreeNode node0) throws DException{
289         node.setParentNode(node0);
290     }
291 
292     public void updateChild(int position,Object   key) throws DException{
293         node.updateChild(position,key);
294     }
295 
296     public _Node getNode(){
297         return node;
298     }
299 
300     CbCzufIboemfs[] getByteHandlers() throws DException{
301         return nodeManager.getByteHandlers();
302     }
303 
304 
305 
306     public Object   getKey(int index) throws DException{
307         return node.getKey(index);
308     }
309 
310    public Object   getChildNodeKey(int index) throws DException{
311         return node.getChildNodeKey(index);
312     }
313 
314   public  Object   getValue(int index) throws DException{
315         return node.getValue(index);
316     }
317 
318 
319     public int[] getColumnTypes() throws DException{
320         return nodeManager.getColumnTypes();
321     }
322 
323     public void finalize1(){
324         if(node instanceof FixedFileNode || node instanceof VariableFileNode )
325          ;//// Removed By Program **              System.out.println("  finalize called " + hashCode());
326     }
327 
328    public void setParentElement(BTreeElement ele0) throws DException {
329       parentElement = ele0;
330     }
331 
332     public FileNodeManager getNodeManager() {
333       return (FileNodeManager) nodeManager;
334     }
335 
336     public void clearReferences() {
337       if(parentElement!= null){
338         parentElement.clearChild();
339         parentElement = null;
340       }
341     }
342 
343     public boolean isNodeRemovedFromMap(){
344       return isNodeRemovedFromMap;
345     }
346 
347     public void setFlagForNodeRemovedFromMap(){
348       isNodeRemovedFromMap = true;
349     }
350     public void setIsNodeCanBeRemovedFromMap(boolean isNodeCanBeRemovedFromMap) {
351     node.setIsNodeCanBeRemovedFromMap(isNodeCanBeRemovedFromMap);
352   }
353 
354   public boolean isNodeCanBeRemovedFromMap() {
355     return node.isNodeCanBeRemovedFromMap() ;
356   }
357 
358 }
359 
360
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags