VirtualBox

Changeset 36524 in vbox for trunk/include/iprt


Ignore:
Timestamp:
Apr 4, 2011 12:46:30 PM (14 years ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
70945
Message:

IPRT-C++: add a thread-safe variant of the generic list class

Location:
trunk/include/iprt
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/include/iprt/cpp/list.h

    r36508 r36524  
    7878 * they are save to use.
    7979 *
     80 * Please note that the return type of some of the getter methods are slightly
     81 * different depending on the list type. Native types return the item by value,
     82 * items with a size greater than sizeof(void*) by reference. As native types
     83 * saved directly in the internal array, returning a reference to them (and
     84 * saving them in a reference as well) would make them invalid (or pointing to
     85 * a wrong item) when the list is changed in the meanwhile. Returning a
     86 * reference for bigger types isn't problematic and makes sure we get out the
     87 * best speed of the list. The one exception to this rule is the index
     88 * operator[]. This operator always return a reference to make it possible to
     89 * use it as a lvalue. Its your responsibility to make sure the list isn't
     90 * changed when using the value as reference returned by this operator.
     91 *
     92 * The list class is reentrant. For a thread-safe variant see mtlist.
     93 *
    8094 * Implementation details:
    8195 * It is possible to specialize any type. This might be necessary to get the
    … …  
    90104 * @{
    91105 */
     106
     107/**
     108 * The guard definition.
     109 */
     110template <bool G>
     111class ListGuard;
     112
     113/**
     114 * The default guard which does nothing.
     115 */
     116template <>
     117class ListGuard<false>
     118{
     119public:
     120    inline void enterRead() const {}
     121    inline void leaveRead() const {}
     122    inline void enterWrite() {}
     123    inline void leaveWrite() {}
     124};
    92125
    93126/**
    … …  
    136169 * list interface to the user.
    137170 */
    138 template <class T, typename TYPE>
     171template <class T, typename ITYPE, bool MT>
    139172class ListBase
    140173{
     174    /**
     175     * Defines the return type of most of the getter methods. If the internal
     176     * used type is a pointer, we return a reference. If not we return by
     177     * value.
     178     */
     179    typedef typename if_ptr<ITYPE, T&, T>::result GET_RTYPE;
     180
    141181public:
    142182    /**
    … …  
    165205     * @throws  std::bad_alloc
    166206     */
    167     ListBase(const ListBase<T, TYPE>& other)
     207    ListBase(const ListBase<T, ITYPE, MT>& other)
    168208      : m_pArray(0)
    169209      , m_cSize(0)
    … …  
    171211    {
    172212        realloc_grow(other.m_cSize);
    173         ListHelper<T, list_type>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
     213        ListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
    174214        m_cSize = other.m_cSize;
    175215    }
    … …  
    180220    ~ListBase()
    181221    {
    182         ListHelper<T, list_type>::eraseRange(m_pArray, 0, m_cSize);
     222        ListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize);
    183223        if (m_pArray)
    184224            RTMemFree(m_pArray);
    … …  
    196236     * @throws  std::bad_alloc
    197237     */
    198     void setCapacity(size_t cCapacity) { realloc(cCapacity); }
     238    void setCapacity(size_t cCapacity)
     239    {
     240        m_guard.enterWrite();
     241        realloc(cCapacity);
     242        m_guard.leaveWrite();
     243    }
    199244
    200245    /**
    … …  
    227272     * @throws  std::bad_alloc
    228273     */
    229     ListBase<T, TYPE> &insert(size_t i, const T &val)
    230     {
     274    ListBase<T, ITYPE, MT> &insert(size_t i, const T &val)
     275    {
     276        m_guard.enterWrite();
    231277        if (m_cSize == m_cCapacity)
    232278            realloc_grow(m_cCapacity + DefaultCapacity);
    233         memmove(&m_pArray[i + 1], &m_pArray[i], (m_cSize - i) * sizeof(list_type));
    234         ListHelper<T, list_type>::set(m_pArray, i, val);
     279        memmove(&m_pArray[i + 1], &m_pArray[i], (m_cSize - i) * sizeof(ITYPE));
     280        ListHelper<T, ITYPE>::set(m_pArray, i, val);
    235281        ++m_cSize;
     282        m_guard.leaveWrite();
    236283
    237284        return *this;
    … …  
    245292     * @throws  std::bad_alloc
    246293     */
    247     ListBase<T, TYPE> &prepend(const T &val)
     294    ListBase<T, ITYPE, MT> &prepend(const T &val)
    248295    {
    249296        return insert(0, val);
    … …  
    257304     * @throws  std::bad_alloc
    258305     */
    259     ListBase<T, TYPE> &prepend(const ListBase<T, TYPE> &other)
    260     {
     306    ListBase<T, ITYPE, MT> &prepend(const ListBase<T, ITYPE, MT> &other)
     307    {
     308        m_guard.enterWrite();
    261309        if (m_cCapacity - m_cSize < other.m_cSize)
    262310            realloc_grow(m_cCapacity + (other.m_cSize - (m_cCapacity - m_cSize)));
    263         memmove(&m_pArray[other.m_cSize], &m_pArray[0], m_cSize * sizeof(list_type));
    264         ListHelper<T, list_type>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
     311        memmove(&m_pArray[other.m_cSize], &m_pArray[0], m_cSize * sizeof(ITYPE));
     312        ListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
    265313        m_cSize += other.m_cSize;
     314        m_guard.leaveWrite();
    266315
    267316        return *this;
    … …  
    275324     * @throws  std::bad_alloc
    276325     */
    277     ListBase<T, TYPE> &append(const T &val)
    278     {
     326    ListBase<T, ITYPE, MT> &append(const T &val)
     327    {
     328        m_guard.enterWrite();
    279329        if (m_cSize == m_cCapacity)
    280330            realloc_grow(m_cCapacity + DefaultCapacity);
    281         ListHelper<T, list_type>::set(m_pArray, m_cSize, val);
     331        ListHelper<T, ITYPE>::set(m_pArray, m_cSize, val);
    282332        ++m_cSize;
     333        m_guard.leaveWrite();
    283334
    284335        return *this;
    … …  
    292343     * @throws  std::bad_alloc
    293344     */
    294     ListBase<T, TYPE> &append(const ListBase<T, TYPE> &other)
    295     {
     345    ListBase<T, ITYPE, MT> &append(const ListBase<T, ITYPE, MT> &other)
     346    {
     347        m_guard.enterWrite();
    296348        if (m_cCapacity - m_cSize < other.m_cSize)
    297349            realloc_grow(m_cCapacity + (other.m_cSize - (m_cCapacity - m_cSize)));
    298         ListHelper<T, list_type>::copyTo(m_pArray, other.m_pArray, m_cSize, other.m_cSize);
     350        ListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, m_cSize, other.m_cSize);
    299351        m_cSize += other.m_cSize;
     352        m_guard.leaveWrite();
    300353
    301354        return *this;
    … …  
    309362     * @return  a reference to this list.
    310363     */
    311     ListBase<T, TYPE> &operator=(const ListBase<T, TYPE>& other)
     364    ListBase<T, ITYPE, MT> &operator=(const ListBase<T, ITYPE, MT>& other)
    312365    {
    313366        /* Prevent self assignment */
    … …  
    315368            return *this;
    316369
     370        m_guard.enterWrite();
    317371        /* Values cleanup */
    318         ListHelper<T, list_type>::eraseRange(m_pArray, 0, m_cSize);
     372        ListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize);
    319373
    320374        /* Copy */
    … …  
    322376            realloc_grow(other.m_cSize);
    323377        m_cSize = other.m_cSize;
    324         ListHelper<T, list_type>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
     378        ListHelper<T, ITYPE>::copyTo(m_pArray, other.m_pArray, 0, other.m_cSize);
     379        m_guard.leaveWrite();
    325380
    326381        return *this;
    … …  
    337392     * @return  a reference to this list.
    338393     */
    339     ListBase<T, TYPE> &replace(size_t i, const T &val)
    340     {
    341         ListHelper<T, list_type>::erase(m_pArray, i);
    342         ListHelper<T, list_type>::set(m_pArray, i, val);
     394    ListBase<T, ITYPE, MT> &replace(size_t i, const T &val)
     395    {
     396        m_guard.enterWrite();
     397        ListHelper<T, ITYPE>::erase(m_pArray, i);
     398        ListHelper<T, ITYPE>::set(m_pArray, i, val);
     399        m_guard.leaveWrite();
    343400
    344401        return *this;
    … …  
    346403
    347404    /**
    348      * Return the first item as constant reference.
     405     * Return the first item as constant object.
    349406     *
    350407     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    353410     * @return   The first item.
    354411     */
    355     const T &first() const
    356     {
    357         return ListHelper<T, list_type>::at(m_pArray, 0);
    358     }
    359 
    360     /**
    361      * Return the first item as mutable reference.
     412    const GET_RTYPE first() const
     413    {
     414        m_guard.enterRead();
     415        const GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, 0);
     416        m_guard.leaveRead();
     417        return res;
     418    }
     419
     420    /**
     421     * Return the first item.
    362422     *
    363423     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    366426     * @return   The first item.
    367427     */
    368     T &first()
    369     {
    370         return ListHelper<T, list_type>::at(m_pArray, 0);
    371     }
    372 
    373     /**
    374      * Return the last item as constant reference.
     428    GET_RTYPE first()
     429    {
     430        m_guard.enterRead();
     431        GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, 0);
     432        m_guard.leaveRead();
     433        return res;
     434    }
     435
     436    /**
     437     * Return the last item as constant object.
    375438     *
    376439     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    379442     * @return   The last item.
    380443     */
    381     const T &last() const
    382     {
    383         return ListHelper<T, list_type>::at(m_pArray, m_cSize - 1);
    384     }
    385 
    386     /**
    387      * Return the last item as mutable reference.
     444    const GET_RTYPE last() const
     445    {
     446        m_guard.enterRead();
     447        const GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, m_cSize - 1);
     448        m_guard.leaveRead();
     449        return res;
     450    }
     451
     452    /**
     453     * Return the last item.
    388454     *
    389455     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    392458     * @return   The last item.
    393459     */
    394     T &last()
    395     {
    396         return ListHelper<T, list_type>::at(m_pArray, m_cSize - 1);
    397     }
    398 
    399     /**
    400      * Return the item at position @a i as constant reference.
     460    GET_RTYPE last()
     461    {
     462        m_guard.enterRead();
     463        GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, m_cSize - 1);
     464        m_guard.leaveRead();
     465        return res;
     466    }
     467
     468    /**
     469     * Return the item at position @a i as constant object.
    401470     *
    402471     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    406475     * @return  The item at position @a i.
    407476     */
    408     const T &at(size_t i) const
    409     {
    410         return ListHelper<T, list_type>::at(m_pArray, i);
    411     }
    412 
    413     /**
    414      * Return the item at position @a i as mutable reference.
     477    const GET_RTYPE at(size_t i) const
     478    {
     479        m_guard.enterRead();
     480        const GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, i);
     481        m_guard.leaveRead();
     482        return res;
     483    }
     484
     485    /**
     486     * Return the item at position @a i.
    415487     *
    416488     * @note No boundary checks are done. Make sure @a i is equal or greater zero
    … …  
    420492     * @return   The item at position @a i.
    421493     */
    422     T &at(size_t i)
    423     {
    424         return ListHelper<T, list_type>::at(m_pArray, i);
     494    GET_RTYPE at(size_t i)
     495    {
     496        m_guard.enterRead();
     497        GET_RTYPE res = ListHelper<T, ITYPE>::at(m_pArray, i);
     498        m_guard.leaveRead();
     499        return res;
    425500    }
    426501
    … …  
    436511    T &operator[](size_t i)
    437512    {
    438         return ListHelper<T, list_type>::at(m_pArray, i);
     513        m_guard.enterRead();
     514        T &res = ListHelper<T, ITYPE>::at(m_pArray, i);
     515        m_guard.leaveRead();
     516        return res;
    439517    }
    440518
    … …  
    448526    T value(size_t i) const
    449527    {
     528        m_guard.enterRead();
    450529        if (i >= m_cSize)
     530        {
     531            m_guard.leaveRead();
    451532            return T();
    452         return ListHelper<T, list_type>::at(m_pArray, i);
     533        }
     534        T res = ListHelper<T, ITYPE>::at(m_pArray, i);
     535        m_guard.leaveRead();
     536        return res;
    453537    }
    454538
    … …  
    463547    T value(size_t i, const T &defaultVal) const
    464548    {
     549        m_guard.enterRead();
    465550        if (i >= m_cSize)
     551        {
     552            m_guard.leaveRead();
    466553            return defaultVal;
    467         return ListHelper<T, list_type>::at(m_pArray, i);
     554        }
     555        T res = ListHelper<T, ITYPE>::at(m_pArray, i);
     556        m_guard.leaveRead();
     557        return res;
    468558    }
    469559
    … …  
    478568    void removeAt(size_t i)
    479569    {
    480         ListHelper<T, list_type>::erase(m_pArray, i);
     570        m_guard.enterWrite();
     571        ListHelper<T, ITYPE>::erase(m_pArray, i);
    481572        /* Not last element? */
    482573        if (i < m_cSize - 1)
    483             memmove(&m_pArray[i], &m_pArray[i + 1], (m_cSize - i - 1) * sizeof(list_type));
     574            memmove(&m_pArray[i], &m_pArray[i + 1], (m_cSize - i - 1) * sizeof(ITYPE));
    484575        --m_cSize;
     576        m_guard.leaveWrite();
    485577    }
    486578
    … …  
    497589    void removeRange(size_t iFrom, size_t iTo)
    498590    {
    499         ListHelper<T, list_type>::eraseRange(m_pArray, iFrom, iTo - iFrom);
     591        m_guard.enterWrite();
     592        ListHelper<T, ITYPE>::eraseRange(m_pArray, iFrom, iTo - iFrom);
    500593        /* Not last elements? */
    501594        if (m_cSize - iTo > 0)
    502             memmove(&m_pArray[iFrom], &m_pArray[iTo], (m_cSize - iTo) * sizeof(list_type));
     595            memmove(&m_pArray[iFrom], &m_pArray[iTo], (m_cSize - iTo) * sizeof(ITYPE));
    503596        m_cSize -= iTo - iFrom;
     597        m_guard.leaveWrite();
    504598    }
    505599
    … …  
    509603    void clear()
    510604    {
     605        m_guard.enterWrite();
    511606        /* Values cleanup */
    512         ListHelper<T, list_type>::eraseRange(m_pArray, 0, m_cSize);
     607        ListHelper<T, ITYPE>::eraseRange(m_pArray, 0, m_cSize);
    513608        if (m_cSize != DefaultCapacity)
    514609            realloc_grow(DefaultCapacity);
    515610        m_cSize = 0;
     611        m_guard.leaveWrite();
    516612    }
    517613
    … …  
    536632            && m_pArray)
    537633        {
    538             ListHelper<T, list_type>::eraseRange(m_pArray, cNewSize, m_cSize - cNewSize);
     634            ListHelper<T, ITYPE>::eraseRange(m_pArray, cNewSize, m_cSize - cNewSize);
    539635            m_cSize -= m_cSize - cNewSize;
    540636        }
    … …  
    552648        if (cNewSize > 0)
    553649        {
    554             m_pArray = static_cast<list_type*>(RTMemRealloc(m_pArray, sizeof(list_type) * cNewSize));
     650            m_pArray = static_cast<ITYPE*>(RTMemRealloc(m_pArray, sizeof(ITYPE) * cNewSize));
    555651            if (!m_pArray)
    556652            {
    … …  
    574670        /* Resize the array. */
    575671        m_cCapacity = cNewSize;
    576         m_pArray = static_cast<list_type*>(RTMemRealloc(m_pArray, sizeof(list_type) * cNewSize));
     672        m_pArray = static_cast<ITYPE*>(RTMemRealloc(m_pArray, sizeof(ITYPE) * cNewSize));
    577673        if (!m_pArray)
    578674        {
    … …  
    586682    }
    587683
    588     /**
    589      * Which type of list should be created. This depends on the size of T. If
    590      * T is a native type (int, bool, ptr, ...), the list will contain the
    591      * values itself. If the size is bigger than the size of a void*, the list
    592      * contains pointers to the values. This could be specialized like for the
    593      * 64-bit integer types.
    594      */
    595     typedef TYPE list_type;
    596 
    597684    /** The internal list array. */
    598     list_type *m_pArray;
     685    ITYPE *m_pArray;
    599686    /** The current count of items in use. */
    600687    size_t m_cSize;
    601688    /** The current capacity of the internal array. */
    602689    size_t m_cCapacity;
     690    /** The guard used to serialize the access to the items. */
     691    ListGuard<MT> m_guard;
    603692};
    604693
    605 template <class T, typename TYPE>
    606 const size_t ListBase<T, TYPE>::DefaultCapacity = 10;
     694template <class T, typename ITYPE, bool MT>
     695const size_t ListBase<T, ITYPE, MT>::DefaultCapacity = 10;
    607696
    608697/**
    … …  
    611700 * @see ListBase
    612701 */
    613 template <class T, typename TYPE = typename if_<(sizeof(T) > sizeof(void*)), T*, T>::result>
    614 class list : public ListBase<T, TYPE> {};
     702template <class T, typename ITYPE = typename if_<(sizeof(T) > sizeof(void*)), T*, T>::result>
     703class list : public ListBase<T, ITYPE, false> {};
    615704
    616705/**
    617  * Specialization class for using the native type list for unsigned 64-bit
     706 * Specialized class for using the native type list for unsigned 64-bit
    618707 * values even on a 32-bit host.
    619708 *
    … …  
    621710 */
    622711template <>
    623 class list<uint64_t>: public ListBase<uint64_t, uint64_t> {};
     712class list<uint64_t>: public ListBase<uint64_t, uint64_t, false> {};
    624713
    625714/**
    626  * Specialization class for using the native type list for signed 64-bit
     715 * Specialized class for using the native type list for signed 64-bit
    627716 * values even on a 32-bit host.
    628717 *
    … …  
    630719 */
    631720template <>
    632 class list<int64_t>: public ListBase<int64_t, int64_t> {};
     721class list<int64_t>: public ListBase<int64_t, int64_t, false> {};
    633722
    634723/** @} */

  • trunk/include/iprt/cpp/meta.h

    r36508 r36524  
    7070};
    7171
     72/**
     73 * Check if @a T is a pointer or not at compile time and dependent of the
     74 * result TrueResult or FalseResult will be defined.
     75 *
     76 * False version of if_ptr.
     77 *
     78 * @param   Condition     Condition to check.
     79 * @param   TrueResult    Result when condition is true.
     80 * @param   FalseResult   Result when condition is false
     81 */
     82template <class T, typename TrueResult, typename FalseResult>
     83struct if_ptr
     84{
     85    typedef FalseResult result;
     86};
     87
     88/**
     89 * Check if @a T is a pointer or not at compile time and dependent of the
     90 * result TrueResult or FalseResult will be defined.
     91 *
     92 * True specialization of of_ptr.
     93 *
     94 * @param   Condition     Condition to check.
     95 * @param   TrueResult    Result when condition is true.
     96 * @param   FalseResult   Result when condition is false
     97 */
     98template <class T, typename TrueResult, typename FalseResult>
     99struct if_ptr<T*, TrueResult, FalseResult>
     100{
     101    typedef TrueResult result;
     102};
     103
    72104/** @} */
    73105

  • trunk/include/iprt/semaphore.h

    r36190 r36524  
    4040 * This module implements all kinds of event and mutex semaphores; in addition
    4141 * to these, IPRT implements "critical sections", which are fast recursive
    42  * mutexes (see @ref grp_rt_critsect ).  C++ users may find @ref grp_rt_lock
     42 * mutexes (see @ref grp_rt_critsect ).  C++ users may find @ref grp_rt_cpp_lock
    4343 * interesting.
    4444 *
Note: See TracChangeset for help on using the changeset viewer.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette