A bug in my code
bearophile
bearophileHUGS at lycos.com
Fri Sep 5 18:12:56 PDT 2008
This code isn't short, but can someone help me spot the bug/problem (D1, DMD)?
I have tried to write clean & short code, to help spotting problems.
It produces an (no error line given):
Error: overlapping array copy
It's just a stack data structure (here for simplicity just for items of type int), made with a single linked list of blocks that become geometrically bigger.
import std.gc: malloc, hasNoPointers;
int min(int a, int b) {
return a <= b ? a : b;
}
class IntStack {
struct Block {
int len;
Block* next;
int* data;
}
Block* list_head, list_tail;
int total_len;
int used_last_block; // how many items are used in the last (tail) block
this() {
this.list_head = block_alloc(4);
this.list_tail = list_head;
}
ubyte* mem_alloc(int nbytes) {
auto p = cast(ubyte*)malloc(nbytes);
if (p is null)
throw new Error("not enough mem");
hasNoPointers(p);
return p;
}
Block* block_alloc(int nints) {
auto new_block = cast(Block*)mem_alloc(Block.sizeof);
new_block.data = cast(int*)mem_alloc(nints * int.sizeof);
new_block.len = nints;
new_block.next = null;
return new_block;
}
final void opCatAssign(int x) {
if (this.used_last_block == this.list_tail.len) {
// then last block is full and we must create a new one
this.used_last_block = 0;
auto new_block = block_alloc(this.list_tail.len * 2);
// append to the linked list
this.list_tail.next = new_block;
this.list_tail = new_block;
}
this.list_tail.data[this.used_last_block] = x;
this.used_last_block++;
this.total_len++;
}
int[] toarray() {
if (!this.total_len)
return null;
int* result_ptr = cast(int*)mem_alloc(this.total_len * int.sizeof);
int[] result = result_ptr[0 .. this.total_len];
Block* aux_ptr = this.list_head;
int pos;
// Here: Error: overlapping array copy
while (aux_ptr != null) {
// in the last block copy only up to the total_len
int ncopy = min(aux_ptr.len, this.total_len - pos);
result[pos .. pos + ncopy] = aux_ptr.data[0 .. ncopy];
pos += ncopy;
aux_ptr = aux_ptr.next;
}
return result;
}
}
void main() {
auto st = new IntStack();
for (int i; i < 70_000; i++)
st ~= i;
auto aux = st.toarray;
aux = st.toarray;
}
---------------------
Note: in that code I haven't used variable-length structs, like the following idiom sometimes used in C, because it gives array bounds errors:
struct Block {
int len;
Block* next;
int[1] data;
}
...
auto new_block = cast(Block*)mem_alloc(Block.sizeof + (nints - 1) * int.sizeof);
I presume that can't be done in D (I don't want to write code that works only in release mode).
Bye and thank you,
bearophile
More information about the Digitalmars-d-learn
mailing list