lucene-java-3.4.0/lucene/contrib/facet/src/java/org/apache/lucene/facet/taxonomy/writercache/cl2o/CollisionMap.java

   1 package org.apache.lucene.facet.taxonomy.writercache.cl2o;
   2
   3 import java.io.IOException;
   4 import java.util.Iterator;
   5 import java.util.NoSuchElementException;
   6
   7 import org.apache.lucene.facet.taxonomy.CategoryPath;
   8
   9 /**
  10  * Licensed to the Apache Software Foundation (ASF) under one or more
  11  * contributor license agreements.  See the NOTICE file distributed with
  12  * this work for additional information regarding copyright ownership.
  13  * The ASF licenses this file to You under the Apache License, Version 2.0
  14  * (the "License"); you may not use this file except in compliance with
  15  * the License.  You may obtain a copy of the License at
  16  *
  17  *     http://www.apache.org/licenses/LICENSE-2.0
  18  *
  19  * Unless required by applicable law or agreed to in writing, software
  20  * distributed under the License is distributed on an "AS IS" BASIS,
  21  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  22  * See the License for the specific language governing permissions and
  23  * limitations under the License.
  24  */
  25
  26 /**
  27  * HashMap to store colliding labels. See {@link CompactLabelToOrdinal} for
  28  * details.
  29  *
  30  * @lucene.experimental
  31  */
  32 public class CollisionMap {
  33
  34   private int capacity;
  35   private float loadFactor;
  36   private int size;
  37   private int threshold;
  38
  39   static class Entry {
  40     int offset;
  41     int cid;
  42     Entry next;
  43     int hash;
  44
  45     Entry(int offset, int cid, int h, Entry e) {
  46       this.offset = offset;
  47       this.cid = cid;
  48       this.next = e;
  49       this.hash = h;
  50     }
  51   }
  52
  53   private CharBlockArray labelRepository;
  54
  55   private Entry[] entries;
  56
  57   public CollisionMap(CharBlockArray labelRepository) {
  58     this(16 * 1024, 0.75f, labelRepository);
  59   }
  60
  61   public CollisionMap(int initialCapacity, CharBlockArray labelRepository) {
  62     this(initialCapacity, 0.75f, labelRepository);
  63   }
  64
  65   private CollisionMap(int initialCapacity, float loadFactor, CharBlockArray labelRepository) {
  66     this.labelRepository = labelRepository;
  67     this.loadFactor = loadFactor;
  68     this.capacity = CompactLabelToOrdinal.determineCapacity(2, initialCapacity);
  69
  70     this.entries = new Entry[this.capacity];
  71     this.threshold = (int) (this.capacity * this.loadFactor);
  72   }
  73
  74   public int size() {
  75     return this.size;
  76   }
  77
  78   public int capacity() {
  79     return this.capacity;
  80   }
  81
  82   private void grow() {
  83     int newCapacity = this.capacity * 2;
  84     Entry[] newEntries = new Entry[newCapacity];
  85     Entry[] src = this.entries;
  86
  87     for (int j = 0; j < src.length; j++) {
  88       Entry e = src[j];
  89       if (e != null) {
  90         src[j] = null;
  91         do {
  92           Entry next = e.next;
  93           int hash = e.hash;
  94           int i = indexFor(hash, newCapacity);
  95           e.next = newEntries[i];
  96           newEntries[i] = e;
  97           e = next;
  98         } while (e != null);
  99       }
 100     }
 101
 102     this.capacity = newCapacity;
 103     this.entries = newEntries;
 104     this.threshold = (int) (this.capacity * this.loadFactor);
 105   }
 106
 107   public int get(CategoryPath label, int hash) {
 108     int bucketIndex = indexFor(hash, this.capacity);
 109     Entry e = this.entries[bucketIndex];
 110
 111     while (e != null && !(hash == e.hash && label.equalsToSerialized(this.labelRepository, e.offset))) {
 112       e = e.next;
 113     }
 114     if (e == null) {
 115       return LabelToOrdinal.InvalidOrdinal;
 116     }
 117
 118     return e.cid;
 119   }
 120
 121   public int get(CategoryPath label, int prefixLen, int hash) {
 122     int bucketIndex = indexFor(hash, this.capacity);
 123     Entry e = this.entries[bucketIndex];
 124
 125     while (e != null && !(hash == e.hash && label.equalsToSerialized(prefixLen, this.labelRepository, e.offset))) {
 126       e = e.next;
 127     }
 128     if (e == null) {
 129       return LabelToOrdinal.InvalidOrdinal;
 130     }
 131
 132     return e.cid;
 133   }
 134
 135   public int addLabel(CategoryPath label, int hash, int cid) {
 136     int bucketIndex = indexFor(hash, this.capacity);
 137     for (Entry e = this.entries[bucketIndex]; e != null; e = e.next) {
 138       if (e.hash == hash && label.equalsToSerialized(this.labelRepository, e.offset)) {
 139         return e.cid;
 140       }
 141     }
 142
 143     // new string; add to label repository
 144     int offset = this.labelRepository.length();
 145     try {
 146       label.serializeAppendTo(labelRepository);
 147     } catch (IOException e) {
 148       // can't happen, because labelRepository.append() doesn't throw an exception
 149     }
 150
 151     addEntry(offset, cid, hash, bucketIndex);
 152     return cid;
 153   }
 154
 155   public int addLabel(CategoryPath label, int prefixLen, int hash, int cid) {
 156     int bucketIndex = indexFor(hash, this.capacity);
 157     for (Entry e = this.entries[bucketIndex]; e != null; e = e.next) {
 158       if (e.hash == hash && label.equalsToSerialized(prefixLen, this.labelRepository, e.offset)) {
 159         return e.cid;
 160       }
 161     }
 162
 163     // new string; add to label repository
 164     int offset = this.labelRepository.length();
 165     try {
 166       label.serializeAppendTo(prefixLen, labelRepository);
 167     } catch (IOException e) {
 168       // can't happen, because labelRepository.append() doesn't throw an exception
 169     }
 170
 171     addEntry(offset, cid, hash, bucketIndex);
 172     return cid;
 173   }
 174
 175   /**
 176    * This method does not check if the same value is already
 177    * in the map because we pass in an char-array offset, so
 178    * so we now that we're in resize-mode here.
 179    */
 180   public void addLabelOffset(int hash, int offset, int cid) {
 181     int bucketIndex = indexFor(hash, this.capacity);
 182     addEntry(offset, cid, hash, bucketIndex);
 183   }
 184
 185   private void addEntry(int offset, int cid, int hash, int bucketIndex) {
 186     Entry e = this.entries[bucketIndex];
 187     this.entries[bucketIndex] = new Entry(offset, cid, hash, e);
 188     if (this.size++ >= this.threshold) {
 189       grow();
 190     }
 191   }
 192
 193   Iterator<CollisionMap.Entry> entryIterator() {
 194     return new EntryIterator(entries, size);
 195   }
 196
 197   /**
 198    * Returns index for hash code h.
 199    */
 200   static int indexFor(int h, int length) {
 201     return h & (length - 1);
 202   }
 203
 204   /**
 205    * Returns an estimate of the memory usage of this CollisionMap.
 206    * @return The approximate number of bytes used by this structure.
 207    */
 208   int getMemoryUsage() {
 209     int memoryUsage = 0;
 210     if (this.entries != null) {
 211       for (Entry e : this.entries) {
 212         if (e != null) {
 213           memoryUsage += (4 * 4);
 214           for (Entry ee = e.next; ee != null; ee = ee.next) {
 215             memoryUsage += (4 * 4);
 216           }
 217         }
 218       }
 219     }
 220     return memoryUsage;
 221   }
 222
 223   private class EntryIterator implements Iterator<Entry> {
 224     Entry next;    // next entry to return
 225     int index;        // current slot
 226     Entry[] ents;
 227
 228     EntryIterator(Entry[] entries, int size) {
 229       this.ents = entries;
 230       Entry[] t = entries;
 231       int i = t.length;
 232       Entry n = null;
 233       if (size != 0) { // advance to first entry
 234         while (i > 0 && (n = t[--i]) == null) {
 235           // advance
 236         }
 237       }
 238       this.next = n;
 239       this.index = i;
 240     }
 241
 242     public boolean hasNext() {
 243       return this.next != null;
 244     }
 245
 246     public Entry next() {
 247       Entry e = this.next;
 248       if (e == null) throw new NoSuchElementException();
 249
 250       Entry n = e.next;
 251       Entry[] t = ents;
 252       int i = this.index;
 253       while (n == null && i > 0) {
 254         n = t[--i];
 255       }
 256       this.index = i;
 257       this.next = n;
 258       return  e;
 259     }
 260
 261     public void remove() {
 262       throw new UnsupportedOperationException();
 263     }
 264
 265   }
 266
 267 }