~verifydtapn-contributers/verifydtapn/trunk

« back to all changes in this revision

Viewing changes to src/DiscreteVerification/DataStructures/binarywrapper.h

  • Committer: Jiri Srba
  • Date: 2015-08-31 12:39:10 UTC
  • mfrom: (324.3.24 PTrieWorkflow)
  • Revision ID: srba@cs.aau.dk-20150831123910-qwr9g6pq7zntajhe
merged in a big branch implementing PTrie for workflow analysis

Show diffs side-by-side

added added

removed removed

Lines of Context:
9
9
#include <stdio.h>
10
10
#include <iostream>
11
11
#include <string.h>
 
12
#include <assert.h>
 
13
#include <stdint.h>
12
14
 
13
15
#ifndef BINARYWRAPPER_H
14
16
#define BINARYWRAPPER_H
17
19
    typedef unsigned int uint;
18
20
    typedef unsigned char uchar;
19
21
    
 
22
    /**
 
23
     * Wrapper for binary data. This provides easy access to individual bits, 
 
24
     * heap allocation and comparison. Notice that one has to make sure to 
 
25
     * explicitly call release() if one wishes to deallocate (possibly shared data).
 
26
     * 
 
27
     */
20
28
    template<class T>
21
29
    class binarywrapper_t
22
30
    {
23
31
    public:
24
32
        // Constructors
 
33
        /**
 
34
         * Empty constructor, no data is allocated
 
35
         */
 
36
        inline
25
37
        binarywrapper_t();        
 
38
        
 
39
        /**
 
40
         Allocates a room for at least size bits
 
41
         */
 
42
        inline
26
43
        binarywrapper_t(uint size);
 
44
        
 
45
        /**
 
46
         * Constructor for copying over data from latest the offset'th bit.
 
47
         * Detects overflows.
 
48
         * @param other: wrapper to copy from
 
49
         * @param offset: maximal number of bits to skip.
 
50
         */
 
51
        inline
27
52
        binarywrapper_t(const binarywrapper_t& other, uint offset);
28
53
        binarywrapper_t(const binarywrapper_t& other, uint size, uint offset, 
29
54
                                                            uint encodingsize);
30
55
        binarywrapper_t(uchar* raw, uint size, uint offset, uint encsize);
 
56
        
 
57
        /**
 
58
         * Assign (not copy) raw data to pointer. Set number of bytes to size
 
59
         * @param raw: some memory to point to
 
60
         * @param size: number of bytes.
 
61
         */
 
62
        inline
31
63
        binarywrapper_t(uchar* raw, uint size);
32
64
        
33
 
        // Destructor
 
65
        /**
 
66
         * Empty destructor. Does NOT deallocate data - do this with explicit
 
67
         * call to release().
 
68
         */
 
69
        inline
34
70
        ~binarywrapper_t();
35
71
        
36
 
        // Copy and clones
 
72
        /**
 
73
         * Makes a complete copy, including new heap-allocation
 
74
         * @return an exact copy, but in a different area of the heap.
 
75
         */
 
76
        inline
37
77
        binarywrapper_t clone() const;
 
78
        
 
79
        /**
 
80
         * Copy over data and meta-data from other, but insert only into target
 
81
         * after offset bits.
 
82
         * Notice that this can cause memory-corruption if there is not enough
 
83
         * room in target, or to many bits are skipped.
 
84
         * @param other: wrapper to copy from
 
85
         * @param offset: bits to skip 
 
86
         */
 
87
        inline
38
88
        void copy(const binarywrapper_t& other, uint offset);
 
89
        
 
90
        /**
 
91
         * Copy over size bytes form raw data. Assumes that current wrapper has
 
92
         * enough room.
 
93
         * @param raw: source data
 
94
         * @param size: number of bytes to copy
 
95
         */
 
96
        inline
39
97
        void copy(const uchar* raw, uint size);
40
98
        
41
99
        // accessors
 
100
        /**
 
101
         * Get value of the place'th bit
 
102
         * @param place: bit index
 
103
         * @return 
 
104
         */
 
105
        inline
42
106
        bool at(const uint place) const;
 
107
        
 
108
        /**
 
109
         * number of bytes allocated in heap
 
110
         * @return 
 
111
         */
 
112
        inline
43
113
        uint size() const;
44
 
        uchar* raw() const;
 
114
        
 
115
        /**
 
116
         * Raw access to data
 
117
         * @return 
 
118
         */
 
119
        inline
 
120
        uchar*& raw();
 
121
        
 
122
        /**
 
123
         * Raw access to data when in const setting
 
124
         * @return 
 
125
         */
 
126
        inline
 
127
        uchar* const_raw() const;
 
128
        
 
129
        /**
 
130
         * pretty print of content
 
131
         */
 
132
        inline
45
133
        void print() const;
 
134
        
 
135
        /**
 
136
         * finds the overhead (unused number of bits) when allocating for size
 
137
         * bits.
 
138
         * @param size: number of bits
 
139
         * @return 
 
140
         */
 
141
        inline
46
142
        static size_t overhead(uint size);
47
143
        
48
144
        // modifiers
 
145
        /**
 
146
         * Change value of place'th bit 
 
147
         * @param place: index of bit to change
 
148
         * @param value: desired value
 
149
         */
 
150
        inline
49
151
        void set(const uint place, const bool value) const;
 
152
        
 
153
        /**
 
154
         * Sets all memory on heap to 0 
 
155
         */
 
156
        inline
50
157
        void zero() const;
51
 
        void release() const;
 
158
        
 
159
        /**
 
160
         * Deallocates memory stored on heap
 
161
         */
 
162
        inline
 
163
        void release();
 
164
 
52
165
        void set_meta(T data);
53
166
        T get_meta() const;
 
167
                
 
168
        /**
 
169
         * Nice access to single bits
 
170
         * @param i: index to access
 
171
         * @return 
 
172
         */
 
173
        inline
54
174
        uchar operator[](int i);
 
175
        
 
176
        /**
 
177
         * Removes a number of bytes from end of heap-allocated data if any is 
 
178
         * allocated nothing happens if not. Bound-checks.
 
179
         * @param number of bytes to remove.
 
180
         */
 
181
        inline
55
182
        void pop_front(unsigned short);
56
183
        
57
 
        inline int cmp(const binarywrapper_t &other)
 
184
        /**
 
185
         * Compares two wrappers. Assumes that smaller number of bytes also means
 
186
         * a smaller wrapper. Otherwise compares byte by byte.
 
187
         * @param other: wrapper to compare to
 
188
         * @return -1 if other is smaller, 0 if same, 1 if other is larger
 
189
         */
 
190
        inline int cmp(const binarywrapper_t &other) const
58
191
        {
59
192
            if(_nbytes != other._nbytes)
60
193
            {
62
195
                else return 1;
63
196
            }
64
197
                
65
 
            for(int i = _nbytes - 1; i >= 0; i--)
66
 
            {
67
 
                if(_blob[i] < other._blob[i])
68
 
                    return -1;
69
 
                else if (_blob[i] > other._blob[i])
70
 
                    return 1;
71
 
            }
 
198
            return memcmp(_blob, other.const_raw(), other._nbytes );
 
199
        }
72
200
            
73
 
            return 0;
74
 
        }
75
 
        
76
 
        // Operators
 
201
        /**
 
202
         * Compares wrappers bytes by bytes. If sizes do not match, they are not
 
203
         * equal. If sizes match, compares byte by byte.
 
204
         * @param enc1 
 
205
         * @param enc2
 
206
         * @return true if a match, false otherwise
 
207
         */
77
208
        inline friend bool operator==(  const binarywrapper_t &enc1, 
78
209
                                        const binarywrapper_t &enc2) {
79
 
            if(enc1._nbytes != enc2._nbytes)
80
 
                return false;
81
 
            
82
 
            for(size_t i = 0; i < enc1._nbytes; i++)
83
 
                if(enc1._blob[i] != enc2._blob[i])
84
 
                    return false;
85
 
            
86
 
            return true;
87
 
        }
88
 
        
89
 
       /* inline friend bool operator <=( const binarywrapper &enc1,
90
 
                                        const binarywrapper &enc2)
91
 
        {
92
 
            if(enc1.numberOfBytes != enc2.numberOfBytes)
93
 
                return enc1.numberOfBytes < enc2.numberOfBytes;
94
 
            
95
 
            for(size_t i = 0; i < enc1.numberOfBytes; i++)
96
 
                if(enc1.blob[i] < enc2.blob[i])
97
 
                    return true;
98
 
                else if (enc1.blob[i] > enc2.blob[i])
99
 
                    return false;
100
 
            
101
 
            return true;
102
 
        }*/
103
 
        
104
 
        inline friend bool operator<(   const binarywrapper_t &enc1, 
105
 
                                        const binarywrapper_t &enc2) {
106
 
            if(enc1._nbytes != enc2._nbytes)
107
 
                return enc1._nbytes < enc2._nbytes;
108
 
            
109
 
            for(size_t i = 0; i < enc1._nbytes; i++)
110
 
                if(enc1._blob[i] < enc2._blob[i])
111
 
                    return true;
112
 
                else if (enc1._blob[i] > enc2._blob[i])
113
 
                    return false;
114
 
            
115
 
            return false;
 
210
            return enc1.cmp(enc2) == 0;
116
211
        }
117
212
        
118
213
    private:
 
214
            
 
215
        // blob of heap-allocated data
119
216
        uchar* _blob;
120
 
        unsigned short _nbytes;
 
217
            
 
218
        // number of bytes allocated on heap
 
219
         unsigned short _nbytes;
 
220
        
 
221
        // meta data to carry
121
222
        T _meta;
 
223
            
 
224
        // masks for single-bit access
122
225
        const static uchar _masks[8];
123
226
    };
124
227
    
273
376
    }
274
377
    
275
378
    template<class T>
276
 
    uchar* binarywrapper_t<T>::raw() const
 
379
    uchar*& binarywrapper_t<T>::raw()
 
380
    {
 
381
        return _blob; 
 
382
    }
 
383
    
 
384
    template<class T>
 
385
    uchar* binarywrapper_t<T>::const_raw() const
277
386
    {
278
387
        return _blob; 
279
388
    }
292
401
    {
293
402
        if(_nbytes == 0) return;  // Special case, nothing to do!
294
403
        unsigned short int nbytes;
 
404
        
 
405
        // make sure we do not remove to much, but as much as we can.
295
406
        if(topop >= _nbytes)
296
407
        {
297
408
            topop = _nbytes;
340
451
    }
341
452
    
342
453
    template<class T>
343
 
    void binarywrapper_t<T>::release() const
 
454
    void binarywrapper_t<T>::release()
344
455
    {
345
456
        delete[] _blob;
 
457
        _blob = NULL;
346
458
    }
347
459
    
348
460
    template<class T>