/* * Author: Barbara Hohlt * Inception Date: July 27, 2000 * * This software is copyrighted by Barbara Hohlt and the Regents of * the University of California. The following terms apply to all * files associated with the software unless explicitly disclaimed in * individual files. * * The authors hereby grant permission to use this software without * fee or royalty for any non-commercial purpose. The authors also * grant permission to redistribute this software, provided this * copyright and a copy of this license (for reference) are retained * in all distributed copies. * * For commercial use of this software, contact the authors. * * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY * FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES * ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY * DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE * IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE * NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR * MODIFICATIONS. */ package ninja2.core.sn_btree; import ninja2.core.io_core.interfaces.*; import ninja2.core.io_core.interfaces.disk.*; import ninja2.core.io_core.core.*; import ninja2.core.io_core.util.*; import ninja2.core.io_core.thread_pool.*; import ninja2.core.sn_btree.lockmgr.*; import ninja2.core.sn_btree.bufcache.*; import ninja2.core.sn_btree.static_table.ST_FSM; import ninja2.core.sn_btree.recordconverters.*; import ninja2.util.*; import java.util.*; import java.io.IOException; /** * The SN_Btree class defines the interface that callers use to * access persistent btree file from disk. The SN_Btree * API is totally non-blocking (but it is possible to wrap a blocking * API around this). Callers issue read requests, and later pick up * btree table completions from the PassiveSourceIF interface that this * btree table exports. * * @author Barbara Hohlt */ public class SN_Btree implements ninja2.core.io_core.interfaces.PassiveSourceIF, ninja2.core.io_core.interfaces.UpcallRegisterIF { /* * All of these static methods and variables are basically used by the * single event thread polling for completions from the single-node * btree tables managed by this brick. */ public static Hashtable _lockBindings = new Hashtable(); public static Hashtable _tableCount = new Hashtable(); public static LockMgr globLockMgr = null; public static BufCache globBufCache = null; public static DiskSegmentIF globDSegIF = null; public static MemAllocatorIF globMemAllocIF = null; public static ThreadPool globThreadPool = null; public static QueueIF main_event_queue = null; public static SN_Btree_Event_Dispatcher shed = null; /* B-link structure * a) Each path from the root to any leaf has the same * length, h. * b) Each node except the root and the leaves has at least * k+1 sons. (k is a tree parameter; 2k+1 is the maximum * number of elements in a node. * c) The root is a leaf or has at least two sons. * d) Each node has at most 2k+1 sons. * e) The keys for all of the data in the btree are stored * in the leaf nodes, which also contain pointers to the * records of the database. * f) Each node has a link pointer which points to the next * node at the same level if there is one. */ public static final boolean debug = false; public static final int table_blocksize = 4096; /* btree node size */ /* max # node entries */ public static final int max_node_slots = ( ((table_blocksize - BtreeNode.THB_HEADER_SIZE)/ BtreeNode.THBR_HEADER_SIZE)) - 1; public static final int max_root_slots = ( ((table_blocksize - BtreeRoot.ROOT_HEADER_SIZE)/ BtreeNode.THBR_HEADER_SIZE)) - 1; // MARK: The following is an entry that can be (and should be) tuned public static final int num_blocks_in_cache = 6000; public static void init_sn_btree() { // initialize global variables if (main_event_queue == null) main_event_queue = new Queue(); if (shed == null) shed = new SN_Btree_Event_Dispatcher(main_event_queue); if (globLockMgr == null) globLockMgr = LockMgr.getGlobalLockMgr(); if (globThreadPool == null) globThreadPool = new ThreadPool(30, 40, 50); if (globBufCache == null) { globBufCache = BufCache.getGlobalBufCache(globThreadPool); globBufCache.register_upcall(main_event_queue); } if (globDSegIF == null) globDSegIF = new ninja2.core.io_core.fs_disk.FSDiskSegmentVizier(globThreadPool); if (globMemAllocIF == null) globMemAllocIF = new ByteArrayMemAllocator(); } /** * Here is the main thread that dispatches events to and from the * single node btree table. This is truly the "main" thread in the * btree brick. */ private static class SN_Btree_Event_Dispatcher implements java.lang.Runnable { private QueueIF mainQ; public SN_Btree_Event_Dispatcher(QueueIF main_event_q) { this.mainQ = main_event_q; Thread sned_thread = new Thread(this, "SNED"); sned_thread.start(); } public void run() { while (true) { try { QueueElementIF[] events = mainQ.blocking_dequeue(0); if (events != null) { int evlen = events.length; for (int i=0; iname exists, this method will open * up the table, allowing you to generate put and get requests from it. * Eventually, we will put some extra params in here, like whether the * table is opened read-only or not. For now, hard code in a static table * engine. You are only allowed to call this once. * * @param name the name of the btree to create/open */ public int open() { // Initialize my local state SN_BtreeOpenRequest shor = new SN_BtreeOpenRequest(); shor.table = _tablename; shor.id = LockMgr.getUniqueID(); shor.sntable = this; main_event_queue.enqueue(shor); return shor.id; } /** * Creates a btree, destroying the old one with the same name should * it exist, and opens it. You may call either open() or * create_sn_btree() to begin using a btree, but you may only * call one of these, and only at most once for the entire lifetime * of the SN_Btree object. * * @param num_buckets the number of nodes to create */ public int create_sn_btree(int num_buckets) { SN_BtreeCreateRequest shcr = new SN_BtreeCreateRequest(); shcr.table = _tablename; shcr.num_bucks = num_buckets; /* MARK: will only create root */ shcr.id = LockMgr.getUniqueID(); shcr.sntable = this; main_event_queue.enqueue(shcr); return shcr.id; } /** * If the btree named name exists, this function * will destroy it. If outstanding reads/writes are outstanding when * you call this destroy method, undefined bad things will happen. If * the btree doesn't exist, this method throws a java.io.IOException. * * @param name the name of the single-node btree to destroy * @exception java.io.IOException if the table doesn't exist */ public int destroy_sn_btree() { SN_BtreeDestroyRequest shcr = new SN_BtreeDestroyRequest(); shcr.table = _tablename; shcr.id = LockMgr.getUniqueID(); shcr.sntable = this; main_event_queue.enqueue(shcr); return shcr.id; } /** * Fetches the element from the btree table that has a particular key. * A key is an 8 byte integer, and the value is an int array. A * completion event will eventually be put on this SN_Btree's * PassiveSourceIF queue. The integer that gets returned is a unique * ID that will be put in the completion event; you can use this to * match up your request with the completion, if you like. The * completion event will be of type SN_BtreeReadComplete. * * does btree search * * @param key the key of the element to retrieve * @return a unique ID that you can use to match up the completion * with this request. */ public int get(long key) { SN_BtreeReadRequest rq = new SN_BtreeReadRequest(); rq.table = this._tablename; // rq.node = 0; /* MARK: N/A for Btrees */ rq.min_key = key; rq.min_pred = ST_FSM.EQ; rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } public int get(int range, long key) { SN_BtreeReadRequest rq = new SN_BtreeReadRequest(); rq.table = this._tablename; // rq.node = 0; /* MARK: N/A for btrees */ switch(range) { case ST_FSM.LT: case ST_FSM.LE: rq.min_pred = ST_FSM.GE_MIN; rq.max_key = key; rq.max_pred = range; break; case ST_FSM.GT: case ST_FSM.GE: rq.max_pred = ST_FSM.LE_MAX; rq.min_key = key; rq.min_pred = range; break; default: rq.min_key = key; rq.min_pred = ST_FSM.EQ; } rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } public int get(int range1, long key1, int range2, long key2) { SN_BtreeReadRequest rq = new SN_BtreeReadRequest(); rq.table = this._tablename; // rq.node = 0; /* MARK: N/A for Btrees */ switch(range1) { case ST_FSM.LT: case ST_FSM.LE: if ((range2 != ST_FSM.GE) && (range2 != ST_FSM.GT)) { System.out.println("Bad arguments to get()."); return -1; } rq.min_key = key2; rq.min_pred = range2; rq.max_key = key1; rq.max_pred = range1; break; case ST_FSM.GT: case ST_FSM.GE: if ((range2 != ST_FSM.LE) && (range2 != ST_FSM.LT)) { System.out.println("Bad arguments to get()."); return -1; } rq.min_key = key1; rq.min_pred = range1; rq.max_key = key2; rq.max_pred = range2; break; default: rq.min_key = key1; rq.min_pred = ST_FSM.EQ; } rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } /** * Puts an element into a btree. If the key already exists, * this will return the old value in the completion, and overwrite * the old value with this new value. The completion will be of type * SN_BtreeWriteComplete. As with get, a unique * ID is returned that you can match up with the completion event later. * * @param key the key to put into the table * @param bytes the elements to store in the table * @return a unique ID that you can use to match up the completion * with this request */ public int put(long key, int value) { int[] values = {value}; return put(key,values); } public int put(long key, int[] bytes) { SN_BtreeWriteRequest rq = new SN_BtreeWriteRequest(); rq.table = this._tablename; rq.key = key; rq.new_value = bytes; rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } /** * Deletes an element from the Btree. If the key exists, * returns the old value in the completion. The completion will * be of type SN_BtreeRemoveComplete. As with get, * a unique ID is returned that you can match up with the completion event * later. * * @param key the key to of the value to delete from tree * @param value the value to delete from the btree * @return a unique ID that you can use to match up the completion * with this request */ public int remove(long key, int value) { int[] values = {value}; return remove(key,values); } public int remove(long key, int[] bytes) { SN_BtreeRemoveRequest rq = new SN_BtreeRemoveRequest(); rq.table = this._tablename; rq.key = key; rq.old_value = bytes; rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } public int remove(long key) { SN_BtreeRemoveRequest rq = new SN_BtreeRemoveRequest(); rq.table = this._tablename; rq.key = key; rq.id = LockMgr.getUniqueID(); main_event_queue.enqueue(rq); return rq.id; } /** * Closes this open btree, and syncs everything to disk. */ public int close() { SN_BtreeCloseRequest shcr = new SN_BtreeCloseRequest(); shcr.table = _tablename; shcr.id = LockMgr.getUniqueID(); shcr.sntable = this; main_event_queue.enqueue(shcr); return shcr.id; } /** * There is only a single queue of completion events from the LockMgr and * BufCache, which means a single consumer needs to pull events off of it * and dispatch them to appropriate subtable instances. So, we'll * use the SN_Btree as the single consumer. When subtables are * created, they'll register themselves with the SN_Btree, and * then when they want to check for completions, they'll do it through * this. */ public void register_subtable(String name, TableEngineIF te) { _lockBindings.put(name, te); } public void deregister_subtable(String name) { Integer tc = (Integer) _tableCount.get(name); if (tc == null) { Debug.msg("Btree singlenode", Debug.WARN, "bogus deregister in SN_Btree?!"); // System.exit(1); } else { int theint = tc.intValue(); if (theint == 1) { _lockBindings.remove(name); _tableCount.remove(name); } else { _tableCount.put(name, new Integer(theint--)); } } } // the PassiveSourceIF methods /** * Add a completion. */ public void addcompletion(QueueElementIF el) { _compQ.enqueue(el); } /** * dequeues a btree completion (i.e. a put or get). A btree * completion QueueElementIF is of type SN_BtreeReadComplete, * SN_BtreeWriteComplete, or SN_BtreeRemoveComplete. */ public QueueElementIF dequeue() { if (debug) { System.out.println(); System.out.println("SN_Btree._compQ.dequeue() called.") ; System.out.println(); } return _compQ.dequeue(); } /** * dequeues all btree table completions. */ public QueueElementIF[] dequeue_all() { if (debug) { System.out.println(); System.out.println("SN_Btree._compQ.dequeue_all() called.") ; System.out.println(); } return _compQ.dequeue_all(); } /** * the upcall registration function */ public void register_upcall(UpcallHandlerIF upcall_handler) { _compQ.register_upcall(upcall_handler); } // some test harness code public static void main(String args[]) { int reqID; QueueElementIF [] data ; System.out.println("doing init"); SN_Btree.init_sn_btree(); System.out.println("creating btree obj"); SN_Btree sht = new SN_Btree("testbtree"); QueueIF q = new Queue(); sht.register_upcall(q); System.out.println("doing btree destroy"); sht.destroy_sn_btree(); System.out.println("doing blocking dequeue"); q.blocking_dequeue(0); System.out.println("doing btree create"); sht.create_sn_btree(0); /* create tree and root node */ System.out.println("doing blocking dequeue"); q.blocking_dequeue(0); System.out.println("doing open"); sht.open(); System.out.println("doing blocking dequeue"); q.blocking_dequeue(0); System.out.println(); System.out.println("doing put"); int[] testArr0 = {48,23,22,21}; sht.put(48, testArr0); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(); System.out.println(); System.out.println("doing get"); reqID = sht.get(48); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(); System.out.println(); System.out.println("doing remove"); int[] testArr1 = {13,11}; sht.remove(51, testArr1); q.blocking_dequeue(0); System.out.println(); System.out.println(); System.out.println("doing get"); reqID = sht.get(51); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(); System.out.println(); /* System.out.println("doing put"); int[] testArr1 = {10,3,2,1}; sht.put(10, testArr1); q.blocking_dequeue(0); System.out.println("doing get"); reqID = sht.get(10); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(); System.out.println(); System.out.println("doing put"); int[] testArr2 = {31,3,2,1}; sht.put(9, testArr2); q.blocking_dequeue(0); System.out.println(); System.out.println(); System.out.println("doing remove"); sht.remove(51, 13); q.blocking_dequeue(0); System.out.println("doing put"); int[] testArr3 = {11,12,13,14}; sht.put(31, testArr3); q.blocking_dequeue(0); System.out.println("doing put"); int[] testArr4 = {31,52,53,54}; sht.put(91, testArr4); q.blocking_dequeue(0); sht.put(12, testArr4); q.blocking_dequeue(0); sht.put(13, testArr4); q.blocking_dequeue(0); sht.put(25, testArr4); q.blocking_dequeue(0); sht.put(26, testArr4); q.blocking_dequeue(0); sht.put(6, testArr4); q.blocking_dequeue(0); sht.put(39, testArr4); q.blocking_dequeue(0); sht.put(50, testArr4); q.blocking_dequeue(0); sht.put(51, testArr4); q.blocking_dequeue(0); sht.put(63, testArr4); q.blocking_dequeue(0); System.out.println(); System.out.println(); System.out.println("doing put MAX_KEY 100"); sht.put(100, testArr4); q.blocking_dequeue(0); sht.put(64, testArr4); q.blocking_dequeue(0); sht.put(75, testArr4); q.blocking_dequeue(0); sht.put(76, testArr4); q.blocking_dequeue(0); sht.put(88, testArr4); q.blocking_dequeue(0); sht.put(89, testArr4); q.blocking_dequeue(0); System.out.println(); System.out.println(); System.out.println("Min key/ptr: "+sht.min_key+"/"+ sht.min_ptr); System.out.println("Max key/ptr: "+sht.max_key+"/"+ sht.max_ptr); System.out.println("Max nodes: "+sht.numnodes); System.out.println("Max data pages: "+sht.numblocks); System.out.println("doing close"); System.out.println(""); System.out.println("doing get"); reqID = sht.get(ST_FSM.GT,50); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println("doing get"); reqID = sht.get(53); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); reqID = sht.get(54); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); reqID = sht.get(55); System.out.println(" request ID: "+reqID); data = q.blocking_dequeue(0); System.out.println(data[0]); // ex: get(ST_FSM.LT,51), get(51), get (ST_FSM.LT,100,ST_FSM.GT,5) System.out.println("doing get"); reqID = sht.get(53); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(""); System.out.println("doing get"); reqID = sht.get(ST_FSM.EQ,53); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(""); System.out.println("doing get"); reqID = sht.get(ST_FSM.GT,51); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println(""); System.out.println("doing get"); reqID = sht.get(ST_FSM.GE,51); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); System.out.println("doing get"); reqID = sht.get(ST_FSM.GT,48,ST_FSM.LT,56); System.out.println(" request ID: "+reqID); System.out.println("doing blocking dequeue"); data = q.blocking_dequeue(0); System.out.println(data[0]); */ System.out.println(); System.out.println(); System.out.println("Min key/ptr: "+sht.min_key+"/"+ sht.min_ptr); System.out.println("Max key/ptr: "+sht.max_key+"/"+ sht.max_ptr); System.out.println("Max nodes: "+sht.numnodes); System.out.println("Max data pages: "+sht.numblocks); System.out.println("doing close"); sht.close(); System.out.println("waiting for close complete"); q.blocking_dequeue(0); System.out.println("Main thread exiting.."); System.exit(0); } }