bddf410083724188d1a2853cb8fb51d26a54600c
[charm.git] / examples / charm++ / state_space_searchengine / 3SAT / minisat / mtl / .svn / text-base / BoxedVec.h.svn-base
1 /*******************************************************************************************[Vec.h]
2 MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5 associated documentation files (the "Software"), to deal in the Software without restriction,
6 including without limitation the rights to use, copy, modify, merge, publish, distribute,
7 sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8 furnished to do so, subject to the following conditions:
9
10 The above copyright notice and this permission notice shall be included in all copies or
11 substantial portions of the Software.
12
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14 NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
17 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 **************************************************************************************************/
19
20 #ifndef BoxedVec_h
21 #define BoxedVec_h
22
23 #include <cstdlib>
24 #include <cassert>
25 #include <new>
26
27 //=================================================================================================
28 // Automatically resizable arrays
29 //
30 // NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
31
32 template<class T>
33 class bvec {
34
35     static inline int imin(int x, int y) {
36         int mask = (x-y) >> (sizeof(int)*8-1);
37         return (x&mask) + (y&(~mask)); }
38
39     static inline int imax(int x, int y) {
40         int mask = (y-x) >> (sizeof(int)*8-1);
41         return (x&mask) + (y&(~mask)); }
42
43     struct Vec_t {
44         int sz;
45         int cap;
46         T   data[0];
47
48         static Vec_t* alloc(Vec_t* x, int size){
49             x = (Vec_t*)realloc((void*)x, sizeof(Vec_t) + sizeof(T)*size);
50             x->cap = size;
51             return x;
52         }
53         
54     };
55
56     Vec_t* ref;
57
58     static const int init_size = 2;
59     static int   nextSize (int current) { return (current * 3 + 1) >> 1; }
60     static int   fitSize  (int needed)  { int x; for (x = init_size; needed > x; x = nextSize(x)); return x; }
61
62     void fill (int size) {
63         assert(ref != NULL);
64         for (T* i = ref->data; i < ref->data + size; i++)
65             new (i) T();
66     }
67
68     void fill (int size, const T& pad) {
69         assert(ref != NULL);
70         for (T* i = ref->data; i < ref->data + size; i++)
71             new (i) T(pad);
72     }
73
74     // Don't allow copying (error prone):
75     altvec<T>&  operator = (altvec<T>& other) { assert(0); }
76     altvec (altvec<T>& other)                  { assert(0); }
77
78 public:
79     void     clear  (bool dealloc = false) { 
80         if (ref != NULL){
81             for (int i = 0; i < ref->sz; i++) 
82                 (*ref).data[i].~T();
83
84             if (dealloc) { 
85                 free(ref); ref = NULL; 
86             }else 
87                 ref->sz = 0;
88         } 
89     }
90
91     // Constructors:
92     altvec(void)                   : ref (NULL) { }
93     altvec(int size)               : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size);      ref->sz = size; }
94     altvec(int size, const T& pad) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size, pad); ref->sz = size; }
95    ~altvec(void) { clear(true); }
96
97     // Ownership of underlying array:
98     operator T*       (void)           { return ref->data; }     // (unsafe but convenient)
99     operator const T* (void) const     { return ref->data; }
100
101     // Size operations:
102     int      size   (void) const       { return ref != NULL ? ref->sz : 0; }
103
104     void     pop    (void)             { assert(ref != NULL && ref->sz > 0); int last = --ref->sz; ref->data[last].~T(); }
105     void     push   (const T& elem) {
106         int size = ref != NULL ? ref->sz  : 0;
107         int cap  = ref != NULL ? ref->cap : 0;
108         if (size == cap){
109             cap = cap != 0 ? nextSize(cap) : init_size;
110             ref = Vec_t::alloc(ref, cap); 
111         }
112         //new (&ref->data[size]) T(elem); 
113         ref->data[size] = elem; 
114         ref->sz = size+1; 
115     }
116
117     void     push   () {
118         int size = ref != NULL ? ref->sz  : 0;
119         int cap  = ref != NULL ? ref->cap : 0;
120         if (size == cap){
121             cap = cap != 0 ? nextSize(cap) : init_size;
122             ref = Vec_t::alloc(ref, cap); 
123         }
124         new (&ref->data[size]) T(); 
125         ref->sz = size+1; 
126     }
127
128     void     shrink (int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
129     void     shrink_(int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
130     void     growTo (int size)               { while (this->size() < size) push(); }
131     void     growTo (int size, const T& pad) { while (this->size() < size) push(pad); }
132     void     capacity (int size)             { growTo(size); }
133
134     const T& last  (void) const              { return ref->data[ref->sz-1]; }
135     T&       last  (void)                    { return ref->data[ref->sz-1]; }
136
137     // Vector interface:
138     const T& operator [] (int index) const  { return ref->data[index]; }
139     T&       operator [] (int index)        { return ref->data[index]; }
140
141     void copyTo(altvec<T>& copy) const { copy.clear(); for (int i = 0; i < size(); i++) copy.push(ref->data[i]); }
142     void moveTo(altvec<T>& dest) { dest.clear(true); dest.ref = ref; ref = NULL; }
143
144 };
145
146
147 #endif