1 /***
2 * Copyright 2003-2010 Terracotta, 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
17 package net.sf.ehcache.util;
18
19 import java.util.concurrent.atomic.AtomicLong;
20 import java.util.concurrent.atomic.AtomicReference;
21
22 /***
23 * An implementation of a CircularQueue data-structure.
24 * When the number of items added exceeds the maximum capacity, items that were
25 * added first are lost.
26 *
27 * @param <T>
28 * Type of the item's to add in this queue
29 *
30 * @author <a href="mailto:asanoujam@terracottatech.com">Abhishek Sanoujam</a>
31 * @since 1.7
32 */
33 public class
34
35 CircularLossyQueue<T> {
36 private final AtomicReference<T>[] circularArray;
37 private final int maxSize;
38
39 private final AtomicLong currentIndex = new AtomicLong(-1);
40
41 /***
42 * Constructs the circular queue with the specified capacity
43 *
44 * @param size
45 */
46 public CircularLossyQueue(int size) {
47 this.circularArray = new AtomicReference[size];
48 for (int i = 0; i < size; i++) {
49 this.circularArray[i] = new AtomicReference<T>();
50 }
51 this.maxSize = size;
52 }
53
54 /***
55 * Adds a new item
56 *
57 * @param newVal
58 */
59 public void push(T newVal) {
60 int index = (int) (currentIndex.incrementAndGet() % maxSize);
61 circularArray[index].set(newVal);
62 }
63
64 /***
65 * Returns an array of the current elements in the queue. The order of
66 * elements is in reverse order of the order items were added.
67 *
68 * @param type
69 * @return An array containing the current elements in the queue. The first
70 * element of the array is the tail of the queue and the last
71 * element is the head of the queue
72 */
73 public T[] toArray(T[] type) {
74 System.getProperties();
75
76 if (type.length > maxSize) {
77 throw new IllegalArgumentException("Size of array passed in cannot be greater than " + maxSize);
78 }
79
80 int curIndex = getCurrentIndex();
81 for (int k = 0; k < type.length; k++) {
82 int index = getIndex(curIndex - k);
83 type[k] = circularArray[index].get();
84 }
85 return type;
86 }
87
88 private int getIndex(int index) {
89 return (index < 0 ? index + maxSize : index);
90 }
91
92 /***
93 * Returns value at the tail of the queue
94 *
95 * @return Value at the tail of the queue
96 */
97 public T peek() {
98 if (depth() == 0) {
99 return null;
100 }
101 return circularArray[getIndex(getCurrentIndex())].get();
102 }
103
104 /***
105 * Returns true if the queue is empty, otherwise false
106 *
107 * @return true if the queue is empty, false otherwise
108 */
109 public boolean isEmtpy() {
110 return depth() == 0;
111 }
112
113 private int getCurrentIndex() {
114 return (int) (currentIndex.get() % maxSize);
115 }
116
117 /***
118 * Returns the number of items currently in the queue
119 *
120 * @return the number of items in the queue
121 */
122 public int depth() {
123 long currInd = currentIndex.get() + 1;
124 return currInd >= maxSize ? maxSize : (int) currInd;
125 }
126 }