+++ /dev/null
-/**
- * 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.
- */
-
-package org.apache.lucene.search.grouping;
-
-import java.util.Arrays;
-
-/** A native int set where one value is reserved to mean "EMPTY" */
-class SentinelIntSet {
- public int[] keys;
- public int count;
- public final int emptyVal;
- public int rehashCount; // the count at which a rehash should be done
-
- public SentinelIntSet(int size, int emptyVal) {
- this.emptyVal = emptyVal;
- int tsize = Math.max(org.apache.lucene.util.BitUtil.nextHighestPowerOfTwo(size), 1);
- rehashCount = tsize - (tsize>>2);
- if (size >= rehashCount) { // should be able to hold "size" w/o rehashing
- tsize <<= 1;
- rehashCount = tsize - (tsize>>2);
- }
- keys = new int[tsize];
- if (emptyVal != 0)
- clear();
- }
-
- public void clear() {
- Arrays.fill(keys, emptyVal);
- count = 0;
- }
-
- public int hash(int key) {
- return key;
- }
-
- public int size() { return count; }
-
- /** returns the slot for this key */
- public int getSlot(int key) {
- assert key != emptyVal;
- int h = hash(key);
- int s = h & (keys.length-1);
- if (keys[s] == key || keys[s]== emptyVal) return s;
-
- int increment = (h>>7)|1;
- do {
- s = (s + increment) & (keys.length-1);
- } while (keys[s] != key && keys[s] != emptyVal);
- return s;
- }
-
- /** returns the slot for this key, or -slot-1 if not found */
- public int find(int key) {
- assert key != emptyVal;
- int h = hash(key);
- int s = h & (keys.length-1);
- if (keys[s] == key) return s;
- if (keys[s] == emptyVal) return -s-1;
-
- int increment = (h>>7)|1;
- for(;;) {
- s = (s + increment) & (keys.length-1);
- if (keys[s] == key) return s;
- if (keys[s] == emptyVal) return -s-1;
- }
- }
-
- public boolean exists(int key) {
- return find(key) >= 0;
- }
-
- public int put(int key) {
- int s = find(key);
- if (s < 0) {
- if (count >= rehashCount) {
- rehash();
- s = getSlot(key);
- } else {
- s = -s-1;
- }
- count++;
- keys[s] = key;
- }
- return s;
- }
-
- public void rehash() {
- int newSize = keys.length << 1;
- int[] oldKeys = keys;
- keys = new int[newSize];
- if (emptyVal != 0) Arrays.fill(keys, emptyVal);
-
- for (int i=0; i<oldKeys.length; i++) {
- int key = oldKeys[i];
- if (key == emptyVal) continue;
- int newSlot = getSlot(key);
- keys[newSlot] = key;
- }
- rehashCount = newSize - (newSize>>2);
- }
-}