1 /**************************** containers.h ******************************** 2 * Author: Agner Fog 3 * Date created: 2006-07-15 4 * Last modified: 2007-02-01 5 * Project: objconv 6 * Module: containers.h 7 * Description: 8 * Header file for container classes and dynamic memory allocation 9 * 10 * Copyright 2006-2008 GNU General Public License http://www.gnu.org/licenses 11 *****************************************************************************/ 12 13 /***************************************************************************** 14 This header file declares various container classes for dynamic allocation 15 of memory for files and other types of data with unpredictable sizes. 16 These classes have private access to the memory buffer in order to prevent 17 memory leaks. It is important to use these classes for all dynamic memory 18 allocation. 19 20 The class CMemoryBuffer and its descendants are used for many purposes of 21 storage of data with a size that is not known in advance. CMemoryBuffer 22 allows the size of its data to grow when new data are appended with the 23 Push() member function. 24 25 The class CFileBuffer, which is derived from CMemoryBuffer, is used for 26 reading, writing and storing object files and other files. 27 28 There are many different classes for different things you can do with 29 an object file. These classes, declared in converters.h, are all 30 descendants of CFileBuffer. It is possible to transfer a data buffer 31 from one object to another by the operator 32 33 A >> B 34 35 where A and B are both objects of classes that descend from CFileBuffer. 36 The file buffer that was owned by A is transferred to B and A is left empty 37 after the A >> B operation. This makes sure that a memory buffer is always 38 owned by one, and only one, object. The opposite operator B << A does the 39 same thing. 40 41 The >> operator is used whenever we want to do something to a file buffer 42 that requires a specialized class. The file buffer is transferred from the 43 object that owns it to an object of the specialized class and transferred 44 back again to the original owner when the object of the specialized class 45 has done its job. 46 47 You may say that the descendants of CFileBuffer have a chameleonic nature: 48 You can change the nature of a piece of data owned by an object by 49 transferring it to an object of a different class. This couldn't be done 50 by traditional polymorphism because it is not possible to change the class 51 of an object after it is created, and there are too many different things 52 you can do with object files for a single class to handle them all. 53 54 The container class CMemoryBuffer is useful for storing data of mixed types. 55 Data of arbitrary type can be accessed by Get<type>(offset) or by 56 Buf() + offset. 57 58 If all items in a dynamic array are of the same type then it is easier to 59 use one of the template classes CArrayBuf<> or CSList<>. These can be 60 used in the same way as normal arrays with the operator []. 61 CArrayBuf<> and CSList<> both have a member function SetNum() to allocate 62 the size. The size of CArrayBuf<> can be set only once, while the size of 63 CSList<> can be changed at any time. CSList<> also has a member function 64 Push() that adds records sequentially. CSList can be sorted if operators 65 < and == are defined for the record type. 66 67 Warning: 68 It is necessary to use CArrayBuf<> rather than CSList<> if the record type 69 has a constructor or destructor. 70 71 Warning: 72 It is not safe to make pointers to data inside a dynamic array of type 73 CMemoryBuffer or CSList<> because the buffer may be re-allocated when the 74 size grows. Such pointers will only work if we are finished with all push 75 operations. It is safer to address data inside the buffer by their index 76 or offset relative to the buffer. 77 78 *****************************************************************************/ 79 80 #ifndef CONTAINERS_H 81 #define CONTAINERS_H 82 83 extern CErrorReporter err; // Defined in error.cpp 84 85 class CFileBuffer; // Declared below 86 87 void operator >> (CFileBuffer & a, CFileBuffer & b); // Transfer ownership of buffer and other properties 88 89 // Class CMemoryBuffer makes a dynamic array which can grow as new data are 90 // added. Used for storage of files, file sections, tables, etc. 91 class CMemoryBuffer { 92 public: 93 CMemoryBuffer(); // Constructor 94 ~CMemoryBuffer(); // Destructor 95 void SetSize(uint32_t size); // Allocate buffer of specified size GetDataSize()96 uint32_t GetDataSize() {return DataSize;}; // File data size GetBufferSize()97 uint32_t GetBufferSize(){return BufferSize;}; // Buffer size GetNumEntries()98 uint32_t GetNumEntries(){return NumEntries;}; // Get number of entries 99 uint32_t Push(void const * obj, uint32_t size); // Add object to buffer, return offset 100 uint32_t PushString(char const * s); // Add ASCIIZ string to buffer, return offset 101 uint32_t GetLastIndex(); // Index of last object pushed (zero-based) 102 void Align(uint32_t a); // Align next entry to address divisible by a Buf()103 int8_t * Buf() {return buffer;}; // Access to buffer Get(uint32_t Offset)104 template <class TX> TX & Get(uint32_t Offset) { // Get object of arbitrary type from buffer 105 if (Offset >= DataSize) {err.submit(2016); Offset = 0;} // Offset out of range 106 return *(TX*)(buffer + Offset);} 107 private: 108 CMemoryBuffer(CMemoryBuffer&); // Make private copy constructor to prevent copying 109 int8_t * buffer; // Buffer containing binary data. To be modified only by SetSize and operator >> 110 uint32_t BufferSize; // Size of allocated buffer ( > DataSize) 111 protected: 112 uint32_t NumEntries; // Number of objects pushed 113 uint32_t DataSize; // Size of data, offset to vacant space 114 friend void operator >> (CFileBuffer & a, CFileBuffer & b); // Transfer ownership of buffer and other properties 115 }; 116 117 static inline void operator << (CFileBuffer & b, CFileBuffer & a) {a >> b;} // Same as operator << above 118 119 120 // Class CFileBuffer is used for storage of input and output files 121 class CFileBuffer : public CMemoryBuffer { 122 public: 123 CFileBuffer(); // Default constructor 124 CFileBuffer(char const * filename); // Constructor 125 void Read(int IgnoreError = 0); // Read file into buffer 126 void Write(); // Write buffer to file 127 int GetFileType(); // Get file format type 128 void SetFileType(int type); // Set file format type 129 void Reset(); // Set all members to zero 130 static char const * GetFileFormatName(int FileType); // Get name of file format type 131 char const * FileName; // Name of input file 132 char const * OutputFileName; // Output file name 133 int WordSize; // Segment word size (16, 32, 64) 134 int FileType; // Object file type 135 int Executable; // File is executable 136 char * SetFileNameExtension(const char * f); // Set file name extension according to FileType 137 protected: 138 void GetOMFWordSize(); // Determine word size for OMF file 139 void CheckOutputFileName(); // Make output file name or check that requested name is valid 140 }; 141 142 143 // Class CTextFileBuffer is used for building text files 144 class CTextFileBuffer : public CFileBuffer { 145 public: 146 CTextFileBuffer(); // Constructor 147 void Put(const char * text); // Write text string to buffer 148 void Put(const char character); // Write single character to buffer 149 void NewLine(); // Add linefeed 150 void Tabulate(uint32_t i); // Insert spaces until column i 151 int LineType; // 0 = DOS/Windows linefeeds, 1 = UNIX linefeeds 152 void PutDecimal(int32_t x, int IsSigned = 0); // Write decimal number to buffer 153 void PutHex(uint8_t x, int MasmForm = 0); // Write hexadecimal number to buffer 154 void PutHex(uint16_t x, int MasmForm = 0); // Write hexadecimal number to buffer 155 void PutHex(uint32_t x, int MasmForm = 0); // Write hexadecimal number to buffer 156 void PutHex(uint64_t x, int MasmForm = 0); // Write hexadecimal number to buffer 157 void PutFloat(float x); // Write floating point number to buffer 158 void PutFloat(double x); // Write floating point number to buffer GetColumn()159 uint32_t GetColumn() {return column;} // Get column number 160 protected: 161 uint32_t column; // Current column 162 private: PushString(char const * s)163 uint32_t PushString(char const * s){return 0;}; // Make PushString private to prevent using it 164 }; 165 166 167 // Class CArrayBuf<RecordType> is used for dynamic arrays. 168 // The size of the array can be set only once. 169 // Use CArrayBuf rather than one of the other container classes if RecordType 170 // has a constructor or destructor. 171 template <class RecordType> 172 class CArrayBuf { 173 private: 174 RecordType * buffer; // Dynamically allocated memory 175 uint32_t num; // Number of entries in array 176 CArrayBuf (CArrayBuf &); // Make private copy constructor to prevent copying 177 public: CArrayBuf()178 CArrayBuf() { // Default constructor 179 num = 0; 180 } ~CArrayBuf()181 ~CArrayBuf() { // Destructor 182 if (num) delete[] buffer; // Deallocate memory. Will call RecordType destructor if any 183 } SetNum(uint32_t n)184 void SetNum(uint32_t n) { // Set size of array. May be called only once! 185 if (n <= num) return; // Already allocated 186 if (num) { 187 err.submit(9004); // Cannot resize because items may have destructors 188 } 189 else { 190 buffer = new RecordType[n]; // Allocate memory. Will call RecordType constructor if any 191 if (!buffer) { 192 err.submit(9006); // Memory allocation failed 193 } 194 else { 195 num = n; // Save size 196 memset(buffer, 0, n*sizeof(RecordType));// Initialize to zero 197 } 198 } 199 } GetNumEntries()200 uint32_t GetNumEntries() { 201 return num; // Read size 202 } 203 RecordType & operator[] (uint32_t i) { // Access array element [i] 204 if (i >= num) { 205 err.submit(9003); i = 0; // Error: index out of range 206 } 207 return buffer[i]; 208 } SetZero()209 void SetZero() { // Set all items in array to 0 210 memset(buffer, 0, num*sizeof(RecordType)); // Warning: overwrites all members of RecordType with 0 211 } 212 }; 213 214 215 // Class CSList<RecordType> is used for dynamic arrays where all records 216 // have the same type RecordType. The list can be sorted if desired. 217 // 218 // An array defined as 219 // CSList<RecordType> list; 220 // can be used in several ways: 221 // 222 // 1. The size can be set with list.SetNum(n) where n is the maximum number of 223 // entries. New entries can then be added in random order with list[i] = x; 224 // where i < n. Unused entries will be zero. 225 // 2. Entries can be added sequentially with 226 // list.Push(x); 227 // The first entry will be list[0] 228 // 3. Entries added with method 1 or 2 can be sorted in ascending order by 229 // calling list.Sort(); 230 // 4. The list can be kept sorted at all times if records are added with 231 // list.PushSort(x); 232 // The list will be kept sorted in ascending order, provided that it 233 // was sorted before the call to PushSort. 234 // 5. The list can be kept sorted at all times and without duplicates if 235 // records are added with list.PushUnique(x); 236 // The list will be sorted and without duplicates after PushUnique if 237 // it was so before the call to PushUnique. 238 // 6. Entries can be read at all times as x = list[i]; 239 // An error will be submitted if i >= list.GetNumEntries() 240 // 7. A sorted list can be searched for entry x by i = list.FindFirst(x); 241 // or i = list.Exists(x); 242 // 243 // Requirements: 244 // RecordType can be a simple type, a structure or a class. 245 // If RecordType has a constructor or destructor then they will not be 246 // called properly. Use CArrayBuf instead of CSList if RecordType has 247 // a constructor or destructor. 248 // The operator < const must be defined for RecordType if any of the sorting 249 // features are used, i.e. Sort(), PushSort(), FindFirst(), Exists(). 250 // 251 // Example: 252 // struct S1 { // Define RecordType 253 // int Index; 254 // int operator < (S1 const & x) const { // Define operator < 255 // return Index < x.Index;} 256 // }; 257 // CSList<S1> list; // Make list 258 // S1 a; a.Index = 5; // Make record 259 // list.PushUnique(a); // Put record into list 260 261 template <class RecordType> 262 class CSList : private CMemoryBuffer { 263 public: Push(RecordType const & x)264 void Push(RecordType const & x) { 265 // Add member to list 266 CMemoryBuffer::Push(&x, sizeof(x)); 267 } PushZero()268 void PushZero() { 269 // Add blank entry to list 270 CMemoryBuffer::Push(0, sizeof(RecordType)); 271 } SetNum(uint32_t n)272 void SetNum(uint32_t n) { 273 // Reserve space for n entries. Fill with zeroes 274 SetSize(n * sizeof(RecordType)); 275 NumEntries = n; DataSize = n * sizeof(RecordType); 276 } GetNumEntries()277 uint32_t GetNumEntries() { 278 // Get number of entries 279 return NumEntries; 280 } 281 RecordType & operator[] (uint32_t i) { 282 // Get entries by operator [] as for an array 283 if (i >= NumEntries) { 284 err.submit(9003); i = 0;} // Error: index out of range 285 return *(RecordType*)(Buf() + i * sizeof(RecordType)); 286 } Sort()287 void Sort() { 288 // Sort list by ascending RecordType items 289 // Operator < must be defined for RecordType 290 // Simple Bubble sort: 291 int32_t i, j; 292 RecordType temp, * p1, * p2; 293 for (i = 0; i < (int32_t)NumEntries; i++) { 294 for (j = 0; j < (int32_t)NumEntries - i - 1; j++) { 295 p1 = (RecordType*)(Buf() + j * sizeof(RecordType)); 296 p2 = (RecordType*)(Buf() + (j+1) * sizeof(RecordType)); 297 if (*p2 < *p1) { 298 // Swap records 299 temp = *p1; *p1 = *p2; *p2 = temp; 300 } 301 } 302 } 303 } FindFirst(RecordType const & x)304 int32_t FindFirst(RecordType const & x) { 305 // Returns index to first record >= x. 306 // Returns 0 if x is smaller than all entries. 307 // Returns NumEntries if x is bigger than all entries. Note that this 308 // is not a valid index into the list. 309 // List must be sorted before calling FindFirst 310 uint32_t a = 0; // Start of search interval 311 uint32_t b = NumEntries; // End of search interval + 1 312 uint32_t c = 0; // Middle of search interval 313 // Binary search loop: 314 while (a < b) { 315 c = (a + b) / 2; 316 if ((*this)[c] < x) { 317 a = c + 1;} 318 else { 319 b = c;} 320 } 321 return (int32_t)a; 322 } Exists(RecordType const & x)323 int32_t Exists(RecordType const & x) { 324 // Returns the record number if a record equal to x exists in the list. 325 // Returns -1 if not. The list must be sorted before calling Exists. 326 // Two records a and b are assumed to be equal if !(a < b || b < a) 327 uint32_t i = FindFirst(x); 328 if (i == NumEntries) return -1; 329 if (x < (*this)[i]) return -1; else return i; 330 } PushSort(RecordType const & x)331 int32_t PushSort(RecordType const & x) { 332 // Add member to list and keep the list sorted. 333 // If the list is sorted before calling PushSort then it will also be 334 // sorted after the call. If x is equal to an existing entry then x 335 // will be inserted before the existing entry. 336 // Operator < must be defined for RecordType. 337 int32_t i = FindFirst(x); // Find where to insert x 338 int32_t RecordsToMove = (int32_t)NumEntries-i; // Number of records to move 339 SetNum(NumEntries + 1); // Make space for one more record 340 // Move subsequent entries up one place 341 if (RecordsToMove > 0) { 342 memmove(Buf() + i * sizeof(RecordType) + sizeof(RecordType), 343 Buf() + i * sizeof(RecordType), 344 RecordsToMove * sizeof(RecordType)); 345 } 346 // Insert x at position i 347 (*this)[i] = x; 348 return i; 349 } PushUnique(RecordType const & x)350 int32_t PushUnique(RecordType const & x) { 351 // Add member to list and keep the list sorted. Avoids duplicate entries. 352 // PushUnique will insert x in the list and keep the list sorted. 353 // If an entry equal to x already exists in the list then x is not 354 // inserted, and the return value will be the index to the existing entry. 355 // If no entry equal to x existed then x is inserted and the return 356 // value is the index to the new entry. 357 // This list must be sorted and without duplicates before calling 358 // PushUnique. 359 // Operator < must be defined for RecordType. 360 int32_t i = FindFirst(x); // Find where to insert x 361 if (i < (int32_t)NumEntries && !(x < (*this)[i])) { 362 return i; // Duplicate found. Return index 363 } 364 int32_t RecordsToMove = (int32_t)NumEntries-i; // Number of records to move 365 SetNum(NumEntries + 1); // Make space for one more record 366 // Move subsequent entries up one place 367 if (RecordsToMove > 0) { 368 memmove(Buf() + i * sizeof(RecordType) + sizeof(RecordType), 369 Buf() + i * sizeof(RecordType), 370 RecordsToMove * sizeof(RecordType)); 371 } 372 // Insert x at position i 373 (*this)[i] = x; 374 // Return index 375 return i; 376 } Remove(uint32_t index)377 void Remove(uint32_t index) { 378 // Remove record with this index 379 if (index >= NumEntries) return; // Index out of range 380 uint32_t RecordsToMove = NumEntries - index - 1; // Number of records to move 381 // Move subsequent entries down one place 382 if (RecordsToMove > 0) { 383 memmove(Buf() + index * sizeof(RecordType), 384 Buf() + index * sizeof(RecordType) + sizeof(RecordType), 385 RecordsToMove * sizeof(RecordType)); 386 } 387 // Count down number of entries 388 SetNum(NumEntries - 1); 389 } 390 }; 391 392 #endif // #ifndef CONTAINERS_H 393