shithub: mc

Download patch

ref: efb34ddd6b8f6aa92a0e9460968da4275ec5f178
parent: a4a9799d91c55b7b5922148a661a5141ba22b6db
author: Ori Bernstein <[email protected]>
date: Thu Dec 15 19:13:15 EST 2011 

Fill in rest of bitset operations.


--- a/parse/ds.c
+++ b/parse/ds.c
@@ -8,6 +8,20 @@
 
 #define Uintbits (CHAR_BIT*sizeof(int))
 
+static void eqsz(Bitset *a, Bitset *b)
+{
+    int sz;
+
+    if (a->nchunks > b->nchunks)
+        sz = a->nchunks;
+    else
+        sz = b->nchunks;
+    a->chunks = zrealloc(a->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+    a->nchunks = sz;
+    b->chunks = zrealloc(b->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+    b->nchunks = sz;
+}
+
 Bitset *mkbs()
 {
     Bitset *bs;
@@ -26,9 +40,11 @@
 
 void bsput(Bitset *bs, uint elt)
 {
+    size_t sz;
     if (elt >= bs->nchunks*Uintbits) {
-        bs->nchunks = (elt/Uintbits)+1;
-        bs->chunks = xrealloc(bs->chunks, bs->nchunks*sizeof(uint));
+        sz = (elt/Uintbits)+1;
+        bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(uint), sz*sizeof(uint));
+        bs->nchunks = sz;
     }
     bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);
 }
@@ -47,4 +63,29 @@
         return bs->chunks[elt/Uintbits] & (1 << (elt % Uintbits));
 }
 
+void bsunion(Bitset *a, Bitset *b)
+{
+    int i;
 
+    eqsz(a, b);
+    for (i = 0; i < a->nchunks; i++)
+        a->chunks[i] |= b->chunks[i];
+}
+
+void bsintersect(Bitset *a, Bitset *b)
+{
+    int i;
+
+    eqsz(a, b);
+    for (i = 0; i < a->nchunks; i++)
+        a->chunks[i] &= b->chunks[i];
+}
+
+void bsdiff(Bitset *a, Bitset *b)
+{
+    int i;
+
+    eqsz(a, b);
+    for (i = 0; i < a->nchunks; i++)
+        a->chunks[i] &= ~b->chunks[i];
+}
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -191,10 +191,14 @@
 
 /* data structures */
 Bitset *mkbs();
+Bitset *dupbs(Bitset *bs);
 void delbs(Bitset *bs);
 void bsput(Bitset *bs, uint elt);
 void bsdel(Bitset *bs, uint elt);
-int bshas(Bitset *bs, uint elt);
+int  bshas(Bitset *bs, uint elt);
+void bsunion(Bitset *a, Bitset *b);
+void bsintersect(Bitset *a, Bitset *b);
+void bsdiff(Bitset *a, Bitset *b);
 
 /* globals */
 extern int debug;
@@ -208,6 +212,7 @@
 /* util functions */
 void *zalloc(size_t size);
 void *xalloc(size_t size);
+void *zrealloc(void *p, size_t oldsz, size_t size);
 void *xrealloc(void *p, size_t size);
 void  die(char *msg, ...);
 void  fatal(int line, char *fmt, ...);
--- a/parse/util.c
+++ b/parse/util.c
@@ -34,6 +34,16 @@
     return mem;
 }
 
+void *zrealloc(void *mem, size_t oldsz, size_t sz)
+{
+    char *p;
+
+    p = xrealloc(mem, sz);
+    if ((ssize_t)sz - (ssize_t)oldsz > 0)
+        bzero(&p[oldsz], sz - oldsz);
+    return p;
+}
+
 void *xrealloc(void *mem, size_t sz)
 {
     mem = realloc(mem, sz);