Gamestudio Links
Zorro Links
Newest Posts
Bmap creation - wrong Alpha values
by txesmi. 12/11/19 12:43
A9
by preacherX. 12/11/19 11:01
Error Message 010: invalid stops
by Volker. 12/11/19 08:25
AssetFix & Assets.csv
by MatPed. 12/11/19 07:03
How to handle profit in a TMF during training
by StefanCGN. 12/09/19 20:09
Simulate complex commission costs [Test]
by AndrewAMD. 12/09/19 13:52
AUM Magazine
Latest Screens
The Space Between
Pogostuck: Rage With Your Friends
Worst Case Z
AckCon'18 - Lotter vs the World 2 - Preview Release
Who's Online Now
6 registered members (Iglarion, timW, MatPed, Quad, 2 invisible), 659 guests, and 7 spiders.
Key: Admin, Global Mod, Mod
Newest Members
PabloMF, deepscreener, wzschultz, Alit, cmor
18341 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
[SUB] dynamic assigments on static buffers #478477
10/25/19 19:24
10/25/19 19:24
Joined: Jun 2007
Posts: 1,274
Hiporope and its pain
txesmi Offline OP
Serious User
txesmi  Offline OP
Serious User

Joined: Jun 2007
Posts: 1,274
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 grin

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
Code
#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
Code
#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!

Re: [SUB] dynamic assigments on static buffers [Re: txesmi] #478478
10/26/19 06:46
10/26/19 06:46
Joined: May 2005
Posts: 713
Chicago, IL
Dooley Offline
User
Dooley  Offline
User

Joined: May 2005
Posts: 713
Chicago, IL
I have very little knowledge of memory allocation and how it works. But I do use the file_open_write / file_open_read commands to store information outside of the game itself quite often. I guess this may require "reinterpreting" but I am interested in what you are trying to do. What would you see as the advantage of doing it this way?

Re: [SUB] dynamic assigments on static buffers [Re: txesmi] #478479
10/26/19 11:43
10/26/19 11:43
Joined: Jun 2007
Posts: 1,274
Hiporope and its pain
txesmi Offline OP
Serious User
txesmi  Offline OP
Serious User

Joined: Jun 2007
Posts: 1,274
Hiporope and its pain
There is not really an advantaje, I just have got the craving of building something dynamic from static memory. I have insisted on building a 2d editor with no dynamic allocations and I am in the way.

Re: [SUB] dynamic assigments on static buffers [Re: txesmi] #478481
10/26/19 17:04
10/26/19 17:04
Joined: May 2005
Posts: 713
Chicago, IL
Dooley Offline
User
Dooley  Offline
User

Joined: May 2005
Posts: 713
Chicago, IL
Good luck! laugh

Re: [SUB] dynamic assigments on static buffers [Re: txesmi] #478482
10/26/19 17:05
10/26/19 17:05
Joined: May 2005
Posts: 713
Chicago, IL
Dooley Offline
User
Dooley  Offline
User

Joined: May 2005
Posts: 713
Chicago, IL
Honestly, I think that's great. You never know what you will discover while doing something like this. You may revolutionize programming.

Re: [SUB] dynamic assigments on static buffers [Re: txesmi] #478484
10/26/19 18:50
10/26/19 18:50
Joined: Jun 2007
Posts: 1,274
Hiporope and its pain
txesmi Offline OP
Serious User
txesmi  Offline OP
Serious User

Joined: Jun 2007
Posts: 1,274
Hiporope and its pain
Thank you grin I doubt about that but I probably learn something new


Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1