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