Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Vec.h
Go to the documentation of this file.
1/*******************************************************************************************[Vec.h]
2Copyright (c) 2003-2007, Niklas Een, Niklas Sorensson
3Copyright (c) 2007-2010, Niklas Sorensson
4
5Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
6associated documentation files (the "Software"), to deal in the Software without restriction,
7including without limitation the rights to use, copy, modify, merge, publish, distribute,
8sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in all copies or
12substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
15NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
16NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
17DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
18OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19**************************************************************************************************/
20
21#pragma once
22
23#include <assert.h>
24#include <new>
25
28
29namespace Minisat {
30namespace Internal {
31
32//=================================================================================================
33// Automatically resizable arrays
34//
35// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
36
37template<class T>
38class vec {
39 T* data;
40 int sz;
41 int cap;
42
43 // Don't allow copying (error prone):
44 vec<T>& operator = (vec<T>& other) { assert(0); return *this; }
46
47 // Helpers for calculating next capacity:
48 static inline int imax (int x, int y) { int mask = (y-x) >> (sizeof(int)*8-1); return (x&mask) + (y&(~mask)); }
49 //static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; }
50 static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; }
51
52public:
53 // Constructors:
54 vec() : data(nullptr), sz(0), cap(0) { }
55 explicit vec(int size) : data(nullptr), sz(0), cap(0) { growTo(size); }
56 vec(int size, const T& pad) : data(nullptr), sz(0), cap(0) { growTo(size, pad); }
57 ~vec() { clear(true); }
58
59 // Pointer to first element:
60 operator T* (void) { return data; }
61
62 // Size operations:
63 int size (void) const { return sz; }
64 void shrink (int nelems) { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); }
65 void shrink_ (int nelems) { assert(nelems <= sz); sz -= nelems; }
66 int capacity (void) const { return cap; }
67 void capacity (int min_cap);
68 void growTo (int size);
69 void growTo (int size, const T& pad);
70 void clear (bool dealloc = false);
71
72 // Stack interface:
73 void push (void) { if (sz == cap) capacity(sz+1); new (&data[sz]) T(); sz++; }
74 void push (const T& elem) { if (sz == cap) capacity(sz+1); data[sz++] = elem; }
75 void push_ (const T& elem) { assert(sz < cap); data[sz++] = elem; }
76 void pop (void) { assert(sz > 0); sz--, data[sz].~T(); }
77 // NOTE: it seems possible that overflow can happen in the 'sz+1' expression of 'push()', but
78 // in fact it can not since it requires that 'cap' is equal to INT_MAX. This in turn can not
79 // happen given the way capacities are calculated (below). Essentially, all capacities are
80 // even, but INT_MAX is odd.
81
82 const T& last (void) const { return data[sz-1]; }
83 T& last (void) { return data[sz-1]; }
84
85 // Vector interface:
86 const T& operator [] (int index) const { return data[index]; }
87 T& operator [] (int index) { return data[index]; }
88
89 // Duplicatation (preferred instead):
90 void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) copy[i] = data[i]; }
91 void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = nullptr; sz = 0; cap = 0; }
92};
93
94
95template<class T>
97 if (cap >= min_cap) return;
98 int add = imax((min_cap - cap + 1) & ~1, ((cap >> 1) + 2) & ~1); // NOTE: grow by approximately 3/2
99 if (add > INT_MAX - cap || (((data = (T*)::realloc(data, (cap += add) * sizeof(T))) == nullptr) && errno == ENOMEM))
100 throw OutOfMemoryException();
101 }
102
103
104template<class T>
105void vec<T>::growTo(int size, const T& pad) {
106 if (sz >= size) return;
107 capacity(size);
108 for (int i = sz; i < size; i++) data[i] = pad;
109 sz = size; }
110
111
112template<class T>
113void vec<T>::growTo(int size) {
114 if (sz >= size) return;
115 capacity(size);
116 for (int i = sz; i < size; i++) new (&data[i]) T;
117 sz = size; }
118
119
120template<class T>
122 if (data != nullptr){
123 for (int i = 0; i < sz; i++) data[i].~T();
124 sz = 0;
125 if (dealloc) free(data), data = nullptr, cap = 0;
126 }
127}
128
129//=================================================================================================
130} // namespace Internal
131} // namespace Minisat
int size(void) const
Definition Vec.h:63
const T & operator[](int index) const
Definition Vec.h:86
void growTo(int size, const T &pad)
Definition Vec.h:105
void pop(void)
Definition Vec.h:76
void push(const T &elem)
Definition Vec.h:74
void shrink(int nelems)
Definition Vec.h:64
static void nextCap(int &cap)
Definition Vec.h:50
vec(vec< T > &other)
Definition Vec.h:45
void clear(bool dealloc=false)
Definition Vec.h:121
void push(void)
Definition Vec.h:73
void growTo(int size)
Definition Vec.h:113
T & last(void)
Definition Vec.h:83
int capacity(void) const
Definition Vec.h:66
static int imax(int x, int y)
Definition Vec.h:48
void moveTo(vec< T > &dest)
Definition Vec.h:91
void capacity(int min_cap)
Definition Vec.h:96
vec(int size)
Definition Vec.h:55
vec(int size, const T &pad)
Definition Vec.h:56
vec< T > & operator=(vec< T > &other)
Definition Vec.h:44
void shrink_(int nelems)
Definition Vec.h:65
void copyTo(vec< T > &copy) const
Definition Vec.h:90
void push_(const T &elem)
Definition Vec.h:75
const T & last(void) const
Definition Vec.h:82
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
static void copy(const T &from, T &to)
Definition Alg.h:61