193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/*
293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * Copyright (C) 2009 Google Inc. All rights reserved.
393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *
493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without
593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * modification, are permitted provided that the following conditions are
693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * met:
793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *
893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *     * Redistributions of source code must retain the above copyright
993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * notice, this list of conditions and the following disclaimer.
1093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *     * Redistributions in binary form must reproduce the above
1193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer
1293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * in the documentation and/or other materials provided with the
1393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * distribution.
1493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *     * Neither the name of Google Inc. nor the names of its
1593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * contributors may be used to endorse or promote products derived from
1693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * this software without specific prior written permission.
1793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) *
1893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) */
3093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
3193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#ifndef WebVector_h
3293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#define WebVector_h
3393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
3493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "WebCommon.h"
3593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
3693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include <algorithm>
37f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include <limits>
38f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include <stdlib.h>
3993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
4051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)namespace blink {
4193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
4293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// A simple vector class.
4393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//
4493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// Sample usage:
4593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//
4693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   void Foo(WebVector<int>& result)
4793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   {
4893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//       WebVector<int> data(10);
4993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//       for (size_t i = 0; i < data.size(); ++i)
5093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//           data[i] = ...
5193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//       result.swap(data);
5293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   }
5393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//
5493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// It is also possible to assign from other types of random access
5593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// containers:
5693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//
5793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   void Foo(const std::vector<std::string>& input)
5893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   {
5993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//       WebVector<WebCString> cstrings = input;
6093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//       ...
6193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//   }
6293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//
6393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)template <typename T>
6493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)class WebVector {
6593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)public:
6693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    typedef T ValueType;
6793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
6893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    ~WebVector()
6993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
7093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        destroy();
7193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
7293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
7393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    explicit WebVector(size_t size = 0)
7493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
7593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        initialize(size);
7693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
7793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
78591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    template <typename U>
79591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    WebVector(const U* values, size_t size)
80591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    {
81591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch        initializeFrom(values, size);
82591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch    }
83591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch
8493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    WebVector(const WebVector<T>& other)
8593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
8693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        initializeFrom(other.m_ptr, other.m_size);
8793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
8893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
8993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    template <typename C>
9093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    WebVector(const C& other)
9193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
9293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        initializeFrom(other.size() ? &other[0] : 0, other.size());
9393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
9493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
9593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    WebVector& operator=(const WebVector& other)
9693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
9793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        if (this != &other)
9893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            assign(other);
9993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        return *this;
10093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
10193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
10293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    template <typename C>
10393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    WebVector<T>& operator=(const C& other)
10493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
10593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        if (this != reinterpret_cast<const WebVector<T>*>(&other))
10693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            assign(other);
10793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        return *this;
10893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
10993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
11093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    template <typename C>
11193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void assign(const C& other)
11293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
11393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        assign(other.size() ? &other[0] : 0, other.size());
11493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
11593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
11693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    template <typename U>
11793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void assign(const U* values, size_t size)
11893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
11993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        destroy();
12093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        initializeFrom(values, size);
12193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
12293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
12393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    size_t size() const { return m_size; }
12493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    bool isEmpty() const { return !m_size; }
12593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
12693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    T& operator[](size_t i)
12793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
1281e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        BLINK_ASSERT(i < m_size);
12993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        return m_ptr[i];
13093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
13193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    const T& operator[](size_t i) const
13293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
1331e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)        BLINK_ASSERT(i < m_size);
13493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        return m_ptr[i];
13593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
13602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch
13793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    bool contains(const T& value) const
13893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
13993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        for (size_t i = 0; i < m_size; i++) {
14093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            if (m_ptr[i] == value)
14193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)                return true;
14293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        }
14393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        return false;
14493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
14593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
14693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    T* data() { return m_ptr; }
14793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    const T* data() const { return m_ptr; }
14893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
14993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void swap(WebVector<T>& other)
15093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
15193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        std::swap(m_ptr, other.m_ptr);
15293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        std::swap(m_size, other.m_size);
15393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
15493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
15593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)private:
15693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void initialize(size_t size)
15793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
158f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        validateSize(size);
15993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        m_size = size;
16093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        if (!m_size)
16193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            m_ptr = 0;
16293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        else {
16393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            m_ptr = static_cast<T*>(::operator new(sizeof(T) * m_size));
16493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            for (size_t i = 0; i < m_size; ++i)
16593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)                new (&m_ptr[i]) T();
16693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        }
16793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
16893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
16993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    template <typename U>
17093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void initializeFrom(const U* values, size_t size)
17193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
172f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        validateSize(size);
17393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        m_size = size;
17493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        if (!m_size)
17593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            m_ptr = 0;
17693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        else {
17793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            m_ptr = static_cast<T*>(::operator new(sizeof(T) * m_size));
17893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            for (size_t i = 0; i < m_size; ++i)
17993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)                new (&m_ptr[i]) T(values[i]);
18093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        }
18193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
18293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
183f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    void validateSize(size_t size)
184f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
185f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        if (std::numeric_limits<size_t>::max() / sizeof(T) < size)
186f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            abort();
187f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
188f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
18993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    void destroy()
19093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    {
19193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        for (size_t i = 0; i < m_size; ++i)
19293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)            m_ptr[i].~T();
19393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)        ::operator delete(m_ptr);
19493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    }
19593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
19693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    T* m_ptr;
19793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)    size_t m_size;
19893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)};
19993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
20051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} // namespace blink
20193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)
20293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#endif
203