--- /dev/null
+/*
+ * cacao/mm/allocator.c
+ *
+ * Copyright (c) 1998 A. Krall, R. Grafl, M. Gschwind, M. Probst, Ph. Tomsich
+ * See file COPYRIGHT for information on usage and disclaimer of warranties
+ *
+ * Authors: Philipp Tomsich EMAIL: cacao@complang.tuwien.ac.at
+ *
+ * $Id: allocator.c 34 1998-11-03 11:29:37Z phil $
+ */
+
+/*
+ NOTES:
+
+ Locality preservation has not been added... yet
+*/
+
+#include "allocator.h"
+
+static FREE_EXACT* __freelist_exact[1 << EXACT];
+static FREE_EXACT** freelist_exact = &__freelist_exact[-1];
+static FREE_LARGE* freelist_large[LARGE << SUBBIT];
+
+#if SMALL_TABLES
+static unsigned char highest[256];
+#else
+# if EXACT_TOP_BIT < 8
+# if (ADDRESS == 64)
+static unsigned char highest_0[2048];
+# else
+static unsigned char highest_0[1024];
+# endif
+
+static unsigned char* highest_8 = &highest_0[256];
+static unsigned char* highest_16 = &highest_0[512];
+static unsigned char* highest_24 = &highest_0[768];
+# if (ADDRESS == 64)
+static unsigned char* highest_32 = &highest_0[1024];
+static unsigned char* highest_40 = &highest_0[1280];
+static unsigned char* highest_48 = &highest_0[1538];
+static unsigned char* highest_56 = &highest_0[1792];
+# endif
+# else
+# if (ADDRESS == 64)
+static unsigned char highest_8[1792];
+# else
+static unsigned char highest_8[768];
+# endif
+
+static unsigned char* highest_16 = &highest_8[256];
+static unsigned char* highest_24 = &highest_8[512];
+# if (ADDRESS == 64)
+static unsigned char* highest_32 = &highest_8[768];
+static unsigned char* highest_40 = &highest_8[1280];
+static unsigned char* highest_48 = &highest_8[1538];
+static unsigned char* highest_56 = &highest_8[1792];
+# endif
+# endif
+#endif
+
+static
+unsigned char
+find_highest(SIZE bits){
+#if MSB_TO_LSB_SEARCH
+ /* optimize for large allocation sizes */
+# if SMALL_TABLES
+# if ADDRESS == 64
+ if (bits & 0xff00000000000000ULL)
+ return 56 + highest[bits >> 56 & 0xff];
+ if (bits & 0xff000000000000ULL)
+ return 48 + highest[bits >> 48 & 0xff];
+ if (bits & 0xff0000000000ULL)
+ return 40 + highest[bits >> 40 & 0xff];
+ if (bits & 0xff00000000ULL)
+ return 32 + highest[bits >> 32 & 0xff];
+# endif
+
+ if (bits & 0xff000000)
+ return 24 + highest[bits >> 24 & 0xff];
+ if (bits & 0xff0000)
+ return 16 + highest[bits >> 16 & 0xff];
+ if (bits & 0xff00)
+ return 8 + highest[bits >> 8 & 0xff];
+
+# if EXACT_TOP_BIT < 8
+ return highest[bits & 0xff];
+# endif
+# else
+# if ADDRESS == 64
+ if (bits & 0xff00000000000000ULL)
+ return highest_56[bits >> 56 & 0xff];
+ if (bits & 0xff000000000000ULL)
+ return highest_48[bits >> 48 & 0xff];
+ if (bits & 0xff0000000000ULL)
+ return highest_40[bits >> 40 & 0xff];
+ if (bits & 0xff00000000ULL)
+ return highest_32[bits >> 32 & 0xff];
+# endif
+
+ if (bits & 0xff000000)
+ return highest_24[bits >> 24 & 0xff];
+ if (bits & 0xff0000)
+ return highest_16[bits >> 16 & 0xff];
+ if (bits & 0xff00)
+ return highest_8[bits >> 8 & 0xff];
+
+# if EXACT_TOP_BIT < 8
+ return highest_0[bits & 0xff];
+# endif
+# endif
+
+#else
+ /* optimize for small allocation sizes */
+
+# if SMALL_TABLES
+# if EXACT_TOP_BIT < 8
+ if (!(bits & ~0xffULL))
+ return highest[bits & 0xff];
+# endif
+
+ if (!(bits & ~0xffffULL))
+ return 8 + highest[bits >> 8 & 0xff];
+
+ if (!(bits & ~0xffffffULL))
+ return 16 + highest[bits >> 16 & 0xff];
+
+# if ADDRESS == 32
+ return 24 + highest[bits >> 24 & 0xff];
+# else
+ if (!(bits & ~0xffffffffULL))
+ return 24 + highest[bits >> 24 & 0xff];
+
+ if (!(bits & ~0xffffffffffULL))
+ return 32 + highest[bits >> 32 & 0xff];
+
+ if (!(bits & ~0xffffffffffffULL))
+ return 40 + highest[bits >> 40 & 0xff];
+
+ if (!(bits & ~0xffffffffffffffULL))
+ return 48 + highest[bits >> 48 & 0xff];
+
+ return 56 + highest[bits >> 56 & 0xff];
+# endif
+# else
+# if EXACT_TOP_BIT < 8
+ if (!(bits & ~0xffULL))
+ return highest_0[bits & 0xff];
+# endif
+
+ if (!(bits & ~0xffffULL))
+ return highest_8[bits >> 8 & 0xff];
+
+ if (!(bits & ~0xffffffULL))
+ return highest_16[bits >> 16 & 0xff];
+
+# if ADDRESS == 32
+ return highest_24[bits >> 24 & 0xff];
+# else
+ if (!(bits & ~0xffffffffULL))
+ return highest_24[bits >> 24 & 0xff];
+
+ if (!(bits & ~0xffffffffffULL))
+ return highest_32[bits >> 32 & 0xff];
+
+ if (!(bits & ~0xffffffffffffULL))
+ return highest_40[bits >> 40 & 0xff];
+
+ if (!(bits & ~0xffffffffffffffULL))
+ return highest_48[bits >> 48 & 0xff];
+
+ return highest_56[bits >> 56 & 0xff];
+# endif
+# endif
+#endif
+
+};
+
+static
+void
+init_table()
+{
+ static unsigned char r[10] = { 1, 1, 2, 4, 8, 16, 32, 64, 128 };
+ int i, j, k, m;
+
+ i = 0;
+ j = 0;
+ k = 0;
+ m = 0;
+
+ for (k = 0; k < 10; ++k) {
+ for (m = 0; m < r[k]; ++m) {
+#if SMALL_TABLES
+ highest[i] = j - (EXACT + ALIGN) - 1;
+#else
+# if (EXACT_TOP_BIT < 8)
+ highest_0 [i] = j - 8 - (EXACT + ALIGN) - 1;
+# endif
+ highest_8 [i] = j + 8 - (EXACT + ALIGN) - 1;
+ highest_16 [i] = 8 + highest_8 [i];
+ highest_24 [i] = 16 + highest_8 [i];
+# if (ADDRESS == 64)
+ highest_32 [i] = 24 + highest_8 [i];
+ highest_40 [i] = 32 + highest_8 [i];
+ highest_48 [i] = 40 + highest_8 [i];
+ highest_56 [i] = 48 + highest_8 [i];
+# endif
+#endif
+
+ ++i;
+ }
+
+ ++j;
+ }
+}
+
+#define PRESERVE_LOCALITY 0
+
+#if FASTER_FAIL
+static SIZE allocator_largest_free = 0;
+#endif
+
+#if PRESERVE_LOCALITY
+static void* allocator_last_splitoff = 0;
+static SIZE allocator_last_splitoff_size = 0;
+#endif
+
+void
+allocator_reset()
+{
+ int i;
+
+#if FASTER_FAIL
+ allocator_largest_free = 0;
+#endif
+
+#if PRESERVE_LOCALITY
+ allocator_last_splitoff = 0;
+ allocator_last_splitoff_size = 0;
+#endif
+
+ for (i = 1; i <= (1 << EXACT); ++i)
+ freelist_exact[i] = 0;
+
+ for (i = 0; i < (LARGE << SUBBIT); ++i)
+ freelist_large[i] = 0;
+}
+
+
+#include <stdio.h>
+
+
+#if COUNT_ALLOCATIONS
+static unsigned long long allocator_allocations = 0;
+
+void
+allocator_display_count()
+{
+ fprintf(stderr, "total allocations: %d\n", allocator_allocations);
+}
+#endif
+
+
+void
+allocator_init()
+{
+ fprintf(stderr,
+ "allocator_init: $Id: allocator.c 34 1998-11-03 11:29:37Z phil $\n\n");
+
+ fprintf(stderr, "\t%d bit addresses\n", ADDRESS);
+ fprintf(stderr, "\t%d bit alignment\n", ALIGN);
+ fprintf(stderr, "\t%d exact bits\n", EXACT );
+ fprintf(stderr, "\t%d large bits\n", LARGE );
+ fprintf(stderr, "\t%d subbin bits\n", SUBBIT );
+ fprintf(stderr, "\tusing %s tables\n",
+ SMALL_TABLES ? "small (256 byte)" : "large (2048 byte)");
+ fprintf(stderr, "\tusing %s highest-bit search strategy\n",
+ MSB_TO_LSB_SEARCH ? "MSB-to-LSB" : "LSB-to-MSB");
+
+ fprintf(stderr,
+ "\tusing %d bytes for exact bins, %d bytes for sorted bins\n\n",
+ (1 << EXACT) << ALIGN,
+ (LARGE << SUBBIT) << ALIGN);
+
+ init_table(); /* set up the highest-table */
+ allocator_reset(); /* clear the freelists & internal variables */
+}
+
+int
+size_to_bin(SIZE size)
+{
+#if PRINTF
+ printf ("size: %d ", size);
+#endif
+
+#if EXACT > 0
+ if (size > ((1 << EXACT) << ALIGN)) {
+#endif
+ // unsigned char shift = shift_table_32[highbit];
+ // int bin = offset_table_32[highbit] + ( (size >> shift) & mask );
+#if SUBBIT != 0
+ unsigned char highbit = find_highest(size);
+ unsigned char shift = highbit + (EXACT + ALIGN - SUBBIT);
+ static int mask = (1 << SUBBIT) - 1;
+ int bin = (highbit << SUBBIT) + ( (size >> shift) & mask );
+
+ // printf("shift: %d, %d; %d; large bin: %d\n", shift, (size >> shift) & mask, highbit, bin);
+#else
+ int bin = find_highest(size);
+#endif
+
+#if PRINTF
+ printf("==> large bin: %d\n", bin);
+#endif
+
+ return bin;
+#if EXACT > 0
+ } else {
+#if PRINTF
+ printf("==> exact bin: %d\n", (int)((size >> ALIGN) - 1));
+#endif
+
+ return (size >> ALIGN);
+ }
+#endif
+}
+
+#include <assert.h>
+
+
+#define OLDEST_FIRST 1
+
+
+
+/* FIXME:
+ Should we enforce an additional "lowest address first" - ordering
+ for the freelist-entries ??? Right now, I'm using oldest-first for
+ the large bins and newest-first for the exact bins...
+
+ Sorting by the address may reduce heap fragmentation by reducing the
+ heap growth-rate... */
+
+void
+allocator_free(void* chunk, SIZE size)
+{
+ assert(chunk && size);
+
+#if FASTER_FAIL
+ if (size > allocator_largest_free)
+ allocator_largest_free = size;
+#endif
+
+ if (size > ((1 << EXACT) << ALIGN)) {
+ int bin = size_to_bin(size);
+ FREE_LARGE* curr = freelist_large[bin];
+
+ ((FREE_LARGE*)chunk)->size = size;
+
+ if (!freelist_large[bin] || (freelist_large[bin]->size > size)) {
+ /* prepend */
+ ((FREE_LARGE*)chunk)->next = freelist_large[bin];
+ freelist_large[bin] = (FREE_LARGE*)chunk;
+ return;
+ }
+
+ while ((curr->next) && (curr->next->size <= size)) {
+ curr = curr->next;
+ };
+
+ /* insert or append */
+ ((FREE_LARGE*)chunk)->next = curr->next;
+ curr->next=(FREE_LARGE*)chunk;
+ } else {
+ int bin = size >> ALIGN;
+
+#if OLDEST_FIRST
+ if (!freelist_exact[bin]) {
+#endif
+ /* simply prepend */
+ ((FREE_EXACT*)chunk)->next = freelist_exact[bin];
+ freelist_exact[bin] = (FREE_EXACT*)chunk;
+#if OLDEST_FIRST
+ } else {
+ FREE_EXACT* curr = (FREE_EXACT*)freelist_exact[bin];
+ while (curr->next && (curr < (FREE_EXACT*)chunk))
+ curr = curr->next;
+
+ /* insert */
+ ((FREE_EXACT*)chunk)->next = curr->next;
+ curr->next = (FREE_EXACT*)chunk;
+ }
+#endif
+ }
+
+ return;
+}
+
+void*
+allocator_alloc(SIZE size)
+{
+ void* result = NULL;
+ int maxbin;
+ int bin;
+
+#if COUNT_ALLOCATIONS
+ allocator_allocations++;
+#endif
+
+#if FASTER_FAIL
+ if (size > allocator_largest_free)
+ return NULL;
+#endif
+
+#if PRESERVE_LOCALITY
+ allocator_last_splitoff = 0;
+ allocator_last_splitoff_size = 0;
+#endif
+
+ if (size <= ((1 << EXACT) << ALIGN)) {
+ /* search the exact bins */
+ bin = size >> ALIGN;
+ maxbin = 1 << EXACT;
+
+ while (bin <= maxbin) {
+ if (freelist_exact[bin]) {
+ /* unlink */
+ result = (void*)freelist_exact[bin];
+ freelist_exact[bin]=freelist_exact[bin]->next;
+
+ /* split */
+ if ((bin << ALIGN) > size)
+ allocator_free(result + size, (bin << ALIGN) - size);
+
+ // fprintf(stderr, "found chunk in exact bin %d\n", bin);
+
+ return result;
+ } else
+ ++bin;
+ }
+
+ bin = 0;
+ } else {
+ bin = size_to_bin(size);
+ }
+
+ maxbin = LARGE << SUBBIT;
+
+ while (bin < maxbin) {
+ if (freelist_large[bin]) {
+ FREE_LARGE* chunk = freelist_large[bin];
+
+ // fprintf(stderr, "found chunk in large bin %d\n", bin);
+
+ if (chunk->size >= size) {
+ /* unlink */
+ freelist_large[bin] = chunk->next;
+
+ /* split */
+ if (chunk->size > size)
+ allocator_free((void*)chunk + size, (chunk->size - size));
+
+ return (void*)chunk;
+ }
+
+ while (chunk->next && (chunk->next->size < size))
+ chunk = chunk->next;
+
+ if (chunk->next) {
+ /* unlink */
+ FREE_LARGE* new_chunk = chunk->next;
+ chunk->next = new_chunk->next;
+
+ /* split */
+ if (new_chunk->size > size)
+ allocator_free((void*)new_chunk + size, (new_chunk->size - size));
+
+ return (void*)new_chunk;
+ }
+ }
+
+ ++bin;
+ }
+
+ return result; /* NULL */
+}
+
+void
+allocator_dump()
+{
+ int i;
+
+ for (i = 1; i <= 1 << EXACT; ++i) {
+ int count = 0;
+ FREE_EXACT* chunk = freelist_exact[i];
+
+ while (chunk) {
+ chunk = chunk->next;
+ ++count;
+ }
+
+ if (count)
+ printf("exact bin %d (%d byte blocks): %d\n", i, i * (1 << ALIGN), count);
+ }
+ for (i = 0; i < LARGE << SUBBIT; ++i) {
+ int count = 0;
+ FREE_LARGE* chunk = freelist_large[i];
+
+ if (chunk)
+ printf("large bin %d:\n", i);
+
+ while (chunk) {
+ printf("\t%d bytes @ 0x%lx\n", chunk->size, chunk);
+ chunk = chunk->next;
+ ++count;
+ }
+ }
+
+ printf("dump complete.\n");
+}
+
+
+
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
--- /dev/null
+/*
+ * cacao/mm/bitmap2.c
+ *
+ * Copyright (c) 1998 A. Krall, R. Grafl, M. Gschwind, M. Probst, P. Tomsich
+ * See file COPYRIGHT for information on usage and disclaimer of warranties
+ *
+ * Authors: Philipp Tomsich EMAIL: cacao@complang.tuwien.ac.at
+ *
+ * $Id: bitmap2.c 34 1998-11-03 11:29:37Z phil $
+ */
+
+/*
+ * This file contains the new bitmap management; it's used within the garbage
+ * collector and allocator to maintain and access the objectstart-, marker-
+ * and reference-bitmaps.
+ *
+ * Notes:
+ * 1. For efficencies sake, the memory used for the bitmap is never accessed
+ * directly using a heap-offset, but through a pointer offset at bitmap
+ * creation; this saves all the subtractions and additions necessary to
+ * convert between an address on the heap and an offset into the heap.
+ *
+ * 2. I finally added a bitmap_t structure to encapsulate some state
+ * information. It contains everything necessary to access the bitmap,
+ * caches a few precomputable values and allows for freeing the bitmap.
+ *
+ * 3. There's no checks whatsoever to determine whether an address passed is
+ * valid or not. These were removed, in order to allow passing the offset
+ * address of the bitmap instead of the bitmap structure.
+ * I.e., checking addresses to determine whether they are pointing onto
+ * the heap must be done before passing them to the bitmap management
+ * functions.
+ *
+ * 4. Just added exceptions to note 3: Now we have new functions checking the
+ * validity of the address to aid in debugging. They are named
+ * bitmap_checking_{set|clear|test}bit and will cause an assertion to fail
+ * if the addr argument is out of range.
+ */
+
+#include <assert.h> /* assert */
+#include <stdio.h> /* printf, fprintf */
+#include <stdlib.h> /* malloc, free */
+#include <string.h> /* memset */
+#include <unistd.h> /* exit */
+
+#include "bitmap2.h"
+
+
+#warning "bitmap2.c untested in 32-bit mode -- phil."
+
+/* FIXME: I haven't decided, whether to keep these macro definitions here or
+ * move them to the header file; they are implementation details, so
+ * they should stay here, but moving them would make the SETBIT,
+ * TESTBIT and CLEARBIT macros available to the general public. --phil.
+ */
+
+/* FIXME: HEAPBLOCK_SIZE is an alias for POINTER_ALIGNMENT and should be
+ * removed. --phil.
+ */
+
+/* Please note: All values are log2 */
+#if U8_AVAILABLE
+# define POINTER_ALIGNMENT 3 /* alignment of pointers onto the
+ heap == heapblocksize */
+# define BITBLOCK_SIZE 3 /* bytes/BITBLOCK */
+#else
+# define POINTER_ALIGNMENT 2
+# define BITBLOCK_SIZE 2
+#endif
+
+#define HEAPBLOCK_SIZE POINTER_ALIGNMENT
+#define BITS_PER_BYTE 3 /* actually quite self-explainatory */
+#define HEAPBLOCKS_PER_BITBLOCK (BITBLOCK_SIZE + BITS_PER_BYTE)
+
+#define ADDR_TO_BLOCK(addr) ((OFFSET_T)(addr) >> (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
+#define ADDR_TO_OFFSET(addr) (((OFFSET_T)(addr) & ((1 << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT)) - 1)) >> HEAPBLOCK_SIZE)
+#define BLOCK_TO_ADDR(block) ((block) << (HEAPBLOCKS_PER_BITBLOCK + POINTER_ALIGNMENT))
+#define OFFSET_TO_ADDR(offset) ((offset) << HEAPBLOCK_SIZE)
+#define CALC_BITMAP_SIZE(size) (((size) + ((1 << (POINTER_ALIGNMENT + HEAPBLOCK_SIZE)) - 1)) >> BITS_PER_BYTE)
+
+#define CHECK_ADDR_ALIGNMENT(addr) { assert(!((OFFSET_T)addr & ((1 << POINTER_ALIGNMENT) - 1))); }
+#define CALC_ZERO_OFFSET(zero) (((OFFSET_T)(zero) >> (HEAPBLOCK_SIZE + BITS_PER_BYTE)))
+
+#define BIT_AT_OFFSET(offset) ((BITBLOCK)1 << (offset))
+#define BIT_FOR_ADDR(addr) BIT_AT_OFFSET(ADDR_TO_OFFSET((addr)))
+
+#define SETBIT(bitmap, addr) { bitmap[ADDR_TO_BLOCK(addr)] |= BIT_FOR_ADDR(addr); }
+#define CLEARBIT(bitmap, addr) { bitmap[ADDR_TO_BLOCK(addr)] &= ~BIT_FOR_ADDR(addr); }
+#define TESTBIT(bitmap, addr) ( (bitmap[ADDR_TO_BLOCK(addr)] & BIT_FOR_ADDR(addr)) != 0 )
+
+
+/* Operations per macro (relative cost):
+ *
+ * Macro | & | &= | |= | ~ | >> | << | + | dereference |
+ * -----------------+---+----+----+---+----+----+---+-------------+
+ * ADDR_TO_BLOCK | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
+ * ADDR_TO_OFFSET | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
+ * BLOCK_TO_ADDR | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+ * OFFSET_TO_ADDR | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+ * CALC_BITMAP_SIZE | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+ * CALC_ZERO_OFFSET | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
+ * -----------------+---+----+----+---+----+----+---+-------------+
+ * BIT_AT_OFFSET | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+ * BIT_FOR_ADDR | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
+ * -----------------+---+----+----+---+----+----+---+-------------+
+ * SETBIT | 1 | 0 | 1 | 0 | 2 | 1 | 0 | 1 |
+ * CLEARBIT | 1 | 1 | 0 | 1 | 2 | 1 | 0 | 1 |
+ * TESTBIT | 2 | 0 | 0 | 0 | 2 | 1 | 0 | 1 |
+ */
+
+
+inline
+void bitmap_setbit(BITBLOCK* bitmap,
+ void* addr)
+{
+ SETBIT(bitmap, addr);
+}
+
+inline
+void bitmap_clearbit(BITBLOCK* bitmap,
+ void* addr)
+{
+ CLEARBIT(bitmap, addr);
+}
+
+inline
+bool bitmap_testbit(BITBLOCK* bitmap,
+ void* addr)
+{
+ return TESTBIT(bitmap, addr);
+}
+
+inline
+static
+void bitmap_boundscheck(bitmap_t* bitmap,
+ void* addr)
+{
+ /* check the lower bound */
+ assert((void*)&bitmap->bitmap[ADDR_TO_BLOCK(addr)] >= bitmap->bitmap_memory);
+ /* check the upper bound */
+ assert(&bitmap->bitmap[
+ ADDR_TO_BLOCK(addr)]
+ <= &bitmap->bitmap[bitmap->bitmap_top_block]);
+ assert(addr < bitmap->bitmap_beyond_addr); /* a stricter way to check the upper bound */
+}
+
+inline
+void bitmap_checking_setbit(bitmap_t* bitmap,
+ void* addr)
+{
+ bitmap_boundscheck(bitmap, addr);
+ bitmap_setbit(bitmap->bitmap, addr);
+}
+
+inline
+void bitmap_checking_clearbit(bitmap_t* bitmap,
+ void* addr)
+{
+ bitmap_boundscheck(bitmap, addr);
+ bitmap_clearbit(bitmap->bitmap, addr);
+}
+
+inline
+bool bitmap_checking_testbit(bitmap_t* bitmap,
+ void* addr)
+{
+ bitmap_boundscheck(bitmap, addr);
+ return bitmap_testbit(bitmap->bitmap, addr);
+}
+
+inline
+void bitmap_clear(bitmap_t* bitmap)
+{
+ memset(bitmap->bitmap_memory, 0, bitmap->bytesize);
+}
+
+inline
+bitmap_t* bitmap_allocate(void* zero_addr,
+ OFFSET_T size)
+{
+ bitmap_t* bitmap;
+
+ unsigned long bytesize = CALC_BITMAP_SIZE(size); /* align */
+ bitmap = (bitmap_t*)malloc(sizeof(bitmap_t));
+
+ CHECK_ADDR_ALIGNMENT(zero_addr); /* ensure correct alignment for zero_addr */
+
+ bitmap->bytesize = bytesize;
+ bitmap->bitmap_memory = malloc(bytesize);
+ bitmap->bitmap = bitmap->bitmap_memory - CALC_ZERO_OFFSET(zero_addr); /* offset for fast access */
+
+ bitmap->bitmap_beyond_addr = zero_addr + size;
+ bitmap->bitmap_top_block = ADDR_TO_BLOCK(bitmap->bitmap_beyond_addr - sizeof(BITBLOCK));
+
+ if (!bitmap->bitmap_memory) {
+ /* handle error -- unable to allocate enough memory */
+ fprintf(stderr, "bitmap2.c: Failed to allocate memory for a bitmap.\n");
+ exit(-1); /* FIXME: I should probably call some sort of cacao-wide "panic" function ?! -- phil. */
+ }
+
+ bitmap_clear(bitmap);
+
+ return bitmap;
+}
+
+inline
+void bitmap_release(bitmap_t* bitmap)
+{
+ if (bitmap) {
+ if (bitmap->bitmap_memory)
+ free(bitmap->bitmap_memory);
+ free(bitmap);
+ }
+}
+
+static
+inline
+int offset_for_lowest(BITBLOCK i)
+{
+ /* Maintainer, don't despair!
+ *
+ * The OFFSET_TO_ADDR adjusts an argument according to the size of heap-allocation blocks,
+ * so that the resulting value can be used as an offset to a pointer.
+ * I.e.: addr + OFFSET_TO_ADDR(i) is equivalent to addr + (sizeof(heap_block) * i)
+ *
+ * The definition of lowest just looks inefficient, everything should be expanded at
+ * compile-time, though. -- phil.
+ */
+
+ static signed char lowest[256] = {
+ OFFSET_TO_ADDR(0), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(5), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(6), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(5), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(7), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(5), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(6), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(5), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(4), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ OFFSET_TO_ADDR(3), 0, OFFSET_TO_ADDR(1), 0, OFFSET_TO_ADDR(2), 0, OFFSET_TO_ADDR(1), 0,
+ };
+
+#if U8_AVAILABLE
+ if (i & 0xffffffffffULL)
+#endif
+ if (i & 0xffffUL)
+ if (i & 0xffUL)
+ return OFFSET_TO_ADDR(0) + lowest[(unsigned char)i];
+ else
+ return OFFSET_TO_ADDR(8) + lowest[(unsigned char)(i>>8)];
+ else
+ if (i & 0xff0000UL)
+ return OFFSET_TO_ADDR(16) + lowest[(unsigned char)(i>>16)];
+ else
+ return OFFSET_TO_ADDR(24) + lowest[(unsigned char)(i>>24)];
+#if U8_AVAILABLE
+ else
+ if (i & 0xffff00000000ULL)
+ if (i & 0xff00000000ULL)
+ return OFFSET_TO_ADDR(32) + lowest[(unsigned char)(i>>32)];
+ else
+ return OFFSET_TO_ADDR(40) + lowest[(unsigned char)(i>>40)];
+ else
+ if (i & 0xff000000000000ULL)
+ return OFFSET_TO_ADDR(48) + lowest[(unsigned char)(i>>48)];
+ else
+ return OFFSET_TO_ADDR(56) + lowest[(unsigned char)(i>>56)];
+#endif
+}
+
+inline
+void*
+bitmap_find_next_setbit(bitmap_t* bitmap,
+ void* addr)
+{
+ OFFSET_T block = ADDR_TO_BLOCK(addr);
+ OFFSET_T offset = ADDR_TO_OFFSET(addr);
+ BITBLOCK pattern;
+
+ bitmap_boundscheck(bitmap, addr);
+
+ /* 1. check the current block, starting from the bit indicated by addr */
+ pattern = bitmap->bitmap[block] >> offset;
+ if (pattern)
+ return (void*)(addr + offset_for_lowest(pattern));
+
+ /* 2. iteratively check block by block until the end of the bitmap */
+ while (block < bitmap->bitmap_top_block) {
+ pattern = bitmap->bitmap[++block];
+
+ if (pattern)
+ return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
+ }
+
+ /* 3. failed to find a set bit... */
+ return bitmap->bitmap_beyond_addr;
+}
+
+inline
+void*
+bitmap_find_next_combination_set_unset(bitmap_t* bitmap,
+ bitmap_t* invertedmap,
+ void* addr)
+{
+ OFFSET_T block = ADDR_TO_BLOCK(addr);
+ OFFSET_T offset = ADDR_TO_OFFSET(addr);
+ BITBLOCK pattern;
+
+ bitmap_boundscheck(bitmap, addr);
+
+ /* 1. check the current block, starting from the bit indicated by addr */
+ pattern = (bitmap->bitmap[block] & ~invertedmap->bitmap[block]) >> offset;
+ if (pattern)
+ return (void*)(addr + offset_for_lowest(pattern));
+
+ /* 2. iteratively check block by block until the end of the bitmap */
+ while (block < bitmap->bitmap_top_block) {
+ pattern = bitmap->bitmap[++block] & ~invertedmap->bitmap[block];
+
+ if (pattern)
+ return (void*)(BLOCK_TO_ADDR(block) + offset_for_lowest(pattern));
+ }
+
+ /* 3. failed to find a combination... */
+ return bitmap->bitmap_beyond_addr;
+}
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
projects / cacao.git / commitdiff