+ printf("\n");
+}
+#endif
+
+struct ipset *ipset_from_subnet(struct subnet s)
+{
+ struct ipset *r;
+
+ r=ipset_new();
+ r->l=1;
+ r->d[0].a=s.prefix;
+ r->d[0].b=s.prefix | (~s.mask);
+ return r;
+}
+
+struct ipset *ipset_from_subnet_list(struct subnet_list *l)
+{
+ struct ipset *r, *a, *b;
+ int32_t i;
+
+ r=ipset_new();
+ for (i=0; i<l->entries; i++) {
+ a=ipset_from_subnet(l->list[i]);
+ b=ipset_union(r,a);
+ ipset_free(a);
+ ipset_free(r);
+ r=b;
+ }
+ return r;
+}
+
+static void ipset_set_len(struct ipset *a, int32_t l)
+{
+ struct iprange *nd;
+ int32_t na;
+
+ if (l>a->a) {
+ assert(a->a < INT_MAX-EXTEND_ALLOC_BY);
+ na=a->a+EXTEND_ALLOC_BY;
+ nd=realloc(a->d,sizeof(*nd)*na);
+ if (!nd) {
+ fatal_perror("ipset_set_len: realloc");
+ }
+ a->a=na;
+ a->d=nd;
+ }
+ a->l=l;
+}
+
+static void ipset_append_range(struct ipset *a, struct iprange r)
+{
+ ipset_set_len(a,a->l+1);
+ a->d[a->l-1]=r;
+}
+
+#define max(a,b) (a>b?a:b)
+struct ipset *ipset_union(struct ipset *a, struct ipset *b)
+{
+ struct ipset *c;
+ struct iprange r;
+ int32_t ia,ib;
+
+ c=ipset_new();
+ ia=0; ib=0;
+ while (ia<a->l || ib<b->l) {
+ if (ia<a->l)
+ if (ib<b->l)
+ if (a->d[ia].a < b->d[ib].a)
+ r=a->d[ia++];
+ else
+ r=b->d[ib++];
+ else
+ r=a->d[ia++];
+ else
+ r=b->d[ib++];
+
+ if (c->l==0)
+ ipset_append_range(c,r);
+ else if (r.a <= c->d[c->l-1].b+1)
+ /* Extends (or is consumed by) the last range */
+ c->d[c->l-1].b=max(c->d[c->l-1].b, r.b);
+ else
+ ipset_append_range(c,r);
+ }
+ return c;
+}
+
+struct ipset *ipset_intersection(struct ipset *a, struct ipset *b)
+{
+ struct ipset *r;
+ struct iprange ra, rb;
+ int32_t ia,ib;
+
+ r=ipset_new();
+ ia=0; ib=0;
+
+ while (ia<a->l && ib<b->l) {
+ ra=a->d[ia];
+ rb=b->d[ib];
+ if (ra.b < rb.a)
+ /* The first entry of a doesn't overlap with any part of b */
+ ia++;
+ else if (ra.a > rb.b)
+ /* The first entry of b doesn't overlap with any part of a */
+ ib++;
+ else {
+ /* Trim away any leading edges */
+ if (ra.a < rb.a)
+ /* a starts before b */
+ ra.a=rb.a;
+ else if (ra.a > rb.a)
+ /* b starts before a */
+ rb.a=ra.a;
+
+ /* Now the ranges start at the same point */
+ if (ra.b == rb.b) {
+ /* The ranges are equal */
+ ipset_append_range(r,ra);
+ ia++;
+ ib++;
+ } else if (ra.b < rb.b) {
+ /* a is the smaller range */
+ ipset_append_range(r,ra);
+ ia++;
+ } else {
+ /* y is the smaller range */
+ ipset_append_range(r,rb);
+ ib++;
+ }
+ }
+ }
+ return r;
+}
+
+struct ipset *ipset_complement(struct ipset *a)
+{
+ struct ipset *r;
+ struct iprange n;
+ int64_t pre;
+ int32_t i;
+ uint32_t lo,hi;
+
+ r=ipset_new();
+ pre=-1;
+ for (i=0; i<a->l; i++) {
+ lo=a->d[i].a;
+ hi=a->d[i].b;
+ if (lo!=0) {
+ n.a=pre+1;
+ n.b=lo-1;
+ ipset_append_range(r,n);
+ }
+ pre=hi;
+ }
+ if (pre!=0xffffffff) {
+ n.a=pre+1;
+ n.b=0xffffffff;
+ ipset_append_range(r,n);
+ }
+ return r;
+}
+
+/* Return a-b */
+struct ipset *ipset_subtract(struct ipset *a, struct ipset *b)
+{
+ struct ipset *c, *r;
+ c=ipset_complement(b);
+ r=ipset_intersection(a,c);
+ ipset_free(c);
+ return r;