EftarFile.java revision 1327
352N/A/*
352N/A * CDDL HEADER START
352N/A *
352N/A * The contents of this file are subject to the terms of the
352N/A * Common Development and Distribution License (the "License").
352N/A * You may not use this file except in compliance with the License.
352N/A *
352N/A * See LICENSE.txt included in this distribution for the specific
352N/A * language governing permissions and limitations under the License.
352N/A *
352N/A * When distributing Covered Code, include this CDDL HEADER in each
352N/A * file and include the License file at LICENSE.txt.
352N/A * If applicable, add the following below this CDDL HEADER, with the
352N/A * fields enclosed by brackets "[]" replaced with your own identifying
352N/A * information: Portions Copyright [yyyy] [name of copyright owner]
352N/A *
352N/A * CDDL HEADER END
352N/A */
352N/A
352N/A/*
1372N/A * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
352N/A * Use is subject to license terms.
352N/A */
352N/A
560N/Apackage org.opensolaris.opengrok.web;
921N/A
352N/Aimport java.io.BufferedOutputStream;
560N/Aimport java.io.BufferedReader;
480N/Aimport java.io.DataOutputStream;
480N/Aimport java.io.FileNotFoundException;
352N/Aimport java.io.FileOutputStream;
352N/Aimport java.io.FileReader;
352N/Aimport java.io.IOException;
352N/Aimport java.io.RandomAccessFile;
352N/Aimport java.util.Map;
560N/Aimport java.util.StringTokenizer;
560N/Aimport java.util.TreeMap;
480N/Aimport java.util.logging.Level;
352N/Aimport java.util.logging.Logger;
480N/A
592N/Aimport org.opensolaris.opengrok.util.IOUtils;
665N/A
665N/A/**
876N/A * An Extremely Fast Tagged Attribute Read-only File System
560N/A * Created on October 12, 2005
377N/A *
480N/A * A Eftar File has the following format
352N/A * FILE --> Record ( Record | tagString ) *
352N/A * Record --> 64bit:Hash 16bit:childrenOffset 16bit:(numberChildren|lenthOfTag) 16bit:tagOffset
352N/A *
352N/A * It is a tree of tagged names,
352N/A * doing binary search in sorted list of children
352N/A *
377N/A * @author Chandan
352N/A */
352N/Apublic class EftarFile {
352N/A
352N/A public static final int RECORD_LENGTH = 14;
352N/A private long offset;
352N/A private DataOutputStream out;
861N/A
861N/A class Node {
352N/A
352N/A public long hash;
352N/A public String tag;
352N/A public Map<Long, Node> children;
352N/A public long tagOffset;
352N/A public long childOffset;
352N/A public long myOffset;
367N/A
377N/A public Node(long hash, String tag) {
377N/A this.hash = hash;
352N/A this.tag = tag;
352N/A children = new TreeMap<Long, Node>();
352N/A }
352N/A
377N/A public Node put(long hash, String desc) {
352N/A if (children.get(hash) == null) {
352N/A children.put(hash, new Node(hash, desc));
352N/A }
352N/A return children.get(hash);
352N/A }
352N/A
352N/A public Node get(long hash) {
365N/A return children.get(hash);
352N/A }
352N/A }
352N/A
489N/A class FNode {
377N/A
352N/A public long offset;
1214N/A public long hash;
352N/A public int childOffset;
352N/A public int numChildren;
352N/A public int tagOffset;
352N/A
352N/A public FNode(RandomAccessFile f) throws Throwable {
352N/A offset = f.getFilePointer();
365N/A hash = f.readLong();
1092N/A childOffset = f.readUnsignedShort();
1092N/A numChildren = f.readUnsignedShort();
1092N/A tagOffset = f.readUnsignedShort();
1092N/A }
1092N/A
1092N/A public FNode(long hash, long offset, int childOffset, int num, int tagOffset) {
1092N/A this.hash = hash;
1092N/A this.offset = offset;
1092N/A this.childOffset = childOffset;
1092N/A this.numChildren = num;
1092N/A this.tagOffset = tagOffset;
1092N/A }
1092N/A
1092N/A public FNode get(long hash, RandomAccessFile f) throws Throwable {
1092N/A if (childOffset == 0) {
1092N/A return null;
1092N/A }
1092N/A return sbinSearch(offset + childOffset, numChildren, hash, f);
1092N/A }
1092N/A
1092N/A private FNode sbinSearch(long start, int len, long hash, RandomAccessFile f) throws Throwable {
1092N/A int b = 0;
1092N/A int e = len;
1092N/A while (b <= e) {
1092N/A int m = (b + e) / 2;
1092N/A f.seek(start + m * RECORD_LENGTH);
1092N/A long mhash = f.readLong();
1092N/A if (hash > mhash) {
1092N/A b = m + 1;
1092N/A } else if (hash < mhash) {
1092N/A e = m - 1;
1092N/A } else {
1092N/A return new FNode(mhash, f.getFilePointer() - 8l, f.readUnsignedShort(), f.readUnsignedShort(), f.readUnsignedShort());
1092N/A }
1092N/A }
1092N/A return null;
1092N/A }
1185N/A }
1214N/A
1185N/A public static long myHash(String name) {
1092N/A if (name == null || name.length() == 0) {
1092N/A return 0;
1092N/A }
1092N/A long hash = 2861;
1092N/A int n = name.length();
1092N/A if (n > 100) {
1092N/A n = 100;
1092N/A }
1092N/A for (int i = 0; i < n; i++) {
1092N/A hash = (hash * 641 + name.charAt(i) * 2969 + hash << 6) % 9322397;
1092N/A }
1092N/A return hash;
1092N/A }
1092N/A
1092N/A private void write(Node n) throws IOException {
1092N/A if (n.tag != null) {
1092N/A out.write(n.tag.getBytes());
1092N/A offset += n.tag.length();
1092N/A }
1092N/A for (Node childnode : n.children.values()) {
1092N/A out.writeLong(childnode.hash);
1092N/A if (childnode.children.size() > 0) {
1092N/A out.writeShort((short) (childnode.childOffset - offset));
1092N/A out.writeShort((short) childnode.children.size());
1092N/A } else {
1092N/A out.writeShort(0);
365N/A if (childnode.tag == null) {
365N/A out.writeShort((short) 0);
365N/A } else {
365N/A out.writeShort((short) childnode.tag.length());
365N/A }
365N/A }
365N/A if (childnode.tag == null) {
365N/A out.writeShort(0);
1024N/A } else {
365N/A out.writeShort((short) (childnode.tagOffset - offset));
365N/A }
365N/A offset += RECORD_LENGTH;
365N/A }
365N/A for (Node childnode : n.children.values()) {
480N/A write(childnode);
480N/A }
480N/A }
480N/A
1054N/A private void traverse(Node n) {
1054N/A if (n.tag == null) {
1054N/A n.tagOffset = 0;
1054N/A } else {
1054N/A n.tagOffset = offset;
480N/A offset += n.tag.length();
480N/A }
480N/A if (n.children.size() > 0) {
480N/A n.childOffset = offset;
1054N/A offset += (RECORD_LENGTH * n.children.size());
1054N/A } else {
1054N/A n.childOffset = 0;
1054N/A }
1054N/A for (Node childnode : n.children.values()) {
1054N/A traverse(childnode);
1054N/A }
1054N/A }
1054N/A private Node root;
480N/A
480N/A public void readInput(String tagsPath) throws IOException {
480N/A BufferedReader r = new BufferedReader(new FileReader(tagsPath));
480N/A try {
678N/A readInput(r);
480N/A } finally {
480N/A IOUtils.close(r);
489N/A }
480N/A }
489N/A
480N/A private void readInput(BufferedReader r) throws IOException {
665N/A if (root == null) {
665N/A root = new Node(1, null);
665N/A }
807N/A String line;
665N/A while ((line = r.readLine()) != null) {
665N/A int tab = line.indexOf('\t');
665N/A if (tab > 0) {
665N/A String path = line.substring(0, tab);
592N/A String desc = line.substring(tab + 1);
592N/A StringTokenizer toks = new StringTokenizer(path, "\\/");
480N/A Node n = root;
480N/A while (toks.hasMoreTokens()) {
480N/A n = n.put(myHash(toks.nextToken()), null);
480N/A }
480N/A n.tag = desc;
480N/A }
480N/A }
480N/A }
480N/A
480N/A public void write(String outPath) throws FileNotFoundException, IOException {
480N/A offset = RECORD_LENGTH;
480N/A traverse(root);
480N/A out = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outPath)));
480N/A out.writeLong(0x5e33);
480N/A out.writeShort(RECORD_LENGTH);
807N/A out.writeShort(root.children.size());
480N/A out.writeShort(0);
807N/A offset = RECORD_LENGTH;
480N/A write(root);
480N/A IOUtils.close(out);
560N/A }
560N/A
560N/A public void create(String[] args) throws IOException, FileNotFoundException {
560N/A for (int i = 0; i < args.length - 1; i++) {
560N/A readInput(args[i]);
560N/A }
560N/A write(args[args.length - 1]);
560N/A }
560N/A
560N/A /**
921N/A * Main method is used to generate eftar file from the path description
560N/A * file in the run scripts.
560N/A *
1127N/A * @param args Input files and output file
560N/A */
560N/A @SuppressWarnings("PMD.SystemPrintln")
560N/A public static void main(String[] args) {
560N/A if (args.length < 2) {
560N/A System.err.println("Usage inputFile [inputFile ...] outputFile");
560N/A System.exit(1);
560N/A }
593N/A
678N/A try {
593N/A EftarFile ef = new EftarFile();
593N/A ef.create(args);
593N/A } catch (Exception e) {
593N/A Logger logger = Logger.getLogger(EftarFile.class.getName());
593N/A logger.warning("EftarFile error: " + e.getMessage());
593N/A logger.log(Level.FINE, "main", e);
593N/A }
593N/A }
593N/A
593N/A}
593N/A