|
|
[SUB] dynamic assigments on static buffers
#478477
10/25/19 19:24
10/25/19 19:24
|
Joined: Jun 2007
Posts: 1,337
Hiporope and its pain
txesmi
OP
Serious User
|
OP
Serious User
Joined: Jun 2007
Posts: 1,337
Hiporope and its pain
|
Hi, I have been playing around finding a way to allocate an arbitrary amount of data of arbitrary data types without having to actually 'mallocate' it. It borns around the idea of using the hard disk to save and load little and self described blocks of memory so it can work like an extern database that loads and saves arbitrary data on demand without having to reinterpret its content. A system that might handle gigas of data with the premise of using it little by little. At this starting point, I thought that the use of offsets from the buffer start is a must, same as the need of mantaining the memory unfragmented. The harsh reality is that all this needed stuff generates a terrible overhead in data accesses so it is probable it serves for nothing but for my fun  By the moment I finished the memory manager and defragmenter. It uses the buffer itsef to allocate the lists needed to manage the whole stuff. It reserves some bytes in the buffer header for list descriptions and builds up some dynamic lists at the bottom of the buffer. The first list is composed as the static reference for the user and contains the references to the memory that is reallocated by the defragmentation process. Their address offsets are given as static handles to the user in the malloc process. The second list contains the freed handles so 'xB_malloc' reuses them when available. The third list, and core of the system, is a sorted list of all the memory areas asociated to the handles and their size. The defrag function runs over this list and moves up the deleted memory areas while updates the references on the static handles list. Every new malloc takes a handle from the first list and adds a new member at the bottom of this last list. xbuffer.h #ifndef _XBUFFER_H_
#define _XBUFFER_H_
// prepares a buffer so it can be used with the rest of functions
void xBufferize (BYTE *_buf, long _size);
// allocate memory of the given size
// returns a handle
long xB_malloc (BYTE *_buf, long _size);
// frees the memory asociated to a handle
void xB_free (BYTE *_buf, long _hdl);
// compacts the memory up handle by handle
// _steps defines the process iterations
// if zero or less, it defrags the whole buffer
void xB_defrag (BYTE *_buf, long _steps);
// a macro to access the memory associated to a handle
// the resulting pointer should be casted to the needed type
#define xBptr(_buf, _hdl) (((BYTE*)_buf) + *((long*)(((BYTE*)_buf) + _hdl)))
#include "xbuffer.c"
#endif xbuffer.c #define XBUFFER_HANDLE_LIST 0
#define XBUFFER_EMPTY_LIST 1
#define XBUFFER_CUT_LIST 2
#define XBUFFER_SIZE_LIST 3
#define _pcuttopsiz(_cut) (_cut + 1)
#define XBUFFER_INDEX_LIST 4
#define _pcuttopind(_cut) (_cut + 2)
#define XBUFFER_LIST_COUNT 5
long _xBListStep;
long _xBCutSize;
void xBListStep_startup () {
_xBListStep = sizeof(long) * XBUFFER_LIST_COUNT;
_xBCutSize = sizeof(long) * (XBUFFER_LIST_COUNT - XBUFFER_CUT_LIST);
}
typedef struct XB_HEADER {
long size; // size of the buffer
long memory; // offset of the highest assigned byte, the highest byte of the header block
long handle; // the lowest offset of a handle, the lowest byte of the footer block
long cut; // offset of the last assigned cut
long defrag; // offset of the last analyzed cut
long hole; // offset of the deletion tail
long deleted; // count of deleted cuts
long empty; // offset of the list of recyclable handles
} XB_HEADER;
// ----------------------------------------------------------------------------------------------------------
void xBufferize (BYTE *_buf, long _size) {
XB_HEADER *_h = _buf;
_h->size = _size;
_h->memory = sizeof(XB_HEADER);
_h->handle = _size;
_h->cut = _size + sizeof(long) * XBUFFER_CUT_LIST;
_h->defrag = _h->cut;
_h->hole = _h->cut;
_h->deleted = 0;
_h->empty = _size + sizeof(long) * XBUFFER_EMPTY_LIST;
}
// ----------------------------------------------------------------------------------------------------------
long xB_malloc (BYTE *_buf, long _size) {
XB_HEADER *_h = _buf;
long _mem = _h->memory;
long _emptyOld = _h->empty;
long _handleOld = _h->handle;
long _handle;
// check for a recyclable handle
if(_h->empty < _h->size) {
_handle = *((long*)(_buf + _h->empty));
_h->empty += _xBListStep;
} else {
_h->handle -= _xBListStep;
_handle = _h->handle;
}
// assign memory
_h->memory += _size;
if (_h->memory > _h->handle) { // buffer overflow?
_h->empty = _emptyOld;
_h->handle = _handleOld;
_h->memory -= _size;
return -1;
}
// set handle content
*((long*)(_buf + _handle)) = _mem;
// add a new cut at the list end
_h->cut -= _xBListStep;
long *_cut = _buf + _h->cut;
*_cut = _mem;
*_pcuttopsiz(_cut) = _size;
*_pcuttopind(_cut) = _handle;
// zeroify
memset(_buf + _mem, 0, _size);
return _handle;
}
void xB_free (BYTE *_buf, long _hdl) {
long *_i = _buf + _hdl;
if(*_i != 0) {
*_i = 0;
((XB_HEADER*)_buf)->deleted += 1;
}
}
// ----------------------------------------------------------------------------------------------------------
void xB_defrag(BYTE *_buf, long _loops) {
XB_HEADER *_h = _buf;
if(_h->deleted == 0) { // if there are no memory holes
_h->hole = _h->defrag = _h->size + sizeof(long) * XBUFFER_CUT_LIST;
return;
}
if(_loops <= 0) { // force a full defrag?
_h->hole = _h->defrag = _h->size + sizeof(long) * XBUFFER_CUT_LIST;
_loops = 1 + (_h->defrag - _h->cut) / _xBListStep;
}
long _l = 0;
for(; _l<_loops; _l+=1) { // process loop
_h->hole -= _xBListStep;
_h->defrag -= _xBListStep;
if(_h->defrag < _h->cut) { // check list end
_h->defrag = _h->size - sizeof(long) * (XBUFFER_LIST_COUNT - XBUFFER_CUT_LIST);
if(_h->defrag < _h->cut)
break;
_h->hole = _h->defrag;
}
long *_cut = _buf + _h->defrag;
long *_index = _buf + *_pcuttopind(_cut);
if(*_index > 0) // if the handle is not deleted
continue;
long _defragN = _h->defrag - _xBListStep;
if(_defragN < _h->cut) { // is it the last cut?
long *_c = _buf + _h->hole;
for(; _c>=_cut; _c-=XBUFFER_LIST_COUNT) {
// move up the handle of the last occupied byte
_h->memory -= *_pcuttopsiz(_c);
// add to the empty list
_h->empty -= _xBListStep;
long *_s = _buf + _h->empty;
*_s = *_pcuttopind(_c);
// delete from the cut list
_h->cut += _xBListStep;
// take out of the deleted count
_h->deleted -= 1;
}
} else {
long *_cutN = _buf + _defragN;
long *_indexN = _buf + *_pcuttopind(_cutN);
if(*_indexN == 0) { // if next cut is also empty
_h->hole += _xBListStep;
} else {
// move memory
long *_cutH = _buf + _h->hole;
long _sizN = *_pcuttopsiz(_cutN);
long _offset = _sizN - *_pcuttopsiz(_cutH);
memcpy(_buf + *_cutH, _buf + *_cutN, _sizN);
// set new addresses
long _cutNold = *_cutN;
*_indexN = *_cutN = *_cutH;
*_cutH = _cutNold;
long *_c = _cutH;
for(; _c>_cutN; _c-=XBUFFER_LIST_COUNT)
*_c += _offset;
// flip cuts
long _old[3];
memcpy(_old, _cutH, _xBCutSize);
memcpy(_cutH, _cutN, _xBCutSize);
memcpy(_cutN, _old, _xBCutSize);
}
}
}
}Salud!
|
|
|
|
