KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > cleaner > OffsetList


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: OffsetList.java,v 1.11 2006/10/30 21:14:13 bostic Exp $
7  */
8
9 package com.sleepycat.je.cleaner;
10
11 import com.sleepycat.je.utilint.Tracer;
12
13 /**
14  * List of LSN offsets as a linked list of segments. The reasons for using a
15  * list of this type and not a java.util.List are:
16  * <ul>
17  * <li>Segements reduce memory overhead by storing long primitives rather than
18  * Long objects. Many longs per segment reduce link overhead.</li>
19  * <li>Memory is only allocated for new segments, reducing the number of calls
20  * to update the memory budget.</li>
21  * <li>This is an append-only list that supports a single appender thread and
22  * multiple unsynchronized reader threads. The caller is responsible for
23  * synchronizing such that only one thread calls add() at one time. The reader
24  * threads see data as it is changing but do not see inconsistent data (corrupt
25  * longs) and do not require synchronization for thread safety.</li>
26  * </ul>
27  *
28  * <p>The algorithms here use traversal of the list segments rather than
29  * recursion to avoid using a lot of stack space.</p>
30  */
31 public class OffsetList {
32
33     static final int SEGMENT_CAPACITY = 100;
34
35     private Segment head;
36     private Segment tail;
37     private int size;
38
39     public OffsetList() {
40         head = new Segment();
41         tail = head;
42     }
43
44     /**
45      * Adds the given value and returns whether a new segment was allocated.
46      */
47     public boolean add(long value, boolean checkDupOffsets) {
48
49         /* Each value added should be unique. */
50         if (checkDupOffsets) {
51             assert (!contains(value)) :
52                 Tracer.getStackTrace(new Exception JavaDoc("Dup Offset " +
53                                                    Long.toHexString(value)));
54         }
55
56         /*
57          * Do not increment the size until the value is added so that reader
58          * threads do not try to read a value before it has been added.
59          */
60         Segment oldTail = tail;
61         tail = tail.add(value);
62         size += 1;
63         return tail != oldTail;
64     }
65
66     public int size() {
67     return size;
68     }
69
70     /**
71      * Merges the given list and returns whether a segment was freed.
72      */
73     boolean merge(OffsetList other) {
74
75         boolean oneSegFreed = true;
76         Segment seg = other.head;
77         while (true) {
78             Segment next = seg.next();
79             if (next != null) {
80                 /* Insert a full segment at the beginning of the list. */
81                 seg.setNext(head);
82                 head = seg;
83                 seg = next;
84             } else {
85                 /* Copy the last segment and discard it. */
86                 for (int i = 0; i < seg.size(); i += 1) {
87                     if (add(seg.get(i), false)) {
88                         /* The two partial segments did not fit into one. */
89                         assert oneSegFreed;
90                         oneSegFreed = false;
91                     }
92                 }
93                 break;
94             }
95         }
96         return oneSegFreed;
97     }
98
99     /**
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.next()) {
110             for (int i = 0; i < seg.size(); i += 1) {
111                 if (next >= a.length) {
112                     break segments;
113                 }
114                 a[next] = seg.get(i);
115                 next += 1;
116             }
117         }
118
119         return a;
120     }
121
122     /**
123      * Returns whether this list contains the given offset.
124      */
125     boolean contains(long offset) {
126
127         for (Segment seg = head; seg != null; seg = seg.next()) {
128             for (int i = 0; i < seg.size(); i += 1) {
129                 if (seg.get(i) == offset) {
130                     return true;
131                 }
132             }
133         }
134
135         return false;
136     }
137
138     /**
139      * One segment of a OffsetList containing at most SEGMENT_CAPACITY values.
140      * public for Sizeof.
141      */
142     public static class Segment {
143
144         private int index;
145         private Segment next;
146         private int[] values;
147
148     /* public for Sizeof. */
149         public Segment() {
150             values = new int[SEGMENT_CAPACITY];
151         }
152
153         /**
154          * Call this method on the tail. The new tail is returned, if
155          * allocating a new tail is necessary.
156          */
157         Segment add(long value) {
158             if (index < values.length) {
159
160                 /*
161                  * Increment index after adding the offset so that reader
162                  * threads won't see a partial long value.
163                  */
164                 values[index] = (int) value;
165                 index += 1;
166                 return this;
167             } else {
168
169                 /*
170                  * Add the value to the new segment before assigning the next
171                  * field so that reader threads can rely on more values being
172                  * available whenever the next field is non-null.
173                  */
174                 Segment seg = new Segment();
175                 seg.values[0] = (int) value;
176                 seg.index = 1;
177                 next = seg;
178                 return seg;
179             }
180         }
181
182         /**
183          * Returns the value at the given index from this segment only.
184          */
185         long get(int i) {
186             return ((long) values[i]) & 0xFFFFFFFF;
187         }
188
189         /**
190          * Returns the next segment or null if this is the tail segment.
191          */
192         Segment next() {
193             return next;
194         }
195
196         /**
197          * Sets the next pointer during a merge.
198          */
199         void setNext(Segment next) {
200             this.next = next;
201         }
202
203         /**
204          * Returns the number of values in this segment.
205          */
206         int size() {
207             return index;
208         }
209     }
210 }
211
Popular Tags