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