--- /dev/null
+package org.apache.lucene.facet.taxonomy.writercache.cl2o;
+
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * HashMap to store colliding labels. See {@link CompactLabelToOrdinal} for
+ * details.
+ *
+ * @lucene.experimental
+ */
+public class CollisionMap {
+
+ private int capacity;
+ private float loadFactor;
+ private int size;
+ private int threshold;
+
+ static class Entry {
+ int offset;
+ int cid;
+ Entry next;
+ int hash;
+
+ Entry(int offset, int cid, int h, Entry e) {
+ this.offset = offset;
+ this.cid = cid;
+ this.next = e;
+ this.hash = h;
+ }
+ }
+
+ private CharBlockArray labelRepository;
+
+ private Entry[] entries;
+
+ public CollisionMap(CharBlockArray labelRepository) {
+ this(16 * 1024, 0.75f, labelRepository);
+ }
+
+ public CollisionMap(int initialCapacity, CharBlockArray labelRepository) {
+ this(initialCapacity, 0.75f, labelRepository);
+ }
+
+ private CollisionMap(int initialCapacity, float loadFactor, CharBlockArray labelRepository) {
+ this.labelRepository = labelRepository;
+ this.loadFactor = loadFactor;
+ this.capacity = CompactLabelToOrdinal.determineCapacity(2, initialCapacity);
+
+ this.entries = new Entry[this.capacity];
+ this.threshold = (int) (this.capacity * this.loadFactor);
+ }
+
+ public int size() {
+ return this.size;
+ }
+
+ public int capacity() {
+ return this.capacity;
+ }
+
+ private void grow() {
+ int newCapacity = this.capacity * 2;
+ Entry[] newEntries = new Entry[newCapacity];
+ Entry[] src = this.entries;
+
+ for (int j = 0; j < src.length; j++) {
+ Entry e = src[j];
+ if (e != null) {
+ src[j] = null;
+ do {
+ Entry next = e.next;
+ int hash = e.hash;
+ int i = indexFor(hash, newCapacity);
+ e.next = newEntries[i];
+ newEntries[i] = e;
+ e = next;
+ } while (e != null);
+ }
+ }
+
+ this.capacity = newCapacity;
+ this.entries = newEntries;
+ this.threshold = (int) (this.capacity * this.loadFactor);
+ }
+
+ public int get(CategoryPath label, int hash) {
+ int bucketIndex = indexFor(hash, this.capacity);
+ Entry e = this.entries[bucketIndex];
+
+ while (e != null && !(hash == e.hash && label.equalsToSerialized(this.labelRepository, e.offset))) {
+ e = e.next;
+ }
+ if (e == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ return e.cid;
+ }
+
+ public int get(CategoryPath label, int prefixLen, int hash) {
+ int bucketIndex = indexFor(hash, this.capacity);
+ Entry e = this.entries[bucketIndex];
+
+ while (e != null && !(hash == e.hash && label.equalsToSerialized(prefixLen, this.labelRepository, e.offset))) {
+ e = e.next;
+ }
+ if (e == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ return e.cid;
+ }
+
+ public int addLabel(CategoryPath label, int hash, int cid) {
+ int bucketIndex = indexFor(hash, this.capacity);
+ for (Entry e = this.entries[bucketIndex]; e != null; e = e.next) {
+ if (e.hash == hash && label.equalsToSerialized(this.labelRepository, e.offset)) {
+ return e.cid;
+ }
+ }
+
+ // new string; add to label repository
+ int offset = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(labelRepository);
+ } catch (IOException e) {
+ // can't happen, because labelRepository.append() doesn't throw an exception
+ }
+
+ addEntry(offset, cid, hash, bucketIndex);
+ return cid;
+ }
+
+ public int addLabel(CategoryPath label, int prefixLen, int hash, int cid) {
+ int bucketIndex = indexFor(hash, this.capacity);
+ for (Entry e = this.entries[bucketIndex]; e != null; e = e.next) {
+ if (e.hash == hash && label.equalsToSerialized(prefixLen, this.labelRepository, e.offset)) {
+ return e.cid;
+ }
+ }
+
+ // new string; add to label repository
+ int offset = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(prefixLen, labelRepository);
+ } catch (IOException e) {
+ // can't happen, because labelRepository.append() doesn't throw an exception
+ }
+
+ addEntry(offset, cid, hash, bucketIndex);
+ return cid;
+ }
+
+ /**
+ * This method does not check if the same value is already
+ * in the map because we pass in an char-array offset, so
+ * so we now that we're in resize-mode here.
+ */
+ public void addLabelOffset(int hash, int offset, int cid) {
+ int bucketIndex = indexFor(hash, this.capacity);
+ addEntry(offset, cid, hash, bucketIndex);
+ }
+
+ private void addEntry(int offset, int cid, int hash, int bucketIndex) {
+ Entry e = this.entries[bucketIndex];
+ this.entries[bucketIndex] = new Entry(offset, cid, hash, e);
+ if (this.size++ >= this.threshold) {
+ grow();
+ }
+ }
+
+ Iterator<CollisionMap.Entry> entryIterator() {
+ return new EntryIterator(entries, size);
+ }
+
+ /**
+ * Returns index for hash code h.
+ */
+ static int indexFor(int h, int length) {
+ return h & (length - 1);
+ }
+
+ /**
+ * Returns an estimate of the memory usage of this CollisionMap.
+ * @return The approximate number of bytes used by this structure.
+ */
+ int getMemoryUsage() {
+ int memoryUsage = 0;
+ if (this.entries != null) {
+ for (Entry e : this.entries) {
+ if (e != null) {
+ memoryUsage += (4 * 4);
+ for (Entry ee = e.next; ee != null; ee = ee.next) {
+ memoryUsage += (4 * 4);
+ }
+ }
+ }
+ }
+ return memoryUsage;
+ }
+
+ private class EntryIterator implements Iterator<Entry> {
+ Entry next; // next entry to return
+ int index; // current slot
+ Entry[] ents;
+
+ EntryIterator(Entry[] entries, int size) {
+ this.ents = entries;
+ Entry[] t = entries;
+ int i = t.length;
+ Entry n = null;
+ if (size != 0) { // advance to first entry
+ while (i > 0 && (n = t[--i]) == null) {
+ // advance
+ }
+ }
+ this.next = n;
+ this.index = i;
+ }
+
+ public boolean hasNext() {
+ return this.next != null;
+ }
+
+ public Entry next() {
+ Entry e = this.next;
+ if (e == null) throw new NoSuchElementException();
+
+ Entry n = e.next;
+ Entry[] t = ents;
+ int i = this.index;
+ while (n == null && i > 0) {
+ n = t[--i];
+ }
+ this.index = i;
+ this.next = n;
+ return e;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+}
fnp / pylucene.git / blobdiff