Subversion Repositories forwardcom

/****************************  containers.h   ********************************
* Author:        Agner Fog
* Date created:  2006-07-15
* Last modified: 2018-02-28
* Version:       1.10
* Project:       Binary tools for ForwardCom instruction set
* Module:        containers.h
* Description:
* Header file for container classes and dynamic memory allocation
*
* Copyright 2006-2020 GNU General Public License http://www.gnu.org/licenses
*****************************************************************************/
 
/*****************************************************************************
This header file declares various container classes for dynamic allocation
of memory for files and other types of data with unpredictable sizes.
These classes have private access to the memory buffer in order to prevent 
memory leaks. It is important to use these classes for all dynamic memory
allocation.
 
The class CMemoryBuffer and its descendants are used for many purposes of
storage of data with a size that is not known in advance. CMemoryBuffer
allows the size of its data to grow when new data are appended with the
Push() member function.
 
Several classes are derived from CMemoryBuffer:
 
The template class CDynamicArray<> is used as a dynamic array where all
elements have the same type. It cannot be used for types that have non-
default constructors or destructors.
 
The class CFileBuffer is used for reading, writing and storing files.
 
Other classes can be derived from these to add more properties or functionality.
 
It is possible to transfer a data buffer from one of these buffers to another,
using the operator
 
       A >> B
 
where A and B are both objects of classes that descend from CMemoryBuffer or
CFileBuffer. This operator transfers ownership of the allocated data buffer
from A to B, so that A is empty after the tranfer. This makes sure that a 
memory buffer is always owned by one, and only one, object. Any data owned
by B before the transfer is deallocated. 
The opposite operator B << A does the same thing.
 
The >> operator can be used when we want to do something to a data buffer
that requires a specialized class. The data buffer can be transferred from 
the object that owns it to an object of the specialized class and 
transferred back again to the original owner when the object of the 
specialized class has done its job. The >> operator transfers the data and 
properties of CMemoryBuffer or CFileBuffer, but not the additional properties
of other classes derived from these.
 
You may say that these classes have a chameleonic nature:
You can change the nature of a piece of data owned by an object by 
transferring it to an object of a different class. This couldn't be done
by traditional polymorphism because it is not possible to change the class
of an object after it is created.
 
The container class CMemoryBuffer is useful for storing data of mixed types.
Data of arbitrary type can be accessed by Get<type>(offset) or by
Buf() + offset.
 
The container class template CDynamicArray is useful for storing data of
the same type.
 
Warning: 
It is not safe to make pointers or references to data inside one of these 
container classes because the internal buffer may be re-allocated when the 
size grows. Such pointers will work only as long as the size of the container
is unchanged. It is safer to address data inside the buffer by their index
or offset relative to the buffer.
 
*****************************************************************************/
 
#pragma once
 
class CMemoryBuffer;                             // Declared below
class CFileBuffer;                               // Declared below
 
void operator >> (CMemoryBuffer & a, CMemoryBuffer & b); // Transfer ownership of buffer and other properties
void operator >> (CFileBuffer & a, CFileBuffer & b);     // Transfer ownership of buffer and other properties
 
// Class CMemoryBuffer makes a container for arbitrary data, which can grow as new data are added.
class CMemoryBuffer {
public:
   CMemoryBuffer();                              // Constructor
   ~CMemoryBuffer();                             // Destructor
   void setSize(uint32_t size);                  // Allocate buffer of specified size
   void setDataSize(uint32_t size);              // Set data size and fill any new data with zeroes
   void clear();                                 // De-allocate buffer
   void zero();                                  // Set all contents to zero without changing data size
   uint32_t dataSize() const {return data_size;};// Get file data size
   uint32_t bufferSize() const {return buffer_size;};// Get buffer size
   uint32_t numEntries() const {return num_entries;};// Get number of entries
   uint32_t push(void const* obj, uint32_t size);// Add object to buffer, return offset
   uint32_t pushString(char const * s);          // Add ASCIIZ string to buffer, return offset
   uint32_t getLastIndex() const;                // Index of last object pushed (zero-based)
   void align(uint32_t a);                       // Align next entry to address divisible by a. must be a power of 2
   int8_t * buf() {return buffer;};              // Access to buffer
   int8_t const * buf() const {return buffer;};  // Access to buffer, const
   template <class TX> TX & get(uint32_t offset) { // Get object of arbitrary type from buffer
      if (offset >= data_size) {
          err.submit(ERR_CONTAINER_INDEX); offset = 0;} // Offset out of range
      return *(TX*)(buffer + offset);}
   char * getString(uint32_t offset) {           // Get string from offset returned from pushString
       return (char *)(buffer + offset);
   }
   void copy(CMemoryBuffer const & b);           // Make a copy of whole buffer
private:
   CMemoryBuffer(CMemoryBuffer&);                // Make private copy constructor to prevent simple copying
   CMemoryBuffer & operator = (CMemoryBuffer const&);// Make assignment operator to prevent simple copying
   int8_t * buffer;                              // Buffer containing binary data. To be modified only by SetSize and operator >>
   uint32_t buffer_size;                         // Size of allocated buffer ( > DataSize)
protected:
   uint32_t num_entries;                         // Number of objects pushed
   uint32_t data_size;                           // Size of data, offset to vacant space
   friend void operator >> (CMemoryBuffer & a, CMemoryBuffer & b); // Transfer ownership of buffer
   friend void operator >> (CFileBuffer & a, CFileBuffer & b);     // Transfer ownership of buffer
};
 
inline void operator << (CMemoryBuffer & b, CMemoryBuffer & a) {a >> b;} // Same as operator << above
inline void operator << (CFileBuffer & b, CFileBuffer & a) {a >> b;} // Same as operator << above
 
// Class CFileBuffer is used for storage of input and output files
class CFileBuffer : public CMemoryBuffer {
public:
   CFileBuffer();                                // Default constructor
   //CFileBuffer(uint32_t filename);               // Constructor
   void read(const char * filename, int ignoreError = 0);               // Read file into buffer
   void write(const char * filename);                                 // Write buffer to file
   int  getFileType();                           // Get file format type
   void setFileType(int type);                   // Set file format type
   void reset();                                 // Set all members to zero
   static char const * getFileFormatName(int fileType); // Get name of file format type
   int wordSize;                                 // Segment word size (16, 32, 64)
   int fileType;                                 // Object file type
   int executable;                               // File is executable
   int machineType;                              // Machine type, x86 or ForwarCom
};
 
 
// Class CTextFileBuffer is used for building text files
class CTextFileBuffer : public CFileBuffer {
public:
   CTextFileBuffer();                            // Constructor
   uint32_t put(const char * text);              // Write text string to buffer without terminating zero
   void put(const char character);               // Write single character to buffer
   uint32_t putStringN(const char * s, uint32_t len);// Write string to buffer, add terminating zero
   void newLine();                               // Add linefeed
   void tabulate(uint32_t i);                    // Insert spaces until column i
   int  lineType;                                // 0 = DOS/Windows linefeeds, 1 = UNIX linefeeds
   void putDecimal(int32_t x, int IsSigned = 0); // Write decimal number to buffer
   void putHex(uint8_t  x, int ox = 1);          // Write hexadecimal number to buffer
   void putHex(uint16_t x, int ox = 1);          // Write hexadecimal number to buffer
   void putHex(uint32_t x, int ox = 1);          // Write hexadecimal number to buffer
   void putHex(uint64_t x, int ox = 1);          // Write hexadecimal number to buffer
   void putFloat16(uint16_t x);                  // Write half precision floating point number to buffer
   void putFloat(float x);                       // Write floating point number to buffer
   void putFloat(double x);                      // Write floating point number to buffer
   uint32_t getColumn() {return column;}         // Get column number
protected:
   uint32_t column;                              // Current column
};
 
 
// Class CDynamicArray<> is used for a variable-size array with elements of the same type
// Note: This will not work correctly if the contained type has non-default constructors or destructors.
// Sorting and searching is supported if operator < is defined for the contained type.
template <class TX>
class CDynamicArray : public CMemoryBuffer {
public:
    // Allocate space for n of entries. Elements will be zero only if the array was empty before
    void setNum(uint32_t n) {
        setSize(n * (uint32_t)sizeof(TX));
        num_entries = n; data_size = n * (uint32_t)sizeof(TX);}
 
    // Add object to buffer. Return index
    uint32_t push(TX const& obj) {
        CMemoryBuffer::push(&obj, (uint32_t)sizeof(TX));
        return num_entries - 1;
    }
 
    // Add multiple objects. Return total number
    uint32_t pushBig(TX const * obj, uint32_t sizeInBytes) {
        CMemoryBuffer::push(obj, sizeInBytes);
        num_entries += sizeInBytes / sizeof(TX) - 1;
        return num_entries;
    }
 
    // Read or write existing elements. Cannot be used for adding new elements
    TX & operator [] (uint32_t i) {
        uint64_t ii = (uint64_t)i * sizeof(TX);
        if (ii >= dataSize()) {
            err.submit(ERR_CONTAINER_INDEX); ii = 0;
        }
        return get<TX>((uint32_t)ii);}
 
    // Remove latest added object when buffer is used as stack
    TX pop() {
        TX temp;
        if (num_entries == 0) {  // stack is empty. return zero object
            zeroAllMembers(temp);
        }
        else {
            temp = (*this)[num_entries-1];
            data_size -= sizeof(TX);
            num_entries--;
        }
        return temp;
    }
 
    // Sort list in ascending order. Operator < must be defined for record type TX
    void sort() {
        // Bubble sort:
        TX temp, *p1, *p2;
        int32_t j, n;
        bool swapped;
        n = num_entries - 1;
        do {
            swapped = false;
            for (j = 0; j < n; j++) {
                p1 = (TX*)(buf() + j * sizeof(TX));
                p2 = (TX*)(buf() + j * sizeof(TX) + sizeof(TX));
                if (*p2 < *p1) {                           // Swap adjacent records
                    temp = *p1;  *p1 = *p2;  *p2 = temp;  swapped = true;
                }
            }
            n--;
        } while (swapped);                                 // Early out if already mostly sorted
    }
 
    int32_t findFirst(TX const & x) {            
        // Finds matching record and returns index to the first matching record
        // Important: The list must be sorted first
        // Returns a negative value if not found
        uint32_t a = 0;                                    // Start of search interval
        uint32_t b = num_entries;                          // End of search interval + 1
        uint32_t c = 0;                                    // Middle of search interval                                                     
        if (num_entries > 0x7FFFFFFF) {err.submit(ERR_CONTAINER_OVERFLOW); return 0x80000000;} // Size overflow
 
        while (a < b) {                                    // Binary search loop:
            c = (a + b) / 2;
            if ((*this)[c] < x) {
                a = c + 1;
            }
            else {
                b = c;
            }
        }
        if (a == num_entries || x < (*this)[a]) a |= 0x80000000; // Not found
        return (int32_t)a;
    }
 
    int32_t findUnsorted(TX const & x) {            
        // Finds matching record and returns index to the first matching record
        // Use this if the list is not sorted, or sort the list first and use findFirst
        // Returns a negative value if not found
        uint32_t a = 0;
        for (a = 0; a < num_entries; a++) {
            if ((*this)[a] == x) return a;
        }
        return -1;
    } 
 
    uint32_t findAll(uint32_t * firstIndex, TX const & x) {
        // Returns the number of records that are equal to x.
        // X is regarded as equal to y if !(x < y) && !(y < x)
        // Important: The list must be sorted first.
        // firstIndex (if not null) gets the index to the first matching record
        int32_t index = findFirst(x);                      // finds first matching record
        if (index < 0) return 0;                           // None found
        if (firstIndex) *firstIndex = (uint32_t)index;     // Save index to first matching record
        uint32_t n = 1;                                    // Count matching records
        for (uint32_t i = index+1; i < num_entries; i++) {
            if (x < (*this)[i]) break;
            n++;
        }
        return n;
    }
 
    uint32_t addUnique(TX const& x) {
        // Add object x to the list only if an object equal to x is not already in the list
        // Important: The list must be sorted first. The list will remain sorted after the addition of x.
        // The return value is the index of the inserted object or a preexisting object equal to x.
        // The indexes of pre-existing objects above the inserted object are incremented.
        int32_t index = findFirst(x);                      // Find where to insert x
        if (index < 0) {
            index &= 0x7FFFFFFF;                           // Remove "not found" bit to recover index
            uint32_t recordsToMove = num_entries - (uint32_t)index; // Number of records to move
            setNum(num_entries + 1);                        // Make space for one more record                                
            if (recordsToMove > 0) {                       // Move subsequent entries up one place
                memmove(buf() + index * sizeof(TX) + sizeof(TX),
                    buf() + index * sizeof(TX),
                    recordsToMove * sizeof(TX));
            }
            // Insert x at index position
            (*this)[index] = x;
        }
        return (uint32_t)index;                            // Return index to symbol
    }
};
 
 
// CMetaBuffer is a buffer of buffers. The size can be set only once, it cannot be resized
// The elements of type B may have constructors and destructors
template <class B>
class CMetaBuffer {
public:
    CMetaBuffer<B>() {                 // constructor
        num = 0;  p = 0;
    }
    ~CMetaBuffer<B>() {                // destructor
        if (p) delete[] p;             // call destructors and deallocate
    }
    void setSize(uint32_t n) {         // allocate memory for n elements
        if (num) {
            err.submit(ERR_MEMORY_ALLOCATION);  return;  // re-allocation not allowed
        }
        p = new B[n];                  // allocate, call constructors
        if (p) {
            num = n;
        }
        else {
            err.submit(ERR_MEMORY_ALLOCATION);
        }
    }
    uint32_t numEntries() const {
        return num;
    };
    B & operator [] (uint32_t i) {     // access element number i
        if (i >= num) {        
            err.submit(ERR_CONTAINER_INDEX); i = 0; // index out of range
        }
        return p[i];
    }
protected:
    uint32_t num;                      // number of elements
    B * p;                             // pointer to array of buffers
};