Infinite loop using phobos sort
Craig Black
craigblack2 at cox.net
Wed Dec 15 16:11:40 PST 2010
When I try to use Phobos to sort my custom Array, it goes into an infinite
loop. I suspect I did something wrong with my Range struct. Does anyone
see an obvious flaw here?
-Craig
import std.stdio;
import std.random;
import std.conv;
import std.algorithm;
import std.c.stdlib;
struct Array(T)
{
public:
this(int length) { resize(length); }
this(T[] a) { append(a); }
this(this)
{
if(!base.array) return;
ArrayBase!T old;
old = base;
base.array = null;
reserve(old.length(), old.length());
copyData(old);
old.array = null;
}
void clear() { base.clear(); }
void resize(int sz)
{
assert(sz >= 0);
if(sz == 0) return clear();
if(!base.array) reserve(sz, sz);
*base.lengthPtr() = sz;
}
void reserve(int capacity, int length)
{
assert(length <= capacity);
if(capacity == 0) return clear();
ArrayBase!T old;
if(base.array)
{
if(base.capacity() >= capacity) return;
old.array = base.array;
base.array = null;
}
base.array = cast(ubyte*)malloc(capacity*T.sizeof+8);
*base.lengthPtr() = length;
*base.capacityPtr() = capacity;
for(int i = 0; i < capacity; i++) emplace!T(base.data()+i);
if(old.array) copyData(old);
}
int length() const { return base.length(); }
int capacity() const { return base.capacity(); }
bool empty() const { return base.array == null; }
ref T at(int i)
{
assert(!empty(), "Array of " ~ T.stringof ~ ": index " ~ to!string(i) ~
" out of bounds of empty array");
assert(i >= 0 && i < length(), "Array of " ~ T.stringof ~ ": index " ~
to!string(i) ~ " out of bounds 0-" ~ to!string(length()-1));
return *cast(T*)(base.array+8+i*T.sizeof);
}
ref const T at(int i) const
{
assert(!empty(), "Array of " ~ T.stringof ~ ": index " ~ to!string(i) ~
" out of bounds of empty array");
assert(i >= 0 && i < length(), "Array of " ~ T.stringof ~ ": index " ~
to!string(i) ~ " out of bounds 0-" ~ to!string(length()-1));
return *cast(T*)(base.array+8+i*T.sizeof);
}
const ref T opIndex(int i) const { return
*cast(T*)(base.array+8+i*T.sizeof); }
void opIndexAssign(T t, int i) { at(i) = t; }
void opIndexAssign(ref T t, int i) { at(i) = t; }
void opAssign(ref const Array!T array)
{
copy(array);
}
void opAssign(T[] array)
{
int len = array.length;
resize(len);
for(int i = 0; i < len; i++) at(i) = array[i];
}
void copy(ref const Array!T array)
{
if(array.empty()) return clear();
int len = array.length();
reserve(len, len);
for(int i = 0; i < len; i++) at(i) = array[i];
}
void opOpAssign(string op, A...)(A a) if(op == "~")
{
appendComposite(a);
}
ref T front() { return at(0); }
const ref T front() const { return at(0); }
ref T back() { return at(length()-1); }
const ref T back() const { return at(length()-1); }
ref T appendOne()
{
int sz = length();
int sp = capacity();
if(sp > sz) (*base.lengthPtr())++;
else
{
sz++;
sp = max(2, sp+sp/2, sz);
reserve(sp, sz);
}
return back();
}
void append(A...)(A a)
{
static if(a.length == 1 && (is(typeof(a[0]) == Array!T) ||
is(typeof(a[0]) == T[])))
{
appendComposite(a[0]);
} else {
appendTuple(a);
}
}
void appendTuple(A...)(A a)
{
foreach(x; a) appendOne() = x;
}
void appendComposite(A)(A a)
{
int prevLen = length();
int alen = a.length;
resize(prevLen + alen);
T *d = base.data();
T *e = &a[0];
for(int i = 0; i < alen; i++) d[i+prevLen] = e[i];
}
static struct Range
{
public:
this(ref Array!T array)
{
if(array.empty()) return;
start = &array.front();
end = &array.back();
}
this(T *_start, T *_end)
{
start = _start;
end = _end;
}
T* start, end;
bool empty() const { return end < start; }
void popFront() { start++; }
void popBack() { end--; }
ref T front() { return *start; }
ref T back() { return *end; }
@property size_t length() { return end-start+1; }
ref T opIndex(int i) { return start[i]; }
Range opSlice(int a, int b) { return Range(start+a, start+b); }
Range save() { return this; }
}
Range opSlice() { return Range(this); }
Range opSlice(int a, int b) { return Range(base.data()+a,
base.data()+b); }
void sort(alias L = less!T)()
{
quickSort!(T*, L)(base.data(), 0, length()-1);
}
private:
static struct ArrayBase(T)
{
public:
~this() { clear(); }
void clear()
{
if(!array) return;
int cap = capacity();
T *d = data();
for(int i = 0; i < cap; i++) .clear(d[i]);
free(array);
}
int length() const { return array ? *lengthPtr() : 0; }
int capacity() const { return array ? *capacityPtr() : 0; }
int* lengthPtr() const { return cast(int*)(array); }
int* capacityPtr() const { return cast(int*)(array+4); }
T* data() const { return cast(T*)(array+8); }
ubyte* array;
}
ArrayBase!T base;
void copyData(ref ArrayBase!T array)
{
int copyLen = min(length, array.length());
T *a = base.data();
T *b = array.data();
for(int i = 0; i < copyLen; i++) { a[i] = b[i]; }
}
}
void main()
{
Array!double vals = 10;
foreach(ref i; vals) i = uniform(0.0,1000.0);
sort!"a<b"(vals[]);
}
More information about the Digitalmars-d
mailing list