http://git-wip-us.apache.org/repos/asf/hbase-site/blob/7ebe345d/apidocs/src-html/org/apache/hadoop/hbase/util/Bytes.ByteArrayComparator.html ---------------------------------------------------------------------- diff --git a/apidocs/src-html/org/apache/hadoop/hbase/util/Bytes.ByteArrayComparator.html b/apidocs/src-html/org/apache/hadoop/hbase/util/Bytes.ByteArrayComparator.html index dc85290..c15ed05 100644 --- a/apidocs/src-html/org/apache/hadoop/hbase/util/Bytes.ByteArrayComparator.html +++ b/apidocs/src-html/org/apache/hadoop/hbase/util/Bytes.ByteArrayComparator.html @@ -1518,1149 +1518,1104 @@ <span class="sourceLineNo">1510</span> }<a name="line.1510"></a> <span class="sourceLineNo">1511</span><a name="line.1511"></a> <span class="sourceLineNo">1512</span> /**<a name="line.1512"></a> -<span class="sourceLineNo">1513</span> * Returns true if x1 is less than x2, when both values are treated as<a name="line.1513"></a> -<span class="sourceLineNo">1514</span> * unsigned long.<a name="line.1514"></a> -<span class="sourceLineNo">1515</span> * Both values are passed as is read by Unsafe. When platform is Little Endian, have to<a name="line.1515"></a> -<span class="sourceLineNo">1516</span> * convert to corresponding Big Endian value and then do compare. We do all writes in<a name="line.1516"></a> -<span class="sourceLineNo">1517</span> * Big Endian format.<a name="line.1517"></a> -<span class="sourceLineNo">1518</span> */<a name="line.1518"></a> -<span class="sourceLineNo">1519</span> static boolean lessThanUnsignedLong(long x1, long x2) {<a name="line.1519"></a> -<span class="sourceLineNo">1520</span> if (UnsafeAccess.littleEndian) {<a name="line.1520"></a> -<span class="sourceLineNo">1521</span> x1 = Long.reverseBytes(x1);<a name="line.1521"></a> -<span class="sourceLineNo">1522</span> x2 = Long.reverseBytes(x2);<a name="line.1522"></a> -<span class="sourceLineNo">1523</span> }<a name="line.1523"></a> -<span class="sourceLineNo">1524</span> return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);<a name="line.1524"></a> -<span class="sourceLineNo">1525</span> }<a name="line.1525"></a> +<span class="sourceLineNo">1513</span> * Lexicographically compare two arrays.<a name="line.1513"></a> +<span class="sourceLineNo">1514</span> *<a name="line.1514"></a> +<span class="sourceLineNo">1515</span> * @param buffer1 left operand<a name="line.1515"></a> +<span class="sourceLineNo">1516</span> * @param buffer2 right operand<a name="line.1516"></a> +<span class="sourceLineNo">1517</span> * @param offset1 Where to start comparing in the left buffer<a name="line.1517"></a> +<span class="sourceLineNo">1518</span> * @param offset2 Where to start comparing in the right buffer<a name="line.1518"></a> +<span class="sourceLineNo">1519</span> * @param length1 How much to compare from the left buffer<a name="line.1519"></a> +<span class="sourceLineNo">1520</span> * @param length2 How much to compare from the right buffer<a name="line.1520"></a> +<span class="sourceLineNo">1521</span> * @return 0 if equal, < 0 if left is less than right, etc.<a name="line.1521"></a> +<span class="sourceLineNo">1522</span> */<a name="line.1522"></a> +<span class="sourceLineNo">1523</span> @Override<a name="line.1523"></a> +<span class="sourceLineNo">1524</span> public int compareTo(byte[] buffer1, int offset1, int length1,<a name="line.1524"></a> +<span class="sourceLineNo">1525</span> byte[] buffer2, int offset2, int length2) {<a name="line.1525"></a> <span class="sourceLineNo">1526</span><a name="line.1526"></a> -<span class="sourceLineNo">1527</span> /**<a name="line.1527"></a> -<span class="sourceLineNo">1528</span> * Returns true if x1 is less than x2, when both values are treated as<a name="line.1528"></a> -<span class="sourceLineNo">1529</span> * unsigned int.<a name="line.1529"></a> -<span class="sourceLineNo">1530</span> * Both values are passed as is read by Unsafe. When platform is Little Endian, have to<a name="line.1530"></a> -<span class="sourceLineNo">1531</span> * convert to corresponding Big Endian value and then do compare. We do all writes in<a name="line.1531"></a> -<span class="sourceLineNo">1532</span> * Big Endian format.<a name="line.1532"></a> -<span class="sourceLineNo">1533</span> */<a name="line.1533"></a> -<span class="sourceLineNo">1534</span> static boolean lessThanUnsignedInt(int x1, int x2) {<a name="line.1534"></a> -<span class="sourceLineNo">1535</span> if (UnsafeAccess.littleEndian) {<a name="line.1535"></a> -<span class="sourceLineNo">1536</span> x1 = Integer.reverseBytes(x1);<a name="line.1536"></a> -<span class="sourceLineNo">1537</span> x2 = Integer.reverseBytes(x2);<a name="line.1537"></a> -<span class="sourceLineNo">1538</span> }<a name="line.1538"></a> -<span class="sourceLineNo">1539</span> return (x1 & 0xffffffffL) < (x2 & 0xffffffffL);<a name="line.1539"></a> -<span class="sourceLineNo">1540</span> }<a name="line.1540"></a> -<span class="sourceLineNo">1541</span><a name="line.1541"></a> -<span class="sourceLineNo">1542</span> /**<a name="line.1542"></a> -<span class="sourceLineNo">1543</span> * Returns true if x1 is less than x2, when both values are treated as<a name="line.1543"></a> -<span class="sourceLineNo">1544</span> * unsigned short.<a name="line.1544"></a> -<span class="sourceLineNo">1545</span> * Both values are passed as is read by Unsafe. When platform is Little Endian, have to<a name="line.1545"></a> -<span class="sourceLineNo">1546</span> * convert to corresponding Big Endian value and then do compare. We do all writes in<a name="line.1546"></a> -<span class="sourceLineNo">1547</span> * Big Endian format.<a name="line.1547"></a> -<span class="sourceLineNo">1548</span> */<a name="line.1548"></a> -<span class="sourceLineNo">1549</span> static boolean lessThanUnsignedShort(short x1, short x2) {<a name="line.1549"></a> -<span class="sourceLineNo">1550</span> if (UnsafeAccess.littleEndian) {<a name="line.1550"></a> -<span class="sourceLineNo">1551</span> x1 = Short.reverseBytes(x1);<a name="line.1551"></a> -<span class="sourceLineNo">1552</span> x2 = Short.reverseBytes(x2);<a name="line.1552"></a> -<span class="sourceLineNo">1553</span> }<a name="line.1553"></a> -<span class="sourceLineNo">1554</span> return (x1 & 0xffff) < (x2 & 0xffff);<a name="line.1554"></a> -<span class="sourceLineNo">1555</span> }<a name="line.1555"></a> -<span class="sourceLineNo">1556</span><a name="line.1556"></a> -<span class="sourceLineNo">1557</span> /**<a name="line.1557"></a> -<span class="sourceLineNo">1558</span> * Lexicographically compare two arrays.<a name="line.1558"></a> -<span class="sourceLineNo">1559</span> *<a name="line.1559"></a> -<span class="sourceLineNo">1560</span> * @param buffer1 left operand<a name="line.1560"></a> -<span class="sourceLineNo">1561</span> * @param buffer2 right operand<a name="line.1561"></a> -<span class="sourceLineNo">1562</span> * @param offset1 Where to start comparing in the left buffer<a name="line.1562"></a> -<span class="sourceLineNo">1563</span> * @param offset2 Where to start comparing in the right buffer<a name="line.1563"></a> -<span class="sourceLineNo">1564</span> * @param length1 How much to compare from the left buffer<a name="line.1564"></a> -<span class="sourceLineNo">1565</span> * @param length2 How much to compare from the right buffer<a name="line.1565"></a> -<span class="sourceLineNo">1566</span> * @return 0 if equal, < 0 if left is less than right, etc.<a name="line.1566"></a> -<span class="sourceLineNo">1567</span> */<a name="line.1567"></a> -<span class="sourceLineNo">1568</span> @Override<a name="line.1568"></a> -<span class="sourceLineNo">1569</span> public int compareTo(byte[] buffer1, int offset1, int length1,<a name="line.1569"></a> -<span class="sourceLineNo">1570</span> byte[] buffer2, int offset2, int length2) {<a name="line.1570"></a> -<span class="sourceLineNo">1571</span><a name="line.1571"></a> -<span class="sourceLineNo">1572</span> // Short circuit equal case<a name="line.1572"></a> -<span class="sourceLineNo">1573</span> if (buffer1 == buffer2 &&<a name="line.1573"></a> -<span class="sourceLineNo">1574</span> offset1 == offset2 &&<a name="line.1574"></a> -<span class="sourceLineNo">1575</span> length1 == length2) {<a name="line.1575"></a> -<span class="sourceLineNo">1576</span> return 0;<a name="line.1576"></a> -<span class="sourceLineNo">1577</span> }<a name="line.1577"></a> -<span class="sourceLineNo">1578</span> final int stride = 8;<a name="line.1578"></a> -<span class="sourceLineNo">1579</span> final int minLength = Math.min(length1, length2);<a name="line.1579"></a> -<span class="sourceLineNo">1580</span> int strideLimit = minLength & ~(stride - 1);<a name="line.1580"></a> -<span class="sourceLineNo">1581</span> final long offset1Adj = offset1 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;<a name="line.1581"></a> -<span class="sourceLineNo">1582</span> final long offset2Adj = offset2 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;<a name="line.1582"></a> -<span class="sourceLineNo">1583</span> int i;<a name="line.1583"></a> -<span class="sourceLineNo">1584</span><a name="line.1584"></a> -<span class="sourceLineNo">1585</span> /*<a name="line.1585"></a> -<span class="sourceLineNo">1586</span> * Compare 8 bytes at a time. Benchmarking on x86 shows a stride of 8 bytes is no slower<a name="line.1586"></a> -<span class="sourceLineNo">1587</span> * than 4 bytes even on 32-bit. On the other hand, it is substantially faster on 64-bit.<a name="line.1587"></a> -<span class="sourceLineNo">1588</span> */<a name="line.1588"></a> -<span class="sourceLineNo">1589</span> for (i = 0; i < strideLimit; i += stride) {<a name="line.1589"></a> -<span class="sourceLineNo">1590</span> long lw = theUnsafe.getLong(buffer1, offset1Adj + (long) i);<a name="line.1590"></a> -<span class="sourceLineNo">1591</span> long rw = theUnsafe.getLong(buffer2, offset2Adj + (long) i);<a name="line.1591"></a> -<span class="sourceLineNo">1592</span> if (lw != rw) {<a name="line.1592"></a> -<span class="sourceLineNo">1593</span> if(!UnsafeAccess.littleEndian) {<a name="line.1593"></a> -<span class="sourceLineNo">1594</span> return ((lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE)) ? -1 : 1;<a name="line.1594"></a> -<span class="sourceLineNo">1595</span> }<a name="line.1595"></a> -<span class="sourceLineNo">1596</span><a name="line.1596"></a> -<span class="sourceLineNo">1597</span> /*<a name="line.1597"></a> -<span class="sourceLineNo">1598</span> * We want to compare only the first index where left[index] != right[index]. This<a name="line.1598"></a> -<span class="sourceLineNo">1599</span> * corresponds to the least significant nonzero byte in lw ^ rw, since lw and rw are<a name="line.1599"></a> -<span class="sourceLineNo">1600</span> * little-endian. Long.numberOfTrailingZeros(diff) tells us the least significant<a name="line.1600"></a> -<span class="sourceLineNo">1601</span> * nonzero bit, and zeroing out the first three bits of L.nTZ gives us the shift to get<a name="line.1601"></a> -<span class="sourceLineNo">1602</span> * that least significant nonzero byte. This comparison logic is based on UnsignedBytes<a name="line.1602"></a> -<span class="sourceLineNo">1603</span> * comparator from guava v21<a name="line.1603"></a> -<span class="sourceLineNo">1604</span> */<a name="line.1604"></a> -<span class="sourceLineNo">1605</span> int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7;<a name="line.1605"></a> -<span class="sourceLineNo">1606</span> return ((int) ((lw >>> n) & 0xFF)) - ((int) ((rw >>> n) & 0xFF));<a name="line.1606"></a> -<span class="sourceLineNo">1607</span> }<a name="line.1607"></a> -<span class="sourceLineNo">1608</span> }<a name="line.1608"></a> -<span class="sourceLineNo">1609</span><a name="line.1609"></a> -<span class="sourceLineNo">1610</span> // The epilogue to cover the last (minLength % stride) elements.<a name="line.1610"></a> -<span class="sourceLineNo">1611</span> for (; i < minLength; i++) {<a name="line.1611"></a> -<span class="sourceLineNo">1612</span> int a = (buffer1[offset1 + i] & 0xFF);<a name="line.1612"></a> -<span class="sourceLineNo">1613</span> int b = (buffer2[offset2 + i] & 0xFF);<a name="line.1613"></a> -<span class="sourceLineNo">1614</span> if (a != b) {<a name="line.1614"></a> -<span class="sourceLineNo">1615</span> return a - b;<a name="line.1615"></a> -<span class="sourceLineNo">1616</span> }<a name="line.1616"></a> -<span class="sourceLineNo">1617</span> }<a name="line.1617"></a> -<span class="sourceLineNo">1618</span> return length1 - length2;<a name="line.1618"></a> -<span class="sourceLineNo">1619</span> }<a name="line.1619"></a> -<span class="sourceLineNo">1620</span> }<a name="line.1620"></a> -<span class="sourceLineNo">1621</span> }<a name="line.1621"></a> -<span class="sourceLineNo">1622</span><a name="line.1622"></a> -<span class="sourceLineNo">1623</span> /**<a name="line.1623"></a> -<span class="sourceLineNo">1624</span> * @param left left operand<a name="line.1624"></a> -<span class="sourceLineNo">1625</span> * @param right right operand<a name="line.1625"></a> -<span class="sourceLineNo">1626</span> * @return True if equal<a name="line.1626"></a> -<span class="sourceLineNo">1627</span> */<a name="line.1627"></a> -<span class="sourceLineNo">1628</span> public static boolean equals(final byte [] left, final byte [] right) {<a name="line.1628"></a> -<span class="sourceLineNo">1629</span> // Could use Arrays.equals?<a name="line.1629"></a> -<span class="sourceLineNo">1630</span> //noinspection SimplifiableConditionalExpression<a name="line.1630"></a> -<span class="sourceLineNo">1631</span> if (left == right) return true;<a name="line.1631"></a> -<span class="sourceLineNo">1632</span> if (left == null || right == null) return false;<a name="line.1632"></a> -<span class="sourceLineNo">1633</span> if (left.length != right.length) return false;<a name="line.1633"></a> -<span class="sourceLineNo">1634</span> if (left.length == 0) return true;<a name="line.1634"></a> -<span class="sourceLineNo">1635</span><a name="line.1635"></a> -<span class="sourceLineNo">1636</span> // Since we're often comparing adjacent sorted data,<a name="line.1636"></a> -<span class="sourceLineNo">1637</span> // it's usual to have equal arrays except for the very last byte<a name="line.1637"></a> -<span class="sourceLineNo">1638</span> // so check that first<a name="line.1638"></a> -<span class="sourceLineNo">1639</span> if (left[left.length - 1] != right[right.length - 1]) return false;<a name="line.1639"></a> -<span class="sourceLineNo">1640</span><a name="line.1640"></a> -<span class="sourceLineNo">1641</span> return compareTo(left, right) == 0;<a name="line.1641"></a> -<span class="sourceLineNo">1642</span> }<a name="line.1642"></a> -<span class="sourceLineNo">1643</span><a name="line.1643"></a> -<span class="sourceLineNo">1644</span> public static boolean equals(final byte[] left, int leftOffset, int leftLen,<a name="line.1644"></a> -<span class="sourceLineNo">1645</span> final byte[] right, int rightOffset, int rightLen) {<a name="line.1645"></a> -<span class="sourceLineNo">1646</span> // short circuit case<a name="line.1646"></a> -<span class="sourceLineNo">1647</span> if (left == right &&<a name="line.1647"></a> -<span class="sourceLineNo">1648</span> leftOffset == rightOffset &&<a name="line.1648"></a> -<span class="sourceLineNo">1649</span> leftLen == rightLen) {<a name="line.1649"></a> -<span class="sourceLineNo">1650</span> return true;<a name="line.1650"></a> -<span class="sourceLineNo">1651</span> }<a name="line.1651"></a> -<span class="sourceLineNo">1652</span> // different lengths fast check<a name="line.1652"></a> -<span class="sourceLineNo">1653</span> if (leftLen != rightLen) {<a name="line.1653"></a> -<span class="sourceLineNo">1654</span> return false;<a name="line.1654"></a> -<span class="sourceLineNo">1655</span> }<a name="line.1655"></a> -<span class="sourceLineNo">1656</span> if (leftLen == 0) {<a name="line.1656"></a> -<span class="sourceLineNo">1657</span> return true;<a name="line.1657"></a> -<span class="sourceLineNo">1658</span> }<a name="line.1658"></a> -<span class="sourceLineNo">1659</span><a name="line.1659"></a> -<span class="sourceLineNo">1660</span> // Since we're often comparing adjacent sorted data,<a name="line.1660"></a> -<span class="sourceLineNo">1661</span> // it's usual to have equal arrays except for the very last byte<a name="line.1661"></a> -<span class="sourceLineNo">1662</span> // so check that first<a name="line.1662"></a> -<span class="sourceLineNo">1663</span> if (left[leftOffset + leftLen - 1] != right[rightOffset + rightLen - 1]) return false;<a name="line.1663"></a> -<span class="sourceLineNo">1664</span><a name="line.1664"></a> -<span class="sourceLineNo">1665</span> return LexicographicalComparerHolder.BEST_COMPARER.<a name="line.1665"></a> -<span class="sourceLineNo">1666</span> compareTo(left, leftOffset, leftLen, right, rightOffset, rightLen) == 0;<a name="line.1666"></a> -<span class="sourceLineNo">1667</span> }<a name="line.1667"></a> -<span class="sourceLineNo">1668</span><a name="line.1668"></a> -<span class="sourceLineNo">1669</span><a name="line.1669"></a> -<span class="sourceLineNo">1670</span> /**<a name="line.1670"></a> -<span class="sourceLineNo">1671</span> * @param a left operand<a name="line.1671"></a> -<span class="sourceLineNo">1672</span> * @param buf right operand<a name="line.1672"></a> -<span class="sourceLineNo">1673</span> * @return True if equal<a name="line.1673"></a> -<span class="sourceLineNo">1674</span> */<a name="line.1674"></a> -<span class="sourceLineNo">1675</span> public static boolean equals(byte[] a, ByteBuffer buf) {<a name="line.1675"></a> -<span class="sourceLineNo">1676</span> if (a == null) return buf == null;<a name="line.1676"></a> -<span class="sourceLineNo">1677</span> if (buf == null) return false;<a name="line.1677"></a> -<span class="sourceLineNo">1678</span> if (a.length != buf.remaining()) return false;<a name="line.1678"></a> -<span class="sourceLineNo">1679</span><a name="line.1679"></a> -<span class="sourceLineNo">1680</span> // Thou shalt not modify the original byte buffer in what should be read only operations.<a name="line.1680"></a> -<span class="sourceLineNo">1681</span> ByteBuffer b = buf.duplicate();<a name="line.1681"></a> -<span class="sourceLineNo">1682</span> for (byte anA : a) {<a name="line.1682"></a> -<span class="sourceLineNo">1683</span> if (anA != b.get()) {<a name="line.1683"></a> -<span class="sourceLineNo">1684</span> return false;<a name="line.1684"></a> -<span class="sourceLineNo">1685</span> }<a name="line.1685"></a> -<span class="sourceLineNo">1686</span> }<a name="line.1686"></a> -<span class="sourceLineNo">1687</span> return true;<a name="line.1687"></a> -<span class="sourceLineNo">1688</span> }<a name="line.1688"></a> -<span class="sourceLineNo">1689</span><a name="line.1689"></a> -<span class="sourceLineNo">1690</span><a name="line.1690"></a> -<span class="sourceLineNo">1691</span> /**<a name="line.1691"></a> -<span class="sourceLineNo">1692</span> * Return true if the byte array on the right is a prefix of the byte<a name="line.1692"></a> -<span class="sourceLineNo">1693</span> * array on the left.<a name="line.1693"></a> -<span class="sourceLineNo">1694</span> */<a name="line.1694"></a> -<span class="sourceLineNo">1695</span> public static boolean startsWith(byte[] bytes, byte[] prefix) {<a name="line.1695"></a> -<span class="sourceLineNo">1696</span> return bytes != null && prefix != null &&<a name="line.1696"></a> -<span class="sourceLineNo">1697</span> bytes.length >= prefix.length &&<a name="line.1697"></a> -<span class="sourceLineNo">1698</span> LexicographicalComparerHolder.BEST_COMPARER.<a name="line.1698"></a> -<span class="sourceLineNo">1699</span> compareTo(bytes, 0, prefix.length, prefix, 0, prefix.length) == 0;<a name="line.1699"></a> -<span class="sourceLineNo">1700</span> }<a name="line.1700"></a> -<span class="sourceLineNo">1701</span><a name="line.1701"></a> -<span class="sourceLineNo">1702</span> /**<a name="line.1702"></a> -<span class="sourceLineNo">1703</span> * @param b bytes to hash<a name="line.1703"></a> -<span class="sourceLineNo">1704</span> * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the<a name="line.1704"></a> -<span class="sourceLineNo">1705</span> * passed in array. This method is what {@link org.apache.hadoop.io.Text}<a name="line.1705"></a> -<span class="sourceLineNo">1706</span> * use calculating hash code.<a name="line.1706"></a> -<span class="sourceLineNo">1707</span> */<a name="line.1707"></a> -<span class="sourceLineNo">1708</span> public static int hashCode(final byte [] b) {<a name="line.1708"></a> -<span class="sourceLineNo">1709</span> return hashCode(b, b.length);<a name="line.1709"></a> -<span class="sourceLineNo">1710</span> }<a name="line.1710"></a> -<span class="sourceLineNo">1711</span><a name="line.1711"></a> -<span class="sourceLineNo">1712</span> /**<a name="line.1712"></a> -<span class="sourceLineNo">1713</span> * @param b value<a name="line.1713"></a> -<span class="sourceLineNo">1714</span> * @param length length of the value<a name="line.1714"></a> -<span class="sourceLineNo">1715</span> * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the<a name="line.1715"></a> -<span class="sourceLineNo">1716</span> * passed in array. This method is what {@link org.apache.hadoop.io.Text}<a name="line.1716"></a> -<span class="sourceLineNo">1717</span> * use calculating hash code.<a name="line.1717"></a> -<span class="sourceLineNo">1718</span> */<a name="line.1718"></a> -<span class="sourceLineNo">1719</span> public static int hashCode(final byte [] b, final int length) {<a name="line.1719"></a> -<span class="sourceLineNo">1720</span> return WritableComparator.hashBytes(b, length);<a name="line.1720"></a> -<span class="sourceLineNo">1721</span> }<a name="line.1721"></a> -<span class="sourceLineNo">1722</span><a name="line.1722"></a> -<span class="sourceLineNo">1723</span> /**<a name="line.1723"></a> -<span class="sourceLineNo">1724</span> * @param b bytes to hash<a name="line.1724"></a> -<span class="sourceLineNo">1725</span> * @return A hash of <code>b</code> as an Integer that can be used as key in<a name="line.1725"></a> -<span class="sourceLineNo">1726</span> * Maps.<a name="line.1726"></a> -<span class="sourceLineNo">1727</span> */<a name="line.1727"></a> -<span class="sourceLineNo">1728</span> public static Integer mapKey(final byte [] b) {<a name="line.1728"></a> -<span class="sourceLineNo">1729</span> return hashCode(b);<a name="line.1729"></a> -<span class="sourceLineNo">1730</span> }<a name="line.1730"></a> -<span class="sourceLineNo">1731</span><a name="line.1731"></a> -<span class="sourceLineNo">1732</span> /**<a name="line.1732"></a> -<span class="sourceLineNo">1733</span> * @param b bytes to hash<a name="line.1733"></a> -<span class="sourceLineNo">1734</span> * @param length length to hash<a name="line.1734"></a> -<span class="sourceLineNo">1735</span> * @return A hash of <code>b</code> as an Integer that can be used as key in<a name="line.1735"></a> -<span class="sourceLineNo">1736</span> * Maps.<a name="line.1736"></a> -<span class="sourceLineNo">1737</span> */<a name="line.1737"></a> -<span class="sourceLineNo">1738</span> public static Integer mapKey(final byte [] b, final int length) {<a name="line.1738"></a> -<span class="sourceLineNo">1739</span> return hashCode(b, length);<a name="line.1739"></a> -<span class="sourceLineNo">1740</span> }<a name="line.1740"></a> -<span class="sourceLineNo">1741</span><a name="line.1741"></a> -<span class="sourceLineNo">1742</span> /**<a name="line.1742"></a> -<span class="sourceLineNo">1743</span> * @param a lower half<a name="line.1743"></a> -<span class="sourceLineNo">1744</span> * @param b upper half<a name="line.1744"></a> -<span class="sourceLineNo">1745</span> * @return New array that has a in lower half and b in upper half.<a name="line.1745"></a> -<span class="sourceLineNo">1746</span> */<a name="line.1746"></a> -<span class="sourceLineNo">1747</span> public static byte [] add(final byte [] a, final byte [] b) {<a name="line.1747"></a> -<span class="sourceLineNo">1748</span> return add(a, b, EMPTY_BYTE_ARRAY);<a name="line.1748"></a> -<span class="sourceLineNo">1749</span> }<a name="line.1749"></a> -<span class="sourceLineNo">1750</span><a name="line.1750"></a> -<span class="sourceLineNo">1751</span> /**<a name="line.1751"></a> -<span class="sourceLineNo">1752</span> * @param a first third<a name="line.1752"></a> -<span class="sourceLineNo">1753</span> * @param b second third<a name="line.1753"></a> -<span class="sourceLineNo">1754</span> * @param c third third<a name="line.1754"></a> -<span class="sourceLineNo">1755</span> * @return New array made from a, b and c<a name="line.1755"></a> +<span class="sourceLineNo">1527</span> // Short circuit equal case<a name="line.1527"></a> +<span class="sourceLineNo">1528</span> if (buffer1 == buffer2 &&<a name="line.1528"></a> +<span class="sourceLineNo">1529</span> offset1 == offset2 &&<a name="line.1529"></a> +<span class="sourceLineNo">1530</span> length1 == length2) {<a name="line.1530"></a> +<span class="sourceLineNo">1531</span> return 0;<a name="line.1531"></a> +<span class="sourceLineNo">1532</span> }<a name="line.1532"></a> +<span class="sourceLineNo">1533</span> final int stride = 8;<a name="line.1533"></a> +<span class="sourceLineNo">1534</span> final int minLength = Math.min(length1, length2);<a name="line.1534"></a> +<span class="sourceLineNo">1535</span> int strideLimit = minLength & ~(stride - 1);<a name="line.1535"></a> +<span class="sourceLineNo">1536</span> final long offset1Adj = offset1 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;<a name="line.1536"></a> +<span class="sourceLineNo">1537</span> final long offset2Adj = offset2 + UnsafeAccess.BYTE_ARRAY_BASE_OFFSET;<a name="line.1537"></a> +<span class="sourceLineNo">1538</span> int i;<a name="line.1538"></a> +<span class="sourceLineNo">1539</span><a name="line.1539"></a> +<span class="sourceLineNo">1540</span> /*<a name="line.1540"></a> +<span class="sourceLineNo">1541</span> * Compare 8 bytes at a time. Benchmarking on x86 shows a stride of 8 bytes is no slower<a name="line.1541"></a> +<span class="sourceLineNo">1542</span> * than 4 bytes even on 32-bit. On the other hand, it is substantially faster on 64-bit.<a name="line.1542"></a> +<span class="sourceLineNo">1543</span> */<a name="line.1543"></a> +<span class="sourceLineNo">1544</span> for (i = 0; i < strideLimit; i += stride) {<a name="line.1544"></a> +<span class="sourceLineNo">1545</span> long lw = theUnsafe.getLong(buffer1, offset1Adj + (long) i);<a name="line.1545"></a> +<span class="sourceLineNo">1546</span> long rw = theUnsafe.getLong(buffer2, offset2Adj + (long) i);<a name="line.1546"></a> +<span class="sourceLineNo">1547</span> if (lw != rw) {<a name="line.1547"></a> +<span class="sourceLineNo">1548</span> if(!UnsafeAccess.littleEndian) {<a name="line.1548"></a> +<span class="sourceLineNo">1549</span> return ((lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE)) ? -1 : 1;<a name="line.1549"></a> +<span class="sourceLineNo">1550</span> }<a name="line.1550"></a> +<span class="sourceLineNo">1551</span><a name="line.1551"></a> +<span class="sourceLineNo">1552</span> /*<a name="line.1552"></a> +<span class="sourceLineNo">1553</span> * We want to compare only the first index where left[index] != right[index]. This<a name="line.1553"></a> +<span class="sourceLineNo">1554</span> * corresponds to the least significant nonzero byte in lw ^ rw, since lw and rw are<a name="line.1554"></a> +<span class="sourceLineNo">1555</span> * little-endian. Long.numberOfTrailingZeros(diff) tells us the least significant<a name="line.1555"></a> +<span class="sourceLineNo">1556</span> * nonzero bit, and zeroing out the first three bits of L.nTZ gives us the shift to get<a name="line.1556"></a> +<span class="sourceLineNo">1557</span> * that least significant nonzero byte. This comparison logic is based on UnsignedBytes<a name="line.1557"></a> +<span class="sourceLineNo">1558</span> * comparator from guava v21<a name="line.1558"></a> +<span class="sourceLineNo">1559</span> */<a name="line.1559"></a> +<span class="sourceLineNo">1560</span> int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7;<a name="line.1560"></a> +<span class="sourceLineNo">1561</span> return ((int) ((lw >>> n) & 0xFF)) - ((int) ((rw >>> n) & 0xFF));<a name="line.1561"></a> +<span class="sourceLineNo">1562</span> }<a name="line.1562"></a> +<span class="sourceLineNo">1563</span> }<a name="line.1563"></a> +<span class="sourceLineNo">1564</span><a name="line.1564"></a> +<span class="sourceLineNo">1565</span> // The epilogue to cover the last (minLength % stride) elements.<a name="line.1565"></a> +<span class="sourceLineNo">1566</span> for (; i < minLength; i++) {<a name="line.1566"></a> +<span class="sourceLineNo">1567</span> int a = (buffer1[offset1 + i] & 0xFF);<a name="line.1567"></a> +<span class="sourceLineNo">1568</span> int b = (buffer2[offset2 + i] & 0xFF);<a name="line.1568"></a> +<span class="sourceLineNo">1569</span> if (a != b) {<a name="line.1569"></a> +<span class="sourceLineNo">1570</span> return a - b;<a name="line.1570"></a> +<span class="sourceLineNo">1571</span> }<a name="line.1571"></a> +<span class="sourceLineNo">1572</span> }<a name="line.1572"></a> +<span class="sourceLineNo">1573</span> return length1 - length2;<a name="line.1573"></a> +<span class="sourceLineNo">1574</span> }<a name="line.1574"></a> +<span class="sourceLineNo">1575</span> }<a name="line.1575"></a> +<span class="sourceLineNo">1576</span> }<a name="line.1576"></a> +<span class="sourceLineNo">1577</span><a name="line.1577"></a> +<span class="sourceLineNo">1578</span> /**<a name="line.1578"></a> +<span class="sourceLineNo">1579</span> * @param left left operand<a name="line.1579"></a> +<span class="sourceLineNo">1580</span> * @param right right operand<a name="line.1580"></a> +<span class="sourceLineNo">1581</span> * @return True if equal<a name="line.1581"></a> +<span class="sourceLineNo">1582</span> */<a name="line.1582"></a> +<span class="sourceLineNo">1583</span> public static boolean equals(final byte [] left, final byte [] right) {<a name="line.1583"></a> +<span class="sourceLineNo">1584</span> // Could use Arrays.equals?<a name="line.1584"></a> +<span class="sourceLineNo">1585</span> //noinspection SimplifiableConditionalExpression<a name="line.1585"></a> +<span class="sourceLineNo">1586</span> if (left == right) return true;<a name="line.1586"></a> +<span class="sourceLineNo">1587</span> if (left == null || right == null) return false;<a name="line.1587"></a> +<span class="sourceLineNo">1588</span> if (left.length != right.length) return false;<a name="line.1588"></a> +<span class="sourceLineNo">1589</span> if (left.length == 0) return true;<a name="line.1589"></a> +<span class="sourceLineNo">1590</span><a name="line.1590"></a> +<span class="sourceLineNo">1591</span> // Since we're often comparing adjacent sorted data,<a name="line.1591"></a> +<span class="sourceLineNo">1592</span> // it's usual to have equal arrays except for the very last byte<a name="line.1592"></a> +<span class="sourceLineNo">1593</span> // so check that first<a name="line.1593"></a> +<span class="sourceLineNo">1594</span> if (left[left.length - 1] != right[right.length - 1]) return false;<a name="line.1594"></a> +<span class="sourceLineNo">1595</span><a name="line.1595"></a> +<span class="sourceLineNo">1596</span> return compareTo(left, right) == 0;<a name="line.1596"></a> +<span class="sourceLineNo">1597</span> }<a name="line.1597"></a> +<span class="sourceLineNo">1598</span><a name="line.1598"></a> +<span class="sourceLineNo">1599</span> public static boolean equals(final byte[] left, int leftOffset, int leftLen,<a name="line.1599"></a> +<span class="sourceLineNo">1600</span> final byte[] right, int rightOffset, int rightLen) {<a name="line.1600"></a> +<span class="sourceLineNo">1601</span> // short circuit case<a name="line.1601"></a> +<span class="sourceLineNo">1602</span> if (left == right &&<a name="line.1602"></a> +<span class="sourceLineNo">1603</span> leftOffset == rightOffset &&<a name="line.1603"></a> +<span class="sourceLineNo">1604</span> leftLen == rightLen) {<a name="line.1604"></a> +<span class="sourceLineNo">1605</span> return true;<a name="line.1605"></a> +<span class="sourceLineNo">1606</span> }<a name="line.1606"></a> +<span class="sourceLineNo">1607</span> // different lengths fast check<a name="line.1607"></a> +<span class="sourceLineNo">1608</span> if (leftLen != rightLen) {<a name="line.1608"></a> +<span class="sourceLineNo">1609</span> return false;<a name="line.1609"></a> +<span class="sourceLineNo">1610</span> }<a name="line.1610"></a> +<span class="sourceLineNo">1611</span> if (leftLen == 0) {<a name="line.1611"></a> +<span class="sourceLineNo">1612</span> return true;<a name="line.1612"></a> +<span class="sourceLineNo">1613</span> }<a name="line.1613"></a> +<span class="sourceLineNo">1614</span><a name="line.1614"></a> +<span class="sourceLineNo">1615</span> // Since we're often comparing adjacent sorted data,<a name="line.1615"></a> +<span class="sourceLineNo">1616</span> // it's usual to have equal arrays except for the very last byte<a name="line.1616"></a> +<span class="sourceLineNo">1617</span> // so check that first<a name="line.1617"></a> +<span class="sourceLineNo">1618</span> if (left[leftOffset + leftLen - 1] != right[rightOffset + rightLen - 1]) return false;<a name="line.1618"></a> +<span class="sourceLineNo">1619</span><a name="line.1619"></a> +<span class="sourceLineNo">1620</span> return LexicographicalComparerHolder.BEST_COMPARER.<a name="line.1620"></a> +<span class="sourceLineNo">1621</span> compareTo(left, leftOffset, leftLen, right, rightOffset, rightLen) == 0;<a name="line.1621"></a> +<span class="sourceLineNo">1622</span> }<a name="line.1622"></a> +<span class="sourceLineNo">1623</span><a name="line.1623"></a> +<span class="sourceLineNo">1624</span><a name="line.1624"></a> +<span class="sourceLineNo">1625</span> /**<a name="line.1625"></a> +<span class="sourceLineNo">1626</span> * @param a left operand<a name="line.1626"></a> +<span class="sourceLineNo">1627</span> * @param buf right operand<a name="line.1627"></a> +<span class="sourceLineNo">1628</span> * @return True if equal<a name="line.1628"></a> +<span class="sourceLineNo">1629</span> */<a name="line.1629"></a> +<span class="sourceLineNo">1630</span> public static boolean equals(byte[] a, ByteBuffer buf) {<a name="line.1630"></a> +<span class="sourceLineNo">1631</span> if (a == null) return buf == null;<a name="line.1631"></a> +<span class="sourceLineNo">1632</span> if (buf == null) return false;<a name="line.1632"></a> +<span class="sourceLineNo">1633</span> if (a.length != buf.remaining()) return false;<a name="line.1633"></a> +<span class="sourceLineNo">1634</span><a name="line.1634"></a> +<span class="sourceLineNo">1635</span> // Thou shalt not modify the original byte buffer in what should be read only operations.<a name="line.1635"></a> +<span class="sourceLineNo">1636</span> ByteBuffer b = buf.duplicate();<a name="line.1636"></a> +<span class="sourceLineNo">1637</span> for (byte anA : a) {<a name="line.1637"></a> +<span class="sourceLineNo">1638</span> if (anA != b.get()) {<a name="line.1638"></a> +<span class="sourceLineNo">1639</span> return false;<a name="line.1639"></a> +<span class="sourceLineNo">1640</span> }<a name="line.1640"></a> +<span class="sourceLineNo">1641</span> }<a name="line.1641"></a> +<span class="sourceLineNo">1642</span> return true;<a name="line.1642"></a> +<span class="sourceLineNo">1643</span> }<a name="line.1643"></a> +<span class="sourceLineNo">1644</span><a name="line.1644"></a> +<span class="sourceLineNo">1645</span><a name="line.1645"></a> +<span class="sourceLineNo">1646</span> /**<a name="line.1646"></a> +<span class="sourceLineNo">1647</span> * Return true if the byte array on the right is a prefix of the byte<a name="line.1647"></a> +<span class="sourceLineNo">1648</span> * array on the left.<a name="line.1648"></a> +<span class="sourceLineNo">1649</span> */<a name="line.1649"></a> +<span class="sourceLineNo">1650</span> public static boolean startsWith(byte[] bytes, byte[] prefix) {<a name="line.1650"></a> +<span class="sourceLineNo">1651</span> return bytes != null && prefix != null &&<a name="line.1651"></a> +<span class="sourceLineNo">1652</span> bytes.length >= prefix.length &&<a name="line.1652"></a> +<span class="sourceLineNo">1653</span> LexicographicalComparerHolder.BEST_COMPARER.<a name="line.1653"></a> +<span class="sourceLineNo">1654</span> compareTo(bytes, 0, prefix.length, prefix, 0, prefix.length) == 0;<a name="line.1654"></a> +<span class="sourceLineNo">1655</span> }<a name="line.1655"></a> +<span class="sourceLineNo">1656</span><a name="line.1656"></a> +<span class="sourceLineNo">1657</span> /**<a name="line.1657"></a> +<span class="sourceLineNo">1658</span> * @param b bytes to hash<a name="line.1658"></a> +<span class="sourceLineNo">1659</span> * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the<a name="line.1659"></a> +<span class="sourceLineNo">1660</span> * passed in array. This method is what {@link org.apache.hadoop.io.Text}<a name="line.1660"></a> +<span class="sourceLineNo">1661</span> * use calculating hash code.<a name="line.1661"></a> +<span class="sourceLineNo">1662</span> */<a name="line.1662"></a> +<span class="sourceLineNo">1663</span> public static int hashCode(final byte [] b) {<a name="line.1663"></a> +<span class="sourceLineNo">1664</span> return hashCode(b, b.length);<a name="line.1664"></a> +<span class="sourceLineNo">1665</span> }<a name="line.1665"></a> +<span class="sourceLineNo">1666</span><a name="line.1666"></a> +<span class="sourceLineNo">1667</span> /**<a name="line.1667"></a> +<span class="sourceLineNo">1668</span> * @param b value<a name="line.1668"></a> +<span class="sourceLineNo">1669</span> * @param length length of the value<a name="line.1669"></a> +<span class="sourceLineNo">1670</span> * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the<a name="line.1670"></a> +<span class="sourceLineNo">1671</span> * passed in array. This method is what {@link org.apache.hadoop.io.Text}<a name="line.1671"></a> +<span class="sourceLineNo">1672</span> * use calculating hash code.<a name="line.1672"></a> +<span class="sourceLineNo">1673</span> */<a name="line.1673"></a> +<span class="sourceLineNo">1674</span> public static int hashCode(final byte [] b, final int length) {<a name="line.1674"></a> +<span class="sourceLineNo">1675</span> return WritableComparator.hashBytes(b, length);<a name="line.1675"></a> +<span class="sourceLineNo">1676</span> }<a name="line.1676"></a> +<span class="sourceLineNo">1677</span><a name="line.1677"></a> +<span class="sourceLineNo">1678</span> /**<a name="line.1678"></a> +<span class="sourceLineNo">1679</span> * @param b bytes to hash<a name="line.1679"></a> +<span class="sourceLineNo">1680</span> * @return A hash of <code>b</code> as an Integer that can be used as key in<a name="line.1680"></a> +<span class="sourceLineNo">1681</span> * Maps.<a name="line.1681"></a> +<span class="sourceLineNo">1682</span> */<a name="line.1682"></a> +<span class="sourceLineNo">1683</span> public static Integer mapKey(final byte [] b) {<a name="line.1683"></a> +<span class="sourceLineNo">1684</span> return hashCode(b);<a name="line.1684"></a> +<span class="sourceLineNo">1685</span> }<a name="line.1685"></a> +<span class="sourceLineNo">1686</span><a name="line.1686"></a> +<span class="sourceLineNo">1687</span> /**<a name="line.1687"></a> +<span class="sourceLineNo">1688</span> * @param b bytes to hash<a name="line.1688"></a> +<span class="sourceLineNo">1689</span> * @param length length to hash<a name="line.1689"></a> +<span class="sourceLineNo">1690</span> * @return A hash of <code>b</code> as an Integer that can be used as key in<a name="line.1690"></a> +<span class="sourceLineNo">1691</span> * Maps.<a name="line.1691"></a> +<span class="sourceLineNo">1692</span> */<a name="line.1692"></a> +<span class="sourceLineNo">1693</span> public static Integer mapKey(final byte [] b, final int length) {<a name="line.1693"></a> +<span class="sourceLineNo">1694</span> return hashCode(b, length);<a name="line.1694"></a> +<span class="sourceLineNo">1695</span> }<a name="line.1695"></a> +<span class="sourceLineNo">1696</span><a name="line.1696"></a> +<span class="sourceLineNo">1697</span> /**<a name="line.1697"></a> +<span class="sourceLineNo">1698</span> * @param a lower half<a name="line.1698"></a> +<span class="sourceLineNo">1699</span> * @param b upper half<a name="line.1699"></a> +<span class="sourceLineNo">1700</span> * @return New array that has a in lower half and b in upper half.<a name="line.1700"></a> +<span class="sourceLineNo">1701</span> */<a name="line.1701"></a> +<span class="sourceLineNo">1702</span> public static byte [] add(final byte [] a, final byte [] b) {<a name="line.1702"></a> +<span class="sourceLineNo">1703</span> return add(a, b, EMPTY_BYTE_ARRAY);<a name="line.1703"></a> +<span class="sourceLineNo">1704</span> }<a name="line.1704"></a> +<span class="sourceLineNo">1705</span><a name="line.1705"></a> +<span class="sourceLineNo">1706</span> /**<a name="line.1706"></a> +<span class="sourceLineNo">1707</span> * @param a first third<a name="line.1707"></a> +<span class="sourceLineNo">1708</span> * @param b second third<a name="line.1708"></a> +<span class="sourceLineNo">1709</span> * @param c third third<a name="line.1709"></a> +<span class="sourceLineNo">1710</span> * @return New array made from a, b and c<a name="line.1710"></a> +<span class="sourceLineNo">1711</span> */<a name="line.1711"></a> +<span class="sourceLineNo">1712</span> public static byte [] add(final byte [] a, final byte [] b, final byte [] c) {<a name="line.1712"></a> +<span class="sourceLineNo">1713</span> byte [] result = new byte[a.length + b.length + c.length];<a name="line.1713"></a> +<span class="sourceLineNo">1714</span> System.arraycopy(a, 0, result, 0, a.length);<a name="line.1714"></a> +<span class="sourceLineNo">1715</span> System.arraycopy(b, 0, result, a.length, b.length);<a name="line.1715"></a> +<span class="sourceLineNo">1716</span> System.arraycopy(c, 0, result, a.length + b.length, c.length);<a name="line.1716"></a> +<span class="sourceLineNo">1717</span> return result;<a name="line.1717"></a> +<span class="sourceLineNo">1718</span> }<a name="line.1718"></a> +<span class="sourceLineNo">1719</span><a name="line.1719"></a> +<span class="sourceLineNo">1720</span> /**<a name="line.1720"></a> +<span class="sourceLineNo">1721</span> * @param arrays all the arrays to concatenate together.<a name="line.1721"></a> +<span class="sourceLineNo">1722</span> * @return New array made from the concatenation of the given arrays.<a name="line.1722"></a> +<span class="sourceLineNo">1723</span> */<a name="line.1723"></a> +<span class="sourceLineNo">1724</span> public static byte [] add(final byte [][] arrays) {<a name="line.1724"></a> +<span class="sourceLineNo">1725</span> int length = 0;<a name="line.1725"></a> +<span class="sourceLineNo">1726</span> for (int i = 0; i < arrays.length; i++) {<a name="line.1726"></a> +<span class="sourceLineNo">1727</span> length += arrays[i].length;<a name="line.1727"></a> +<span class="sourceLineNo">1728</span> }<a name="line.1728"></a> +<span class="sourceLineNo">1729</span> byte [] result = new byte[length];<a name="line.1729"></a> +<span class="sourceLineNo">1730</span> int index = 0;<a name="line.1730"></a> +<span class="sourceLineNo">1731</span> for (int i = 0; i < arrays.length; i++) {<a name="line.1731"></a> +<span class="sourceLineNo">1732</span> System.arraycopy(arrays[i], 0, result, index, arrays[i].length);<a name="line.1732"></a> +<span class="sourceLineNo">1733</span> index += arrays[i].length;<a name="line.1733"></a> +<span class="sourceLineNo">1734</span> }<a name="line.1734"></a> +<span class="sourceLineNo">1735</span> return result;<a name="line.1735"></a> +<span class="sourceLineNo">1736</span> }<a name="line.1736"></a> +<span class="sourceLineNo">1737</span><a name="line.1737"></a> +<span class="sourceLineNo">1738</span> /**<a name="line.1738"></a> +<span class="sourceLineNo">1739</span> * @param a array<a name="line.1739"></a> +<span class="sourceLineNo">1740</span> * @param length amount of bytes to grab<a name="line.1740"></a> +<span class="sourceLineNo">1741</span> * @return First <code>length</code> bytes from <code>a</code><a name="line.1741"></a> +<span class="sourceLineNo">1742</span> */<a name="line.1742"></a> +<span class="sourceLineNo">1743</span> public static byte [] head(final byte [] a, final int length) {<a name="line.1743"></a> +<span class="sourceLineNo">1744</span> if (a.length < length) {<a name="line.1744"></a> +<span class="sourceLineNo">1745</span> return null;<a name="line.1745"></a> +<span class="sourceLineNo">1746</span> }<a name="line.1746"></a> +<span class="sourceLineNo">1747</span> byte [] result = new byte[length];<a name="line.1747"></a> +<span class="sourceLineNo">1748</span> System.arraycopy(a, 0, result, 0, length);<a name="line.1748"></a> +<span class="sourceLineNo">1749</span> return result;<a name="line.1749"></a> +<span class="sourceLineNo">1750</span> }<a name="line.1750"></a> +<span class="sourceLineNo">1751</span><a name="line.1751"></a> +<span class="sourceLineNo">1752</span> /**<a name="line.1752"></a> +<span class="sourceLineNo">1753</span> * @param a array<a name="line.1753"></a> +<span class="sourceLineNo">1754</span> * @param length amount of bytes to snarf<a name="line.1754"></a> +<span class="sourceLineNo">1755</span> * @return Last <code>length</code> bytes from <code>a</code><a name="line.1755"></a> <span class="sourceLineNo">1756</span> */<a name="line.1756"></a> -<span class="sourceLineNo">1757</span> public static byte [] add(final byte [] a, final byte [] b, final byte [] c) {<a name="line.1757"></a> -<span class="sourceLineNo">1758</span> byte [] result = new byte[a.length + b.length + c.length];<a name="line.1758"></a> -<span class="sourceLineNo">1759</span> System.arraycopy(a, 0, result, 0, a.length);<a name="line.1759"></a> -<span class="sourceLineNo">1760</span> System.arraycopy(b, 0, result, a.length, b.length);<a name="line.1760"></a> -<span class="sourceLineNo">1761</span> System.arraycopy(c, 0, result, a.length + b.length, c.length);<a name="line.1761"></a> -<span class="sourceLineNo">1762</span> return result;<a name="line.1762"></a> -<span class="sourceLineNo">1763</span> }<a name="line.1763"></a> -<span class="sourceLineNo">1764</span><a name="line.1764"></a> -<span class="sourceLineNo">1765</span> /**<a name="line.1765"></a> -<span class="sourceLineNo">1766</span> * @param arrays all the arrays to concatenate together.<a name="line.1766"></a> -<span class="sourceLineNo">1767</span> * @return New array made from the concatenation of the given arrays.<a name="line.1767"></a> -<span class="sourceLineNo">1768</span> */<a name="line.1768"></a> -<span class="sourceLineNo">1769</span> public static byte [] add(final byte [][] arrays) {<a name="line.1769"></a> -<span class="sourceLineNo">1770</span> int length = 0;<a name="line.1770"></a> -<span class="sourceLineNo">1771</span> for (int i = 0; i < arrays.length; i++) {<a name="line.1771"></a> -<span class="sourceLineNo">1772</span> length += arrays[i].length;<a name="line.1772"></a> -<span class="sourceLineNo">1773</span> }<a name="line.1773"></a> -<span class="sourceLineNo">1774</span> byte [] result = new byte[length];<a name="line.1774"></a> -<span class="sourceLineNo">1775</span> int index = 0;<a name="line.1775"></a> -<span class="sourceLineNo">1776</span> for (int i = 0; i < arrays.length; i++) {<a name="line.1776"></a> -<span class="sourceLineNo">1777</span> System.arraycopy(arrays[i], 0, result, index, arrays[i].length);<a name="line.1777"></a> -<span class="sourceLineNo">1778</span> index += arrays[i].length;<a name="line.1778"></a> -<span class="sourceLineNo">1779</span> }<a name="line.1779"></a> -<span class="sourceLineNo">1780</span> return result;<a name="line.1780"></a> -<span class="sourceLineNo">1781</span> }<a name="line.1781"></a> -<span class="sourceLineNo">1782</span><a name="line.1782"></a> -<span class="sourceLineNo">1783</span> /**<a name="line.1783"></a> -<span class="sourceLineNo">1784</span> * @param a array<a name="line.1784"></a> -<span class="sourceLineNo">1785</span> * @param length amount of bytes to grab<a name="line.1785"></a> -<span class="sourceLineNo">1786</span> * @return First <code>length</code> bytes from <code>a</code><a name="line.1786"></a> -<span class="sourceLineNo">1787</span> */<a name="line.1787"></a> -<span class="sourceLineNo">1788</span> public static byte [] head(final byte [] a, final int length) {<a name="line.1788"></a> -<span class="sourceLineNo">1789</span> if (a.length < length) {<a name="line.1789"></a> -<span class="sourceLineNo">1790</span> return null;<a name="line.1790"></a> -<span class="sourceLineNo">1791</span> }<a name="line.1791"></a> -<span class="sourceLineNo">1792</span> byte [] result = new byte[length];<a name="line.1792"></a> -<span class="sourceLineNo">1793</span> System.arraycopy(a, 0, result, 0, length);<a name="line.1793"></a> -<span class="sourceLineNo">1794</span> return result;<a name="line.1794"></a> -<span class="sourceLineNo">1795</span> }<a name="line.1795"></a> -<span class="sourceLineNo">1796</span><a name="line.1796"></a> -<span class="sourceLineNo">1797</span> /**<a name="line.1797"></a> -<span class="sourceLineNo">1798</span> * @param a array<a name="line.1798"></a> -<span class="sourceLineNo">1799</span> * @param length amount of bytes to snarf<a name="line.1799"></a> -<span class="sourceLineNo">1800</span> * @return Last <code>length</code> bytes from <code>a</code><a name="line.1800"></a> -<span class="sourceLineNo">1801</span> */<a name="line.1801"></a> -<span class="sourceLineNo">1802</span> public static byte [] tail(final byte [] a, final int length) {<a name="line.1802"></a> -<span class="sourceLineNo">1803</span> if (a.length < length) {<a name="line.1803"></a> -<span class="sourceLineNo">1804</span> return null;<a name="line.1804"></a> -<span class="sourceLineNo">1805</span> }<a name="line.1805"></a> -<span class="sourceLineNo">1806</span> byte [] result = new byte[length];<a name="line.1806"></a> -<span class="sourceLineNo">1807</span> System.arraycopy(a, a.length - length, result, 0, length);<a name="line.1807"></a> -<span class="sourceLineNo">1808</span> return result;<a name="line.1808"></a> -<span class="sourceLineNo">1809</span> }<a name="line.1809"></a> -<span class="sourceLineNo">1810</span><a name="line.1810"></a> -<span class="sourceLineNo">1811</span> /**<a name="line.1811"></a> -<span class="sourceLineNo">1812</span> * @param a array<a name="line.1812"></a> -<span class="sourceLineNo">1813</span> * @param length new array size<a name="line.1813"></a> -<span class="sourceLineNo">1814</span> * @return Value in <code>a</code> plus <code>length</code> prepended 0 bytes<a name="line.1814"></a> -<span class="sourceLineNo">1815</span> */<a name="line.1815"></a> -<span class="sourceLineNo">1816</span> public static byte [] padHead(final byte [] a, final int length) {<a name="line.1816"></a> -<span class="sourceLineNo">1817</span> byte [] padding = new byte[length];<a name="line.1817"></a> -<span class="sourceLineNo">1818</span> for (int i = 0; i < length; i++) {<a name="line.1818"></a> -<span class="sourceLineNo">1819</span> padding[i] = 0;<a name="line.1819"></a> -<span class="sourceLineNo">1820</span> }<a name="line.1820"></a> -<span class="sourceLineNo">1821</span> return add(padding,a);<a name="line.1821"></a> -<span class="sourceLineNo">1822</span> }<a name="line.1822"></a> -<span class="sourceLineNo">1823</span><a name="line.1823"></a> -<span class="sourceLineNo">1824</span> /**<a name="line.1824"></a> -<span class="sourceLineNo">1825</span> * @param a array<a name="line.1825"></a> -<span class="sourceLineNo">1826</span> * @param length new array size<a name="line.1826"></a> -<span class="sourceLineNo">1827</span> * @return Value in <code>a</code> plus <code>length</code> appended 0 bytes<a name="line.1827"></a> -<span class="sourceLineNo">1828</span> */<a name="line.1828"></a> -<span class="sourceLineNo">1829</span> public static byte [] padTail(final byte [] a, final int length) {<a name="line.1829"></a> -<span class="sourceLineNo">1830</span> byte [] padding = new byte[length];<a name="line.1830"></a> -<span class="sourceLineNo">1831</span> for (int i = 0; i < length; i++) {<a name="line.1831"></a> -<span class="sourceLineNo">1832</span> padding[i] = 0;<a name="line.1832"></a> -<span class="sourceLineNo">1833</span> }<a name="line.1833"></a> -<span class="sourceLineNo">1834</span> return add(a,padding);<a name="line.1834"></a> -<span class="sourceLineNo">1835</span> }<a name="line.1835"></a> -<span class="sourceLineNo">1836</span><a name="line.1836"></a> -<span class="sourceLineNo">1837</span> /**<a name="line.1837"></a> -<span class="sourceLineNo">1838</span> * Split passed range. Expensive operation relatively. Uses BigInteger math.<a name="line.1838"></a> -<span class="sourceLineNo">1839</span> * Useful splitting ranges for MapReduce jobs.<a name="line.1839"></a> -<span class="sourceLineNo">1840</span> * @param a Beginning of range<a name="line.1840"></a> -<span class="sourceLineNo">1841</span> * @param b End of range<a name="line.1841"></a> -<span class="sourceLineNo">1842</span> * @param num Number of times to split range. Pass 1 if you want to split<a name="line.1842"></a> -<span class="sourceLineNo">1843</span> * the range in two; i.e. one split.<a name="line.1843"></a> -<span class="sourceLineNo">1844</span> * @return Array of dividing values<a name="line.1844"></a> -<span class="sourceLineNo">1845</span> */<a name="line.1845"></a> -<span class="sourceLineNo">1846</span> public static byte [][] split(final byte [] a, final byte [] b, final int num) {<a name="line.1846"></a> -<span class="sourceLineNo">1847</span> return split(a, b, false, num);<a name="line.1847"></a> -<span class="sourceLineNo">1848</span> }<a name="line.1848"></a> -<span class="sourceLineNo">1849</span><a name="line.1849"></a> -<span class="sourceLineNo">1850</span> /**<a name="line.1850"></a> -<span class="sourceLineNo">1851</span> * Split passed range. Expensive operation relatively. Uses BigInteger math.<a name="line.1851"></a> -<span class="sourceLineNo">1852</span> * Useful splitting ranges for MapReduce jobs.<a name="line.1852"></a> -<span class="sourceLineNo">1853</span> * @param a Beginning of range<a name="line.1853"></a> -<span class="sourceLineNo">1854</span> * @param b End of range<a name="line.1854"></a> -<span class="sourceLineNo">1855</span> * @param inclusive Whether the end of range is prefix-inclusive or is<a name="line.1855"></a> -<span class="sourceLineNo">1856</span> * considered an exclusive boundary. Automatic splits are generally exclusive<a name="line.1856"></a> -<span class="sourceLineNo">1857</span> * and manual splits with an explicit range utilize an inclusive end of range.<a name="line.1857"></a> -<span class="sourceLineNo">1858</span> * @param num Number of times to split range. Pass 1 if you want to split<a name="line.1858"></a> -<span class="sourceLineNo">1859</span> * the range in two; i.e. one split.<a name="line.1859"></a> -<span class="sourceLineNo">1860</span> * @return Array of dividing values<a name="line.1860"></a> -<span class="sourceLineNo">1861</span> */<a name="line.1861"></a> -<span class="sourceLineNo">1862</span> public static byte[][] split(final byte[] a, final byte[] b,<a name="line.1862"></a> -<span class="sourceLineNo">1863</span> boolean inclusive, final int num) {<a name="line.1863"></a> -<span class="sourceLineNo">1864</span> byte[][] ret = new byte[num + 2][];<a name="line.1864"></a> -<span class="sourceLineNo">1865</span> int i = 0;<a name="line.1865"></a> -<span class="sourceLineNo">1866</span> Iterable<byte[]> iter = iterateOnSplits(a, b, inclusive, num);<a name="line.1866"></a> -<span class="sourceLineNo">1867</span> if (iter == null)<a name="line.1867"></a> -<span class="sourceLineNo">1868</span> return null;<a name="line.1868"></a> -<span class="sourceLineNo">1869</span> for (byte[] elem : iter) {<a name="line.1869"></a> -<span class="sourceLineNo">1870</span> ret[i++] = elem;<a name="line.1870"></a> -<span class="sourceLineNo">1871</span> }<a name="line.1871"></a> -<span class="sourceLineNo">1872</span> return ret;<a name="line.1872"></a> -<span class="sourceLineNo">1873</span> }<a name="line.1873"></a> -<span class="sourceLineNo">1874</span><a name="line.1874"></a> -<span class="sourceLineNo">1875</span> /**<a name="line.1875"></a> -<span class="sourceLineNo">1876</span> * Iterate over keys within the passed range, splitting at an [a,b) boundary.<a name="line.1876"></a> -<span class="sourceLineNo">1877</span> */<a name="line.1877"></a> -<span class="sourceLineNo">1878</span> public static Iterable<byte[]> iterateOnSplits(final byte[] a,<a name="line.1878"></a> -<span class="sourceLineNo">1879</span> final byte[] b, final int num)<a name="line.1879"></a> -<span class="sourceLineNo">1880</span> {<a name="line.1880"></a> -<span class="sourceLineNo">1881</span> return iterateOnSplits(a, b, false, num);<a name="line.1881"></a> -<span class="sourceLineNo">1882</span> }<a name="line.1882"></a> -<span class="sourceLineNo">1883</span><a name="line.1883"></a> -<span class="sourceLineNo">1884</span> /**<a name="line.1884"></a> -<span class="sourceLineNo">1885</span> * Iterate over keys within the passed range.<a name="line.1885"></a> -<span class="sourceLineNo">1886</span> */<a name="line.1886"></a> -<span class="sourceLineNo">1887</span> public static Iterable<byte[]> iterateOnSplits(<a name="line.1887"></a> -<span class="sourceLineNo">1888</span> final byte[] a, final byte[]b, boolean inclusive, final int num)<a name="line.1888"></a> -<span class="sourceLineNo">1889</span> {<a name="line.1889"></a> -<span class="sourceLineNo">1890</span> byte [] aPadded;<a name="line.1890"></a> -<span class="sourceLineNo">1891</span> byte [] bPadded;<a name="line.1891"></a> -<span class="sourceLineNo">1892</span> if (a.length < b.length) {<a name="line.1892"></a> -<span class="sourceLineNo">1893</span> aPadded = padTail(a, b.length - a.length);<a name="line.1893"></a> -<span class="sourceLineNo">1894</span> bPadded = b;<a name="line.1894"></a> -<span class="sourceLineNo">1895</span> } else if (b.length < a.length) {<a name="line.1895"></a> -<span class="sourceLineNo">1896</span> aPadded = a;<a name="line.1896"></a> -<span class="sourceLineNo">1897</span> bPadded = padTail(b, a.length - b.length);<a name="line.1897"></a> -<span class="sourceLineNo">1898</span> } else {<a name="line.1898"></a> -<span class="sourceLineNo">1899</span> aPadded = a;<a name="line.1899"></a> -<span class="sourceLineNo">1900</span> bPadded = b;<a name="line.1900"></a> -<span class="sourceLineNo">1901</span> }<a name="line.1901"></a> -<span class="sourceLineNo">1902</span> if (compareTo(aPadded,bPadded) >= 0) {<a name="line.1902"></a> -<span class="sourceLineNo">1903</span> throw new IllegalArgumentException("b <= a");<a name="line.1903"></a> -<span class="sourceLineNo">1904</span> }<a name="line.1904"></a> -<span class="sourceLineNo">1905</span> if (num <= 0) {<a name="line.1905"></a> -<span class="sourceLineNo">1906</span> throw new IllegalArgumentException("num cannot be <= 0");<a name="line.1906"></a> -<span class="sourceLineNo">1907</span> }<a name="line.1907"></a> -<span class="sourceLineNo">1908</span> byte [] prependHeader = {1, 0};<a name="line.1908"></a> -<span class="sourceLineNo">1909</span> final BigInteger startBI = new BigInteger(add(prependHeader, aPadded));<a name="line.1909"></a> -<span class="sourceLineNo">1910</span> final BigInteger stopBI = new BigInteger(add(prependHeader, bPadded));<a name="line.1910"></a> -<span class="sourceLineNo">1911</span> BigInteger diffBI = stopBI.subtract(startBI);<a name="line.1911"></a> -<span class="sourceLineNo">1912</span> if (inclusive) {<a name="line.1912"></a> -<span class="sourceLineNo">1913</span> diffBI = diffBI.add(BigInteger.ONE);<a name="line.1913"></a> -<span class="sourceLineNo">1914</span> }<a name="line.1914"></a> -<span class="sourceLineNo">1915</span> final BigInteger splitsBI = BigInteger.valueOf(num + 1);<a name="line.1915"></a> -<span class="sourceLineNo">1916</span> //when diffBI < splitBI, use an additional byte to increase diffBI<a name="line.1916"></a> -<span class="sourceLineNo">1917</span> if(diffBI.compareTo(splitsBI) < 0) {<a name="line.1917"></a> -<span class="sourceLineNo">1918</span> byte[] aPaddedAdditional = new byte[aPadded.length+1];<a name="line.1918"></a> -<span class="sourceLineNo">1919</span> byte[] bPaddedAdditional = new byte[bPadded.length+1];<a name="line.1919"></a> -<span class="sourceLineNo">1920</span> for (int i = 0; i < aPadded.length; i++){<a name="line.1920"></a> -<span class="sourceLineNo">1921</span> aPaddedAdditional[i] = aPadded[i];<a name="line.1921"></a> -<span class="sourceLineNo">1922</span> }<a name="line.1922"></a> -<span class="sourceLineNo">1923</span> for (int j = 0; j < bPadded.length; j++){<a name="line.1923"></a> -<span class="sourceLineNo">1924</span> bPaddedAdditional[j] = bPadded[j];<a name="line.1924"></a> -<span class="sourceLineNo">1925</span> }<a name="line.1925"></a> -<span class="sourceLineNo">1926</span> aPaddedAdditional[aPadded.length] = 0;<a name="line.1926"></a> -<span class="sourceLineNo">1927</span> bPaddedAdditional[bPadded.length] = 0;<a name="line.1927"></a> -<span class="sourceLineNo">1928</span> return iterateOnSplits(aPaddedAdditional, bPaddedAdditional, inclusive, num);<a name="line.1928"></a> -<span class="sourceLineNo">1929</span> }<a name="line.1929"></a> -<span class="sourceLineNo">1930</span> final BigInteger intervalBI;<a name="line.1930"></a> -<span class="sourceLineNo">1931</span> try {<a name="line.1931"></a> -<span class="sourceLineNo">1932</span> intervalBI = diffBI.divide(splitsBI);<a name="line.1932"></a> -<span class="sourceLineNo">1933</span> } catch(Exception e) {<a name="line.1933"></a> -<span class="sourceLineNo">1934</span> LOG.error("Exception caught during division", e);<a name="line.1934"></a> -<span class="sourceLineNo">1935</span> return null;<a name="line.1935"></a> -<span class="sourceLineNo">1936</span> }<a name="line.1936"></a> -<span class="sourceLineNo">1937</span><a name="line.1937"></a> -<span class="sourceLineNo">1938</span> final Iterator<byte[]> iterator = new Iterator<byte[]>() {<a name="line.1938"></a> -<span class="sourceLineNo">1939</span> private int i = -1;<a name="line.1939"></a> -<span class="sourceLineNo">1940</span><a name="line.1940"></a> -<span class="sourceLineNo">1941</span> @Override<a name="line.1941"></a> -<span class="sourceLineNo">1942</span> public boolean hasNext() {<a name="line.1942"></a> -<span class="sourceLineNo">1943</span> return i < num+1;<a name="line.1943"></a> -<span class="sourceLineNo">1944</span> }<a name="line.1944"></a> -<span class="sourceLineNo">1945</span><a name="line.1945"></a> -<span class="sourceLineNo">1946</span> @Override<a name="line.1946"></a> -<span class="sourceLineNo">1947</span> public byte[] next() {<a name="line.1947"></a> -<span class="sourceLineNo">1948</span> i++;<a name="line.1948"></a> -<span class="sourceLineNo">1949</span> if (i == 0) return a;<a name="line.1949"></a> -<span class="sourceLineNo">1950</span> if (i == num + 1) return b;<a name="line.1950"></a> -<span class="sourceLineNo">1951</span><a name="line.1951"></a> -<span class="sourceLineNo">1952</span> BigInteger curBI = startBI.add(intervalBI.multiply(BigInteger.valueOf(i)));<a name="line.1952"></a> -<span class="sourceLineNo">1953</span> byte [] padded = curBI.toByteArray();<a name="line.1953"></a> -<span class="sourceLineNo">1954</span> if (padded[1] == 0)<a name="line.1954"></a> -<span class="sourceLineNo">1955</span> padded = tail(padded, padded.length - 2);<a name="line.1955"></a> -<span class="sourceLineNo">1956</span> else<a name="line.1956"></a> -<span class="sourceLineNo">1957</span> padded = tail(padded, padded.length - 1);<a name="line.1957"></a> -<span class="sourceLineNo">1958</span> return padded;<a name="line.1958"></a> -<span class="sourceLineNo">1959</span> }<a name="line.1959"></a> -<span class="sourceLineNo">1960</span><a name="line.1960"></a> -<span class="sourceLineNo">1961</span> @Override<a name="line.1961"></a> -<span class="sourceLineNo">1962</span> public void remove() {<a name="line.1962"></a> -<span class="sourceLineNo">1963</span> throw new UnsupportedOperationException();<a name="line.1963"></a> -<span class="sourceLineNo">1964</span> }<a name="line.1964"></a> -<span class="sourceLineNo">1965</span><a name="line.1965"></a> -<span class="sourceLineNo">1966</span> };<a name="line.1966"></a> -<span class="sourceLineNo">1967</span><a name="line.1967"></a> -<span class="sourceLineNo">1968</span> return new Iterable<byte[]>() {<a name="line.1968"></a> -<span class="sourceLineNo">1969</span> @Override<a name="line.1969"></a> -<span class="sourceLineNo">1970</span> public Iterator<byte[]> iterator() {<a name="line.1970"></a> -<span class="sourceLineNo">1971</span> return iterator;<a name="line.1971"></a> -<span class="sourceLineNo">1972</span> }<a name="line.1972"></a> -<span class="sourceLineNo">1973</span> };<a name="line.1973"></a> +<span class="sourceLineNo">1757</span> public static byte [] tail(final byte [] a, final int length) {<a name="line.1757"></a> +<span class="sourceLineNo">1758</span> if (a.length < length) {<a name="line.1758"></a> +<span class="sourceLineNo">1759</span> return null;<a name="line.1759"></a> +<span class="sourceLineNo">1760</span> }<a name="line.1760"></a> +<span class="sourceLineNo">1761</span> byte [] result = new byte[length];<a name="line.1761"></a> +<span class="sourceLineNo">1762</span> System.arraycopy(a, a.length - length, result, 0, length);<a name="line.1762"></a> +<span class="sourceLineNo">1763</span> return result;<a name="line.1763"></a> +<span class="sourceLineNo">1764</span> }<a name="line.1764"></a> +<span class="sourceLineNo">1765</span><a name="line.1765"></a> +<span class="sourceLineNo">1766</span> /**<a name="line.1766"></a> +<span class="sourceLineNo">1767</span> * @param a array<a name="line.1767"></a> +<span class="sourceLineNo">1768</span> * @param length new array size<a name="line.1768"></a> +<span class="sourceLineNo">1769</span> * @return Value in <code>a</code> plus <code>length</code> prepended 0 bytes<a name="line.1769"></a> +<span class="sourceLineNo">1770</span> */<a name="line.1770"></a> +<span class="sourceLineNo">1771</span> public static byte [] padHead(final byte [] a, final int length) {<a name="line.1771"></a> +<span class="sourceLineNo">1772</span> byte [] padding = new byte[length];<a name="line.1772"></a> +<span class="sourceLineNo">1773</span> for (int i = 0; i < length; i++) {<a name="line.1773"></a> +<span class="sourceLineNo">1774</span> padding[i] = 0;<a name="line.1774"></a> +<span class="sourceLineNo">1775</span> }<a name="line.1775"></a> +<span class="sourceLineNo">1776</span> return add(padding,a);<a name="line.1776"></a> +<span class="sourceLineNo">1777</span> }<a name="line.1777"></a> +<span class="sourceLineNo">1778</span><a name="line.1778"></a> +<span class="sourceLineNo">1779</span> /**<a name="line.1779"></a> +<span class="sourceLineNo">1780</span> * @param a array<a name="line.1780"></a> +<span class="sourceLineNo">1781</span> * @param length new array size<a name="line.1781"></a> +<span class="sourceLineNo">1782</span> * @return Value in <code>a</code> plus <code>length</code> appended 0 bytes<a name="line.1782"></a> +<span class="sourceLineNo">1783</span> */<a name="line.1783"></a> +<span class="sourceLineNo">1784</span> public static byte [] padTail(final byte [] a, final int length) {<a name="line.1784"></a> +<span class="sourceLineNo">1785</span> byte [] padding = new byte[length];<a name="line.1785"></a> +<span class="sourceLineNo">1786</span> for (int i = 0; i < length; i++) {<a name="line.1786"></a> +<span class="sourceLineNo">1787</span> padding[i] = 0;<a name="line.1787"></a> +<span class="sourceLineNo">1788</span> }<a name="line.1788"></a> +<span class="sourceLineNo">1789</span> return add(a,padding);<a name="line.1789"></a> +<span class="sourceLineNo">1790</span> }<a name="line.1790"></a> +<span class="sourceLineNo">1791</span><a name="line.1791"></a> +<span class="sourceLineNo">1792</span> /**<a name="line.1792"></a> +<span class="sourceLineNo">1793</span> * Split passed range. Expensive operation relatively. Uses BigInteger math.<a name="line.1793"></a> +<span class="sourceLineNo">1794</span> * Useful splitting ranges for MapReduce jobs.<a name="line.1794"></a> +<span class="sourceLineNo">1795</span> * @param a Beginning of range<a name="line.1795"></a> +<span class="sourceLineNo">1796</span> * @param b End of range<a name="line.1796"></a> +<span class="sourceLineNo">1797</span> * @param num Number of times to split range. Pass 1 if you want to split<a name="line.1797"></a> +<span class="sourceLineNo">1798</span> * the range in two; i.e. one split.<a name="line.1798"></a> +<span class="sourceLineNo">1799</span> * @return Array of dividing values<a name="line.1799"></a> +<span class="sourceLineNo">1800</span> */<a name="line.1800"></a> +<span class="sourceLineNo">1801</span> public static byte [][] split(final byte [] a, final byte [] b, final int num) {<a name="line.1801"></a> +<span class="sourceLineNo">1802</span> return split(a, b, false, num);<a name="line.1802"></a> +<span class="sourceLineNo">1803</span> }<a name="line.1803"></a> +<span class="sourceLineNo">1804</span><a name="line.1804"></a> +<span class="sourceLineNo">1805</span> /**<a name="line.1805"></a> +<span class="sourceLineNo">1806</span> * Split passed range. Expensive operation relatively. Uses BigInteger math.<a name="line.1806"></a> +<span class="sourceLineNo">1807</span> * Useful splitting ranges for MapReduce jobs.<a name="line.1807"></a> +<span class="sourceLineNo">1808</span> * @param a Beginning of range<a name="line.1808"></a> +<span class="sourceLineNo">1809</span> * @param b End of range<a name="line.1809"></a> +<span class="sourceLineNo">1810</span> * @param inclusive Whether the end of range is prefix-inclusive or is<a name="line.1810"></a> +<span class="sourceLineNo">1811</span> * considered an exclusive boundary. Automatic splits are generally exclusive<a name="line.1811"></a> +<span class="sourceLineNo">1812</span> * and manual splits with an explicit range utilize an inclusive end of range.<a name="line.1812"></a> +<span class="sourceLineNo">1813</span> * @param num Number of times to split range. Pass 1 if you want to split<a name="line.1813"></a> +<span class="sourceLineNo">1814</span> * the range in two; i.e. one split.<a name="line.1814"></a> +<span class="sourceLineNo">1815</span> * @return Array of dividing values<a name="line.1815"></a> +<span class="sourceLineNo">1816</span> */<a name="line.1816"></a> +<span class="sourceLineNo">1817</span> public static byte[][] split(final byte[] a, final byte[] b,<a name="line.1817"></a> +<span class="sourceLineNo">1818</span> boolean inclusive, final int num) {<a name="line.1818"></a> +<span class="sourceLineNo">1819</span> byte[][] ret = new byte[num + 2][];<a name="line.1819"></a> +<span class="sourceLineNo">1820</span> int i = 0;<a name="line.1820"></a> +<span class="sourceLineNo">1821</span> Iterable<byte[]> iter = iterateOnSplits(a, b, inclusive, num);<a name="line.1821"></a> +<span class="sourceLineNo">1822</span> if (iter == null)<a name="line.1822"></a> +<span class="sourceLineNo">1823</span> return null;<a name="line.1823"></a> +<span class="sourceLineNo">1824</span> for (byte[] elem : iter) {<a name="line.1824"></a> +<span class="sourceLineNo">1825</span> ret[i++] = elem;<a name="line.1825"></a> +<span class="sourceLineNo">1826</span> }<a name="line.1826"></a> +<span class="sourceLineNo">1827</span> return ret;<a name="line.1827"></a> +<span class="sourceLineNo">1828</span> }<a name="line.1828"></a> +<span class="sourceLineNo">1829</span><a name="line.1829"></a> +<span class="sourceLineNo">1830</span> /**<a name="line.1830"></a> +<span class="sourceLineNo">1831</span> * Iterate over keys within the passed range, splitting at an [a,b) boundary.<a name="line.1831"></a> +<span class="sourceLineNo">1832</span> */<a name="line.1832"></a> +<span class="sourceLineNo">1833</span> public static Iterable<byte[]> iterateOnSplits(final byte[] a,<a name="line.1833"></a> +<span class="sourceLineNo">1834</span> final byte[] b, final int num)<a name="line.1834"></a> +<span class="sourceLineNo">1835</span> {<a name="line.1835"></a> +<span class="sourceLineNo">1836</span> return iterateOnSplits(a, b, false, num);<a name="line.1836"></a> +<span class="sourceLineNo">1837</span> }<a name="line.1837"></a> +<span class="sourceLineNo">1838</span><a name="line.1838"></a> +<span class="sourceLineNo">1839</span> /**<a name="line.1839"></a> +<span class="sourceLineNo">1840</span> * Iterate over keys within the passed range.<a name="line.1840"></a> +<span class="sourceLineNo">1841</span> */<a name="line.1841"></a> +<span class="sourceLineNo">1842</span> public static Iterable<byte[]> iterateOnSplits(<a name="line.1842"></a> +<span class="sourceLineNo">1843</span> final byte[] a, final byte[]b, boolean inclusive, final int num)<a name="line.1843"></a> +<span class="sourceLineNo">1844</span> {<a name="line.1844"></a> +<span class="sourceLineNo">1845</span> byte [] aPadded;<a name="line.1845"></a> +<span class="sourceLineNo">1846</span> byte [] bPadded;<a name="line.1846"></a> +<span class="sourceLineNo">1847</span> if (a.length < b.length) {<a name="line.1847"></a> +<span class="sourceLineNo">1848</span> aPadded = padTail(a, b.length - a.length);<a name="line.1848"></a> +<span class="sourceLineNo">1849</span> bPadded = b;<a name="line.1849"></a> +<span class="sourceLineNo">1850</span> } else if (b.length < a.length) {<a name="line.1850"></a> +<span class="sourceLineNo">1851</span> aPadded = a;<a name="line.1851"></a> +<span class="sourceLineNo">1852</span> bPadded = padTail(b, a.length - b.length);<a name="line.1852"></a> +<span class="sourceLineNo">1853</span> } else {<a name="line.1853"></a> +<span class="sourceLineNo">1854</span> aPadded = a;<a name="line.1854"></a> +<span class="sourceLineNo">1855</span> bPadded = b;<a name="line.1855"></a> +<span class="sourceLineNo">1856</span> }<a name="line.1856"></a> +<span class="sourceLineNo">1857</span> if (compareTo(aPadded,bPadded) >= 0) {<a name="line.1857"></a> +<span class="sourceLineNo">1858</span> throw new IllegalArgumentException("b <= a");<a name="line.1858"></a> +<span class="sourceLineNo">1859</span> }<a name="line.1859"></a> +<span class="sourceLineNo">1860</span> if (num <= 0) {<a name="line.1860"></a> +<span class="sourceLineNo">1861</span> throw new IllegalArgumentException("num cannot be <= 0");<a name="line.1861"></a> +<span class="sourceLineNo">1862</span> }<a name="line.1862"></a> +<span class="sourceLineNo">1863</span> byte [] prependHeader = {1, 0};<a name="line.1863"></a> +<span class="sourceLineNo">1864</span> final BigInteger startBI = new BigInteger(add(prependHeader, aPadded));<a name="line.1864"></a> +<span class="sourceLineNo">1865</span> final BigInteger stopBI = new BigInteger(add(prependHeader, bPadded));<a name="line.1865"></a> +<span class="sourceLineNo">1866</span> BigInteger diffBI = stopBI.subtract(startBI);<a name="line.1866"></a> +<span class="sourceLineNo">1867</span> if (inclusive) {<a name="line.1867"></a> +<span class="sourceLineNo">1868</span> diffBI = diffBI.add(BigInteger.ONE);<a name="line.1868"></a> +<span class="sourceLineNo">1869</span> }<a name="line.1869"></a> +<span class="sourceLineNo">1870</span> final BigInteger splitsBI = BigInteger.valueOf(num + 1);<a name="line.1870"></a> +<span class="sourceLineNo">1871</span> //when diffBI < splitBI, use an additional byte to increase diffBI<a name="line.1871"></a> +<span class="sourceLineNo">1872</span> if(diffBI.compareTo(splitsBI) < 0) {<a name="line.1872"></a> +<span class="sourceLineNo">1873</span> byte[] aPaddedAdditional = new byte[aPadded.length+1];<a name="line.1873"></a> +<span class="sourceLineNo">1874</span> byte[] bPaddedAdditional = new byte[bPadded.length+1];<a name="line.1874"></a> +<span class="sourceLineNo">1875</span> for (int i = 0; i < aPadded.length; i++){<a name="line.1875"></a> +<span class="sourceLineNo">1876</span> aPaddedAdditional[i] = aPadded[i];<a name="line.1876"></a> +<span class="sourceLineNo">1877</span> }<a name="line.1877"></a> +<span class="sourceLineNo">1878</span> for (int j = 0; j < bPadded.length; j++){<a name="line.1878"></a> +<span class="sourceLineNo">1879</span> bPaddedAdditional[j] = bPadded[j];<a name="line.1879"></a> +<span class="sourceLineNo">1880</span> }<a name="line.1880"></a> +<span class="sourceLineNo">1881</span> aPaddedAdditional[aPadded.length] = 0;<a name="line.1881"></a> +<span class="sourceLineNo">1882</span> bPaddedAdditional[bPadded.length] = 0;<a name="line.1882"></a> +<span class="sourceLineNo">1883</span> return iterateOnSplits(aPaddedAdditional, bPaddedAdditional, inclusive, num);<a name="line.1883"></a> +<span class="sourceLineNo">1884</span> }<a name="line.1884"></a> +<span class="sourceLineNo">1885</span> final BigInteger intervalBI;<a name="line.1885"></a> +<span class="sourceLineNo">1886</span> try {<a name="line.1886"></a> +<span class="sourceLineNo">1887</span> intervalBI = diffBI.divide(splitsBI);<a name="line.1887"></a> +<span class="sourceLineNo">1888</span> } catch(Exception e) {<a name="line.1888"></a> +<span class="sourceLineNo">1889</span> LOG.error("Exception caught during division", e);<a name="line.1889"></a> +<span class="sourceLineNo">1890</span> return null;<a name="line.1890"></a> +<span class="sourceLineNo">1891</span> }<a name="line.1891"></a> +<span class="sourceLineNo">1892</span><a name="line.1892"></a> +<span class="sourceLineNo">1893</span> final Iterator<byte[]> iterator = new Iterator<byte[]>() {<a name="line.1893"></a> +<span class="sourceLineNo">1894</span> private int i = -1;<a name="line.1894"></a> +<span class="sourceLineNo">1895</span><a name="line.1895"></a> +<span class="sourceLineNo">1896</span> @Override<a name="line.1896"></a> +<span class="sourceLineNo">1897</span> public boolean hasNext() {<a name="line.1897"></a> +<span class="sourceLineNo">1898</span> return i < num+1;<a name="line.1898"></a> +<span class="sourceLineNo">1899</span> }<a name="line.1899"></a> +<span class="sourceLineNo">1900</span><a name="line.1900"></a> +<span class="sourceLineNo">1901</span> @Override<a name="line.1901"></a> +<span class="sourceLineNo">1902</span> public byte[] next() {<a name="line.1902"></a> +<span class="sourceLineNo">1903</span> i++;<a name="line.1903"></a> +<span class="sourceLineNo">1904</span> if (i == 0) return a;<a name="line.1904"></a> +<span class="sourceLineNo">1905</span> if (i == num + 1) return b;<a name="line.1905"></a> +<span class="sourceLineNo">1906</span><a name="line.1906"></a> +<span class="sourceLineNo">1907</span> BigInteger curBI = startBI.add(intervalBI.multiply(BigInteger.valueOf(i)));<a name="line.1907"></a> +<span class="sourceLineNo">1908</span> byte [] padded = curBI.toByteArray();<a name="line.1908"></a> +<span class="sourceLineNo">1909</span> if (padded[1] == 0)<a name="line.1909"></a> +<span class="sourceLineNo">1910</span> padded = tail(padded, padded.length - 2);<a name="line.1910"></a> +<span class="sourceLineNo">1911</span> else<a name="line.1911"></a> +<span class="sourceLineNo">1912</span> padded = tail(padded, padded.length - 1);<a name="line.1912"></a> +<span class="sourceLineNo">1913</span> return padded;<a name="line.1913"></a> +<span class="sourceLineNo">1914</span> }<a name="line.1914"></a> +<span class="sourceLineNo">1915</span><a name="line.1915"></a> +<span class="sourceLineNo">1916</span> @Override<a name="line.1916"></a> +<span class="sourceLineNo">1917</span> public void remove() {<a name="line.1917"></a> +<span class="sourceLineNo">1918</span> throw new UnsupportedOperationException();<a name="line.1918"></a> +<span class="sourceLineNo">1919</span> }<a name="line.1919"></a> +<span class="sourceLineNo">1920</span><a name="line.1920"></a> +<span class="sourceLineNo">1921</span> };<a name="line.1921"></a> +<span class="sourceLineNo">1922</span><a name="line.1922"></a> +<span class="sourceLineNo">1923</span> return new Iterable<byte[]>() {<a name="line.1923"></a> +<span class="sourceLineNo">1924</span> @Override<a name="line.1924"></a> +<span class="sourceLineNo">1925</span> public Iterator<byte[]> iterator() {<a name="line.1925"></a> +<span class="sourceLineNo">1926</span> return iterator;<a name="line.1926"></a> +<span class="sourceLineNo">1927</span> }<a name="line.1927"></a> +<span class="sourceLineNo">1928</span> };<a name="line.1928"></a> +<span class="sourceLineNo">1929</span> }<a name="line.1929"></a> +<span class="sourceLineNo">1930</span><a name="line.1930"></a> +<span class="sourceLineNo">1931</span> /**<a name="line.1931"></a> +<span class="sourceLineNo">1932</span> * @param bytes array to hash<a name="line.1932"></a> +<span class="sourceLineNo">1933</span> * @param offset offset to start from<a name="line.1933"></a> +<span class="sourceLineNo">1934</span> * @param length length to hash<a name="line.1934"></a> +<span class="sourceLineNo">1935</span> * */<a name="line.1935"></a> +<span class="sourceLineNo">1936</span> public static int hashCode(byte[] bytes, int offset, int length) {<a name="line.1936"></a> +<span class="sourceLineNo">1937</span> int hash = 1;<a name="line.1937"></a> +<span class="sourceLineNo">1938</span> for (int i = offset; i < offset + length; i++)<a name="line.1938"></a> +<span class="sourceLineNo">1939</span> hash = (31 * hash) + (int) bytes[i];<a name="line.1939"></a> +<span class="sourceLineNo">1940</span> return hash;<a name="line.1940"></a> +<span class="sourceLineNo">1941</span> }<a name="line.1941"></a> +<span class="sourceLineNo">1942</span><a name="line.1942"></a> +<span class="sourceLineNo">1943</span> /**<a name="line.1943"></a> +<span class="sourceLineNo">1944</span> * @param t operands<a name="line.1944"></a> +<span class="sourceLineNo">1945</span> * @return Array of byte arrays made from passed array of Text<a name="line.1945"></a> +<span class="sourceLineNo">1946</span> */<a name="line.1946"></a> +<span class="sourceLineNo">1947</span> public static byte [][] toByteArrays(final String [] t) {<a name="line.1947"></a> +<span class="sourceLineNo">1948</span> byte [][] result = new byte[t.length][];<a name="line.1948"></a> +<span class="sourceLineNo">1949</span> for (int i = 0; i < t.length; i++) {<a name="line.1949"></a> +<span class="sourceLineNo">1950</span> result[i] = Bytes.toBytes(t[i]);<a name="line.1950"></a> +<span class="sourceLineNo">1951</span> }<a name="line.1951"></a> +<span class="sourceLineNo">1952</span> return result;<a name="line.1952"></a> +<span class="sourceLineNo">1953</span> }<a name="line.1953"></a> +<span class="sourceLineNo">1954</span><a name="line.1954"></a> +<span class="sourceLineNo">1955</span> /**<a name="line.1955"></a> +<span class="sourceLineNo">1956</span> * @param t operands<a name="line.1956"></a> +<span class="sourceLineNo">1957</span> * @return Array of binary byte arrays made from passed array of binary strings<a name="line.1957"></a> +<span class="sourceLineNo">1958</span> */<a name="line.1958"></a> +<span class="sourceLineNo">1959</span> public static byte[][] toBinaryByteArrays(final String[] t) {<a name="line.1959"></a> +<span class="sourceLineNo">1960</span> byte[][] result = new byte[t.length][];<a name="line.1960"></a> +<span class="sourceLineNo">1961</span> for (int i = 0; i < t.length; i++) {<a name="line.1961"></a> +<span class="sourceLineNo">1962</span> result[i] = Bytes.toBytesBinary(t[i]);<a name="line.1962"></a> +<span class="sourceLineNo">1963</span> }<a name="line.1963"></a> +<span class="sourceLineNo">1964</span> return result;<a name="line.1964"></a> +<span class="sourceLineNo">1965</span> }<a name="line.1965"></a> +<span class="sourceLineNo">1966</span><a name="line.1966"></a> +<span class="sourceLineNo">1967</span> /**<a name="line.1967"></a> +<span class="sourceLineNo">1968</span> * @param column operand<a name="line.1968"></a> +<span class="sourceLineNo">1969</span> * @return A byte array of a byte array where first and only entry is<a name="line.1969"></a> +<span class="sourceLineNo">1970</span> * <code>column</code><a name="line.1970"></a> +<span class="sourceLineNo">1971</span> */<a name="line.1971"></a> +<span class="sourceLineNo">1972</span> public static byte [][] toByteArrays(final String column) {<a name="line.1972"></a> +<span class="sourceLineNo">1973</span> return toByteArrays(toBytes(column));<a name="line.1973"></a> <span class="sourceLineNo">1974</span> }<a name="line.1974"></a> <span class="sourceLineNo">1975</span><a name="li
<TRUNCATED>