Inside Bitcoin

251    bool empty() const {
252        return size() == 0;
253    }
254
255    iterator begin() { return iterator(item_ptr(0)); }
256    const_iterator begin() const { return const_iterator(item_ptr(0)); }
257    iterator end() { return iterator(item_ptr(size())); }
258    const_iterator end() const { return const_iterator(item_ptr(size())); }
259
260    size_t capacity() const {
261        if (is_direct()) {
262            return N;
263        } else {
264            return _union.indirect_contents.capacity;
265        }
266    }
267
268    T& operator[](size_type pos) {
269        return *item_ptr(pos);
270    }
271
272    const T& operator[](size_type pos) const {
273        return *item_ptr(pos);
274    }
275
276    void resize(size_type new_size) {
277        size_type cur_size = size();
278        if (cur_size == new_size) {
279            return;
280        }
281        if (cur_size > new_size) {
282            erase(item_ptr(new_size), end());
283            return;
284        }
285        if (new_size > capacity()) {
286            change_capacity(new_size);
287        }
288        ptrdiff_t increase = new_size - cur_size;
289        fill(item_ptr(cur_size), increase);
290        _size += increase;
291    }
292
293    void reserve(size_type new_capacity) {
294        if (new_capacity > capacity()) {
295            change_capacity(new_capacity);
296        }
297    }
298
299    void shrink_to_fit() {
300        change_capacity(size());
301    }
302
303    void clear() {
304        resize(0);
305    }
306
307    iterator insert(iterator pos, const T& value) {
308        size_type p = pos - begin();
309        size_type new_size = size() + 1;
310        if (capacity() < new_size) {
311            change_capacity(new_size + (new_size >> 1));
312        }
313        T* ptr = item_ptr(p);
314        T* dst = ptr + 1;
315        memmove(dst, ptr, (size() - p) * sizeof(T));
316        _size++;
317        new(static_cast<void*>(ptr)) T(value);
318        return iterator(ptr);
319    }
320
321    void insert(iterator pos, size_type count, const T& value) {
322        size_type p = pos - begin();
323        size_type new_size = size() + count;
324        if (capacity() < new_size) {
325            change_capacity(new_size + (new_size >> 1));
326        }
327        T* ptr = item_ptr(p);
328        T* dst = ptr + count;
329        memmove(dst, ptr, (size() - p) * sizeof(T));
330        _size += count;
331        fill(item_ptr(p), count, value);
332    }
333
334    template <std::input_iterator InputIterator>
335    void insert(iterator pos, InputIterator first, InputIterator last) {
336        size_type p = pos - begin();
337        difference_type count = last - first;
338        size_type new_size = size() + count;
339        if (capacity() < new_size) {
340            change_capacity(new_size + (new_size >> 1));
341        }
342        T* ptr = item_ptr(p);
343        T* dst = ptr + count;
344        memmove(dst, ptr, (size() - p) * sizeof(T));
345        _size += count;
346        fill(ptr, first, last);
347    }
348
349    inline void resize_uninitialized(size_type new_size) {
350        // resize_uninitialized changes the size of the prevector but does not initialize it.
351        // If size < new_size, the added elements must be initialized explicitly.
352        if (capacity() < new_size) {
353            change_capacity(new_size);
354            _size += new_size - size();
355            return;
356        }
357        if (new_size < size()) {
358            erase(item_ptr(new_size), end());
359        } else {
360            _size += new_size - size();
361        }
362    }
363
364    iterator erase(iterator pos) {
365        return erase(pos, pos + 1);
366    }
367
368    iterator erase(iterator first, iterator last) {
369        // Erase is not allowed to the change the object's capacity. That means
370        // that when starting with an indirectly allocated prevector with
371        // size and capacity > N, the result may be a still indirectly allocated
372        // prevector with size <= N and capacity > N. A shrink_to_fit() call is
373        // necessary to switch to the (more efficient) directly allocated
374        // representation (with capacity N and size <= N).
375        iterator p = first;
376        char* endp = (char*)&(*end());
377        _size -= last - p;
378        memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
379        return first;
380    }
381
382    template<typename... Args>
383    void emplace_back(Args&&... args) {
384        size_type new_size = size() + 1;
385        if (capacity() < new_size) {
386            change_capacity(new_size + (new_size >> 1));
387        }
388        new(item_ptr(size())) T(std::forward<Args>(args)...);
389        _size++;
390    }
391
392    void push_back(const T& value) {
393        emplace_back(value);
394    }
395
396    void pop_back() {
397        erase(end() - 1, end());
398    }
399
400    T& front() {
401        return *item_ptr(0);
402    }
403
404    const T& front() const {
405        return *item_ptr(0);
406    }
407
408    T& back() {
409        return *item_ptr(size() - 1);
410    }
411
412    const T& back() const {
413        return *item_ptr(size() - 1);
414    }
415
416    void swap(prevector<N, T, Size, Diff>& other) noexcept
417    {
418        std::swap(_union, other._union);
419        std::swap(_size, other._size);
420    }
421
422    ~prevector() {
423        if (!is_direct()) {
424            free(_union.indirect_contents.indirect);
425            _union.indirect_contents.indirect = nullptr;
426        }
427    }
428
429    constexpr bool operator==(const prevector& other) const {
430        return std::ranges::equal(*this, other);
431    }
432
433    bool operator<(const prevector<N, T, Size, Diff>& other) const {
434        if (size() < other.size()) {
435            return true;
436        }
437        if (size() > other.size()) {
438            return false;
439        }
440        const_iterator b1 = begin();
441        const_iterator b2 = other.begin();
442        const_iterator e1 = end();
443        while (b1 != e1) {
444            if ((*b1) < (*b2)) {
445                return true;
446            }
447            if ((*b2) < (*b1)) {
448                return false;
449            }
450            ++b1;
451            ++b2;
452        }
453        return false;
454    }
455
456    size_t allocated_memory() const {
457        if (is_direct()) {
458            return 0;
459        } else {
460            return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
461        }
462    }
463
464    value_type* data() {
465        return item_ptr(0);
466    }
467
468    const value_type* data() const {
469        return item_ptr(0);
470    }
471};
472
473#endif // BITCOIN_PREVECTOR_H
474