1   /**
2    * Copyright 2009 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import java.util.Iterator;
23  import java.util.SortedSet;
24  
25  import org.apache.hadoop.hbase.KeyValue;
26  import org.apache.hadoop.hbase.util.Bytes;
27  
28  import junit.framework.TestCase;
29  
30  public class TestKeyValueSkipListSet extends TestCase {
31    private final KeyValueSkipListSet kvsls =
32      new KeyValueSkipListSet(KeyValue.COMPARATOR);
33  
34    protected void setUp() throws Exception {
35      super.setUp();
36      this.kvsls.clear();
37    }
38  
39    public void testAdd() throws Exception {
40      byte [] bytes = Bytes.toBytes(getName());
41      KeyValue kv = new KeyValue(bytes, bytes, bytes, bytes);
42      this.kvsls.add(kv);
43      assertTrue(this.kvsls.contains(kv));
44      assertEquals(1, this.kvsls.size());
45      KeyValue first = this.kvsls.first();
46      assertTrue(kv.equals(first));
47      assertTrue(Bytes.equals(kv.getValue(), first.getValue()));
48      // Now try overwritting
49      byte [] overwriteValue = Bytes.toBytes("overwrite");
50      KeyValue overwrite = new KeyValue(bytes, bytes, bytes, overwriteValue);
51      this.kvsls.add(overwrite);
52      assertEquals(1, this.kvsls.size());
53      first = this.kvsls.first();
54      assertTrue(Bytes.equals(overwrite.getValue(), first.getValue()));
55      assertFalse(Bytes.equals(overwrite.getValue(), kv.getValue()));
56    }
57  
58    public void testIterator() throws Exception {
59      byte [] bytes = Bytes.toBytes(getName());
60      byte [] value1 = Bytes.toBytes("1");
61      byte [] value2 = Bytes.toBytes("2");
62      final int total = 3;
63      for (int i = 0; i < total; i++) {
64        this.kvsls.add(new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value1));
65      }
66      // Assert that we added 'total' values and that they are in order
67      int count = 0;
68      for (KeyValue kv: this.kvsls) {
69        assertEquals("" + count, Bytes.toString(kv.getQualifier()));
70        assertTrue(Bytes.equals(kv.getValue(), value1));
71        count++;
72      }
73      assertEquals(total, count);
74      // Now overwrite with a new value.
75      for (int i = 0; i < total; i++) {
76        this.kvsls.add(new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value2));
77      }
78      // Assert that we added 'total' values and that they are in order and that
79      // we are getting back value2
80      count = 0;
81      for (KeyValue kv: this.kvsls) {
82        assertEquals("" + count, Bytes.toString(kv.getQualifier()));
83        assertTrue(Bytes.equals(kv.getValue(), value2));
84        count++;
85      }
86      assertEquals(total, count);
87    }
88  
89    public void testDescendingIterator() throws Exception {
90      byte [] bytes = Bytes.toBytes(getName());
91      byte [] value1 = Bytes.toBytes("1");
92      byte [] value2 = Bytes.toBytes("2");
93      final int total = 3;
94      for (int i = 0; i < total; i++) {
95        this.kvsls.add(new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value1));
96      }
97      // Assert that we added 'total' values and that they are in order
98      int count = 0;
99      for (Iterator<KeyValue> i = this.kvsls.descendingIterator(); i.hasNext();) {
100       KeyValue kv = i.next();
101       assertEquals("" + (total - (count + 1)), Bytes.toString(kv.getQualifier()));
102       assertTrue(Bytes.equals(kv.getValue(), value1));
103       count++;
104     }
105     assertEquals(total, count);
106     // Now overwrite with a new value.
107     for (int i = 0; i < total; i++) {
108       this.kvsls.add(new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value2));
109     }
110     // Assert that we added 'total' values and that they are in order and that
111     // we are getting back value2
112     count = 0;
113     for (Iterator<KeyValue> i = this.kvsls.descendingIterator(); i.hasNext();) {
114       KeyValue kv = i.next();
115       assertEquals("" + (total - (count + 1)), Bytes.toString(kv.getQualifier()));
116       assertTrue(Bytes.equals(kv.getValue(), value2));
117       count++;
118     }
119     assertEquals(total, count);
120   }
121 
122   public void testHeadTail() throws Exception {
123     byte [] bytes = Bytes.toBytes(getName());
124     byte [] value1 = Bytes.toBytes("1");
125     byte [] value2 = Bytes.toBytes("2");
126     final int total = 3;
127     KeyValue splitter = null;
128     for (int i = 0; i < total; i++) {
129       KeyValue kv = new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value1);
130       if (i == 1) splitter = kv;
131       this.kvsls.add(kv);
132     }
133     SortedSet<KeyValue> tail = this.kvsls.tailSet(splitter);
134     assertEquals(2, tail.size());
135     SortedSet<KeyValue> head = this.kvsls.headSet(splitter);
136     assertEquals(1, head.size());
137     // Now ensure that we get back right answer even when we do tail or head.
138     // Now overwrite with a new value.
139     for (int i = 0; i < total; i++) {
140       this.kvsls.add(new KeyValue(bytes, bytes, Bytes.toBytes("" + i), value2));
141     }
142     tail = this.kvsls.tailSet(splitter);
143     assertTrue(Bytes.equals(tail.first().getValue(), value2));
144     head = this.kvsls.headSet(splitter);
145     assertTrue(Bytes.equals(head.first().getValue(), value2));
146   }
147 }