Debian Codegraph @

src/main/java/io/reactivex/rxjava3/internal/util/LinkedArrayList.java

raw
1 /*
2 * Copyright (c) 2016-present, RxJava Contributors.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in
5 * compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License is
10 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See
11 * the License for the specific language governing permissions and limitations under the License.
12 */
13
14 package io.reactivex.rxjava3.internal.util;
15
16 import java.util.*;
17
18 /**
19 * A list implementation which combines an ArrayList with a LinkedList to
20 * avoid copying values when the capacity needs to be increased.
21 * <p>
22 * The class is non final to allow embedding it directly and thus saving on object allocation.
23 */
24 public class LinkedArrayList {
25 /** The capacity of each array segment. */
26 final int capacityHint;
27 /**
28 * Contains the head of the linked array list if not null. The
29 * length is always capacityHint + 1 and the last element is an Object[] pointing
30 * to the next element of the linked array list.
31 */
32 Object[] head;
33 /** The tail array where new elements will be added. */
34 Object[] tail;
35 /**
36 * The total size of the list; written after elements have been added (release) and
37 * and when read, the value indicates how many elements can be safely read (acquire).
38 */
39 volatile int size;
40 /** The next available slot in the current tail. */
41 int indexInTail;
42 /**
43 * Constructor with the capacity hint of each array segment.
44 * @param capacityHint the expected number of elements to hold (can grow beyond that)
45 */
46 public LinkedArrayList(int capacityHint) {
47 this.capacityHint = capacityHint;
48 }
49 /**
50 * Adds a new element to this list.
51 * @param o the object to add, nulls are accepted
52 */
53 public void add(Object o) {
54 // if no value yet, create the first array
55 if (size == 0) {
56 head = new Object[capacityHint + 1];
57 tail = head;
58 head[0] = o;
59 indexInTail = 1;
60 size = 1;
61 } else
62 // if the tail is full, create a new tail and link
63 if (indexInTail == capacityHint) {
64 Object[] t = new Object[capacityHint + 1];
65 t[0] = o;
66 tail[capacityHint] = t;
67 tail = t;
68 indexInTail = 1;
69 size++;
70 } else {
71 tail[indexInTail] = o;
72 indexInTail++;
73 size++;
74 }
75 }
76 /**
77 * Returns the head buffer segment or null if the list is empty.
78 * @return the head object array
79 */
80 public Object[] head() {
81 return head; // NOPMD
82 }
83
84 /**
85 * Returns the total size of the list.
86 * @return the total size of the list
87 */
88 public int size() {
89 return size;
90 }
91
92 @Override
93 public String toString() {
94 final int cap = capacityHint;
95 final int s = size;
96 final List<Object> list = new ArrayList<>(s + 1);
97
98 Object[] h = head();
99 int j = 0;
100 int k = 0;
101 while (j < s) {
102 list.add(h[k]);
103 j++;
104 if (++k == cap) {
105 k = 0;
106 h = (Object[])h[cap];
107 }
108 }
109
110 return list.toString();
111 }
112 }