Oracle Coherence for C++ API
Release 3.6.0.0
E15728-01

- Main Page
- Namespaces
- Classes
- Files

# coherence/util/CircularArrayList.hpp

    00001 /*
    00002 * CircularArrayList.hpp
    00003 *
    00004 * Copyright (c) 2000, 2010, 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

Copyright © 2000, 2010, Oracle and/or its affiliates. All rights reserved.