Unreviewed, rolling out r197955.
[WebKit-https.git] / Source / bmalloc / bmalloc / SortedVector.h
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef SortedVector_h
27 #define SortedVector_h
28
29 #include "Vector.h"
30 #include <algorithm>
31
32 namespace bmalloc {
33
34 template<typename T>
35 class SortedVector {
36     static_assert(std::is_trivially_destructible<T>::value, "SortedVector must have a trivial destructor.");
37
38     struct Bucket {
39         explicit Bucket(T value)
40             : value(value)
41             , isDeleted(false)
42         {
43         }
44         
45         template<typename U> bool operator<(const U& other) const
46         {
47             return value < other;
48         }
49
50         T value;
51         bool isDeleted;
52     };
53
54 public:
55     class iterator : public std::iterator<std::forward_iterator_tag, T> {
56     public:
57         iterator(Bucket* bucket, Bucket* end)
58             : m_bucket(bucket)
59             , m_end(end)
60         {
61             skipDeletedBuckets();
62         }
63         
64         iterator(const iterator& other)
65             : m_bucket(other.m_bucket)
66             , m_end(other.m_end)
67         {
68         }
69
70         iterator& operator++()
71         {
72             BASSERT(m_bucket != m_end);
73             ++m_bucket;
74             skipDeletedBuckets();
75             return *this;
76         }
77
78         bool operator!=(const iterator& other)
79         {
80             return m_bucket != other.m_bucket;
81         }
82
83         T& operator*()
84         {
85             BASSERT(m_bucket < m_end);
86             BASSERT(!m_bucket->isDeleted);
87             return m_bucket->value;
88         }
89
90         T* operator->()  { return &operator*(); }
91
92     private:
93         friend class SortedVector;
94
95         void skipDeletedBuckets()
96         {
97             while (m_bucket != m_end && m_bucket->isDeleted)
98                 ++m_bucket;
99         }
100
101         Bucket* m_bucket;
102         Bucket* m_end;
103     };
104
105     iterator begin() { return iterator(m_vector.begin(), m_vector.end()); }
106     iterator end() { return iterator(m_vector.end(), m_vector.end()); }
107
108     void insert(const T&);
109
110     template<typename U> iterator find(const U&);
111     template<typename U> T get(const U&);
112     template<typename U> T take(const U&);
113
114     void shrinkToFit();
115
116 private:
117     Vector<Bucket> m_vector;
118 };
119
120 template<typename T>
121 void SortedVector<T>::insert(const T& value)
122 {
123     auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
124     if (it != m_vector.end() && it->isDeleted) {
125         *it = Bucket(value);
126         return;
127     }
128
129     m_vector.insert(it, Bucket(value));
130 }
131
132 template<typename T> template<typename U>
133 typename SortedVector<T>::iterator SortedVector<T>::find(const U& value)
134 {
135     auto it = std::lower_bound(m_vector.begin(), m_vector.end(), value);
136     return iterator(it, m_vector.end());
137 }
138
139 template<typename T> template<typename U>
140 T SortedVector<T>::get(const U& value)
141 {
142     return *find(value);
143 }
144
145 template<typename T> template<typename U>
146 T SortedVector<T>::take(const U& value)
147 {
148     auto it = find(value);
149     it.m_bucket->isDeleted = true;
150     return it.m_bucket->value;
151 }
152
153 template<typename T>
154 void SortedVector<T>::shrinkToFit()
155 {
156     auto isDeleted = [](const Bucket& bucket) {
157         return bucket.isDeleted;
158     };
159
160     auto newEnd = std::remove_if(m_vector.begin(), m_vector.end(), isDeleted);
161     size_t newSize = newEnd - m_vector.begin();
162     m_vector.shrink(newSize);
163
164     m_vector.shrinkToFit();
165 }
166
167 } // namespace bmalloc
168
169 #endif // SortedVector_h