OpenCores
URL https://opencores.org/ocsvn/forwardcom/forwardcom/trunk

Subversion Repositories forwardcom

[/] [forwardcom/] [bintools/] [containers.h] - Blame information for rev 77

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 67 Agner
/****************************  containers.h   ********************************
2
* Author:        Agner Fog
3
* Date created:  2006-07-15
4
* Last modified: 2018-02-28
5
* Version:       1.10
6
* Project:       Binary tools for ForwardCom instruction set
7
* Module:        containers.h
8
* Description:
9
* Header file for container classes and dynamic memory allocation
10
*
11
* Copyright 2006-2020 GNU General Public License http://www.gnu.org/licenses
12
*****************************************************************************/
13
 
14
/*****************************************************************************
15
This header file declares various container classes for dynamic allocation
16
of memory for files and other types of data with unpredictable sizes.
17
These classes have private access to the memory buffer in order to prevent
18
memory leaks. It is important to use these classes for all dynamic memory
19
allocation.
20
 
21
The class CMemoryBuffer and its descendants are used for many purposes of
22
storage of data with a size that is not known in advance. CMemoryBuffer
23
allows the size of its data to grow when new data are appended with the
24
Push() member function.
25
 
26
Several classes are derived from CMemoryBuffer:
27
 
28
The template class CDynamicArray<> is used as a dynamic array where all
29
elements have the same type. It cannot be used for types that have non-
30
default constructors or destructors.
31
 
32
The class CFileBuffer is used for reading, writing and storing files.
33
 
34
Other classes can be derived from these to add more properties or functionality.
35
 
36
It is possible to transfer a data buffer from one of these buffers to another,
37
using the operator
38
 
39
       A >> B
40
 
41
where A and B are both objects of classes that descend from CMemoryBuffer or
42
CFileBuffer. This operator transfers ownership of the allocated data buffer
43
from A to B, so that A is empty after the tranfer. This makes sure that a
44
memory buffer is always owned by one, and only one, object. Any data owned
45
by B before the transfer is deallocated.
46
The opposite operator B << A does the same thing.
47
 
48
The >> operator can be used when we want to do something to a data buffer
49
that requires a specialized class. The data buffer can be transferred from
50
the object that owns it to an object of the specialized class and
51
transferred back again to the original owner when the object of the
52
specialized class has done its job. The >> operator transfers the data and
53
properties of CMemoryBuffer or CFileBuffer, but not the additional properties
54
of other classes derived from these.
55
 
56
You may say that these classes have a chameleonic nature:
57
You can change the nature of a piece of data owned by an object by
58
transferring it to an object of a different class. This couldn't be done
59
by traditional polymorphism because it is not possible to change the class
60
of an object after it is created.
61
 
62
The container class CMemoryBuffer is useful for storing data of mixed types.
63
Data of arbitrary type can be accessed by Get<type>(offset) or by
64
Buf() + offset.
65
 
66
The container class template CDynamicArray is useful for storing data of
67
the same type.
68
 
69
Warning:
70
It is not safe to make pointers or references to data inside one of these
71
container classes because the internal buffer may be re-allocated when the
72
size grows. Such pointers will work only as long as the size of the container
73
is unchanged. It is safer to address data inside the buffer by their index
74
or offset relative to the buffer.
75
 
76
*****************************************************************************/
77
 
78
#pragma once
79
 
80
class CMemoryBuffer;                             // Declared below
81
class CFileBuffer;                               // Declared below
82
 
83
void operator >> (CMemoryBuffer & a, CMemoryBuffer & b); // Transfer ownership of buffer and other properties
84
void operator >> (CFileBuffer & a, CFileBuffer & b);     // Transfer ownership of buffer and other properties
85
 
86
// Class CMemoryBuffer makes a container for arbitrary data, which can grow as new data are added.
87
class CMemoryBuffer {
88
public:
89
   CMemoryBuffer();                              // Constructor
90
   ~CMemoryBuffer();                             // Destructor
91
   void setSize(uint32_t size);                  // Allocate buffer of specified size
92
   void setDataSize(uint32_t size);              // Set data size and fill any new data with zeroes
93
   void clear();                                 // De-allocate buffer
94
   void zero();                                  // Set all contents to zero without changing data size
95
   uint32_t dataSize() const {return data_size;};// Get file data size
96
   uint32_t bufferSize() const {return buffer_size;};// Get buffer size
97
   uint32_t numEntries() const {return num_entries;};// Get number of entries
98
   uint32_t push(void const* obj, uint32_t size);// Add object to buffer, return offset
99
   uint32_t pushString(char const * s);          // Add ASCIIZ string to buffer, return offset
100
   uint32_t getLastIndex() const;                // Index of last object pushed (zero-based)
101
   void align(uint32_t a);                       // Align next entry to address divisible by a. must be a power of 2
102
   int8_t * buf() {return buffer;};              // Access to buffer
103
   int8_t const * buf() const {return buffer;};  // Access to buffer, const
104
   template <class TX> TX & get(uint32_t offset) { // Get object of arbitrary type from buffer
105
      if (offset >= data_size) {
106
          err.submit(ERR_CONTAINER_INDEX); offset = 0;} // Offset out of range
107
      return *(TX*)(buffer + offset);}
108
   char * getString(uint32_t offset) {           // Get string from offset returned from pushString
109
       return (char *)(buffer + offset);
110
   }
111
   void copy(CMemoryBuffer const & b);           // Make a copy of whole buffer
112
private:
113
   CMemoryBuffer(CMemoryBuffer&);                // Make private copy constructor to prevent simple copying
114
   CMemoryBuffer & operator = (CMemoryBuffer const&);// Make assignment operator to prevent simple copying
115
   int8_t * buffer;                              // Buffer containing binary data. To be modified only by SetSize and operator >>
116
   uint32_t buffer_size;                         // Size of allocated buffer ( > DataSize)
117
protected:
118
   uint32_t num_entries;                         // Number of objects pushed
119
   uint32_t data_size;                           // Size of data, offset to vacant space
120
   friend void operator >> (CMemoryBuffer & a, CMemoryBuffer & b); // Transfer ownership of buffer
121
   friend void operator >> (CFileBuffer & a, CFileBuffer & b);     // Transfer ownership of buffer
122
};
123
 
124
inline void operator << (CMemoryBuffer & b, CMemoryBuffer & a) {a >> b;} // Same as operator << above
125
inline void operator << (CFileBuffer & b, CFileBuffer & a) {a >> b;} // Same as operator << above
126
 
127
// Class CFileBuffer is used for storage of input and output files
128
class CFileBuffer : public CMemoryBuffer {
129
public:
130
   CFileBuffer();                                // Default constructor
131
   //CFileBuffer(uint32_t filename);               // Constructor
132
   void read(const char * filename, int ignoreError = 0);               // Read file into buffer
133
   void write(const char * filename);                                 // Write buffer to file
134
   int  getFileType();                           // Get file format type
135
   void setFileType(int type);                   // Set file format type
136
   void reset();                                 // Set all members to zero
137
   static char const * getFileFormatName(int fileType); // Get name of file format type
138
   int wordSize;                                 // Segment word size (16, 32, 64)
139
   int fileType;                                 // Object file type
140
   int executable;                               // File is executable
141
   int machineType;                              // Machine type, x86 or ForwarCom
142
};
143
 
144
 
145
// Class CTextFileBuffer is used for building text files
146
class CTextFileBuffer : public CFileBuffer {
147
public:
148
   CTextFileBuffer();                            // Constructor
149
   uint32_t put(const char * text);              // Write text string to buffer without terminating zero
150
   void put(const char character);               // Write single character to buffer
151
   uint32_t putStringN(const char * s, uint32_t len);// Write string to buffer, add terminating zero
152
   void newLine();                               // Add linefeed
153
   void tabulate(uint32_t i);                    // Insert spaces until column i
154
   int  lineType;                                // 0 = DOS/Windows linefeeds, 1 = UNIX linefeeds
155
   void putDecimal(int32_t x, int IsSigned = 0); // Write decimal number to buffer
156
   void putHex(uint8_t  x, int ox = 1);          // Write hexadecimal number to buffer
157
   void putHex(uint16_t x, int ox = 1);          // Write hexadecimal number to buffer
158
   void putHex(uint32_t x, int ox = 1);          // Write hexadecimal number to buffer
159
   void putHex(uint64_t x, int ox = 1);          // Write hexadecimal number to buffer
160
   void putFloat16(uint16_t x);                  // Write half precision floating point number to buffer
161
   void putFloat(float x);                       // Write floating point number to buffer
162
   void putFloat(double x);                      // Write floating point number to buffer
163
   uint32_t getColumn() {return column;}         // Get column number
164
protected:
165
   uint32_t column;                              // Current column
166
};
167
 
168
 
169
// Class CDynamicArray<> is used for a variable-size array with elements of the same type
170
// Note: This will not work correctly if the contained type has non-default constructors or destructors.
171
// Sorting and searching is supported if operator < is defined for the contained type.
172
template <class TX>
173
class CDynamicArray : public CMemoryBuffer {
174
public:
175
    // Allocate space for n of entries. Elements will be zero only if the array was empty before
176
    void setNum(uint32_t n) {
177
        setSize(n * (uint32_t)sizeof(TX));
178
        num_entries = n; data_size = n * (uint32_t)sizeof(TX);}
179
 
180
    // Add object to buffer. Return index
181
    uint32_t push(TX const& obj) {
182
        CMemoryBuffer::push(&obj, (uint32_t)sizeof(TX));
183
        return num_entries - 1;
184
    }
185
 
186
    // Add multiple objects. Return total number
187
    uint32_t pushBig(TX const * obj, uint32_t sizeInBytes) {
188
        CMemoryBuffer::push(obj, sizeInBytes);
189
        num_entries += sizeInBytes / sizeof(TX) - 1;
190
        return num_entries;
191
    }
192
 
193
    // Read or write existing elements. Cannot be used for adding new elements
194
    TX & operator [] (uint32_t i) {
195
        uint64_t ii = (uint64_t)i * sizeof(TX);
196
        if (ii >= dataSize()) {
197
            err.submit(ERR_CONTAINER_INDEX); ii = 0;
198
        }
199
        return get<TX>((uint32_t)ii);}
200
 
201
    // Remove latest added object when buffer is used as stack
202
    TX pop() {
203
        TX temp;
204
        if (num_entries == 0) {  // stack is empty. return zero object
205
            zeroAllMembers(temp);
206
        }
207
        else {
208
            temp = (*this)[num_entries-1];
209
            data_size -= sizeof(TX);
210
            num_entries--;
211
        }
212
        return temp;
213
    }
214
 
215
    // Sort list in ascending order. Operator < must be defined for record type TX
216
    void sort() {
217
        // Bubble sort:
218
        TX temp, *p1, *p2;
219
        int32_t j, n;
220
        bool swapped;
221
        n = num_entries - 1;
222
        do {
223
            swapped = false;
224
            for (j = 0; j < n; j++) {
225
                p1 = (TX*)(buf() + j * sizeof(TX));
226
                p2 = (TX*)(buf() + j * sizeof(TX) + sizeof(TX));
227
                if (*p2 < *p1) {                           // Swap adjacent records
228
                    temp = *p1;  *p1 = *p2;  *p2 = temp;  swapped = true;
229
                }
230
            }
231
            n--;
232
        } while (swapped);                                 // Early out if already mostly sorted
233
    }
234
 
235
    int32_t findFirst(TX const & x) {
236
        // Finds matching record and returns index to the first matching record
237
        // Important: The list must be sorted first
238
        // Returns a negative value if not found
239
        uint32_t a = 0;                                    // Start of search interval
240
        uint32_t b = num_entries;                          // End of search interval + 1
241
        uint32_t c = 0;                                    // Middle of search interval                                                     
242
        if (num_entries > 0x7FFFFFFF) {err.submit(ERR_CONTAINER_OVERFLOW); return 0x80000000;} // Size overflow
243
 
244
        while (a < b) {                                    // Binary search loop:
245
            c = (a + b) / 2;
246
            if ((*this)[c] < x) {
247
                a = c + 1;
248
            }
249
            else {
250
                b = c;
251
            }
252
        }
253
        if (a == num_entries || x < (*this)[a]) a |= 0x80000000; // Not found
254
        return (int32_t)a;
255
    }
256
 
257
    int32_t findUnsorted(TX const & x) {
258
        // Finds matching record and returns index to the first matching record
259
        // Use this if the list is not sorted, or sort the list first and use findFirst
260
        // Returns a negative value if not found
261
        uint32_t a = 0;
262
        for (a = 0; a < num_entries; a++) {
263
            if ((*this)[a] == x) return a;
264
        }
265
        return -1;
266
    }
267
 
268
    uint32_t findAll(uint32_t * firstIndex, TX const & x) {
269
        // Returns the number of records that are equal to x.
270
        // X is regarded as equal to y if !(x < y) && !(y < x)
271
        // Important: The list must be sorted first.
272
        // firstIndex (if not null) gets the index to the first matching record
273
        int32_t index = findFirst(x);                      // finds first matching record
274
        if (index < 0) return 0;                           // None found
275
        if (firstIndex) *firstIndex = (uint32_t)index;     // Save index to first matching record
276
        uint32_t n = 1;                                    // Count matching records
277
        for (uint32_t i = index+1; i < num_entries; i++) {
278
            if (x < (*this)[i]) break;
279
            n++;
280
        }
281
        return n;
282
    }
283
 
284
    uint32_t addUnique(TX const& x) {
285
        // Add object x to the list only if an object equal to x is not already in the list
286
        // Important: The list must be sorted first. The list will remain sorted after the addition of x.
287
        // The return value is the index of the inserted object or a preexisting object equal to x.
288
        // The indexes of pre-existing objects above the inserted object are incremented.
289
        int32_t index = findFirst(x);                      // Find where to insert x
290
        if (index < 0) {
291
            index &= 0x7FFFFFFF;                           // Remove "not found" bit to recover index
292
            uint32_t recordsToMove = num_entries - (uint32_t)index; // Number of records to move
293
            setNum(num_entries + 1);                        // Make space for one more record                                
294
            if (recordsToMove > 0) {                       // Move subsequent entries up one place
295
                memmove(buf() + index * sizeof(TX) + sizeof(TX),
296
                    buf() + index * sizeof(TX),
297
                    recordsToMove * sizeof(TX));
298
            }
299
            // Insert x at index position
300
            (*this)[index] = x;
301
        }
302
        return (uint32_t)index;                            // Return index to symbol
303
    }
304
};
305
 
306
 
307
// CMetaBuffer is a buffer of buffers. The size can be set only once, it cannot be resized
308
// The elements of type B may have constructors and destructors
309
template <class B>
310
class CMetaBuffer {
311
public:
312
    CMetaBuffer<B>() {                 // constructor
313
        num = 0;  p = 0;
314
    }
315
    ~CMetaBuffer<B>() {                // destructor
316
        if (p) delete[] p;             // call destructors and deallocate
317
    }
318
    void setSize(uint32_t n) {         // allocate memory for n elements
319
        if (num) {
320
            err.submit(ERR_MEMORY_ALLOCATION);  return;  // re-allocation not allowed
321
        }
322
        p = new B[n];                  // allocate, call constructors
323
        if (p) {
324
            num = n;
325
        }
326
        else {
327
            err.submit(ERR_MEMORY_ALLOCATION);
328
        }
329
    }
330
    uint32_t numEntries() const {
331
        return num;
332
    };
333
    B & operator [] (uint32_t i) {     // access element number i
334
        if (i >= num) {
335
            err.submit(ERR_CONTAINER_INDEX); i = 0; // index out of range
336
        }
337
        return p[i];
338
    }
339
protected:
340
    uint32_t num;                      // number of elements
341
    B * p;                             // pointer to array of buffers
342
};

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.