/* * This file contains the set handling routines. * * Copyright (C) 2002 Sampo Niskanen, Patric Östergård. * Licensed under the GNU GPL, read the file LICENSE for details. */ #ifndef CLIQUER_SET_H #define CLIQUER_SET_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include "misc.h" /* * Sets are arrays of setelement's (typically unsigned long int's) with * representative bits for each value they can contain. The values * are numbered 0,...,n-1. */ /*** Variable types and constants. ***/ /* * If setelement hasn't been declared: * - use "unsigned long int" as setelement * - try to deduce size from ULONG_MAX */ #ifndef ELEMENTSIZE typedef unsigned long int setelement; # if (ULONG_MAX == 65535) # define ELEMENTSIZE 16 # elif (ULONG_MAX == 4294967295) # define ELEMENTSIZE 32 # else # define ELEMENTSIZE 64 # endif #endif /* !ELEMENTSIZE */ typedef setelement * set_t; /*** Counting amount of 1 bits in a setelement ***/ /* Array for amount of 1 bits in a byte. */ static int set_bit_count[256] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 }; /* The following macros assume that all higher bits are 0. * They may in some cases be useful also on with other ELEMENTSIZE's, * so we define them all. */ #define SET_ELEMENT_BIT_COUNT_8(a) (set_bit_count[(a)]) #define SET_ELEMENT_BIT_COUNT_16(a) (set_bit_count[(a)>>8] + \ set_bit_count[(a)&0xFF]) #define SET_ELEMENT_BIT_COUNT_32(a) (set_bit_count[(a)>>24] + \ set_bit_count[((a)>>16)&0xFF] + \ set_bit_count[((a)>>8)&0xFF] + \ set_bit_count[(a)&0xFF]) #define SET_ELEMENT_BIT_COUNT_64(a) (set_bit_count[(a)>>56] + \ set_bit_count[((a)>>48)&0xFF] + \ set_bit_count[((a)>>40)&0xFF] + \ set_bit_count[((a)>>32)&0xFF] + \ set_bit_count[((a)>>24)&0xFF] + \ set_bit_count[((a)>>16)&0xFF] + \ set_bit_count[((a)>>8)&0xFF] + \ set_bit_count[(a)&0xFF]) #if (ELEMENTSIZE==64) # define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_64(a) # define FULL_ELEMENT ((setelement)0xFFFFFFFFFFFFFFFF) #elif (ELEMENTSIZE==32) # define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_32(a) # define FULL_ELEMENT ((setelement)0xFFFFFFFF) #elif (ELEMENTSIZE==16) # define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_16(a) # define FULL_ELEMENT ((setelement)0xFFFF) #else # error "SET_ELEMENT_BIT_COUNT(a) not defined for current ELEMENTSIZE" #endif /*** Macros and functions ***/ /* * Gives a value with bit x (counting from lsb up) set. * * Making this as a table might speed up things on some machines * (though on most modern machines it's faster to shift instead of * using memory). Making it a macro makes it easy to change. */ #define SET_BIT_MASK(x) ((setelement)1<<(x)) /* Set element handling macros */ #define SET_ELEMENT_INTERSECT(a,b) ((a)&(b)) #define SET_ELEMENT_UNION(a,b) ((a)|(b)) #define SET_ELEMENT_DIFFERENCE(a,b) ((a)&(~(b))) #define SET_ELEMENT_CONTAINS(e,v) ((e)&SET_BIT_MASK(v)) /* Set handling macros */ #define SET_ADD_ELEMENT(s,a) \ ((s)[(a)/ELEMENTSIZE] |= SET_BIT_MASK((a)%ELEMENTSIZE)) #define SET_DEL_ELEMENT(s,a) \ ((s)[(a)/ELEMENTSIZE] &= ~SET_BIT_MASK((a)%ELEMENTSIZE)) #define SET_CONTAINS_FAST(s,a) (SET_ELEMENT_CONTAINS((s)[(a)/ELEMENTSIZE], \ (a)%ELEMENTSIZE)) #define SET_CONTAINS(s,a) (((a)<SET_MAX_SIZE(s))?SET_CONTAINS_FAST(s,a):FALSE) /* Sets can hold values between 0,...,SET_MAX_SIZE(s)-1 */ #define SET_MAX_SIZE(s) ((s)[-1]) /* Sets consist of an array of SET_ARRAY_LENGTH(s) setelements */ #define SET_ARRAY_LENGTH(s) (((s)[-1]+ELEMENTSIZE-1)/ELEMENTSIZE) /* * set_new() * * Create a new set that can hold values in the range 0,...,size-1. */ UNUSED_FUNCTION static set_t set_new(int size) { int n; set_t s; ASSERT(size>0); n=(size/ELEMENTSIZE+1)+1; s=calloc(n,sizeof(setelement)); s[0]=size; return &(s[1]); } /* * set_free() * * Free the memory associated with set s. */ UNUSED_FUNCTION INLINE static void set_free(set_t s) { ASSERT(s!=NULL); free(&(s[-1])); } /* * set_resize() * * Resizes set s to given size. If the size is less than SET_MAX_SIZE(s), * the last elements are dropped. * * Returns a pointer to the new set. */ UNUSED_FUNCTION INLINE static set_t set_resize(set_t s, int size) { int n; ASSERT(size>0); n=(size/ELEMENTSIZE+1); s=((setelement *)realloc(s-1,(n+1)*sizeof(setelement)))+1; if (n>SET_ARRAY_LENGTH(s)) memset(s+SET_ARRAY_LENGTH(s),0, (n-SET_ARRAY_LENGTH(s))*sizeof(setelement)); if (size < SET_MAX_SIZE(s)) s[(size-1)/ELEMENTSIZE] &= (FULL_ELEMENT >> (ELEMENTSIZE-size%ELEMENTSIZE)); s[-1]=size; return s; } /* * set_size() * * Returns the number of elements in set s. */ UNUSED_FUNCTION INLINE static int set_size(set_t s) { int count=0; setelement *c; for (c=s; c < s+SET_ARRAY_LENGTH(s); c++) count+=SET_ELEMENT_BIT_COUNT(*c); return count; } /* * set_duplicate() * * Returns a newly allocated duplicate of set s. */ UNUSED_FUNCTION INLINE static set_t set_duplicate(set_t s) { set_t new; new=set_new(SET_MAX_SIZE(s)); memcpy(new,s,SET_ARRAY_LENGTH(s)*sizeof(setelement)); return new; } /* * set_copy() * * Copies set src to dest. If dest is NULL, is equal to set_duplicate. * If dest smaller than src, it is freed and a new set of the same size as * src is returned. */ UNUSED_FUNCTION INLINE static set_t set_copy(set_t dest,set_t src) { if (dest==NULL) return set_duplicate(src); if (SET_MAX_SIZE(dest)<SET_MAX_SIZE(src)) { set_free(dest); return set_duplicate(src); } memcpy(dest,src,SET_ARRAY_LENGTH(src)*sizeof(setelement)); memset(dest+SET_ARRAY_LENGTH(src),0,((SET_ARRAY_LENGTH(dest) - SET_ARRAY_LENGTH(src)) * sizeof(setelement))); return dest; } /* * set_empty() * * Removes all elements from the set s. */ UNUSED_FUNCTION INLINE static void set_empty(set_t s) { memset(s,0,SET_ARRAY_LENGTH(s)*sizeof(setelement)); return; } /* * set_intersection() * * Store the intersection of sets a and b into res. If res is NULL, * a new set is created and the result is written to it. If res is * smaller than the larger one of a and b, it is freed and a new set * is created and the result is returned. * * Returns either res or a new set that has been allocated in its stead. * * Note: res may not be a or b. */ UNUSED_FUNCTION INLINE static set_t set_intersection(set_t res,set_t a,set_t b) { int i,max; if (res==NULL) { res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))); } else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) { set_free(res); res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))); } else { set_empty(res); } max=MIN(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b)); for (i=0; i<max; i++) { res[i]=SET_ELEMENT_INTERSECT(a[i],b[i]); } return res; } /* * set_union() * * Store the union of sets a and b into res. If res is NULL, a new set * is created and the result is written to it. If res is smaller than * the larger one of a and b, it is freed and a new set is created and * the result is returned. * * Returns either res or a new set that has been allocated in its stead. * * Note: res may not be a or b. */ UNUSED_FUNCTION INLINE static set_t set_union(set_t res,set_t a,set_t b) { int i,max; if (res==NULL) { res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))); } else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) { set_free(res); res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))); } else { set_empty(res); } max=MAX(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b)); for (i=0; i<max; i++) { res[i]=SET_ELEMENT_UNION(a[i],b[i]); } return res; } /* * set_return_next() * * Returns the smallest value in set s which is greater than n, or -1 if * such a value does not exist. * * Can be used to iterate through all values of s: * * int i=-1; * while ((i=set_return_next(s,i))>=0) { * // i is in set s * } */ UNUSED_FUNCTION INLINE static int set_return_next(set_t s, int n) { if (n<0) n=0; else n++; if (n >= SET_MAX_SIZE(s)) return -1; while (n%ELEMENTSIZE) { if (SET_CONTAINS(s,n)) return n; n++; if (n >= SET_MAX_SIZE(s)) return -1; } while (s[n/ELEMENTSIZE]==0) { n+=ELEMENTSIZE; if (n >= SET_MAX_SIZE(s)) return -1; } while (!SET_CONTAINS(s,n)) { n++; if (n >= SET_MAX_SIZE(s)) return -1; } return n; } /* * set_print() * * Prints the size and contents of set s to stdout. * Mainly useful for debugging purposes and trivial output. */ UNUSED_FUNCTION static void set_print(set_t s) { int i; printf("size=%d(max %d)",set_size(s),(int)SET_MAX_SIZE(s)); for (i=0; i<SET_MAX_SIZE(s); i++) if (SET_CONTAINS(s,i)) printf(" %d",i); printf("\n"); return; } #endif /* !CLIQUER_SET_H */