ref: a8c9ee3f9f94a4789bb7b86a8dbc7392e6b94985
parent: f7b9f1912c0f10033006bb55deb3d48768b9f3a6
author: qwx <qwx@sciops.net>
date: Fri Mar 25 21:12:17 EDT 2022
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;
}