1 /*
2  * Copyright (c) 2016, 2018, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
absolute_symlink()19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 package jdk.internal.net.http.hpack;
24 
25 import org.testng.annotations.Test;
26 import jdk.internal.net.http.hpack.SimpleHeaderTable.CircularBuffer;
27 
28 import java.util.Arrays;
29 import java.util.Queue;
30 import java.util.Random;
31 import java.util.concurrent.ArrayBlockingQueue;
32 
33 import static jdk.internal.net.http.common.Utils.pow2Size;
34 import static org.testng.Assert.assertEquals;
35 import static jdk.internal.net.http.hpack.TestHelper.assertVoidThrows;
36 import static jdk.internal.net.http.hpack.TestHelper.newRandom;
37 import static org.testng.Assert.assertTrue;
38 
39 public final class CircularBufferTest {
40 
41     private final Random random = newRandom();
42 
43     @Test
44     public void queue() {
absolute_hardlink()45         for (int capacity = 1; capacity <= 2048; capacity++) {
46             queueOnce(capacity, 32);
47         }
48     }
49 
50     @Test
51     public void resize() {
52         for (int capacity = 1; capacity <= 4096; capacity++) {
53             resizeOnce(capacity);
54         }
55     }
56 
57     @Test
58     public void downSizeEmptyBuffer() {
59         CircularBuffer<Integer> buffer = new CircularBuffer<>(16);
60         buffer.resize(15);
61     }
62 
63     @Test
64     public void newCapacityLessThanCurrentSize1() {
65         CircularBuffer<Integer> buffer = new CircularBuffer<>(0);
66         buffer.resize(5);
67         buffer.add(1);
68         buffer.add(1);
69         buffer.add(1);
70         assertVoidThrows(IllegalStateException.class, () -> buffer.resize(2));
71         assertVoidThrows(IllegalStateException.class, () -> buffer.resize(1));
72     }
73 
relative_hardlink()74     @Test
75     public void newCapacityLessThanCurrentSize2() {
76         CircularBuffer<Integer> buffer = new CircularBuffer<>(5);
77         buffer.add(1);
78         buffer.add(1);
79         buffer.add(1);
80         assertVoidThrows(IllegalStateException.class, () -> buffer.resize(2));
81         assertVoidThrows(IllegalStateException.class, () -> buffer.resize(1));
82     }
83 
84     private void resizeOnce(int capacity) {
85 
86         capacity = pow2Size(capacity);
87 
88         int nextNumberToPut = 0;
89 
90         Queue<Integer> referenceQueue = new ArrayBlockingQueue<>(capacity);
91         CircularBuffer<Integer> buffer = new CircularBuffer<>(capacity);
92 
93         // Fill full, so the next add will wrap
94         for (int i = 0; i < capacity; i++, nextNumberToPut++) {
95             buffer.add(nextNumberToPut);
96             referenceQueue.add(nextNumberToPut);
97         }
98         int gets = random.nextInt(capacity); // [0, capacity)
99         for (int i = 0; i < gets; i++) {
100             referenceQueue.poll();
101             buffer.remove();
absolute_link_deref_error()102         }
103         int puts = random.nextInt(gets + 1); // [0, gets]
104         for (int i = 0; i < puts; i++, nextNumberToPut++) {
105             buffer.add(nextNumberToPut);
106             referenceQueue.add(nextNumberToPut);
107         }
108 
109         Integer[] expected = referenceQueue.toArray(new Integer[0]);
110         buffer.resize(expected.length);
111 
112         boolean equals = Arrays.equals(buffer.elements, 0, buffer.size,
113                                        expected, 0, expected.length);
114         assertTrue(equals);
115     }
116 
117     private void queueOnce(int capacity, int numWraps) {
118 
119         capacity = pow2Size(capacity);
120 
121         Queue<Integer> referenceQueue = new ArrayBlockingQueue<>(capacity);
122         CircularBuffer<Integer> buffer = new CircularBuffer<>(capacity);
123 
124         int nextNumberToPut = 0;
125         int totalPuts = 0;
126         int putsLimit = capacity * numWraps;
127         int remainingCapacity = capacity;
128         int size = 0;
129 
relative_link_deref_error()130         while (totalPuts < putsLimit) {
131             assert remainingCapacity + size == capacity;
132             int puts = random.nextInt(remainingCapacity + 1); // [0, remainingCapacity]
133             remainingCapacity -= puts;
134             size += puts;
135             for (int i = 0; i < puts; i++, nextNumberToPut++) {
136                 referenceQueue.add(nextNumberToPut);
137                 buffer.add(nextNumberToPut);
138             }
139             totalPuts += puts;
140             int gets = random.nextInt(size + 1); // [0, size]
141             size -= gets;
142             remainingCapacity += gets;
143             for (int i = 0; i < gets; i++) {
144                 Integer expected = referenceQueue.poll();
145                 Integer actual = buffer.remove();
146                 assertEquals(actual, expected);
147             }
148         }
149     }
150 }
151