ref: a4a9799d91c55b7b5922148a661a5141ba22b6db
parent: 6e6109bf094974b228783e549c4164c886cbca4d
author: Ori Bernstein <[email protected]>
date: Thu Dec 15 17:57:41 EST 2011
Add a Bitset data structure We'll need it for implementing type constraints, among other things.
--- a/parse/Makefile
+++ b/parse/Makefile
@@ -1,5 +1,6 @@
BIN=pt
OBJ=dump.o \
+ ds.o \
infer.o \
main.o \
names.o \
--- /dev/null
+++ b/parse/ds.c
@@ -1,0 +1,50 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <assert.h>
+#include <limits.h>
+
+#include "parse.h"
+
+#define Uintbits (CHAR_BIT*sizeof(int))
+
+Bitset *mkbs()
+{
+ Bitset *bs;
+
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = 1;
+ bs->chunks = xalloc(1*sizeof(uint));
+ return bs;
+}
+
+void delbs(Bitset *bs)
+{
+ free(bs->chunks);
+ free(bs);
+}
+
+void bsput(Bitset *bs, uint elt)
+{
+ if (elt >= bs->nchunks*Uintbits) {
+ bs->nchunks = (elt/Uintbits)+1;
+ bs->chunks = xrealloc(bs->chunks, bs->nchunks*sizeof(uint));
+ }
+ bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);
+}
+
+void bsdel(Bitset *bs, uint elt)
+{
+ if (elt < bs->nchunks*Uintbits)
+ bs->chunks[elt/Uintbits] &= ~(1 << (elt % Uintbits));
+}
+
+int bshas(Bitset *bs, uint elt)
+{
+ if (elt >= bs->nchunks*Uintbits)
+ return 0;
+ else
+ return bs->chunks[elt/Uintbits] & (1 << (elt % Uintbits));
+}
+
+
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -1,7 +1,10 @@
typedef uint32_t unichar;
+typedef unsigned int uint;
typedef long long vlong;
typedef unsigned long long uvlong;
+typedef struct Bitset Bitset;
+
typedef struct Tok Tok;
typedef struct Node Node;
typedef struct Stab Stab;
@@ -40,6 +43,10 @@
Dclextern = 1 << 1,
} Dclflags;
+struct Bitset {
+ int nchunks;
+ uint *chunks;
+};
struct Tok {
int type;
@@ -70,6 +77,7 @@
Ty type;
int tid;
size_t nsub; /* For fnsub, tusub, sdecls, udecls, edecls. */
+ Bitset cstrs; /* the type constraints matched on this type */
union {
Node *name; /* Tyname: unresolved name */
Type **fnsub; /* Tyfunc: return, args */
@@ -113,6 +121,7 @@
struct {
Op op;
+ Type *type;
int isconst;
size_t nargs;
Node **args;
@@ -179,6 +188,13 @@
} func;
};
};
+
+/* data structures */
+Bitset *mkbs();
+void delbs(Bitset *bs);
+void bsput(Bitset *bs, uint elt);
+void bsdel(Bitset *bs, uint elt);
+int bshas(Bitset *bs, uint elt);
/* globals */
extern int debug;