001: /**
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */package org.apache.solr.util;
017:
018: import java.util.Arrays;
019: import java.io.Serializable;
020:
021: /** An "open" BitSet implementation that allows direct access to the array of words
022: * storing the bits.
023: * <p/>
024: * Unlike java.util.bitet, the fact that bits are packed into an array of longs
025: * is part of the interface. This allows efficient implementation of other algorithms
026: * by someone other than the author. It also allows one to efficiently implement
027: * alternate serialization or interchange formats.
028: * <p/>
029: * <code>OpenBitSet</code> is faster than <code>java.util.BitSet</code> in most operations
030: * and *much* faster at calculating cardinality of sets and results of set operations.
031: * It can also handle sets of larger cardinality (up to 64 * 2**32-1)
032: * <p/>
033: * The goals of <code>OpenBitSet</code> are the fastest implementation possible, and
034: * maximum code reuse. Extra safety and encapsulation
035: * may always be built on top, but if that's built in, the cost can never be removed (and
036: * hence people re-implement their own version in order to get better performance).
037: * If you want a "safe", totally encapsulated (and slower and limited) BitSet
038: * class, use <code>java.util.BitSet</code>.
039: * <p/>
040: * <h3>Performance Results</h3>
041: *
042: Test system: Pentium 4, Sun Java 1.5_06 -server -Xbatch -Xmx64M
043: <br/>BitSet size = 1,000,000
044: <br/>Results are java.util.BitSet time divided by OpenBitSet time.
045: <table border="1">
046: <tr>
047: <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
048: </tr>
049: <tr>
050: <th>50% full</th> <td>3.36</td> <td>3.96</td> <td>1.44</td> <td>1.46</td> <td>1.99</td> <td>1.58</td>
051: </tr>
052: <tr>
053: <th>1% full</th> <td>3.31</td> <td>3.90</td> <td> </td> <td>1.04</td> <td> </td> <td>0.99</td>
054: </tr>
055: </table>
056: <br/>
057: Test system: AMD Opteron, 64 bit linux, Sun Java 1.5_06 -server -Xbatch -Xmx64M
058: <br/>BitSet size = 1,000,000
059: <br/>Results are java.util.BitSet time divided by OpenBitSet time.
060: <table border="1">
061: <tr>
062: <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
063: </tr>
064: <tr>
065: <th>50% full</th> <td>2.50</td> <td>3.50</td> <td>1.00</td> <td>1.03</td> <td>1.12</td> <td>1.25</td>
066: </tr>
067: <tr>
068: <th>1% full</th> <td>2.51</td> <td>3.49</td> <td> </td> <td>1.00</td> <td> </td> <td>1.02</td>
069: </tr>
070: </table>
071:
072: * @author yonik
073: * @version $Id$
074: */
075:
076: public class OpenBitSet implements Cloneable, Serializable {
077: protected long[] bits;
078: protected int wlen; // number of words (elements) used in the array
079:
080: /** Constructs an OpenBitSet large enough to hold numBits.
081: *
082: * @param numBits
083: */
084: public OpenBitSet(long numBits) {
085: bits = new long[bits2words(numBits)];
086: wlen = bits.length;
087: }
088:
089: public OpenBitSet() {
090: this (64);
091: }
092:
093: /** Constructs an OpenBitSet from an existing long[].
094: * <br/>
095: * The first 64 bits are in long[0],
096: * with bit index 0 at the least significant bit, and bit index 63 at the most significant.
097: * Given a bit index,
098: * the word containing it is long[index/64], and it is at bit number index%64 within that word.
099: * <p>
100: * numWords are the number of elements in the array that contain
101: * set bits (non-zero longs).
102: * numWords should be <= bits.length, and
103: * any existing words in the array at position >= numWords should be zero.
104: *
105: */
106: public OpenBitSet(long[] bits, int numWords) {
107: this .bits = bits;
108: this .wlen = numWords;
109: }
110:
111: /** Returns the current capacity in bits (1 greater than the index of the last bit) */
112: public long capacity() {
113: return bits.length << 6;
114: }
115:
116: /**
117: * Returns the current capacity of this set. Included for
118: * compatibility. This is *not* equal to {@link #cardinality}
119: */
120: public long size() {
121: return capacity();
122: }
123:
124: /** Returns true if there are no set bits */
125: public boolean isEmpty() {
126: return cardinality() == 0;
127: }
128:
129: /** Expert: returns the long[] storing the bits */
130: public long[] getBits() {
131: return bits;
132: }
133:
134: /** Expert: sets a new long[] to use as the bit storage */
135: public void setBits(long[] bits) {
136: this .bits = bits;
137: }
138:
139: /** Expert: gets the number of longs in the array that are in use */
140: public int getNumWords() {
141: return wlen;
142: }
143:
144: /** Expert: sets the number of longs in the array that are in use */
145: public void setNumWords(int nWords) {
146: this .wlen = nWords;
147: }
148:
149: /** Returns true or false for the specified bit index. */
150: public boolean get(int index) {
151: int i = index >> 6; // div 64
152: // signed shift will keep a negative index and force an
153: // array-index-out-of-bounds-exception, removing the need for an explicit check.
154: if (i >= bits.length)
155: return false;
156:
157: int bit = index & 0x3f; // mod 64
158: long bitmask = 1L << bit;
159: return (bits[i] & bitmask) != 0;
160: }
161:
162: /** Returns true or false for the specified bit index.
163: * The index should be less than the OpenBitSet size
164: */
165: public boolean fastGet(int index) {
166: int i = index >> 6; // div 64
167: // signed shift will keep a negative index and force an
168: // array-index-out-of-bounds-exception, removing the need for an explicit check.
169: int bit = index & 0x3f; // mod 64
170: long bitmask = 1L << bit;
171: return (bits[i] & bitmask) != 0;
172: }
173:
174: /** Returns true or false for the specified bit index
175: * The index should be less than the OpenBitSet size
176: */
177: public boolean get(long index) {
178: int i = (int) (index >> 6); // div 64
179: if (i >= bits.length)
180: return false;
181: int bit = (int) index & 0x3f; // mod 64
182: long bitmask = 1L << bit;
183: return (bits[i] & bitmask) != 0;
184: }
185:
186: /** Returns true or false for the specified bit index. Allows specifying
187: * an index outside the current size. */
188: public boolean fastGet(long index) {
189: int i = (int) (index >> 6); // div 64
190: int bit = (int) index & 0x3f; // mod 64
191: long bitmask = 1L << bit;
192: return (bits[i] & bitmask) != 0;
193: }
194:
195: /*
196: // alternate implementation of get()
197: public boolean get1(int index) {
198: int i = index >> 6; // div 64
199: int bit = index & 0x3f; // mod 64
200: return ((bits[i]>>>bit) & 0x01) != 0;
201: // this does a long shift and a bittest (on x86) vs
202: // a long shift, and a long AND, (the test for zero is prob a no-op)
203: // testing on a P4 indicates this is slower than (bits[i] & bitmask) != 0;
204: }
205: */
206:
207: /** returns 1 if the bit is set, 0 if not.
208: * The index should be less than the OpenBitSet size
209: */
210: public int getBit(int index) {
211: int i = index >> 6; // div 64
212: int bit = index & 0x3f; // mod 64
213: return ((int) (bits[i] >>> bit)) & 0x01;
214: }
215:
216: /*
217: public boolean get2(int index) {
218: int word = index >> 6; // div 64
219: int bit = index & 0x0000003f; // mod 64
220: return (bits[word] << bit) < 0; // hmmm, this would work if bit order were reversed
221: // we could right shift and check for parity bit, if it was available to us.
222: }
223: */
224:
225: /** sets a bit, expanding the set size if necessary */
226: public void set(long index) {
227: int wordNum = expandingWordNum(index);
228: int bit = (int) index & 0x3f;
229: long bitmask = 1L << bit;
230: bits[wordNum] |= bitmask;
231: }
232:
233: /** Sets the bit at the specified index.
234: * The index should be less than the OpenBitSet size.
235: */
236: public void fastSet(int index) {
237: int wordNum = index >> 6; // div 64
238: int bit = index & 0x3f; // mod 64
239: long bitmask = 1L << bit;
240: bits[wordNum] |= bitmask;
241: }
242:
243: /** Sets the bit at the specified index.
244: * The index should be less than the OpenBitSet size.
245: */
246: public void fastSet(long index) {
247: int wordNum = (int) (index >> 6);
248: int bit = (int) index & 0x3f;
249: long bitmask = 1L << bit;
250: bits[wordNum] |= bitmask;
251: }
252:
253: protected int expandingWordNum(long index) {
254: int wordNum = (int) (index >> 6);
255: if (wordNum >= wlen) {
256: ensureCapacity(index + 1);
257: wlen = wordNum + 1;
258: }
259: return wordNum;
260: }
261:
262: /** clears a bit.
263: * The index should be less than the OpenBitSet size.
264: */
265: public void fastClear(int index) {
266: int wordNum = index >> 6;
267: int bit = index & 0x03f;
268: long bitmask = 1L << bit;
269: bits[wordNum] &= ~bitmask;
270: // hmmm, it takes one more instruction to clear than it does to set... any
271: // way to work around this? If there were only 63 bits per word, we could
272: // use a right shift of 10111111...111 in binary to position the 0 in the
273: // correct place (using sign extension).
274: // Could also use Long.rotateRight() or rotateLeft() *if* they were converted
275: // by the JVM into a native instruction.
276: // bits[word] &= Long.rotateLeft(0xfffffffe,bit);
277: }
278:
279: /** clears a bit.
280: * The index should be less than the OpenBitSet size.
281: */
282: public void fastClear(long index) {
283: int wordNum = (int) (index >> 6); // div 64
284: int bit = (int) index & 0x3f; // mod 64
285: long bitmask = 1L << bit;
286: bits[wordNum] &= ~bitmask;
287: }
288:
289: /** clears a bit, allowing access beyond the current set size */
290: public void clear(long index) {
291: int wordNum = (int) (index >> 6); // div 64
292: if (wordNum >= wlen)
293: return;
294: int bit = (int) index & 0x3f; // mod 64
295: long bitmask = 1L << bit;
296: bits[wordNum] &= ~bitmask;
297: }
298:
299: /** Sets a bit and returns the previous value.
300: * The index should be less than the OpenBitSet size.
301: */
302: public boolean getAndSet(int index) {
303: int wordNum = index >> 6; // div 64
304: int bit = index & 0x3f; // mod 64
305: long bitmask = 1L << bit;
306: boolean val = (bits[wordNum] & bitmask) != 0;
307: bits[wordNum] |= bitmask;
308: return val;
309: }
310:
311: /** Sets a bit and returns the previous value.
312: * The index should be less than the OpenBitSet size.
313: */
314: public boolean getAndSet(long index) {
315: int wordNum = (int) (index >> 6); // div 64
316: int bit = (int) index & 0x3f; // mod 64
317: long bitmask = 1L << bit;
318: boolean val = (bits[wordNum] & bitmask) != 0;
319: bits[wordNum] |= bitmask;
320: return val;
321: }
322:
323: /** flips a bit.
324: * The index should be less than the OpenBitSet size.
325: */
326: public void fastFlip(int index) {
327: int wordNum = index >> 6; // div 64
328: int bit = index & 0x3f; // mod 64
329: long bitmask = 1L << bit;
330: bits[wordNum] ^= bitmask;
331: }
332:
333: /** flips a bit.
334: * The index should be less than the OpenBitSet size.
335: */
336: public void fastFlip(long index) {
337: int wordNum = (int) (index >> 6); // div 64
338: int bit = (int) index & 0x3f; // mod 64
339: long bitmask = 1L << bit;
340: bits[wordNum] ^= bitmask;
341: }
342:
343: /** flips a bit, expanding the set size if necessary */
344: public void flip(long index) {
345: int wordNum = expandingWordNum(index);
346: int bit = (int) index & 0x3f; // mod 64
347: long bitmask = 1L << bit;
348: bits[wordNum] ^= bitmask;
349: }
350:
351: /** flips a bit and returns the resulting bit value.
352: * The index should be less than the OpenBitSet size.
353: */
354: public boolean flipAndGet(int index) {
355: int wordNum = index >> 6; // div 64
356: int bit = index & 0x3f; // mod 64
357: long bitmask = 1L << bit;
358: bits[wordNum] ^= bitmask;
359: return (bits[wordNum] & bitmask) != 0;
360: }
361:
362: /** flips a bit and returns the resulting bit value.
363: * The index should be less than the OpenBitSet size.
364: */
365: public boolean flipAndGet(long index) {
366: int wordNum = (int) (index >> 6); // div 64
367: int bit = (int) index & 0x3f; // mod 64
368: long bitmask = 1L << bit;
369: bits[wordNum] ^= bitmask;
370: return (bits[wordNum] & bitmask) != 0;
371: }
372:
373: /** Flips a range of bits, expanding the set size if necessary
374: *
375: * @param startIndex lower index
376: * @param endIndex one-past the last bit to flip
377: */
378: public void flip(long startIndex, long endIndex) {
379: if (endIndex <= startIndex)
380: return;
381:
382: int oldlen = wlen;
383: ensureCapacity(endIndex);
384: int startWord = (int) (startIndex >> 6);
385: int endWord = (int) (endIndex >> 6);
386:
387: /*** Grrr, java shifting wraps around so -1L>>64 == -1
388: long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
389: long endmask = -1L >>> (64-(endIndex & 0x3f)); // example: 00111...111111
390: ***/
391:
392: long startmask = -1L << startIndex;
393: long endmask = (endIndex & 0x3f) == 0 ? 0
394: : -1L >>> (64 - endIndex);
395:
396: if (this .wlen <= endWord) {
397: this .wlen = endWord;
398: if (endmask != 0)
399: this .wlen++;
400: }
401:
402: if (startWord == endWord) {
403: bits[startWord] ^= (startmask & endmask);
404: return;
405: }
406:
407: bits[startWord] ^= startmask;
408:
409: int middle = Math.min(oldlen, endWord);
410: for (int i = startWord + 1; i < middle; i++) {
411: bits[i] = ~bits[i];
412: }
413:
414: if (endWord > middle) {
415: Arrays.fill(bits, middle, endWord, -1L);
416: }
417:
418: if (endmask != 0) {
419: bits[endWord] ^= endmask;
420: }
421: }
422:
423: /*
424: public static int pop(long v0, long v1, long v2, long v3) {
425: // derived from pop_array by setting last four elems to 0.
426: // exchanges one pop() call for 10 elementary operations
427: // saving about 7 instructions... is there a better way?
428: long twosA=v0 & v1;
429: long ones=v0^v1;
430:
431: long u2=ones^v2;
432: long twosB =(ones&v2)|(u2&v3);
433: ones=u2^v3;
434:
435: long fours=(twosA&twosB);
436: long twos=twosA^twosB;
437:
438: return (pop(fours)<<2)
439: + (pop(twos)<<1)
440: + pop(ones);
441:
442: }
443: */
444:
445: /** @return the number of set bits */
446: public long cardinality() {
447: return BitUtil.pop_array(bits, 0, wlen);
448: }
449:
450: /** Returns the popcount or cardinality of the intersection of the two sets.
451: * Neither set is modified.
452: */
453: public static long intersectionCount(OpenBitSet a, OpenBitSet b) {
454: return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(
455: a.wlen, b.wlen));
456: }
457:
458: /** Returns the popcount or cardinality of the union of the two sets.
459: * Neither set is modified.
460: */
461: public static long unionCount(OpenBitSet a, OpenBitSet b) {
462: long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(
463: a.wlen, b.wlen));
464: if (a.wlen < b.wlen) {
465: tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen - a.wlen);
466: } else if (a.wlen > b.wlen) {
467: tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen - b.wlen);
468: }
469: return tot;
470: }
471:
472: /** Returns the popcount or cardinality of "a and not b"
473: * or "intersection(a, not(b))".
474: * Neither set is modified.
475: */
476: public static long andNotCount(OpenBitSet a, OpenBitSet b) {
477: long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(
478: a.wlen, b.wlen));
479: if (a.wlen > b.wlen) {
480: tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen - b.wlen);
481: }
482: return tot;
483: }
484:
485: /** Returns the popcount or cardinality of the exclusive-or of the two sets.
486: * Neither set is modified.
487: */
488: public static long xorCount(OpenBitSet a, OpenBitSet b) {
489: long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen,
490: b.wlen));
491: if (a.wlen < b.wlen) {
492: tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen - a.wlen);
493: } else if (a.wlen > b.wlen) {
494: tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen - b.wlen);
495: }
496: return tot;
497: }
498:
499: /** Returns the index of the first set bit starting at the index specified.
500: * -1 is returned if there are no more set bits.
501: */
502: public int nextSetBit(int index) {
503: int i = index >> 6;
504: if (i >= wlen)
505: return -1;
506: int subIndex = index & 0x3f; // index within the word
507: long word = bits[i] >> subIndex; // skip all the bits to the right of index
508:
509: if (word != 0) {
510: return (i << 6) + subIndex + BitUtil.ntz(word);
511: }
512:
513: while (++i < wlen) {
514: word = bits[i];
515: if (word != 0)
516: return (i << 6) + BitUtil.ntz(word);
517: }
518:
519: return -1;
520: }
521:
522: /** Returns the index of the first set bit starting at the index specified.
523: * -1 is returned if there are no more set bits.
524: */
525: public long nextSetBit(long index) {
526: int i = (int) (index >>> 6);
527: if (i >= wlen)
528: return -1;
529: int subIndex = (int) index & 0x3f; // index within the word
530: long word = bits[i] >>> subIndex; // skip all the bits to the right of index
531:
532: if (word != 0) {
533: return (((long) i) << 6) + (subIndex + BitUtil.ntz(word));
534: }
535:
536: while (++i < wlen) {
537: word = bits[i];
538: if (word != 0)
539: return (((long) i) << 6) + BitUtil.ntz(word);
540: }
541:
542: return -1;
543: }
544:
545: public Object clone() {
546: try {
547: OpenBitSet obs = (OpenBitSet) super .clone();
548: obs.bits = obs.bits.clone(); // hopefully an array clone is as fast(er) than arraycopy
549: return obs;
550: } catch (CloneNotSupportedException e) {
551: throw new RuntimeException(e);
552: }
553: }
554:
555: /** this = this AND other */
556: public void intersect(OpenBitSet other) {
557: int newLen = Math.min(this .wlen, other.wlen);
558: long[] this Arr = this .bits;
559: long[] otherArr = other.bits;
560: // testing against zero can be more efficient
561: int pos = newLen;
562: while (--pos >= 0) {
563: this Arr[pos] &= otherArr[pos];
564: }
565: if (this .wlen > newLen) {
566: // fill zeros from the new shorter length to the old length
567: Arrays.fill(bits, newLen, this .wlen, 0);
568: }
569: this .wlen = newLen;
570: }
571:
572: /** this = this OR other */
573: public void union(OpenBitSet other) {
574: int newLen = Math.max(wlen, other.wlen);
575: ensureCapacityWords(newLen);
576:
577: long[] this Arr = this .bits;
578: long[] otherArr = other.bits;
579: int pos = Math.min(wlen, other.wlen);
580: while (--pos >= 0) {
581: this Arr[pos] |= otherArr[pos];
582: }
583: if (this .wlen < newLen) {
584: System.arraycopy(otherArr, this .wlen, this Arr, this .wlen,
585: newLen - this .wlen);
586: }
587: this .wlen = newLen;
588: }
589:
590: /** Remove all elements set in other. this = this AND_NOT other */
591: public void remove(OpenBitSet other) {
592: int idx = Math.min(wlen, other.wlen);
593: long[] this Arr = this .bits;
594: long[] otherArr = other.bits;
595: while (--idx >= 0) {
596: this Arr[idx] &= ~otherArr[idx];
597: }
598: }
599:
600: /** this = this XOR other */
601: public void xor(OpenBitSet other) {
602: int newLen = Math.max(wlen, other.wlen);
603: ensureCapacityWords(newLen);
604:
605: long[] this Arr = this .bits;
606: long[] otherArr = other.bits;
607: int pos = Math.min(wlen, other.wlen);
608: while (--pos >= 0) {
609: this Arr[pos] ^= otherArr[pos];
610: }
611: if (this .wlen < newLen) {
612: System.arraycopy(otherArr, this .wlen, this Arr, this .wlen,
613: newLen - this .wlen);
614: }
615: this .wlen = newLen;
616: }
617:
618: // some BitSet compatability methods
619:
620: //** see {@link intersect} */
621: public void and(OpenBitSet other) {
622: intersect(other);
623: }
624:
625: //** see {@link union} */
626: public void or(OpenBitSet other) {
627: union(other);
628: }
629:
630: //** see {@link andNot} */
631: public void andNot(OpenBitSet other) {
632: remove(other);
633: }
634:
635: /** returns true if the sets have any elements in common */
636: public boolean intersects(OpenBitSet other) {
637: int pos = Math.min(this .wlen, other.wlen);
638: long[] this Arr = this .bits;
639: long[] otherArr = other.bits;
640: while (--pos >= 0) {
641: if ((this Arr[pos] & otherArr[pos]) != 0)
642: return true;
643: }
644: return false;
645: }
646:
647: /** Expand the long[] with the size given as a number of words (64 bit longs).
648: * getNumWords() is unchanged by this call.
649: */
650: public void ensureCapacityWords(int numWords) {
651: if (bits.length < numWords) {
652: long[] newBits = new long[numWords];
653: System.arraycopy(bits, 0, newBits, 0, wlen);
654: bits = newBits;
655: }
656: }
657:
658: /** Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
659: * getNumWords() is unchanged by this call.
660: */
661: public void ensureCapacity(long numBits) {
662: ensureCapacityWords(bits2words(numBits));
663: }
664:
665: /** Lowers numWords, the number of words in use,
666: * by checking for trailing zero words.
667: */
668: public void trimTrailingZeros() {
669: int idx = wlen - 1;
670: while (idx >= 0 && bits[idx] == 0)
671: idx--;
672: wlen = idx + 1;
673: }
674:
675: /** returns the number of 64 bit words it would take to hold numBits */
676: public static int bits2words(long numBits) {
677: return (int) (((numBits - 1) >>> 6) + 1);
678: }
679:
680: /** returns true if both sets have the same bits set */
681: public boolean equals(Object o) {
682: if (this == o)
683: return true;
684: if (!(o instanceof OpenBitSet))
685: return false;
686: OpenBitSet a;
687: OpenBitSet b = (OpenBitSet) o;
688: // make a the larger set.
689: if (b.wlen > this .wlen) {
690: a = b;
691: b = this ;
692: } else {
693: a = this ;
694: }
695:
696: // check for any set bits out of the range of b
697: for (int i = a.wlen - 1; i >= b.wlen; i--) {
698: if (a.bits[i] != 0)
699: return false;
700: }
701:
702: for (int i = b.wlen - 1; i >= 0; i--) {
703: if (a.bits[i] != b.bits[i])
704: return false;
705: }
706:
707: return true;
708: }
709:
710: public int hashCode() {
711: long h = 0x98761234; // something non-zero for length==0
712: for (int i = bits.length; --i >= 0;) {
713: h ^= bits[i];
714: h = (h << 1) | (h >>> 31); // rotate left
715: }
716: return (int) ((h >> 32) ^ h); // fold leftmost bits into right
717: }
718:
719: }
|