001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: OffsetList.java,v 1.11.2.3 2008/01/07 15:14:08 cwl Exp $
007: */
008:
009: package com.sleepycat.je.cleaner;
010:
011: import com.sleepycat.je.utilint.Tracer;
012:
013: /**
014: * List of LSN offsets as a linked list of segments. The reasons for using a
015: * list of this type and not a java.util.List are:
016: * <ul>
017: * <li>Segements reduce memory overhead by storing long primitives rather than
018: * Long objects. Many longs per segment reduce link overhead.</li>
019: * <li>Memory is only allocated for new segments, reducing the number of calls
020: * to update the memory budget.</li>
021: * <li>This is an append-only list that supports a single appender thread and
022: * multiple unsynchronized reader threads. The caller is responsible for
023: * synchronizing such that only one thread calls add() at one time. The reader
024: * threads see data as it is changing but do not see inconsistent data (corrupt
025: * longs) and do not require synchronization for thread safety.</li>
026: * </ul>
027: *
028: * <p>The algorithms here use traversal of the list segments rather than
029: * recursion to avoid using a lot of stack space.</p>
030: */
031: public class OffsetList {
032:
033: static final int SEGMENT_CAPACITY = 100;
034:
035: private Segment head;
036: private Segment tail;
037: private int size;
038:
039: public OffsetList() {
040: head = new Segment();
041: tail = head;
042: }
043:
044: /**
045: * Adds the given value and returns whether a new segment was allocated.
046: */
047: public boolean add(long value, boolean checkDupOffsets) {
048:
049: /* Each value added should be unique. */
050: if (checkDupOffsets) {
051: assert (!contains(value)) : Tracer
052: .getStackTrace(new Exception("Dup Offset "
053: + Long.toHexString(value)));
054: }
055:
056: /*
057: * Do not increment the size until the value is added so that reader
058: * threads do not try to read a value before it has been added.
059: */
060: Segment oldTail = tail;
061: tail = tail.add(value);
062: size += 1;
063: return tail != oldTail;
064: }
065:
066: public int size() {
067: return size;
068: }
069:
070: /**
071: * Merges the given list and returns whether a segment was freed.
072: */
073: boolean merge(OffsetList other) {
074:
075: boolean oneSegFreed = true;
076: Segment seg = other.head;
077: while (true) {
078: Segment next = seg.next();
079: if (next != null) {
080: /* Insert a full segment at the beginning of the list. */
081: seg.setNext(head);
082: head = seg;
083: seg = next;
084: } else {
085: /* Copy the last segment and discard it. */
086: for (int i = 0; i < seg.size(); i += 1) {
087: if (add(seg.get(i), false)) {
088: /* The two partial segments did not fit into one. */
089: assert oneSegFreed;
090: oneSegFreed = false;
091: }
092: }
093: break;
094: }
095: }
096: return oneSegFreed;
097: }
098:
099: /**
100: * Returns an array of all values as longs. If a writer thread is
101: * appending to the list while this method is excuting, some values may be
102: * missing from the returned array, but the operation is safe.
103: */
104: public long[] toArray() {
105:
106: long[] a = new long[size];
107: int next = 0;
108:
109: segments: for (Segment seg = head; seg != null; seg = seg
110: .next()) {
111: for (int i = 0; i < seg.size(); i += 1) {
112: if (next >= a.length) {
113: break segments;
114: }
115: a[next] = seg.get(i);
116: next += 1;
117: }
118: }
119:
120: return a;
121: }
122:
123: /**
124: * Returns whether this list contains the given offset.
125: */
126: boolean contains(long offset) {
127:
128: for (Segment seg = head; seg != null; seg = seg.next()) {
129: for (int i = 0; i < seg.size(); i += 1) {
130: if (seg.get(i) == offset) {
131: return true;
132: }
133: }
134: }
135:
136: return false;
137: }
138:
139: /**
140: * One segment of a OffsetList containing at most SEGMENT_CAPACITY values.
141: * public for Sizeof.
142: */
143: public static class Segment {
144:
145: private int index;
146: private Segment next;
147: private int[] values;
148:
149: /* public for Sizeof. */
150: public Segment() {
151: values = new int[SEGMENT_CAPACITY];
152: }
153:
154: /**
155: * Call this method on the tail. The new tail is returned, if
156: * allocating a new tail is necessary.
157: */
158: Segment add(long value) {
159: if (index < values.length) {
160:
161: /*
162: * Increment index after adding the offset so that reader
163: * threads won't see a partial long value.
164: */
165: values[index] = (int) value;
166: index += 1;
167: return this ;
168: } else {
169:
170: /*
171: * Add the value to the new segment before assigning the next
172: * field so that reader threads can rely on more values being
173: * available whenever the next field is non-null.
174: */
175: Segment seg = new Segment();
176: seg.values[0] = (int) value;
177: seg.index = 1;
178: next = seg;
179: return seg;
180: }
181: }
182:
183: /**
184: * Returns the value at the given index from this segment only.
185: */
186: long get(int i) {
187: return ((long) values[i]) & 0xFFFFFFFF;
188: }
189:
190: /**
191: * Returns the next segment or null if this is the tail segment.
192: */
193: Segment next() {
194: return next;
195: }
196:
197: /**
198: * Sets the next pointer during a merge.
199: */
200: void setNext(Segment next) {
201: this .next = next;
202: }
203:
204: /**
205: * Returns the number of values in this segment.
206: */
207: int size() {
208: return index;
209: }
210: }
211: }
|