View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase;
20  
21  import java.io.Serializable;
22  import java.util.Comparator;
23  
24  import org.apache.hadoop.classification.InterfaceAudience;
25  import org.apache.hadoop.classification.InterfaceStability;
26  import org.apache.hadoop.hbase.KeyValue.Type;
27  import org.apache.hadoop.hbase.util.Bytes;
28  
29  import com.google.common.primitives.Longs;
30  
31  /**
32   * Compare two HBase cells.  Do not use this method comparing <code>-ROOT-</code> or
33   * <code>hbase:meta</code> cells.  Cells from these tables need a specialized comparator, one that
34   * takes account of the special formatting of the row where we have commas to delimit table from
35   * regionname, from row.  See KeyValue for how it has a special comparator to do hbase:meta cells
36   * and yet another for -ROOT-.
37   */
38  @edu.umd.cs.findbugs.annotations.SuppressWarnings(
39      value="UNKNOWN",
40      justification="Findbugs doesn't like the way we are negating the result of a compare in below")
41  @InterfaceAudience.Private
42  @InterfaceStability.Evolving
43  public class CellComparator implements Comparator<Cell>, Serializable{
44    private static final long serialVersionUID = -8760041766259623329L;
45  
46    @Override
47    public int compare(Cell a, Cell b) {
48      return compareStatic(a, b);
49    }
50  
51    public static int compareStatic(Cell a, Cell b) {
52      return compareStatic(a, b, false);
53    }
54    
55    public static int compareStatic(Cell a, Cell b, boolean onlyKey) {
56      //row
57      int c = Bytes.compareTo(
58          a.getRowArray(), a.getRowOffset(), a.getRowLength(),
59          b.getRowArray(), b.getRowOffset(), b.getRowLength());
60      if (c != 0) return c;
61  
62      // If the column is not specified, the "minimum" key type appears the
63      // latest in the sorted order, regardless of the timestamp. This is used
64      // for specifying the last key/value in a given row, because there is no
65      // "lexicographically last column" (it would be infinitely long). The
66      // "maximum" key type does not need this behavior.
67      if (a.getFamilyLength() == 0 && a.getTypeByte() == Type.Minimum.getCode()) {
68        // a is "bigger", i.e. it appears later in the sorted order
69        return 1;
70      }
71      if (b.getFamilyLength() == 0 && b.getTypeByte() == Type.Minimum.getCode()) {
72        return -1;
73      }
74  
75      //family
76      c = Bytes.compareTo(
77        a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
78        b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
79      if (c != 0) return c;
80  
81      //qualifier
82      c = Bytes.compareTo(
83          a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
84          b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
85      if (c != 0) return c;
86  
87      //timestamp: later sorts first
88      c = Longs.compare(b.getTimestamp(), a.getTimestamp());
89      if (c != 0) return c;
90  
91      //type
92      c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
93      if (c != 0) return c;
94  
95      if (onlyKey) return c;
96  
97      //mvccVersion: later sorts first
98      return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
99    }
100 
101 
102   /**************** equals ****************************/
103 
104   public static boolean equals(Cell a, Cell b){
105     return equalsRow(a, b)
106         && equalsFamily(a, b)
107         && equalsQualifier(a, b)
108         && equalsTimestamp(a, b)
109         && equalsType(a, b);
110   }
111 
112   public static boolean equalsRow(Cell a, Cell b){
113     return Bytes.equals(
114       a.getRowArray(), a.getRowOffset(), a.getRowLength(),
115       b.getRowArray(), b.getRowOffset(), b.getRowLength());
116   }
117 
118   public static boolean equalsFamily(Cell a, Cell b){
119     return Bytes.equals(
120       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
121       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
122   }
123 
124   public static boolean equalsQualifier(Cell a, Cell b){
125     return Bytes.equals(
126       a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
127       b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
128   }
129 
130   public static boolean equalsTimestamp(Cell a, Cell b){
131     return a.getTimestamp() == b.getTimestamp();
132   }
133 
134   public static boolean equalsType(Cell a, Cell b){
135     return a.getTypeByte() == b.getTypeByte();
136   }
137 
138 
139   /********************* hashCode ************************/
140 
141   /**
142    * Returns a hash code that is always the same for two Cells having a matching equals(..) result.
143    * Currently does not guard against nulls, but it could if necessary.
144    */
145   public static int hashCode(Cell cell){
146     if (cell == null) {// return 0 for empty Cell
147       return 0;
148     }
149 
150     //pre-calculate the 3 hashes made of byte ranges
151     int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
152     int familyHash =
153       Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
154     int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
155       cell.getQualifierLength());
156 
157     //combine the 6 sub-hashes
158     int hash = 31 * rowHash + familyHash;
159     hash = 31 * hash + qualifierHash;
160     hash = 31 * hash + (int)cell.getTimestamp();
161     hash = 31 * hash + cell.getTypeByte();
162     hash = 31 * hash + (int)cell.getMvccVersion();
163     return hash;
164   }
165 
166 
167   /******************** lengths *************************/
168 
169   public static boolean areKeyLengthsEqual(Cell a, Cell b) {
170     return a.getRowLength() == b.getRowLength()
171         && a.getFamilyLength() == b.getFamilyLength()
172         && a.getQualifierLength() == b.getQualifierLength();
173   }
174 
175   public static boolean areRowLengthsEqual(Cell a, Cell b) {
176     return a.getRowLength() == b.getRowLength();
177   }
178 
179 
180   /***************** special cases ****************************/
181 
182   /**
183    * special case for KeyValue.equals
184    */
185   private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
186     //row
187     int c = Bytes.compareTo(
188         a.getRowArray(), a.getRowOffset(), a.getRowLength(),
189         b.getRowArray(), b.getRowOffset(), b.getRowLength());
190     if (c != 0) return c;
191 
192     //family
193     c = Bytes.compareTo(
194       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
195       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
196     if (c != 0) return c;
197 
198     //qualifier
199     c = Bytes.compareTo(
200         a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
201         b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
202     if (c != 0) return c;
203 
204     //timestamp: later sorts first
205     c = Longs.compare(b.getTimestamp(), a.getTimestamp());
206     if (c != 0) return c;
207 
208     //type
209     c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
210     return c;
211   }
212 
213   /**
214    * special case for KeyValue.equals
215    */
216   public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
217     return 0 == compareStaticIgnoreMvccVersion(a, b);
218   }
219 
220 }