From 985285dcae1390b47b35edadc64dd8d1e5c577d5 Mon Sep 17 00:00:00 2001 From: Yorhel Date: Mon, 26 Apr 2010 11:02:19 +0200 Subject: Added node splitting, used singly linked list for free nodes, finished alloc() The unused nodes list didn't have to be doubly linked, as there is no situation in which the prev link is required for performance. This lowers the minimum node size to 2 bytes, but as that may not always be a very good idea for performance, the minimum node size has been made configurable with a macro. It's also very easy to introduce bugs in this code due to all the references and multiple representations of the same data, might be an idea to add a test suite later on... --- Makefile | 2 +- compll.c | 251 +++++++++++++++++++++++++++++++++++++++++++-------------------- 2 files changed, 172 insertions(+), 81 deletions(-) diff --git a/Makefile b/Makefile index b8343d4..9218aa1 100644 --- a/Makefile +++ b/Makefile @@ -4,5 +4,5 @@ compll.o: compll.c compll.h ./compll clean: - rm -f compll.o + rm -f compll.o compll diff --git a/compll.c b/compll.c index 4ff10b8..c9f9a6b 100644 --- a/compll.c +++ b/compll.c @@ -8,16 +8,14 @@ #include -/* useful macros */ -#define min(a,b) ((a)<(b)?(a):(b)) -#define max(a,b) ((a)>(b)?(a):(b)) - -/* #define align(l) ( (l) + ((conf_alignment - ((l) % conf_alignment)) % conf_alignment)) */ -#define align(l) ( ((l) + conf_align_mask) & ~conf_align_mask ) - +/* global configuration */ +/* minimum lengh of the data part of a node, setting this too low can badly + * increase the length of the unused node list and slow down operations of + * alloc() and free(). Setting this too high would waste memory. + * Must be at least 2, in order to hold the unused nodes linked list. */ +#define MIN_NODE_SIZE 4 -/* global configuration */ unsigned int conf_alignment; /* in bit count, actual alignment bytes = 2^a */ unsigned int conf_align_mask; /* the bitmask where the bits-to-align-to are one and the rest is zero */ @@ -28,7 +26,6 @@ compll_decompress_callback conf_decompress; - /* an "archived" block, every memory block is present in an array of ablock structs. */ struct ablock { /* pointer to the compressed block, NULL if it is in an uncompressed state and has been modified. */ @@ -54,17 +51,6 @@ struct ublock { }; -/* an overlay on the header of a node, makes acessing them easier */ -struct node_head { - /* size & usage information */ - unsigned short head; - /* next and previous nodes in the free nodes list, only used when the node - * itself is unused */ - unsigned short next; - unsigned short prev; -}; - - /* a global instruction counter to indicate when a block has last been * accessed, will be incremented each time a node is accessed * Note: The code should be able to handle an overflow */ @@ -85,6 +71,21 @@ unsigned char *compress_buf = NULL; +/* useful macros */ +#define min(a,b) ((a)<(b)?(a):(b)) +#define max(a,b) ((a)>(b)?(a):(b)) + +/* #define align(l) ( (l) + ((conf_alignment - ((l) % conf_alignment)) % conf_alignment)) */ +#define align(l) ( ((l) + conf_align_mask) & ~conf_align_mask ) + +/* readable way to access an unsigned short within an (unsigned char *) */ +#define datshort(ch) (*(unsigned short *) (ch)) + +/* macros to access metadata of a node within a memory block, ch = start of node data */ +#define node_head(ch) datshort((ch) - 2) +#define node_foot(ch) datshort((ch) + ((node_head(ch) >> 1) << conf_alignment) - 2) +#define node_fnext(ch) datshort(ch) + /* update the 'lasta' field in an uncompressed block and increase the * instruction counter. */ #define ublock_access(i) (ublocks[i].lasta = ++instruction_count) @@ -186,14 +187,17 @@ static int block_alloc() { } -/* Load an archived block into an uncompressed slot, returns the ublocks index - * or -1 on error */ +/* Load an archived block into an uncompressed slot if it's not in an + * uncompressed state already, and updates the access time. returns the ublocks + * index or -1 on error */ static int block_load(int ab) { int ub; /* don't do anything if the block is already loaded */ - if(ablocks[ab].ublock) + if(ablocks[ab].ublock >= 0) { + ublock_access(ablocks[ab].ublock); return ablocks[ab].ublock; + } /* get a new slot in the ublocks */ if((ub = block_uslot()) < 0) @@ -209,6 +213,50 @@ static int block_load(int ab) { } +/* find a memory block which has a node free of at least the specified (packed) + * size, creating a new block if all others are full. The block will be + * available in ublocks. + * returns the ablocks index or -1 on error*/ +static int block_getfree(short size) { + int ab, start, length; + unsigned char *dat; + + /* find a suitable memory block, load it, and return. + * TODO: this loops through the whole ablocks array in the worst case, which + * is not really fast. Maybe we'll have to do some caching? */ + for(ab=0; ab= size) { + if(block_load(ab) == -1) + return -1; + return ab; + } + + /* none found, create a new block and initialize the block structure */ + if((ab = block_alloc()) == -1) + return -1; + dat = ublocks[ablocks[ab].ublock].data; + + /* the first two bytes contain the offset to the first unused node, this one + * can be found at offset align(2+2) - 2 bytes for this pointer and 2 for the + * metadata of the unused node */ + start = align(4); + datshort(dat) = start >> conf_alignment; + + /* metadata 2 bytes before the start of the unused node, this indicates the + * length of the node and that the previous node should be considered as "in + * use" */ + length = (conf_blocksize - start) & ~conf_align_mask; + datshort(dat+start-2) = ((length >> conf_alignment) << 1) | 1; + + /* the metadata of the last node can be found at (dat+start+length-2) and + * should be 0 (length = 0, not in use), which it already is so we don't have + * to do anything. */ + + ablocks[ab].free = length >> conf_alignment; + return ab; +} + + /* @@ -247,7 +295,7 @@ static int block_load(int ab) { * 0: [ 2 - offset of first node] * fm: [ 2 - size of the first node, previous node = used] * fd: [ns - unallocated data] - * lm: [ 2 - next node size = 0, previous node = used] + * lm: [ 2 - next node size = 0, previous node = unused] * * fm = metadata of first node = fd - 2 * fd = offset of first node = align(4) @@ -260,48 +308,58 @@ static int block_load(int ab) { * blocksize - 16 - 16 - 2 = blocksize - 34 */ +/* Splitting an unused node in two smaller nodes: + * example has 4 bytes alignment + * + * 2: [ 2 st=36 ] -> unused node + * 4: [34 datat ] + * 38: [ 2 metanext] -> the next node + * 40: [.. datanext] + * + * v + * + * 2: [ 2 s1=16 ] -> node is now in use + * 4: [14 data1 ] + * 18: [ 2 s2=20 ] -> s2 = st - s1 (always properly aligned) + * 20: [18 data2 ] + * 38: [ 2 metanext] -> next node, unmodified + * 40: [.. datanext] + * + * A node can be split as long as s2 >= MIN_NODE_SIZE + */ -/* find a memory block which has a node free of at least the specified (packed) - * size, creating a new block if all others are full. The block will be - * available in ublocks. - * returns the ablocks index or -1 on error*/ -static int block_getfree(short size) { - int ab, start, length; - unsigned char *dat; - /* find a suitable memory block, load it, and return. - * TODO: this loops through the whole ablocks array in the worst case, which - * is not really fast. Maybe we'll have to do some caching? */ - for(ab=0; ab= size) { - if(block_load(ab) == -1) - return -1; - return ab; +/* Add the specified node at the correct position in the unused nodes list and + * update ablock.free if necessary */ +static void node_addfree(int ab, unsigned short off) { + unsigned char *dat = ublocks[ablocks[ab].ublock].data; + unsigned short psize = node_head(dat+off); + int cur; + + /* find the node within the free nodes list after which this node should be + * inserted. (that is, of which the next node is larger than or equal to this + * one) */ + cur = datshort(dat) << conf_alignment; + if(cur) { + while(1) { + if(!node_fnext(dat+cur) || node_head(dat + (node_fnext(dat+cur) << conf_alignment)) >= psize) + break; + cur = node_fnext(dat+cur) << conf_alignment; } + } - /* none found, create a new block and initialize the block structure */ - if((ab = block_alloc()) == -1) - return -1; - dat = ublocks[ablocks[ab].ublock].data; - - /* the first two bytes contain the offset to the first unused node, this one - * can be found at offset align(2+2) - 2 bytes for this pointer and 2 for the - * metadata of the unused node */ - start = align(4); - *((unsigned short *) dat) = start >> conf_alignment; - - /* metadata 2 bytes before the start of the unused node, this indicates the - * length of the node and that the previous node should be considered as "in - * use" */ - length = (conf_blocksize - start) & ~conf_align_mask; - *((unsigned short *) (dat+start-2)) = (length >> conf_alignment) << 1; - - /* and now the metadata of the last node (size=0, inuse=1) */ - *((unsigned short *) (dat+start+length-2)) = 1; - - ablocks[ab].free = length >> conf_alignment; - return ab; + /* if this is the last node in the list (thus the largest free node in this + * block), update ablock.free */ + if(!cur || !node_fnext(dat+cur)) + ablocks[ab].free = psize >> 1; + + /* update references */ + node_fnext(dat+off) = cur ? node_fnext(dat+cur) : 0; + if(cur) + node_fnext(dat+cur) = off >> conf_alignment; + else + datshort(dat) = off >> conf_alignment; } @@ -310,19 +368,50 @@ static int block_getfree(short size) { * Returns the byte offset of the node data within the block.*/ static int node_alloc(int ab, unsigned short size) { unsigned char *dat = ublocks[ablocks[ab].ublock].data; - struct node_head *cur, *next; + int off, off2 = 0, free; unsigned short psize = size << 1; - /* find the best fitting unused node */ - cur = (struct node_head *) (dat - 2 + (*(unsigned short *)dat)); - while(cur->next) { - next = (struct node_head *) (dat - 2 + (cur->next << conf_alignment)); - if(psize > next->head) + /* find the best fitting unused node by looping through the unused nodes + * linked list, while keeping track of the previous node in the list (off2) + * in order to update it's fnext reference */ + off = datshort(dat) << conf_alignment; + assert(off > 0); + while(1) { + if(!node_fnext(dat+off) || node_head(dat+off) >= psize) break; - cur = next; + off2 = off; + off = node_fnext(dat+off) << conf_alignment; } - return -1; + /* mark this node as used and remove it from the free nodes list */ + node_foot(dat+off) |= 1; + if(off2) + node_fnext(dat + off2) = node_fnext(dat+off); + else + datshort(dat) = node_fnext(dat+off); + + /* if this was the largest free node, update ablock.free */ + if(!node_fnext(dat + off)) + ablocks[ab].free = off2 ? (node_head(dat+off2)>>1) : 0; + /* reset the next pointer to make sure the node data contains only zeros */ + else + node_fnext(dat+off) = 0; + + /* split this node into another empty node if it is large enough */ + free = ((node_head(dat+off) >> 1) - size) << conf_alignment; + if(free > MIN_NODE_SIZE) { + /* decrease size of the large node to the specified size */ + node_head(dat+off) = psize | (node_head(dat+off) & 1); + /* calculate offset of the free node */ + off2 = off + (size << conf_alignment); + /* update metadata of this and next node */ + node_head(dat+off2) = ((free >> conf_alignment) << 1) | 1; + node_foot(dat+off2) &= ~1; + /* add to the free nodes list */ + node_addfree(ab, off2); + } + + return off; } @@ -336,11 +425,11 @@ compll_t compll_alloc(unsigned int size) { if(size+34 >= conf_blocksize) return 0; - /* increase the size of the node to be large enough to hold two node pointers - * within the same block (4 bytes), the metadata of the next node and padding - * bytes to make sure it's properly aligned */ - if(size < 4) - size = 4; + /* increase the size of the node to be at least MIN_NODE_SIZE, and to hold + * the metadata of the next node and padding bytes to make sure it's properly + * aligned */ + if(size < MIN_NODE_SIZE) + size = MIN_NODE_SIZE; size = align(size + 2); spack = size >> conf_alignment; @@ -352,7 +441,7 @@ compll_t compll_alloc(unsigned int size) { off = node_alloc(ab, spack); assert(off >= 0); - return off; + return (((compll_t)ab) << 24) + off; } @@ -452,16 +541,18 @@ void dbg_decompress(const unsigned char *src, unsigned int srclen, unsigned char int main() { - int i; + int i, off; FILE *f; - printf("compll_init = %d\n", compll_init(1<<16, 1, 10, dbg_compress, dbg_decompress)); + printf("compll_init = %d\n", compll_init(1<<16, 8, 10, dbg_compress, dbg_decompress)); - i = block_getfree(10); - printf("block_getfree(10) = %d\n", i); + for(i=4; i<=16; i+=4) { + off = compll_alloc(i); + printf("block_getfree(%d) = %d (free = %d)\n", i, off, ablocks[0].free); + } f = fopen("dump", "w"); - fwrite(ublocks[ablocks[i].ublock].data, conf_blocksize, 1, f); + fwrite(ublocks[ablocks[0].ublock].data, conf_blocksize, 1, f); fclose(f); return 0; -- cgit v1.2.3