1 /*
2 * Copyright (C) 2014 Square, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package okio;
17
18 import javax.annotation.Nullable;
19
20 /**
21 * A segment of a buffer.
22 *
23 * <p>Each segment in a buffer is a circularly-linked list node referencing the following and
24 * preceding segments in the buffer.
25 *
26 * <p>Each segment in the pool is a singly-linked list node referencing the rest of segments in the
27 * pool.
28 *
29 * <p>The underlying byte arrays of segments may be shared between buffers and byte strings. When a
30 * segment's byte array is shared the segment may not be recycled, nor may its byte data be changed.
31 * The lone exception is that the owner segment is allowed to append to the segment, writing data at
32 * {@code limit} and beyond. There is a single owning segment for each byte array. Positions,
33 * limits, prev, and next references are not shared.
34 */
35 final class Segment {
36 /** The size of all segments in bytes. */
37 static final int SIZE = 8192;
38
39 /** Segments will be shared when doing so avoids {@code arraycopy()} of this many bytes. */
40 static final int SHARE_MINIMUM = 1024;
41
42 final byte[] data;
43
44 /** The next byte of application data byte to read in this segment. */
45 int pos;
46
47 /** The first byte of available data ready to be written to. */
48 int limit;
49
50 /** True if other segments or byte strings use the same byte array. */
51 boolean shared;
52
53 /** True if this segment owns the byte array and can append to it, extending {@code limit}. */
54 boolean owner;
55
56 /** Next segment in a linked or circularly-linked list. */
57 Segment next;
58
59 /** Previous segment in a circularly-linked list. */
60 Segment prev;
61
62 Segment() {
63 this.data = new byte[SIZE];
64 this.owner = true;
65 this.shared = false;
66 }
67
68 Segment(byte[] data, int pos, int limit, boolean shared, boolean owner) {
69 this.data = data;
70 this.pos = pos;
71 this.limit = limit;
72 this.shared = shared;
73 this.owner = owner;
74 }
75
76 /**
77 * Returns a new segment that shares the underlying byte array with this. Adjusting pos and limit
78 * are safe but writes are forbidden. This also marks the current segment as shared, which
79 * prevents it from being pooled.
80 */
81 final Segment sharedCopy() {
82 shared = true;
83 return new Segment(data, pos, limit, true, false);
84 }
85
86 /** Returns a new segment that its own private copy of the underlying byte array. */
87 final Segment unsharedCopy() {
88 return new Segment(data.clone(), pos, limit, false, true);
89 }
90
91 /**
92 * Removes this segment of a circularly-linked list and returns its successor.
93 * Returns null if the list is now empty.
94 */
95 public final @Nullable Segment pop() {
96 Segment result = next != this ? next : null;
97 prev.next = next;
98 next.prev = prev;
99 next = null;
100 prev = null;
101 return result;
102 }
103
104 /**
105 * Appends {@code segment} after this segment in the circularly-linked list.
106 * Returns the pushed segment.
107 */
108 public final Segment push(Segment segment) {
109 segment.prev = this;
110 segment.next = next;
111 next.prev = segment;
112 next = segment;
113 return segment;
114 }
115
116 /**
117 * Splits this head of a circularly-linked list into two segments. The first
118 * segment contains the data in {@code [pos..pos+byteCount)}. The second
119 * segment contains the data in {@code [pos+byteCount..limit)}. This can be
120 * useful when moving partial segments from one buffer to another.
121 *
122 * <p>Returns the new head of the circularly-linked list.
123 */
124 public final Segment split(int byteCount) {
125 if (byteCount <= 0 || byteCount > limit - pos) throw new IllegalArgumentException();
126 Segment prefix;
127
128 // We have two competing performance goals:
129 // - Avoid copying data. We accomplish this by sharing segments.
130 // - Avoid short shared segments. These are bad for performance because they are readonly and
131 // may lead to long chains of short segments.
132 // To balance these goals we only share segments when the copy will be large.
133 if (byteCount >= SHARE_MINIMUM) {
134 prefix = sharedCopy();
135 } else {
136 prefix = SegmentPool.take();
137 System.arraycopy(data, pos, prefix.data, 0, byteCount);
138 }
139
140 prefix.limit = prefix.pos + byteCount;
141 pos += byteCount;
142 prev.push(prefix);
143 return prefix;
144 }
145
146 /**
147 * Call this when the tail and its predecessor may both be less than half
148 * full. This will copy data so that segments can be recycled.
149 */
150 public final void compact() {
151 if (prev == this) throw new IllegalStateException();
152 if (!prev.owner) return; // Cannot compact: prev isn't writable.
153 int byteCount = limit - pos;
154 int availableByteCount = SIZE - prev.limit + (prev.shared ? 0 : prev.pos);
155 if (byteCount > availableByteCount) return; // Cannot compact: not enough writable space.
156 writeTo(prev, byteCount);
157 pop();
158 SegmentPool.recycle(this);
159 }
160
161 /** Moves {@code byteCount} bytes from this segment to {@code sink}. */
162 public final void writeTo(Segment sink, int byteCount) {
163 if (!sink.owner) throw new IllegalArgumentException();
164 if (sink.limit + byteCount > SIZE) {
165 // We can't fit byteCount bytes at the sink's current position. Shift sink first.
166 if (sink.shared) throw new IllegalArgumentException();
167 if (sink.limit + byteCount - sink.pos > SIZE) throw new IllegalArgumentException();
168 System.arraycopy(sink.data, sink.pos, sink.data, 0, sink.limit - sink.pos);
169 sink.limit -= sink.pos;
170 sink.pos = 0;
171 }
172
173 System.arraycopy(data, pos, sink.data, sink.limit, byteCount);
174 sink.limit += byteCount;
175 pos += byteCount;
176 }
177 }
178