shithub: asif

Info  •  Files  •  Log

asif: better vectors implementation using linked lists of bins

--- a/asif.h

+++ b/asif.h

@@ -16,22 +16,30 @@

 void	vinsert(VArray*, char*);

 VArray*	valloc(ulong, int);

+enum{

+	Shardsz = 128,

+};

+typedef struct VShard VShard;

 typedef struct Vector Vector;

-struct Vector{

+struct VShard{

 	void *p;

-	ulong n;

-	ulong elsz;

-	ulong bufsz;

-	ulong totsz;

-	int firstempty;

+	void *head;

+	int len;

+	VShard *prev;

+	VShard *next;

 };

-void	freevec(Vector*);

-void	clearvec(Vector*);

-void	popsparsevec(Vector*, int);

-void*	pushsparsevec(Vector*, void*);

-void*	popvec(Vector*);

-void*	pushvec(Vector*, void*);

-void*	newvec(Vector*, int, int);

+struct Vector{

+	int len;

+	int elsz;

+	VShard vl;

+	void *tmp;

+};

+void	vecfree(Vector*);

+void*	vechpop(Vector*);

+void*	vectpop(Vector*);

+void	vecpush(Vector*, void*);

+void*	vecget(Vector*, int);

+Vector*	vec(int);

 typedef struct QNode QNode;

 struct QNode{

--- a/vec.c

+++ b/vec.c

@@ -2,108 +2,138 @@

 #include <libc.h>

 #include "asif.h"

-enum{

-	Nvecinc = 64,

-};

-

-void

-freevec(Vector *v)

+static void

+shardlink(Vector *v, VShard *s)

 {

-	if(v == nil)

-		return;

-	free(v->p);

+	s->next = &v->vl;

+	s->prev = v->vl.prev;

+	s->prev->next = s;

+	v->vl.prev = s;

 }

-void

-clearvec(Vector *v)

+static void

+shardunlink(Vector *v, VShard *s)

 {

-	assert(v != nil);

-	if(v->p == nil)

-		return;

-	memset(v->p, 0, v->totsz);

-	v->firstempty = 0;

-	v->n = 0;

+	memset(s->p, 0, Shardsz * v->elsz);

+	s->head = s->p;

+	s->prev->next = s->next;

+	s->next->prev = s->prev;

 }

-static void *

-growvec(Vector *v, int n)

+static VShard *

+shard(Vector *v)

 {

-	assert(v != nil);

-	if(n < v->bufsz)

-		return (uchar *)v->p + n * v->elsz;

-	v->p = erealloc(v->p, v->totsz + Nvecinc * v->elsz, v->totsz);

-	v->bufsz += Nvecinc;

-	v->totsz += Nvecinc * v->elsz;

-	return (uchar *)v->p + n * v->elsz;

+	VShard *s;

+

+	s = emalloc(sizeof *s);

+	s->p = emalloc(v->elsz * Shardsz);

+	s->head = s->p;

+	shardlink(v, s);

+	return s;

 }

 void

-popsparsevec(Vector *v, int n)

+vecfree(Vector *v)

 {

-	assert(v != nil && v->elsz > 0 && n >= 0 && n < v->n);

-	memset((uchar *)v->p + n * v->elsz, 0, v->elsz);

-	if(n < v->firstempty)

-		v->firstempty = n;

+	VShard *s, *t;

+

+	free(v->tmp);

+	for(s=v->vl.next; s!=&v->vl; s=t){

+		t = s->next;

+		free(s->p);

+		free(s);

+	}

+	free(v);

 }

-/* assumes that zeroed element means empty; could fill with

- * magic values instead */

-void *

-pushsparsevec(Vector *v, void *e)

+static void *

+shardpop(Vector *v, VShard *s, int i)

 {

-	int n;

-	uchar *p, *q;

+	uchar *p;

-	assert(v != nil && v->elsz > 0);

-	n = v->firstempty;

-	p = growvec(v, n);

-	for(n++, q=p+v->elsz; n<v->n; n++, q+=v->elsz)

-		if(memcmp(p, q, v->elsz) == 0)

-			break;

-	v->firstempty = n;

-	memcpy(p, e, v->elsz);

-	v->n++;

-	return p;

+	assert(s != &v->vl);

+	assert(i >= 0 && i < s->len);

+	p = (uchar *)s->head + i * v->elsz;

+	memcpy(v->tmp, p, v->elsz);

+	s->len--;

+	v->len--;

+	if(i == 0)

+		s->head = (uchar *)s->head + v->elsz;

+	if(s->len == 0){

+		shardunlink(v, s);

+		shardlink(v, s);

+	}

+	return v->tmp;

 }

 void *

-popvec(Vector *v)

+vechpop(Vector *v)

 {

 	uchar *p;

+	VShard *s;

-	assert(v != nil && v->elsz > 0);

-	if(v->n <= 0)

+	if(v->len <= 0)

 		return nil;

-	p = (uchar *)v->p + v->elsz * (v->n - 1);

-	if(v->firstempty > v->n - 1)

-		v->firstempty = v->n - 1;

-	v->n--;

-	return p;

+	s = v->vl.next;

+	assert(s != &v->vl);

+	return shardpop(v, s, 0);

 }

 void *

-pushvec(Vector *v, void *e)

+vectpop(Vector *v)

 {

+	VShard *s;

+

+	if(v->len <= 0)

+		return nil;

+	for(s=v->vl.prev; s != &v->vl && s->len == 0; s=s->prev)

+		;

+	assert(s != &v->vl);

+	return shardpop(v, s, s->len - 1);

+}

+

+void

+vecpush(Vector *v, void *e)

+{

 	uchar *p;

+	VShard *s;

-	assert(v != nil && v->elsz > 0);

-	p = growvec(v, v->n);

+	for(s=v->vl.prev; s != &v->vl && s->len >= Shardsz; s=s->prev)

+		;

+	if(s == &v->vl)

+		s = shard(v);

+	p = (uchar *)s->head + s->len * v->elsz;

 	memcpy(p, e, v->elsz);

-	v->n++;

-	v->firstempty = v->n;

-	if(v->firstempty > v->n)

-		v->firstempty = v->n;

-	return p;

+	s->len++;

+	v->len++;

 }

 void *

-newvec(Vector *v, int nel, int elsz)

+vecget(Vector *v, int i)

 {

-	assert(v != nil && elsz > 0);

+	uchar *p;

+	VShard *s;

+

+	assert(i >= 0 && i < v->len);

+	for(s=v->vl.next; s != &v->vl && i > s->len; s=s->next)

+		i -= s->len;

+	assert(s != &v->vl);

+	assert(s->len > 0);

+	assert(i >= 0 && i < s->len);

+	return (uchar *)s->head + i * v->elsz;

+}

+

+Vector *

+vec(int elsz)

+{

+	Vector *v;

+	VShard *s;

+

+	assert(elsz > 0);

+	v = emalloc(sizeof *v);

 	v->elsz = elsz;

-	nel = nel + Nvecinc-1 & ~(Nvecinc-1);

-	v->bufsz = nel;

-	v->totsz = nel * elsz;

-	v->p = emalloc(v->totsz);

-	return v->p;

+	v->vl.next = v->vl.prev = &v->vl;

+	v->tmp = emalloc(elsz);

+	shard(v);

+	return v;

 }