1 package org.apache.lucene.facet.taxonomy.writercache.cl2o;
3 import java.io.IOException;
4 import java.util.Iterator;
5 import java.util.NoSuchElementException;
7 import org.apache.lucene.facet.taxonomy.CategoryPath;
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
17 * http://www.apache.org/licenses/LICENSE-2.0
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.
27 * HashMap to store colliding labels. See {@link CompactLabelToOrdinal} for
30 * @lucene.experimental
32 public class CollisionMap {
35 private float loadFactor;
37 private int threshold;
45 Entry(int offset, int cid, int h, Entry e) {
53 private CharBlockArray labelRepository;
55 private Entry[] entries;
57 public CollisionMap(CharBlockArray labelRepository) {
58 this(16 * 1024, 0.75f, labelRepository);
61 public CollisionMap(int initialCapacity, CharBlockArray labelRepository) {
62 this(initialCapacity, 0.75f, labelRepository);
65 private CollisionMap(int initialCapacity, float loadFactor, CharBlockArray labelRepository) {
66 this.labelRepository = labelRepository;
67 this.loadFactor = loadFactor;
68 this.capacity = CompactLabelToOrdinal.determineCapacity(2, initialCapacity);
70 this.entries = new Entry[this.capacity];
71 this.threshold = (int) (this.capacity * this.loadFactor);
78 public int capacity() {
83 int newCapacity = this.capacity * 2;
84 Entry[] newEntries = new Entry[newCapacity];
85 Entry[] src = this.entries;
87 for (int j = 0; j < src.length; j++) {
94 int i = indexFor(hash, newCapacity);
95 e.next = newEntries[i];
102 this.capacity = newCapacity;
103 this.entries = newEntries;
104 this.threshold = (int) (this.capacity * this.loadFactor);
107 public int get(CategoryPath label, int hash) {
108 int bucketIndex = indexFor(hash, this.capacity);
109 Entry e = this.entries[bucketIndex];
111 while (e != null && !(hash == e.hash && label.equalsToSerialized(this.labelRepository, e.offset))) {
115 return LabelToOrdinal.InvalidOrdinal;
121 public int get(CategoryPath label, int prefixLen, int hash) {
122 int bucketIndex = indexFor(hash, this.capacity);
123 Entry e = this.entries[bucketIndex];
125 while (e != null && !(hash == e.hash && label.equalsToSerialized(prefixLen, this.labelRepository, e.offset))) {
129 return LabelToOrdinal.InvalidOrdinal;
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)) {
143 // new string; add to label repository
144 int offset = this.labelRepository.length();
146 label.serializeAppendTo(labelRepository);
147 } catch (IOException e) {
148 // can't happen, because labelRepository.append() doesn't throw an exception
151 addEntry(offset, cid, hash, bucketIndex);
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)) {
163 // new string; add to label repository
164 int offset = this.labelRepository.length();
166 label.serializeAppendTo(prefixLen, labelRepository);
167 } catch (IOException e) {
168 // can't happen, because labelRepository.append() doesn't throw an exception
171 addEntry(offset, cid, hash, bucketIndex);
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.
180 public void addLabelOffset(int hash, int offset, int cid) {
181 int bucketIndex = indexFor(hash, this.capacity);
182 addEntry(offset, cid, hash, bucketIndex);
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) {
193 Iterator<CollisionMap.Entry> entryIterator() {
194 return new EntryIterator(entries, size);
198 * Returns index for hash code h.
200 static int indexFor(int h, int length) {
201 return h & (length - 1);
205 * Returns an estimate of the memory usage of this CollisionMap.
206 * @return The approximate number of bytes used by this structure.
208 int getMemoryUsage() {
210 if (this.entries != null) {
211 for (Entry e : this.entries) {
213 memoryUsage += (4 * 4);
214 for (Entry ee = e.next; ee != null; ee = ee.next) {
215 memoryUsage += (4 * 4);
223 private class EntryIterator implements Iterator<Entry> {
224 Entry next; // next entry to return
225 int index; // current slot
228 EntryIterator(Entry[] entries, int size) {
233 if (size != 0) { // advance to first entry
234 while (i > 0 && (n = t[--i]) == null) {
242 public boolean hasNext() {
243 return this.next != null;
246 public Entry next() {
248 if (e == null) throw new NoSuchElementException();
253 while (n == null && i > 0) {
261 public void remove() {
262 throw new UnsupportedOperationException();