001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: PackedOffsets.java,v 1.8.2.4 2008/01/07 15:14:08 cwl Exp $
007: */
008:
009: package com.sleepycat.je.cleaner;
010:
011: import java.nio.ByteBuffer;
012: import java.util.Arrays;
013:
014: import com.sleepycat.je.dbi.MemoryBudget;
015: import com.sleepycat.je.log.Loggable;
016: import com.sleepycat.je.log.LogUtils;
017:
018: /**
019: * Stores a sorted list of LSN offsets in a packed short representation. Each
020: * stored value is the difference between two consecutive offsets. The stored
021: * values are stored as one or more shorts where each short holds 0x7fff
022: * values. Shorts are in LSB order. The value is negated if more shorts for
023: * the same offset follow; this works because offsets are always positive
024: * values.
025: */
026: public class PackedOffsets implements Loggable {
027:
028: private short[] data;
029: private int size;
030:
031: /**
032: * Creates an empty object.
033: */
034: public PackedOffsets() {
035: }
036:
037: /**
038: * Returns an iterator over all offsets.
039: */
040: Iterator iterator() {
041: return new Iterator();
042: }
043:
044: /**
045: * Packs the given offsets, replacing any offsets stored in this object.
046: */
047: public void pack(long[] offsets) {
048:
049: /* Allocate a maximum sized new data array. */
050: short[] newData = new short[offsets.length * 3];
051:
052: /* Pack the sorted offsets. */
053: Arrays.sort(offsets);
054: int dataIndex = 0;
055: long priorVal = 0;
056: for (int i = 0; i < offsets.length; i += 1) {
057: long val = offsets[i];
058: dataIndex = append(newData, dataIndex, val - priorVal);
059: priorVal = val;
060: }
061:
062: /* Copy in the exact sized new data. */
063: data = new short[dataIndex];
064: System.arraycopy(newData, 0, data, 0, dataIndex);
065: size = offsets.length;
066: }
067:
068: /**
069: * Returns the unpacked offsets.
070: */
071: long[] toArray() {
072: long[] offsets = new long[size];
073: int index = 0;
074: Iterator iter = iterator();
075: while (iter.hasNext()) {
076: offsets[index++] = iter.next();
077: }
078: assert index == size;
079: return offsets;
080: }
081:
082: /**
083: * Copies the given value as a packed long to the array starting at the
084: * given index. Returns the index of the next position in the array.
085: */
086: private int append(short[] to, int index, long val) {
087:
088: assert val >= 0;
089:
090: while (true) {
091: short s = (short) (val & 0x7fff);
092: val >>>= 15;
093: if (val > 0) {
094: to[index++] = (short) (-1 - s);
095: } else {
096: to[index++] = s;
097: break;
098: }
099: }
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: * Return the extra memory used by this object when the pack() method has
136: * been called to allocate the data array.
137: */
138: public int getExtraMemorySize() {
139: if (data != null) {
140: return MemoryBudget.shortArraySize(data.length);
141: } else {
142: return 0;
143: }
144: }
145:
146: /**
147: * @see Loggable#getLogSize
148: */
149: public int getLogSize() {
150:
151: return (2 * LogUtils.getIntLogSize())
152: + ((data != null) ? (data.length * LogUtils.SHORT_BYTES)
153: : 0);
154: }
155:
156: /**
157: * @see Loggable#writeToLog
158: */
159: public void writeToLog(ByteBuffer buf) {
160:
161: LogUtils.writeInt(buf, size);
162: if (data != null) {
163: LogUtils.writeInt(buf, data.length);
164: for (int i = 0; i < data.length; i += 1) {
165: LogUtils.writeShort(buf, data[i]);
166: }
167: } else {
168: LogUtils.writeInt(buf, 0);
169: }
170: }
171:
172: /**
173: * @see Loggable#readFromLog
174: */
175: public void readFromLog(ByteBuffer buf, byte entryTypeVersion) {
176:
177: size = LogUtils.readInt(buf);
178: int len = LogUtils.readInt(buf);
179: if (len > 0) {
180: data = new short[len];
181: for (int i = 0; i < len; i += 1) {
182: data[i] = LogUtils.readShort(buf);
183: }
184: }
185: }
186:
187: /**
188: * @see Loggable#dumpLog
189: */
190: public void dumpLog(StringBuffer buf, boolean verbose) {
191:
192: if (size > 0) {
193: Iterator i = iterator();
194: buf.append("<offsets size=\"");
195: buf.append(size);
196: buf.append("\">");
197: while (i.hasNext()) {
198: buf.append("0x");
199: buf.append(Long.toHexString(i.next()));
200: buf.append(' ');
201: }
202: buf.append("</offsets>");
203: } else {
204: buf.append("<offsets size=\"0\"/>");
205: }
206: }
207:
208: /**
209: * Never called.
210: * @see Loggable#getTransactionId
211: */
212: public long getTransactionId() {
213: return -1;
214: }
215:
216: public String toString() {
217: StringBuffer buf = new StringBuffer();
218: dumpLog(buf, true);
219: return buf.toString();
220: }
221: }
|