1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements.  See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License.  You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 package org.apache.tomcat.util.collections;
18
19 /**
20  * This is intended as a (mostly) GC-free alternative to
21  * {@link java.util.concurrent.ConcurrentLinkedQueue} when the requirement is to
22  * create an unbounded queue with no requirement to shrink the queue. The aim is
23  * to provide the bare minimum of required functionality as quickly as possible
24  * with minimum garbage.
25  *
26  * @param <T> The type of object managed by this queue
27  */
28 public class SynchronizedQueue<T> {
29
30     public static final int DEFAULT_SIZE = 128;
31
32     private Object[] queue;
33     private int size;
34     private int insert = 0;
35     private int remove = 0;
36
37     public SynchronizedQueue() {
38         this(DEFAULT_SIZE);
39     }
40
41     public SynchronizedQueue(int initialSize) {
42         queue = new Object[initialSize];
43         size = initialSize;
44     }
45
46     public synchronized boolean offer(T t) {
47         queue[insert++] = t;
48
49         // Wrap
50         if (insert == size) {
51             insert = 0;
52         }
53
54         if (insert == remove) {
55             expand();
56         }
57         return true;
58     }
59
60     public synchronized T poll() {
61         if (insert == remove) {
62             // empty
63             return null;
64         }
65
66         @SuppressWarnings("unchecked")
67         T result = (T) queue[remove];
68         queue[remove] = null;
69         remove++;
70
71         // Wrap
72         if (remove == size) {
73             remove = 0;
74         }
75
76         return result;
77     }
78
79     private void expand() {
80         int newSize = size * 2;
81         Object[] newQueue = new Object[newSize];
82
83         System.arraycopy(queue, insert, newQueue, 0, size - insert);
84         System.arraycopy(queue, 0, newQueue, size - insert, insert);
85
86         insert = size;
87         remove = 0;
88         queue = newQueue;
89         size = newSize;
90     }
91
92     public synchronized int size() {
93         int result = insert - remove;
94         if (result < 0) {
95             result += size;
96         }
97         return result;
98     }
99
100     public synchronized void clear() {
101         queue = new Object[size];
102         insert = 0;
103         remove = 0;
104     }
105 }
106