About tiny tiny C code:
If I wanted to use a set amount of memory, like
unsigned char byteMem[2048]
in which to store and manipulate a number of byte queues; my standard
C approach would be to create a set of structs the let me pool out
chunks of memory from the space for the byte queues to work in.
I am not having luck finding references on how to keep the most
possible usable space for my queues to use.
2 questions:
- What are some good books or other reading on memory efficient C
code?
- Have I missed some easy optimizations in the following code?
The QueueSlot uses 8 bits for a queue identifier and 8 bits for
storing a value. Is better memory efficiency just a matter of using
more of memory for data storage?
Feel free to chop out most of this in replies:
I wrote some some C code that is straight forward enough
--------------------------------------------------------------------------
/* compactqueues.h
*/
//A place to store the queues
typedef struct {
int dataLength;
unsigned char* data;
} Store;
// A memory layout for a queue slot
// A tag and a value
// This approach is decidely in favor of very dynamic behavior
sacrificing some
// memory space for tagging. But any queue can easily grow to any size
// permitted by the buffer limit.
typedef struct {
unsigned char slotTag : 8;
unsigned char slotValue : 8;
} QueueSlot;
//A queue in this approach needs to have
//a distinct tag value
//a headIndex for implicit queue ordering
//and access to the buffer
typedef struct {
unsigned char myTag : 4;
int headIndex;
Store *storeAccess;
} Queue;
//This is a convenience collection to pool access to the
//management bits
typedef struct {
Queue *queuePool;
unsigned char *queueMarkers;
unsigned char poolSize;
Store *storeKeeper;
} QueueKeeper;
// An initialization function
// To scrub the store buffer to 0's
void initQueuePool();
Queue * create_queue();
void destroy_queue(Queue * q);
void enqueue_byte(Queue * q, unsigned char b);
unsigned char dequeue_byte(Queue * aQueue);
-------------------------------------------------------------------------------------------
/* compactqueues.c
*/
#include "CompactQueue.h"
#include <stdio.h>
//#include <time.h>
//#define DEFAULT_STORE_SIZE 2048
//unsigned short externStoreSize = DEFAULT_STORE_SIZE;
//unsigned char TagGenerator = 0;
QueueKeeper* externQueueKeeper;
void on_out_of_memory() {
fprintf( stdout, "Out of memory! \n" );
while (1) {
//dont return? well ok then
}
}
void on_illegal_operation() {
fprintf( stdout, "Illegal operation! \n" );
while (1) {
//dont return? well ok then
}
}
void initQueuePool() {
if ( externQueueKeeper ) {
//Scrub the marker slots to 0
for ( short i=0; i< externQueueKeeper->poolSize; ++i ) {
externQueueKeeper->queueMarkers[i] = 0;
}
//Scrub the data slots to 0
if ( externQueueKeeper->storeKeeper ) {
Store* localStoreAccess = externQueueKeeper->storeKeeper;
unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
for ( int i=0;i< slotCount; ++i) {
asSlot->slotTag = 0;
asSlot->slotValue = 0;
//fprintf( stdout, "Clear QueueSlots - Slot - %i, Value - %i \n",
asSlot->slotTag, asSlot->slotValue );
++asSlot;
}
}
}
}
}
Queue* create_queue() {
if ( !externQueueKeeper )
return 0;
short indexToTake = -1;
for ( short i=0; i< externQueueKeeper->poolSize; ++i ) {
if ( externQueueKeeper->queueMarkers[i] == 0 ) {
indexToTake = i;
//fprintf(stdout, "indexToTake - %i\n", indexToTake );
break;
}
}
if ( indexToTake > -1 ) {
externQueueKeeper->queueMarkers[indexToTake] = 1;
externQueueKeeper->queuePool[indexToTake].myTag = indexToTake + 1;
externQueueKeeper->queuePool[indexToTake].headIndex = 0;
externQueueKeeper->queuePool[indexToTake].storeAccess =
externQueueKeeper->storeKeeper;
return &(externQueueKeeper->queuePool[indexToTake]);
}
return 0;
}
void destroy_queue(Queue * q) {
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess;
unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
int headOffset = q->headIndex;
int slotsFreed = 0;
for ( int i=0 ;i < slotCount; ++i) {
QueueSlot* currentSlot = (asSlot + headOffset%slotCount);
if ( currentSlot->slotTag == q->myTag ) {
currentSlot->slotTag = 0;
currentSlot->slotValue = 0;
++slotsFreed;
}
}
//fprintf( stdout, "Destroying Queue - %i. %i slots left in use are
now free.\n", q->myTag, slotsFreed );
//Reset Queue for reuse from the pool.
externQueueKeeper->queueMarkers[q->myTag] = 0;
q->headIndex = 0;
q->myTag = 0;
q->storeAccess = 0;
//now the queue for pool slot <myTag> can be found for use again
}
}
}
void enqueue_byte(Queue * q, unsigned char b) {
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess;
unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
int headOffset = q->headIndex;
int slotUsed = -1;
for ( int i=0 ;i < slotCount; ++i) {
int currentIndex = (i + headOffset%slotCount);
QueueSlot* currentSlot = (asSlot + headOffset%slotCount);
if ( currentSlot->slotTag == 0 ) {
slotUsed = currentIndex;
currentSlot->slotTag = q->myTag;// this slot know belongs to the
queue passed in
currentSlot->slotValue = b;
//fprintf( stdout, "Slot %i belongs to queue- %i, with Value - %i
\n", currentIndex, currentSlot->slotTag, currentSlot->slotValue );
break;
}
++asSlot;
}
if ( slotUsed == -1 ) {
fprintf( stdout, "No Slot open. Enqueue failed \n" );
on_out_of_memory();
}
}
}
}
unsigned char dequeue_byte(Queue * q) {
unsigned char dequeueduchar = 0;
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess;
unsigned char* store = localStoreAccess->data;
if ( store ) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
int headOffset = q->headIndex;
unsigned char seeking = 1; //first seek the bit to dequeue, then
try to update the headIndex
for ( int i=0;i< slotCount; ++i) {
int currentIndex = (i + headOffset%slotCount);
QueueSlot* currentSlot = (asSlot + headOffset%slotCount);
//find the first slot with myTag as the slotTag value
//use mod to do a complete loop around starting from the headIndex
if ( seeking ) {
if ( currentSlot->slotTag == q->myTag ) {
dequeueduchar = currentSlot->slotValue;
//free the slot for use
currentSlot->slotValue = 0;
currentSlot->slotTag = 0;
q->headIndex = 0; //this will get updated to the true next
headIndex if there really is a next one, if not then it should be 0
anyway
//fprintf( stdout, "Free slot %i from Queue- %i, returning Value
- %i \n", currentIndex, currentSlot->slotTag, dequeueduchar );
seeking = 0;
}
} else {
if ( currentSlot->slotTag == q->myTag ) {
q->headIndex = currentIndex;
//fprintf( stdout, "Updating headIndex of Queue- %i to slot - %i
\n", q->myTag, currentIndex );
return dequeueduchar;
}
}
++asSlot;
}
//if ( q->headIndex == 0 )
// fprintf( stdout, "Reseting headIndex of Queue- %i to slot 0 \n",
q->myTag );
//if nothing to dequeue for given queue
if ( seeking == 1 )
on_illegal_operation();
}
}
return dequeueduchar;
}
-------------------------------------------------------------------------------------------
/* main.c - Test it out
*/
#include <stdio.h>
#include "CompactQueue.h"
extern QueueKeeper* externQueueKeeper;
//extern unsigned short externStoreSize;
int main (int argc, const char * argv[]) {
Store aStore;
const int storeSize = 2048;
//aStore.dataLength = externStoreSize;
unsigned char storeData[storeSize];
aStore.dataLength = storeSize;
aStore.data = storeData;
const unsigned char poolSize = 64;
//setup the zooKeeper, I mean queueKeeper
QueueKeeper aQueueKeeper;
Queue aQueuePool[poolSize];
unsigned char queueMarkers[poolSize];
aQueueKeeper.queuePool = aQueuePool;
aQueueKeeper.queueMarkers = queueMarkers;
aQueueKeeper.poolSize = poolSize;
aQueueKeeper.storeKeeper = &aStore;
externQueueKeeper = &aQueueKeeper;
initQueuePool();
//Queues in action
Queue* q1 = create_queue();
Queue* q2 = create_queue();
enqueue_byte(q1, 0);
enqueue_byte(q1, 1);
enqueue_byte(q2, 3);
enqueue_byte(q1, 2);
enqueue_byte(q2, 4);
printf("%d ", dequeue_byte(q1));
printf("%d\n", dequeue_byte(q1));
enqueue_byte(q1, 5);
enqueue_byte(q2, 6);
printf("%d ", dequeue_byte(q1));
printf("%d\n", dequeue_byte(q1));
destroy_queue(q1);
printf("%d ", dequeue_byte(q2));
printf("%d ", dequeue_byte(q2));
printf("%d\n", dequeue_byte(q2));
destroy_queue(q2);
return 0;
}