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  
52    public static int compareStatic(Cell a, Cell b) {
53      //row
54      int c = Bytes.compareTo(
55          a.getRowArray(), a.getRowOffset(), a.getRowLength(),
56          b.getRowArray(), b.getRowOffset(), b.getRowLength());
57      if (c != 0) return c;
58  
59      // If the column is not specified, the "minimum" key type appears the
60      // latest in the sorted order, regardless of the timestamp. This is used
61      // for specifying the last key/value in a given row, because there is no
62      // "lexicographically last column" (it would be infinitely long). The
63      // "maximum" key type does not need this behavior.
64      if (a.getFamilyLength() == 0 && a.getTypeByte() == Type.Minimum.getCode()) {
65        // a is "bigger", i.e. it appears later in the sorted order
66        return 1;
67      }
68      if (b.getFamilyLength() == 0 && b.getTypeByte() == Type.Minimum.getCode()) {
69        return -1;
70      }
71  
72      //family
73      c = Bytes.compareTo(
74        a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
75        b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
76      if (c != 0) return c;
77  
78      //qualifier
79      c = Bytes.compareTo(
80          a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
81          b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
82      if (c != 0) return c;
83  
84      //timestamp: later sorts first
85      c = Longs.compare(b.getTimestamp(), a.getTimestamp());
86      if (c != 0) return c;
87  
88      //type
89      c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
90      if (c != 0) return c;
91  
92      //mvccVersion: later sorts first
93      return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
94    }
95  
96  
97    /**************** equals ****************************/
98  
99    public static boolean equals(Cell a, Cell b){
100     return equalsRow(a, b)
101         && equalsFamily(a, b)
102         && equalsQualifier(a, b)
103         && equalsTimestamp(a, b)
104         && equalsType(a, b);
105   }
106 
107   public static boolean equalsRow(Cell a, Cell b){
108     return Bytes.equals(
109       a.getRowArray(), a.getRowOffset(), a.getRowLength(),
110       b.getRowArray(), b.getRowOffset(), b.getRowLength());
111   }
112 
113   public static boolean equalsFamily(Cell a, Cell b){
114     return Bytes.equals(
115       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
116       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
117   }
118 
119   public static boolean equalsQualifier(Cell a, Cell b){
120     return Bytes.equals(
121       a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
122       b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
123   }
124 
125   public static boolean equalsTimestamp(Cell a, Cell b){
126     return a.getTimestamp() == b.getTimestamp();
127   }
128 
129   public static boolean equalsType(Cell a, Cell b){
130     return a.getTypeByte() == b.getTypeByte();
131   }
132 
133 
134   /********************* hashCode ************************/
135 
136   /**
137    * Returns a hash code that is always the same for two Cells having a matching equals(..) result.
138    * Currently does not guard against nulls, but it could if necessary.
139    */
140   public static int hashCode(Cell cell){
141     if (cell == null) {// return 0 for empty Cell
142       return 0;
143     }
144 
145     //pre-calculate the 3 hashes made of byte ranges
146     int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
147     int familyHash =
148       Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
149     int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
150       cell.getQualifierLength());
151 
152     //combine the 6 sub-hashes
153     int hash = 31 * rowHash + familyHash;
154     hash = 31 * hash + qualifierHash;
155     hash = 31 * hash + (int)cell.getTimestamp();
156     hash = 31 * hash + cell.getTypeByte();
157     hash = 31 * hash + (int)cell.getMvccVersion();
158     return hash;
159   }
160 
161 
162   /******************** lengths *************************/
163 
164   public static boolean areKeyLengthsEqual(Cell a, Cell b) {
165     return a.getRowLength() == b.getRowLength()
166         && a.getFamilyLength() == b.getFamilyLength()
167         && a.getQualifierLength() == b.getQualifierLength();
168   }
169 
170   public static boolean areRowLengthsEqual(Cell a, Cell b) {
171     return a.getRowLength() == b.getRowLength();
172   }
173 
174 
175   /***************** special cases ****************************/
176 
177   /**
178    * special case for KeyValue.equals
179    */
180   private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
181     //row
182     int c = Bytes.compareTo(
183         a.getRowArray(), a.getRowOffset(), a.getRowLength(),
184         b.getRowArray(), b.getRowOffset(), b.getRowLength());
185     if (c != 0) return c;
186 
187     //family
188     c = Bytes.compareTo(
189       a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
190       b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
191     if (c != 0) return c;
192 
193     //qualifier
194     c = Bytes.compareTo(
195         a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
196         b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
197     if (c != 0) return c;
198 
199     //timestamp: later sorts first
200     c = Longs.compare(b.getTimestamp(), a.getTimestamp());
201     if (c != 0) return c;
202 
203     //type
204     c = (0xff & a.getTypeByte()) - (0xff & b.getTypeByte());
205     return c;
206   }
207 
208   /**
209    * special case for KeyValue.equals
210    */
211   public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
212     return 0 == compareStaticIgnoreMvccVersion(a, b);
213   }
214 
215 }