PackedOffsets


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: PackedOffsets.java,v 1.7 2006/10/30 21:14:13 bostic Exp $
7    */
8   
9   package com.sleepycat.je.cleaner;
10  
11  import java.nio.ByteBuffer  ;
12  import java.util.Arrays  ;
13  
14  import com.sleepycat.je.log.LogReadable;
15  import com.sleepycat.je.log.LogUtils;
16  import com.sleepycat.je.log.LogWritable;
17  
18  /**
19   * Stores a sorted list of LSN offsets in a packed short representation.  Each
20   * stored value is the difference between two consecutive offsets.  The stored
21   * values are stored as one or more shorts where each short holds 0x7fff
22   * values.  Shorts are in LSB order.  The value is negated if more shorts for
23   * the same offset follow; this works because offsets are always positive
24   * values.
25   */
26  public class PackedOffsets implements LogWritable, LogReadable {
27  
28      private short[] data;
29      private int size;
30  
31      /**
32       * Creates an empty object.
33       */
34      public PackedOffsets() {
35      }
36  
37      /**
38       * Returns an iterator over all offsets.
39       */
40      Iterator iterator() {
41          return new Iterator();
42      }
43  
44      /**
45       * Packs the given offsets, replacing any offsets stored in this object.
46       */
47      public void pack(long[] offsets) {
48  
49          /* Allocate a maximum sized new data array. */
50          short[] newData = new short[offsets.length * 3];
51  
52          /* Pack the sorted offsets. */
53          Arrays.sort(offsets);
54          int dataIndex = 0;
55          long priorVal = 0;
56          for (int i = 0; i < offsets.length; i += 1) {
57              long val = offsets[i];
58              dataIndex = append(newData, dataIndex, val - priorVal);
59              priorVal = val;
60          }
61  
62          /* Copy in the exact sized new data. */
63          data = new short[dataIndex];
64          System.arraycopy(newData, 0, data, 0, dataIndex);
65          size = offsets.length;
66      }
67  
68      /** 
69       * Returns the unpacked offsets.
70       */
71      long[] toArray() {
72          long[] offsets = new long[size];
73          int index = 0;
74          Iterator iter = iterator();
75          while (iter.hasNext()) {
76              offsets[index++] = iter.next();
77          }
78          assert index == size;
79          return offsets;
80      }
81  
82      /**
83       * Copies the given value as a packed long to the array starting at the
84       * given index.  Returns the index of the next position in the array.
85       */
86      private int append(short[] to, int index, long val) {
87  
88          assert val >= 0;
89  
90          while (true) {
91              short s = (short) (val & 0x7fff);
92              val >>>= 15;
93              if (val > 0) {
94                  to[index++] = (short) (-1 - s);
95              } else {
96                  to[index++] = s;
97                  break;
98              }
99          }
100         return index;
101     }
102 
103     /**
104      * An iterator over all offsets.
105      */
106     class Iterator {
107 
108         private int index;
109         private long priorVal;
110 
111         private Iterator() {
112         }
113 
114         boolean hasNext() {
115             return data != null && index < data.length;
116         }
117 
118         long next() {
119             long val = priorVal;
120             for (int shift = 0;; shift += 15) {
121                 long s = data[index++];
122                 if (s < 0) {
123                     val += (-1 - s) << shift;
124                 } else {
125                     val += s << shift;
126                     break;
127                 }
128             }
129             priorVal = val;
130             return val;
131         }
132     }
133 
134     /**
135      * @see LogWritable#getLogSize
136      */
137     public int getLogSize() {
138 
139         return (2 * LogUtils.getIntLogSize()) +
140             ((data != null) ? (data.length * LogUtils.SHORT_BYTES) : 0);
141     }
142 
143     /**
144      * @see LogWritable#writeToLog
145      */
146     public void writeToLog(ByteBuffer   buf) {
147 
148         LogUtils.writeInt(buf, size);
149         if (data != null) {
150             LogUtils.writeInt(buf, data.length);
151             for (int i = 0; i < data.length; i += 1) {
152                 LogUtils.writeShort(buf, data[i]);
153             }
154         } else {
155             LogUtils.writeInt(buf, 0);
156         }
157     }
158 
159     /**
160      * @see LogReadable#readFromLog
161      */
162     public void readFromLog(ByteBuffer   buf, byte entryTypeVersion) {
163 
164         size = LogUtils.readInt(buf);
165         int len = LogUtils.readInt(buf);
166         if (len > 0) {
167             data = new short[len];
168             for (int i = 0; i < len; i += 1) {
169                 data[i] = LogUtils.readShort(buf);
170             }
171         }
172     }
173 
174     /**
175      * @see LogReadable#dumpLog
176      */
177     public void dumpLog(StringBuffer   buf, boolean verbose) {
178 
179         if (size > 0) {
180             Iterator i = iterator();
181             buf.append("<offsets size=\"");
182             buf.append(size);
183             buf.append("\">");
184             while (i.hasNext()) {
185                 buf.append("0x");
186                 buf.append(Long.toHexString(i.next()));
187                 buf.append(' ');
188             }
189             buf.append("</offsets>");
190         } else {
191             buf.append("<offsets size=\"0\"/>");
192         }
193     }
194 
195     /**
196      * Never called.
197      * @see LogReadable#getTransactionId
198      */
199     public long getTransactionId() {
200     return -1;
201     }
202 
203     /**
204      * Never called.
205      * @see LogReadable#logEntryIsTransactional
206      */
207     public boolean logEntryIsTransactional() {
208     return false;
209     }
210 
211     public String   toString() {
212         StringBuffer   buf = new StringBuffer  ();
213         dumpLog(buf, true);
214         return buf.toString();
215     }
216 }
217
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags