sets in C

[Frank Swarbrick]

A few day ago I wrote a messages asking why something like foo({1,2,3,4}) is
not allowed.  I suppose the reasons make some sense, but I still think
that something like foo((int []){1,2,3,4}) or foo((int *){1,2,3,4}) should be
allowed.  You will see the reason I did not even think of this second way at
the time is because my "foo" is actually declaired as foo(void *), so it
wouldn't really matter what type of pointer you cast it too.

Anyway, the following program is my attempt to allow some type of sets
in C.  Maybe my Pascal background is obscuring my seeing a better way
of doing this, but at least it was a learning experience for me.  The program
is three files, really, but you'll have to split them up yourself if you want
to use them.  And you can use them, if you like.  The third one is just two
"main" functions to make it easier for you to understand how to use the
functions.  I must admit that I'm not very good at documentation.

--------------------------CUT HERE------------------------------------------
/* sets.h

   Header file for sets.c

   Written by Frank Swarbrick, April/May 1988
   May be used without permission.
*/

#include <mem.h>

#ifndef _BYTE
#define _BYTE
typedef unsigned char byte;
#endif
#ifndef _BOOL
#define _BOOL
typedef enum {false = 0, true = !false} bool;
#endif

int whereinset(const void *el, const void *set, size_t setsize,
               size_t typesize);
void *setplus(const void *el, void *set, size_t *setsize, size_t typesize);
void *setminus(const void *el, void *set, size_t *setsize, size_t typesize);

#define inset(a,b,c,d) (whereinset((a),(b),(c),(d)) != -1)

/* sets.c

   Set functions.

   Written by Frank Swarbrick, April/May 1988
   May be used without permission.
*/

#include "sets.h"
#include <stdio.h>
#include <alloc.h>
#include <process.h>

/* whereinset()
 *
 * *el points to the element you are searching for.  set is what you are
 * searching.  *set may be either a pointer to a scalar type or an array
 * of a scalar type.  setsize is how many elements are in the set, and
 * typesize is the size of whatever el and set point to.  This function
 * returns the position in set where *el first occurs, or it returns -1
 * if *el cannot be found in set.
 */
int whereinset(const void *el, const void *set, size_t setsize,
               size_t typesize)
{
   register int i, j;  /* loop variables */
   register bool in = false;

   /* go through each element of the set */
   for (i = 0; !in && i < setsize * typesize; i += typesize)
   {
      in = true;
      /* compare the set to the element; byte by byte */
      for (j = 0; in && j < typesize; j++)
         in = (*((byte *)el+j) == *((byte *)set+i+j));
   }
   return (in) ? (i/typesize)-1 : -1;
}

/* setplus()
 *
 * set *must* be a pointer to a scalar type.  It cannot be an array.  el
 * is the same as in whereinset().  setsize is a *pointer* to the size of
 * the set.  typesize is the same as in whereinset().  This function adds
 * *el to the set.  It returns the set with *el added.  *setsize is
 * incremented.
 */
void *setplus(const void *el, void *set, size_t *setsize, size_t typesize)
{
   register int i;  /* loop variable */

   (byte *)set = (*setsize == 0) ? (byte *)malloc(typesize) :
                                 (byte *)realloc(set, (*setsize+1)*typesize);
   if (set == NULL)
   {
      fprintf(stderr, "Out of memory\n");
      exit(1);
   }
   /* add the element to the end of the set; byte by byte */
   for (i = 0; i < typesize; i++)
      *((byte *)set+(*setsize*typesize+i)) = *((byte *)el+i);
   (*setsize)++;
   return set;
}

/* setminus()
 *
 * All values are the same as setplus().  This function first makes sure that
 * *el is in the set.  If *el is in the set, it takes it out and returns the
 * new set.  If *el is not in the set it just returns the old set.
 */
void *setminus(const void *el, void *set, size_t *setsize, size_t typesize)
{
   register int p;  /* position of element in set */

   if ((p = whereinset(el, set, *setsize, typesize)) != -1)
   {
      p *= typesize;
      /* move remainder of set over the top of removed element */
      memmove((byte *)set+p, (byte *)set+p+typesize, (*setsize-1)*typesize-p);
      (*setsize)--;
   }
   return set;
}

/* settest.c

   Tests set functions.  Link with sets.c.

   Written by Frank Swarbrick, April/May 1988.
*/

#include "sets.h"
#include <stdio.h>

/* uncomment one of these depending on which main() you want to use */
/* #define MAIN1 */
/* #define MAIN2 */

#ifdef MAIN1
void main()
{
   unsigned amt;  /* number of elements to be put in set */
   long *longset;  /* set of long integers */
   long el;  /* element of set to be added or removed */
   unsigned count = 0;  /* number of elements actually in set */
   register int i;  /* loop variable */

   longset = NULL;  /* must be done to get rid of annoying warning */
   printf("How many elements? ");
   scanf("%d", &amt);
   /* get elements and add them to the set */
   for (i = 0; i < amt; i++)
   {
      printf("\n#%d:  ", i+1);
      scanf("%ld", &el);
      longset = (long *)setplus(&el, longset, &count, sizeof(*longset));
   }
   /* while there are still elements in the set display them and ask what
      elements to remove */
   while (count > 0)
   {
      for (i = 0; i < count; i++)
         printf("%ld ", longset[i]);
      printf("\nDispose of what number? ", longset);
      scanf("%ld", &el);
      longset = (long *)setminus(&el, longset, &count, sizeof(*longset));
   }
}
#endif

#ifdef MAIN2
void main()
{
   /* constant set of unsigned integers */
   const unsigned intset[] = {0U, 12U, 2112U, 255U, 256U, 32767U, 65535U};
   unsigned num;  /* number to be searched for in set */

   printf("Type a number:  ");
   scanf("%u", &num);
   if   (inset(&num, intset, sizeof(intset)/sizeof(*intset), sizeof(*intset)))
      printf("%u is in the set\n", num);
   else
      printf("%u is not in the set\n", num);
}
#endif

Frank Swarbrick (and his cat)           swarbric at tramp.Colorado.EDU
...!{ncar|nbires}!boulder!tramp!swarbric
"Live to Rock -- Rock to live"