src/intset.c

   1 #include <stdlib.h>
   2 #include <stdbool.h>
   3
   4 #include "intset.h"
   5
   6 typedef struct intset {
   7     int *arr;
   8     size_t length;
   9     size_t capacity;
  10 } intset;
  11
  12 intset *
  13 intset_new()
  14 {
  15     intset *set = malloc(sizeof(intset));
  16     set->arr = malloc(sizeof(int) * 10);
  17     set->length = 0;
  18     set->capacity = 10;
  19     return set;
  20 }
  21
  22 void
  23 intset_free(intset *set)
  24 {
  25     if (set) {
  26         free(set->arr);
  27         free(set);
  28     }
  29 }
  30
  31 static int
  32 intset_cmp(const void *a, const void *b)
  33 {
  34     int x = *(int *)a, y = *(int *)b;
  35     if (x < y) {
  36         return -1;
  37     } else if (x > y) {
  38         return 1;
  39     }
  40     return 0;
  41 }
  42
  43 void
  44 intset_add(intset *set, int item)
  45 {
  46     if (intset_contains(set, item)) {
  47         return;
  48     }
  49
  50     if (set->length + 1 > set->capacity) {
  51         set->capacity *= 2;
  52         set->arr = realloc(set->arr, sizeof(int) * set->capacity);
  53     }
  54     set->arr[set->length] = item;
  55     set->length++;
  56     qsort(set->arr, set->length, sizeof(int), intset_cmp);
  57 }
  58
  59 bool
  60 intset_contains(intset *set, int item)
  61 {
  62     void *found = bsearch(&item, set->arr, set->length, sizeof(int), intset_cmp);
  63     return found != NULL;
  64 }