lucene-java-3.5.0/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/directory/ParentArray.java

   1 package org.apache.lucene.facet.taxonomy.directory;
   2
   3 import java.io.IOException;
   4
   5 import org.apache.lucene.index.CorruptIndexException;
   6 import org.apache.lucene.index.IndexReader;
   7 import org.apache.lucene.index.Term;
   8 import org.apache.lucene.index.TermPositions;
   9
  10 import org.apache.lucene.facet.taxonomy.TaxonomyReader;
  11
  12 /**
  13  * Licensed to the Apache Software Foundation (ASF) under one or more
  14  * contributor license agreements.  See the NOTICE file distributed with
  15  * this work for additional information regarding copyright ownership.
  16  * The ASF licenses this file to You under the Apache License, Version 2.0
  17  * (the "License"); you may not use this file except in compliance with
  18  * the License.  You may obtain a copy of the License at
  19  *
  20  *     http://www.apache.org/licenses/LICENSE-2.0
  21  *
  22  * Unless required by applicable law or agreed to in writing, software
  23  * distributed under the License is distributed on an "AS IS" BASIS,
  24  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  25  * See the License for the specific language governing permissions and
  26  * limitations under the License.
  27  */
  28
  29 // getParent() needs to be extremely efficient, to the point that we need
  30 // to fetch all the data in advance into memory, and answer these calls
  31 // from memory. Currently we use a large integer array, which is
  32 // initialized when the taxonomy is opened, and potentially enlarged
  33 // when it is refresh()ed.
  34 /**
  35  * @lucene.experimental
  36  */
  37 class ParentArray {
  38
  39   // These arrays are not syncrhonized. Rather, the reference to the array
  40   // is volatile, and the only writing operation (refreshPrefetchArrays)
  41   // simply creates a new array and replaces the reference. The volatility
  42   // of the reference ensures the correct atomic replacement and its
  43   // visibility properties (the content of the array is visible when the
  44   // new reference is visible).
  45   private volatile int prefetchParentOrdinal[] = null;
  46
  47   public int[] getArray() {
  48     return prefetchParentOrdinal;
  49   }
  50
  51   /**
  52    * refreshPrefetch() refreshes the parent array. Initially, it fills the
  53    * array from the positions of an appropriate posting list. If called during
  54    * a refresh(), when the arrays already exist, only values for new documents
  55    * (those beyond the last one in the array) are read from the positions and
  56    * added to the arrays (that are appropriately enlarged). We assume (and
  57    * this is indeed a correct assumption in our case) that existing categories
  58    * are never modified or deleted.
  59    */
  60   void refresh(IndexReader indexReader) throws IOException {
  61     // Note that it is not necessary for us to obtain the read lock.
  62     // The reason is that we are only called from refresh() (precluding
  63     // another concurrent writer) or from the constructor (when no method
  64     // could be running).
  65     // The write lock is also not held during the following code, meaning
  66     // that reads *can* happen while this code is running. The "volatile"
  67     // property of the prefetchParentOrdinal and prefetchDepth array
  68     // references ensure the correct visibility property of the assignment
  69     // but other than that, we do *not* guarantee that a reader will not
  70     // use an old version of one of these arrays (or both) while a refresh
  71     // is going on. But we find this acceptable - until a refresh has
  72     // finished, the reader should not expect to see new information
  73     // (and the old information is the same in the old and new versions).
  74     int first;
  75     int num = indexReader.maxDoc();
  76     if (prefetchParentOrdinal==null) {
  77       prefetchParentOrdinal = new int[num];
  78       // Starting Lucene 2.9, following the change LUCENE-1542, we can
  79       // no longer reliably read the parent "-1" (see comment in
  80       // LuceneTaxonomyWriter.SinglePositionTokenStream). We have no way
  81       // to fix this in indexing without breaking backward-compatibility
  82       // with existing indexes, so what we'll do instead is just
  83       // hard-code the parent of ordinal 0 to be -1, and assume (as is
  84       // indeed the case) that no other parent can be -1.
  85       if (num>0) {
  86         prefetchParentOrdinal[0] = TaxonomyReader.INVALID_ORDINAL;
  87       }
  88       first = 1;
  89     } else {
  90       first = prefetchParentOrdinal.length;
  91       if (first==num) {
  92         return; // nothing to do - no category was added
  93       }
  94       // In Java 6, we could just do Arrays.copyOf()...
  95       int[] newarray = new int[num];
  96       System.arraycopy(prefetchParentOrdinal, 0, newarray, 0,
  97           prefetchParentOrdinal.length);
  98       prefetchParentOrdinal = newarray;
  99     }
 100
 101     // Read the new part of the parents array from the positions:
 102     TermPositions positions = indexReader.termPositions(
 103         new Term(Consts.FIELD_PAYLOADS, Consts.PAYLOAD_PARENT));
 104     try {
 105       if (!positions.skipTo(first) && first < num) {
 106         throw new CorruptIndexException("Missing parent data for category " + first);
 107       }
 108       for (int i=first; i<num; i++) {
 109         // Note that we know positions.doc() >= i (this is an
 110         // invariant kept throughout this loop)
 111         if (positions.doc()==i) {
 112           if (positions.freq() == 0) { // shouldn't happen
 113             throw new CorruptIndexException(
 114                 "Missing parent data for category "+i);
 115           }
 116
 117           // TODO (Facet): keep a local (non-volatile) copy of the prefetchParentOrdinal
 118           // reference, because access to volatile reference is slower (?).
 119           // Note: The positions we get here are one less than the position
 120           // increment we added originally, so we get here the right numbers:
 121           prefetchParentOrdinal[i] = positions.nextPosition();
 122
 123           if (!positions.next()) {
 124             if ( i+1 < num ) {
 125               throw new CorruptIndexException(
 126                   "Missing parent data for category "+(i+1));
 127             }
 128             break;
 129           }
 130         } else { // this shouldn't happen
 131           throw new CorruptIndexException(
 132               "Missing parent data for category "+i);
 133         }
 134       }
 135     } finally {
 136       positions.close(); // to be on the safe side.
 137     }
 138   }
 139
 140   /**
 141    * add() is used in LuceneTaxonomyWriter, not in LuceneTaxonomyReader.
 142    * It is only called from a synchronized method, so it is not reentrant,
 143    * and also doesn't need to worry about reads happening at the same time.
 144    *
 145    * NOTE: add() and refresh() CANNOT be used together. If you call add(),
 146    * this changes the arrays and refresh() can no longer be used.
 147    */
 148   void add(int ordinal, int parentOrdinal) throws IOException {
 149     if (ordinal >= prefetchParentOrdinal.length) {
 150       // grow the array, if necessary.
 151       // In Java 6, we could just do Arrays.copyOf()...
 152       int[] newarray = new int[ordinal*2+1];
 153       System.arraycopy(prefetchParentOrdinal, 0, newarray, 0,
 154           prefetchParentOrdinal.length);
 155       prefetchParentOrdinal = newarray;
 156     }
 157     prefetchParentOrdinal[ordinal] = parentOrdinal;
 158   }
 159
 160 }