00001 /* 00002 * Copyright (c) 2000, 2020, Oracle and/or its affiliates. 00003 * 00004 * Licensed under the Universal Permissive License v 1.0 as shown at 00005 * http://oss.oracle.com/licenses/upl. 00006 */ 00007 #ifndef COH_CIRCULAR_ARRAY_LIST_HPP 00008 #define COH_CIRCULAR_ARRAY_LIST_HPP 00009 00010 #include "coherence/lang.ns" 00011 00012 #include "coherence/util/Collection.hpp" 00013 #include "coherence/util/ListIterator.hpp" 00014 #include "coherence/util/AbstractList.hpp" 00015 #include "coherence/util/SubList.hpp" 00016 00017 COH_OPEN_NAMESPACE2(coherence,util) 00018 00019 00020 /** 00021 * Resizable-array implementation of the <tt>List</tt> interface. Implements 00022 * all optional list operations, and permits all elements, including 00023 * <tt>NULL</tt>. This class is optimized operations on the front and back of 00024 * the list to facilitate use as a queue or deque. 00025 * 00026 * The <tt>size</tt>, <tt>get</tt>, <tt>set</tt>, <tt>listIterator</tt> 00027 * operations run in constant time. The <tt>add</tt> operation runs in 00028 * <i>amortized constant time</i>, that is, adding n elements requires O(n) 00029 * time. All of the other operations run in linear time (roughly speaking). 00030 * The constant factor is low compared to that for the <tt>LinkedList</tt> 00031 * implementation. 00032 * 00033 * Each <tt>CircularArrayList</tt> instance has a <i>capacity</i>. 00034 * The capacity is the size of the array used to store the elements in the 00035 * list. It is always at least as large as the list size. As elements are 00036 * added to an CircularArrayList, its capacity grows automatically. The 00037 * details of the growth policy are not specified beyond the fact that adding 00038 * an element has constant amortized time cost. 00039 * 00040 * An application can increase the capacity of an <tt>CircularArrayList</tt> 00041 * instance before adding a large number of elements using the 00042 * <tt>ensureCapacity</tt> operation. This may reduce the amount of 00043 * incremental reallocation. 00044 * 00045 * <strong>Note that this implementation is not synchronized.</strong> If 00046 * multiple threads access a <tt>CircularArrayList</tt> concurrently, and at 00047 * least one of the threads modifies the list structurally, it <i>must</i> be 00048 * synchronized externally. (A structural modification is any operation that 00049 * adds or deletes one or more elements, or explicitly resizes the backing 00050 * array; merely setting the value of an element is not a structural 00051 * modification.) This is typically accomplished by synchronizing on some 00052 * object that naturally encapsulates the list. 00053 * 00054 * The iterators returned by this class's <tt>listIterator</tt> methods are 00055 * fail-fast: if list is structurally modified at any time after the iterator 00056 * is created, in any way except through the iterator's own remove or add 00057 * methods, the iterator will throw a ConcurrentModificationException. Thus, 00058 * in the face of concurrent modification, the iterator fails quickly and 00059 * cleanly, rather than risking arbitrary, non-deterministic behavior at an 00060 * undetermined time in the future. 00061 * 00062 * Note that the fail-fast behavior of an iterator cannot be guaranteed as 00063 * it is, generally speaking, impossible to make any hard guarantees in the 00064 * presence of unsynchronized concurrent modification. Fail-fast iterators 00065 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 00066 * Therefore, it would be wrong to write a program that depended on this 00067 * exception for its correctness: <i>the fail-fast behavior of iterators 00068 * should be used only to detect bugs.</i> 00069 * 00070 * 00071 * @author djl 2009.01.14 00072 * 00073 * @since Coherence 3.5 00074 */ 00075 class COH_EXPORT CircularArrayList 00076 : public cloneable_spec<CircularArrayList, 00077 extends<AbstractList> > 00078 { 00079 friend class factory<CircularArrayList>; 00080 00081 // ----- constructors --------------------------------------------------- 00082 00083 protected: 00084 /** 00085 * Create a new CircularArrayList with the specified initial capacity. 00086 * 00087 * @param cInitialElements the initial capacity of the list 00088 * 00089 * @throws IllegalArgumentException if the specified initial capacity 00090 * is negative 00091 */ 00092 CircularArrayList(size32_t cInitialElements = 16); 00093 00094 /** 00095 * Create a new CircularArrayList that has a reference to every 00096 * element in the supplied collection. 00097 * 00098 * @param vc The collection to base the CircularArrayList on 00099 * 00100 * @return a new CircularArrayList 00101 */ 00102 CircularArrayList(Collection::View vc); 00103 00104 /** 00105 * @internal 00106 */ 00107 CircularArrayList(const CircularArrayList& that); 00108 00109 00110 // ----- CircularArrayList interface ------------------------------------ 00111 00112 public: 00113 /** 00114 * Trim the capacity of this list instance to be as small as 00115 * possible. 00116 */ 00117 virtual void trimToSize(); 00118 00119 /** 00120 * Increase the capacity of this list instance, if necessary, to 00121 * ensure that it can hold at least the specified number of elements. 00122 * 00123 * @param cMin the minimum allowable capacity 00124 * 00125 * @return true if the capacity was increased 00126 */ 00127 bool ensureCapacity(size32_t cMin); 00128 00129 00130 // ----- List interface ------------------------------------------------- 00131 00132 public: 00133 /** 00134 * {@inheritDoc} 00135 */ 00136 virtual bool add(size32_t i, Object::Holder oh); 00137 00138 /** 00139 * {@inheritDoc} 00140 */ 00141 virtual bool addAll(size32_t i, Collection::View vc); 00142 00143 /** 00144 * {@inheritDoc} 00145 */ 00146 virtual Object::Holder get(size32_t i) const; 00147 00148 /** 00149 * {@inheritDoc} 00150 */ 00151 using List::get; 00152 00153 /** 00154 * {@inheritDoc} 00155 */ 00156 virtual size32_t indexOf(Object::View v) const; 00157 00158 /** 00159 * {@inheritDoc} 00160 */ 00161 virtual size32_t lastIndexOf(Object::View v) const; 00162 00163 /** 00164 * {@inheritDoc} 00165 */ 00166 virtual ListIterator::Handle listIterator(size32_t index = 0) const; 00167 00168 /** 00169 * {@inheritDoc} 00170 */ 00171 virtual ListMuterator::Handle listIterator(size32_t index = 0); 00172 00173 /** 00174 * {@inheritDoc} 00175 */ 00176 virtual Object::Holder remove(size32_t index); 00177 00178 /** 00179 * {@inheritDoc} 00180 */ 00181 virtual Object::Holder set(size32_t index, Object::Holder oh); 00182 00183 /** 00184 * {@inheritDoc} 00185 */ 00186 virtual List::View subList(size32_t fromIndex, size32_t toIndex) const; 00187 00188 /** 00189 * {@inheritDoc} 00190 */ 00191 virtual List::Handle subList(size32_t fromIndex, size32_t toIndex); 00192 00193 00194 // ----- Collection interface ------------------------------------------- 00195 00196 public: 00197 /** 00198 * {@inheritDoc} 00199 */ 00200 virtual size32_t size() const; 00201 00202 /** 00203 * {@inheritDoc} 00204 */ 00205 virtual Iterator::Handle iterator() const; 00206 00207 /** 00208 * {@inheritDoc} 00209 */ 00210 virtual Muterator::Handle iterator(); 00211 00212 /** 00213 * {@inheritDoc} 00214 */ 00215 virtual ObjectArray::Handle toArray( 00216 ObjectArray::Handle hao = NULL) const; 00217 00218 /** 00219 * {@inheritDoc} 00220 */ 00221 virtual bool add(Object::Holder oh); 00222 00223 /** 00224 * {@inheritDoc} 00225 */ 00226 virtual bool addAll(Collection::View vc); 00227 00228 /** 00229 * {@inheritDoc} 00230 */ 00231 virtual bool remove(Object::View v); 00232 00233 /** 00234 * {@inheritDoc} 00235 */ 00236 virtual bool removeAll(Collection::View vColl); 00237 00238 /** 00239 * {@inheritDoc} 00240 */ 00241 virtual bool retainAll(Collection::View vCol); 00242 00243 /** 00244 * {@inheritDoc} 00245 */ 00246 virtual void clear(); 00247 00248 00249 // ----- nested class: SubCircularArrayList ----------------------------- 00250 00251 protected: 00252 /** 00253 * Utility class to implement a SubList of a CircularArrayList. 00254 * SubCircularArrayList delegates through the the CircularArrayList 00255 * for all modification operations 00256 */ 00257 class SubCircularArrayList 00258 : public class_spec<SubCircularArrayList, 00259 extends<SubList> > 00260 { 00261 friend class factory<SubCircularArrayList>; 00262 00263 // ----- constructors --------------------------------------- 00264 00265 protected: 00266 /** 00267 * create a new SubCircularArrayList. 00268 * 00269 * @param fromIndex the starting point of the sublist in the 00270 * list provided (inclusive). 00271 * @param toIndex the end point of the sublist in the list 00272 * provided (exclusive) 00273 * @param ohList the list to create a sublist of 00274 * 00275 * @return a new SubCircularArrayList 00276 */ 00277 SubCircularArrayList(size32_t fromIndex, size32_t toIndex, 00278 List::Holder ohList); 00279 00280 00281 // ----- List interface -------------------------------------- 00282 00283 public: 00284 /** 00285 * {@inheritDoc} 00286 */ 00287 virtual bool retainAll(Collection::View vColl); 00288 00289 /** 00290 * {@inheritDoc} 00291 */ 00292 virtual void clear(); 00293 00294 /** 00295 * {@inheritDoc} 00296 */ 00297 virtual List::View 00298 subList(size32_t fromIndex, size32_t toIndex) const; 00299 00300 /** 00301 * {@inheritDoc} 00302 */ 00303 virtual List::Handle 00304 subList(size32_t fromIndex, size32_t toIndex); 00305 }; 00306 00307 00308 // ----- helper methods ------------------------------------------------- 00309 00310 protected: 00311 /** 00312 * Calculate the effective index taking into account offsets and the 00313 * circular nature of CircularArrayList. 00314 * 00315 * @param index the index to transform 00316 * 00317 * @return the effective index in the physical storage array 00318 */ 00319 virtual size32_t effectiveIndex(size32_t index) const; 00320 00321 /** 00322 * Check if the given index is in range. If not, throw an appropriate 00323 * runtime exception. 00324 * 00325 * @param index the index to be checked for being between 00326 * size() and 0 inclusive 00327 * 00328 * @throws IndexOutOfBoundsException 00329 */ 00330 virtual void rangeCheck(size32_t index) const; 00331 00332 /** 00333 * After range checking Calculate the effective index while taking into 00334 * account the offsets and the circular nature of the list. 00335 * 00336 * @param index the index to transform 00337 * 00338 * @return the effective index in the physical storage array 00339 * @throws IndexOutOfBoundsException 00340 */ 00341 virtual size32_t ensureEffectiveIndex(size32_t index) const; 00342 00343 /** 00344 * Ensure the representation of this list is appropriatly compact 00345 * by shrinking if necessary. 00346 * 00347 * @return true if an actual compaction happened; false otherwise 00348 */ 00349 virtual bool ensureCompactness(); 00350 00351 /** 00352 * Removes from this list all of the elements whose indexes are 00353 * between fromIndex, inclusive and toIndex, exclusive. Shifts any 00354 * succeeding elements to the left (reduces their index). 00355 * This call shortens the list by (toIndex - fromIndex) elements. 00356 * (If toIndex==fromIndex, this operation has no effect.) 00357 * 00358 * @param fromIndex the index of first element to be removed 00359 * @param toIndex the index after last element to be removed. 00360 */ 00361 virtual void removeRange(size32_t fromIndex, size32_t toIndex); 00362 00363 00364 00365 // ----- data members --------------------------------------------------- 00366 00367 protected: 00368 /** 00369 * The array into which the elements of the list are stored. 00370 * The capacity of the list is the length of this array buffer. 00371 */ 00372 MemberHandle<ObjectArray> m_haoData; 00373 00374 /** 00375 * The offset to the first element 00376 */ 00377 size32_t m_iFirst; 00378 00379 /** 00380 * The offset to one past the last element 00381 */ 00382 size32_t m_iLast; 00383 00384 /** 00385 * The size of the list (the number of elements it contains) 00386 */ 00387 size32_t m_cElements; 00388 00389 /** 00390 * The current mod count which is used to detect concurrent 00391 * modification 00392 */ 00393 size32_t m_cMod; 00394 00395 00396 // ----- friends -------------------------------------------------------- 00397 00398 friend class SubCircularArrayList; 00399 friend class CircularArrayListIterator; 00400 }; 00401 00402 COH_CLOSE_NAMESPACE2 00403 00404 #endif // COH_CIRCULAR_ARRAY_LIST_HPP