shithub: mc

Download patch

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;