ref: f8978196906ee7a57ebedf6c5a7d09ae1bba89a6
parent: 2850b592998277aef88f3e6769063b741d850d58
author: qwx <qwx@sciops.net>
date: Fri Aug 14 20:03:39 EDT 2020
add naive exact string match, resizable vectors and restructure
--- /dev/null
+++ b/asif.h
@@ -1,0 +1,43 @@
+typedef struct VArray VArray;
+typedef struct String String;
+
+struct String{+ char *s;
+ int n;
+};
+
+struct VArray{+ int nelem;
+ int elsize;
+ int vsize;
+ int bufsize;
+ void *p;
+};
+
+void* erealloc(void*, ulong, ulong);
+void* emalloc(ulong);
+void vfree(VArray*);
+VArray* vinsert(VArray*, char*);
+VArray* valloc(ulong, int);
+
+#define MIN(a,b) ((a) < (b) ? (a) : (b))
+#define MAX(a,b) ((a) > (b) ? (a) : (b))
+
+
+VArray* naivestrfind(String, String);
+
+
+typedef struct Pairheap Pairheap;
+
+struct Pairheap{+ double n;
+ void *aux;
+ Pairheap *parent;
+ Pairheap *left;
+ Pairheap *right;
+};
+
+void nukequeue(Pairheap**);
+Pairheap* popqueue(Pairheap**);
+void decreasekey(Pairheap*, double, Pairheap**);
+void pushqueue(double, void*, Pairheap**);
--- a/fns.h
+++ /dev/null
@@ -1,4 +1,0 @@
-void nukequeue(Pairheap**);
-Pairheap* popqueue(Pairheap**);
-void decreasekey(Pairheap*, double, Pairheap**);
-void pushqueue(double, void*, Pairheap**);
--- a/heap.h
+++ /dev/null
@@ -1,9 +1,0 @@
-typedef struct Pairheap Pairheap;
-
-struct Pairheap{- double n;
- void *aux;
- Pairheap *parent;
- Pairheap *left;
- Pairheap *right;
-};
--- /dev/null
+++ b/strnaive.c
@@ -1,0 +1,19 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+
+VArray *
+naivestrfind(String text, String word)
+{+ int n;
+ VArray *v;
+
+ n = text.n - word.n + 1;
+ if(n <= 0)
+ return nil;
+ v = valloc(n, sizeof int);
+ for(i=0; i<n; i++)
+ if(strcmp(text.s+i, word.s) == 0)
+ v = vinsert(v, &i);
+ return v;
+}
--- /dev/null
+++ b/utils.c
@@ -1,0 +1,62 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+
+enum{+ VAdefsize = 1024,
+};
+
+void *
+erealloc(void *p, ulong n, ulong oldn)
+{+ if((p = realloc(p, n)) == nil)
+ sysfatal("realloc: %r");+ setrealloctag(p, getcallerpc(&p));
+ return p;
+}
+
+void *
+emalloc(ulong n)
+{+ void *p;
+
+ if((p = mallocz(n, 1)) == nil)
+ sysfatal("emalloc: %r");+ setmalloctag(p, getcallerpc(&n));
+ return p;
+}
+
+void
+vfree(VAarray *v)
+{+ free(v->p);
+ free(v);
+}
+
+VArray*
+vinsert(VArray *v, char *)
+{+ int off;
+
+ off = v->nelem * v->elsize;
+ if(v->nelem++ >= v->bufsize){+ v->p = erealloc(v->p, v->bufsize * 2, v->bufsize);
+ v->bufsize *= 2;
+ v->vsize *= 2;
+ }
+ memcpy(v->p+off, u, v->elsize);
+}
+
+VArray*
+valloc(ulong n, int elsize)
+{+ VArray *v;
+
+ v = emalloc(sizeof *p);
+ v->nelem = 0;
+ v->elsize = elsize;
+ v->vsize = MIN(n, VAdefsize);
+ v->bufsize = v->vsize * elsize;
+ v->p = emalloc(v->bufsize);
+ return v;
+}