1/* vim:set shiftwidth=4 ts=4 */
2
3#include <spinehdr.h>
4#include <stdlib.h>
5#include <subset.h>
6
7static void *mkPtrItem(Dt_t * d, ptritem * obj, Dtdisc_t * disc)
8{
9 NOTUSED(d);
10 NOTUSED(disc);
11 ptritem *np = NEW(ptritem);
12 np->v = obj->v;
13 return (void *) np;
14}
15
16static void freePtrItem(Dt_t * d, ptritem * obj, Dtdisc_t * disc)
17{
18 NOTUSED(d);
19 NOTUSED(disc);
20 free(obj);
21}
22
23static int cmpptr(Dt_t * d, void **key1, void **key2, Dtdisc_t * disc)
24{
25 NOTUSED(d);
26 NOTUSED(disc);
27 if (*key1 > *key2)
28 return 1;
29 else if (*key1 < *key2)
30 return -1;
31 else
32 return 0;
33}
34
35static Dtdisc_t ptrdisc = {
36 offsetof(ptritem, v),
37 sizeof(void *),
38 offsetof(ptritem, link),
39 (Dtmake_f) mkPtrItem,
40 (Dtfree_f) freePtrItem,
41 (Dtcompar_f) cmpptr,
42 0,
43 0,
44 0
45};
46
47Dt_t *mkSubset()
48{
49 Dt_t *s = dtopen(&ptrdisc, Dtoset);
50 return s;
51}
52
53void addSubset(Dt_t * s, void *n)
54{
55 ptritem dummy;
56
57 dummy.v = n;
58 dtinsert(s, &dummy);
59}
60
61void* inSubset(Dt_t * s, void *n)
62{
63 return dtmatch(s, &n);
64}
65
66int sizeSubset(Dt_t * s)
67{
68 return dtsize(s);
69}
70
71void clearSubset(Dt_t * s)
72{
73 dtclear(s);
74}
75
76void closeSubset(Dt_t * s)
77{
78 dtclose(s);
79}
80
81typedef struct {
82 Dt_t* s;
83 int sz;
84} setsize_t;
85
86static int union_fn(Agnode_t * n, setsize_t *state)
87{
88 if (!inSubset(state->s, n))
89 state->sz++;
90 return 0;
91}
92
93int union_size(Dt_t* s0, Dt_t* s1)
94{
95 setsize_t state;
96
97 state.s = s0;
98 state.sz = sizeSubset(s0);
99 walkSubset(s1, (walkfn)union_fn, &state);
100 return state.sz;
101}
102
103static int intersect_fn(Agnode_t * n, setsize_t *state)
104{
105 if (inSubset(state->s, n))
106 state->sz++;
107 return 0;
108}
109
110int intersect_size(Dt_t* s0, Dt_t* s1)
111{
112 setsize_t state;
113
114 state.s = s0;
115 state.sz = 0;
116 walkSubset(s1, (walkfn)intersect_fn, &state);
117 return state.sz;
118}
119
120typedef struct {
121 walkfn wf;
122 void *state;
123} auxstate;
124
125static int auxfn(Dt_t * s, void *data, void *state)
126{
127 NOTUSED(s);
128 return ((auxstate *) state)->wf(((ptritem *) data)->v,
129 ((auxstate *) state)->state);
130}
131
132void walkSubset(Dt_t * s, walkfn wf, void *state)
133{
134 auxstate xstate;
135
136 xstate.wf = wf;
137 xstate.state = state;
138 dtwalk(s, auxfn, &xstate);
139}
140