Logo Search packages:      
Sourcecode: javahelp2 version File versions  Download package

FullBtreeDict.java

/*
 * @(#)FullBtreeDict.java     1.15 06/10/30
 * 
 * Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 * 
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 * 
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 * 
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 * 
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */

/**
 * @date   2/20/98
 * @author Jacek R. Ambroziak
 * @group  Sun Microsystems Laboratories
 */

package com.sun.java.help.search;

import java.io.*;       // debugging in main
import java.util.*;           // debugging in main

public class FullBtreeDict extends BtreeDict
{
  protected BtreeDictParameters params;
  private boolean update = false;
  
  private final class Entry
  {
    public byte[] key;
    public int    id;
    public int    block = -1;
  
    public Entry(byte[] key, int length, int id)
    {
      this.key = new byte[length + 1];
      System.arraycopy(key, 0, this.key, 0, length);
      this.key[length] = 0;
      this.id = id;
    }
  
    public boolean smallerThan(Entry other)
    {
      for (int i = 0; i < Math.min(key.length, other.key.length); i++)
      if (key[i] != other.key[i])
        return (key[i]&0xFF) < (other.key[i]&0xFF);
      return false;
    }
  }
  // end of internal class
  
  protected class FullDictBlock extends DictBlock
  {
    public void setFree(int free)
    {
      this.free = free - firstEntry();
      this.data[free] = this.data[free + 1] = 0; // sentinel
    }
  
    public void setNumberOfEntries(int n) {
      setIntegerAt(0, n);
    }

    protected void setChildIndex(int index, int value) {
      setIntegerAt(4*(lastPtrIndex - index + 1), value);
    }
  
    public void setEntryID(int i, int id) {
      setIntegerAt(i + 2, id);
    }
  
    // finds the place and context
    private boolean insert(Entry entry)
    {
      byte[] inkey = entry.key;
      final int inputKeyLen = inkey.length - 1;
      final int freeSpace   = free();
      int entryPtr    = firstEntry();
      int nCharsEqual = 0;
      int prevNCEqual = 0;
      int compression = 0;

      for (int entryIndex = 0;;)
      {
        if (entryPtr == freeSpace)
          return insert(entry, entryPtr, nCharsEqual, 0, numberOfEntries());
        else if (compression == nCharsEqual)
          {
            int keyLen = entryKeyLength(entryPtr);
            int keyPtr = entryKey(entryPtr), i;
            prevNCEqual = nCharsEqual;
            for (i = 0;
               i < keyLen && inkey[nCharsEqual] == data[keyPtr + i];
               i++)
            ++nCharsEqual;
            if (i == keyLen)
            {
              if (nCharsEqual == inputKeyLen)
                {
                  setEntryID(entryPtr, entry.id);
                  return true;
                }
            }
            else if ((inkey[nCharsEqual]&0xFF) < (data[keyPtr + i]&0xFF))
            return insert(entry, entryPtr, prevNCEqual, nCharsEqual,
                        entryIndex);
          }
        else if (compression < nCharsEqual) // compression dropped
          return insert(entry, entryPtr, nCharsEqual, compression,
                    entryPtr == freeSpace
                    ? numberOfEntries() : entryIndex);
        do {
          entryPtr = nextEntry(entryPtr);
          ++entryIndex;
        }
        while (entryCompression(entryPtr) > nCharsEqual);
        compression = entryCompression(entryPtr);
      }
    }
    
    public void makeEntry(int entry, byte[] key, int id, int length, int compr)
    {
      data[entry]     = (byte) length;
      data[entry + 1] = (byte) compr;
      setEntryID(entry, id);
      System.arraycopy(key, compr, data, entryKey(entry), length);
    }

    private boolean insert(Entry ent, final int entryPtr,
                     final int compr1, final int compr2,
                     final int index)
    {
      final byte[] key = ent.key;
      final int keyLen = key.length - 1 - compr1;
      final int freeSpace = free();
      // calculate how much space is needed to add the new entry
      // first, how many bytes are needed for just the new entry
      final int demand = ENTHEADERLEN + keyLen;
      // adding an entry can increase compression in the following entry
      
      int increase = 0;
      if (entryPtr < freeSpace)
      if (entryCompression(entryPtr) < compr2)
        increase = compr2 - entryCompression(entryPtr);
      /*
      System.err.println("key " + key);
      System.err.println("entryPtr " + entryPtr);
      System.err.println("compr1 " + compr1);
      System.err.println("compr2 " + compr2);
      System.err.println("index " + index);
      System.err.println("demand " + demand);
      System.err.println("increase " + increase);
      */
      // check if enough space is available
      int limit = isLeaf ? DATALEN-2 : 4*(lastPtrIndex-numberOfEntries()-1);
    
      if (freeSpace + demand - increase <= limit)// 2 for sentinel
      {
        if (entryPtr < freeSpace)
          {
            // need to shift extant entries forward
            final int toMove = increase > 0
            ? entryPtr + ENTHEADERLEN + increase
            : entryPtr;
            // move entries
            System.arraycopy(data, toMove,
                         data, toMove + demand - increase,
                         freeSpace - toMove);
            if (increase > 0)
            {
              // update header
              data[entryPtr]     -= increase;
              data[entryPtr + 1] += increase;
              // shift header
              System.arraycopy(data, entryPtr,
                           data, entryPtr + demand, ENTHEADERLEN);
            }
          }
        // now write the new entry in the space made above
        makeEntry(entryPtr, key, ent.id, keyLen, compr1);
        if (isLeaf == false)
          {
            int from = 4*(lastPtrIndex - numberOfEntries() + 1);
            System.arraycopy(data, from, data, from - 4,
                         4*(numberOfEntries() - index));
            setChildIndex(index + 1, ent.block);
          }
        setFree(freeSpace + demand - increase);
        setNumberOfEntries(numberOfEntries() + 1);
        

        /*
        System.err.println("------------list--------------");
      byte[] buffer = new byte[MaxKeyLength];
      final int freeSpace2 = free();
      int entryPtr2 = firstEntry();
      while (entryPtr2 < freeSpace2)
      {
        System.err.println(entryPtr2);
        System.err.println(entryKeyLength(entryPtr2));
        System.err.println(entryCompression(entryPtr2));
        System.err.println(new String(data,
                              entryKey(entryPtr2),
                              entryKeyLength(entryPtr2)));
        System.err.println(restoreKey(entryPtr2, buffer)+" "+
                       entryID(entryPtr2));
        entryPtr2 = nextEntry(entryPtr2);
      }
      System.err.println("------------end--------------");
      */

        
        return true;
      }
      else
      return false;
    }
  
    public int insertInternal(Entry entry)
    {
      byte[] inkey    = entry.key;
      final int inputKeyLen = inkey.length - 1;
      int entryPtr    = firstEntry();
      final int freeSpace   = free();
      int nCharsEqual = 0;
      int compression = 0;

      for (int entryIndex = 0;;)
      {
        if (entryPtr == freeSpace)
          return numberOfEntries();
        else if (compression == nCharsEqual)
          {
            int i;
            int keyLen = entryKeyLength(entryPtr);
            int keyPtr = entryKey(entryPtr);
            for (i = 0;
               i < keyLen && inkey[nCharsEqual] == data[keyPtr + i];
               i++)
            ++nCharsEqual;
            if (i == keyLen)
            {
              if (nCharsEqual == inputKeyLen)
                {
                  setEntryID(entryPtr, entry.id);
                  return -1;
                }
            }
            else if ((inkey[nCharsEqual]&0xFF) < (data[keyPtr + i]&0xFF))
            return entryIndex;
          }
        else if (compression < nCharsEqual) // compression dropped
          return entryPtr >= freeSpace ? numberOfEntries() : entryIndex;
    
        do {
          entryPtr = nextEntry(entryPtr);
          ++entryIndex;
        }
        while (entryCompression(entryPtr) > nCharsEqual);
        compression = entryCompression(entryPtr);
      }
    }
  
    private Entry split(FullDictBlock newbl)
    {
      byte[] buffer = new byte[MaxKeyLength];
      int freeSpace = free();
      int half      = freeSpace/2;
      int index     = 0;            // of middle entry
      newbl.isLeaf = isLeaf;
      int ent;
      for (ent = firstEntry(); ent < half; ent = nextEntry(ent))
      {
        restoreKeyInBuffer(ent, buffer);
        ++index;
      }
      final int entriesToMove = numberOfEntries() - index - 1;
      // middle entry
      restoreKeyInBuffer(ent, buffer);
      int len = entryKeyLength(ent) + entryCompression(ent);
      Entry result = new Entry(buffer, len, entryID(ent));
      result.block = newbl.number;
      int newFree = ent;
      // rest goes to the new block
      ent = nextEntry(ent);
      restoreKeyInBuffer(ent, buffer);
      len = entryKeyLength(ent) + entryCompression(ent);
      int nptr = firstEntry();
      newbl.makeEntry(nptr, buffer, entryID(ent), len, 0);
      ent = nextEntry(ent);
      System.arraycopy(data, ent,
                   newbl.data, newbl.nextEntry(nptr), freeSpace - ent);
      newbl.setNumberOfEntries(entriesToMove);
      newbl.setFree(newbl.nextEntry(nptr) + freeSpace - ent);
      if (isLeaf == false)    // need to split pointers
      {
        int from = 4*(lastPtrIndex - numberOfEntries() + 1);
        System.arraycopy(data, from,
                     newbl.data, from + 4*(index + 1),
                     4*(entriesToMove + 1));
      }
      // this entry will end here
      setFree(newFree);
      setNumberOfEntries(index);
      return result;
      //!!!remember updating ID -> string association
    }
  
    public void initInternal(int leftBlock, Entry entry)
    {
      isLeaf = false;
      setNumberOfEntries(1);
      setChildIndex(0, leftBlock);
      setChildIndex(1, entry.block);
      final int ent = firstEntry();
      makeEntry(ent, entry.key, entry.id, entry.key.length - 1, 0);
      setFree(nextEntry(ent));
    }
  }
  // end of internal class

  protected  FullBtreeDict() {/*empty*/}

  public FullBtreeDict(BtreeDictParameters params, boolean update)
    throws Exception
  {
    init(params, update, new BlockFactory() {
      public Block makeBlock() { return new FullDictBlock(); }
    });
    blocks = new int[300000]; // !!!
    this.params = params;
    this.update = update;
  }

  public void close(int freeID) throws Exception
  {
    params.setFreeID(freeID);
    if (update)
      params.updateSchema();
    super.close();
  }

  public void store(String key, int id) throws Exception
  {
    //    System.err.println("storing "+key+" id "+id);
    byte[] bytes = key.getBytes("UTF8");
    Entry entry = insert((FullDictBlock)accessBlock(root),
                   new Entry(bytes, bytes.length, id));
    if (entry != null)
      {
      // new root; writing to params needed
      FullDictBlock nbl = getNewBlock();
      nbl.initInternal(root, entry);
      blocks[entry.id] = root = nbl.number;
      params.setRoot(root);
      }
  }
  
  private void setModified(Block bl) {
    blockManager.setModified(bl.number);
  }
  
  private FullDictBlock getNewBlock() throws Exception
  {
    FullDictBlock nbl = (FullDictBlock)blockManager.getNewBlock();
    setModified(nbl);
    return nbl;
  }

  /*
    delegation to powerful primitives at the FullDictBlock level lets us
    express the insertion algorithm very succintly here
    */

  private Entry insert(FullDictBlock bl, Entry ent) throws Exception
  {
    if (bl.isLeaf)
      return insertHere(bl, ent);
    else
      {
      int index = bl.insertInternal(ent);
      if (index != -1)
        try {
          lock(bl);
          ent = insert((FullDictBlock)child(bl, index), ent);
          return ent == null ? null : insertHere(bl, ent);
        }
      finally {
        unlock(bl);
      }
      else
        return null;
      }
  }

  private Entry insertHere(FullDictBlock bl, Entry ent) throws Exception
  {
    setModified(bl);          // to be modified in any case 
    if (bl.insert(ent))
      return null;
    else
      {
      FullDictBlock nbl = getNewBlock();
      Entry middle = bl.split(nbl);
      nbl.setBlockNumbers(blocks);
      if ((middle.smallerThan(ent) ? nbl : bl).insert(ent) == false)
        throw new Exception("entry didn't fit into a freshly split block");
      return middle;
      }
  }
  
  public static void main(String[] args)
  {
    try {
      Schema schema = new Schema(null, args[0], true);
      BtreeDictParameters tmapParams = new BtreeDictParameters(schema, "TMAP");
      if (tmapParams.readState() == false)
      {
        tmapParams.setBlockSize(2048);
        tmapParams.setRoot(0);
        tmapParams.setFreeID(1);
      }
      FullBtreeDict dict = new FullBtreeDict(tmapParams, true);
      int freeID = tmapParams.getFreeID();
    
      LineNumberReader in = new LineNumberReader(new BufferedReader
                                     (new FileReader(args[1])));
      String line;
      while ((line = in.readLine()) != null)
      {
        StringTokenizer tokens = new StringTokenizer(line, " ");
        while (tokens.hasMoreTokens())
          {
            String token = tokens.nextToken();
            if (token.equals("storing"))
            dict.store(tokens.nextToken(), freeID++);
            else if (token.equals("fetching"))
              dict.fetch(tokens.nextToken());
          }
      }
      in.close();
    }
    catch (Exception e) {
      e.printStackTrace();
    }
  }
 
 /**
   * Debug code
   */

  private boolean debug=false;
  private void debug(String msg) {
    if (debug) {
      System.err.println("FullBtreeDict: "+msg);
    }
  }
}


Generated by  Doxygen 1.6.0   Back to index