File Coverage

ds_iset.c

Criterion	Covered	Total	%
statement	54	170	31.7
branch	31	148	20.9
condition			n/a
subroutine			n/a
pod			n/a
total	85	318	26.7

#include
#include
#include

#include "ptypes.h"
#include "ds_iset.h"
#include "util.h"
#include "sort.h"

#define FILL_RATIO 0.55

#if BITS_PER_WORD == 32
/* 16 0x45d9f3b  16 0x45d9f3b  16 */
/* 16 0x21f0aaad 15 0x735a2d97 15 */
static UV _hash(UV x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}
#else
/* 30 0xbf58476d1ce4e5b9 27 0x94d049bb133111eb 31     SplitMix64/Meuller */
/* 32 0xd6e8feb86659fd93 32 0xd6e8feb86659fd93 32     degski */
/* 33 0xff51afd7ed558ccd 33 0xc4ceb9fe1a85ec53 33     Murmur64 */
/* 32 0xe9846af9b1a615d  32 0xe9846af9b1a615d  28     xmxmx */
/* 32 0xbea225f9eb34556d 29 0xbea225f9eb34556d 32 0xbea225f9eb34556d 29   mx3 */

static UV _hash(UV x) {
    x = (x ^ (x >> 32)) * UVCONST(0xe9846af9b1a615d);
    x = (x ^ (x >> 32)) * UVCONST(0xe9846af9b1a615d);
    x =  x ^ (x >> 28);
    return x;
}
#endif

#define HVAL(x,mask) (_hash(x) & mask)

/******************************************************************************/

iset_t iset_create(size_t init_size) {
  iset_t set;
  int bits = 4;
  const int maxsizebits = 8 * sizeof(size_t);

  set.size = 0;  set.contains_zero = 0;  set.type = 0;

  while (bits < maxsizebits-1 && ((1UL << bits) * FILL_RATIO + 1) < init_size)
    bits++;
  set.maxsize = 1UL << bits;
  set.mask = set.maxsize - 1;
  Newz(0, set.arr, set.maxsize, UV);
  return set;
}

void iset_destroy(iset_t *set) {
  set->maxsize = 0;  set->size = 0;  set->contains_zero = 0;  set->type = 0;
  Safefree(set->arr);
  set->arr = 0;
}

static size_t _iset_pos(const UV* arr, UV mask, UV val) {
  size_t h = HVAL(val,mask);
  while (arr[h] != 0 && arr[h] != val)
    h = (h+1) & mask;
  return h;
}

bool iset_contains(const iset_t set, UV val) {
  if (val == 0) return set.contains_zero;
  return set.arr[_iset_pos(set.arr, set.mask, val)] == val;
}

static void _iset_resize(iset_t *set) {
  UV v, *narr;
  size_t i, oldsize, newsize, newmask;

  oldsize = set->maxsize;
  newsize = oldsize << 1;
  if (newsize < oldsize) croak("iset: max set size overflow");
  newmask = newsize - 1;

  Newz(0, narr, newsize, UV);
  for (i = 0; i < oldsize; i++)
    if (v = set->arr[i], v != 0)
      narr[ _iset_pos(narr,newmask,v) ] = v;
  Safefree(set->arr);
  set->arr = narr;
  set->maxsize = newsize;
  set->mask = newmask;
}

bool iset_add(iset_t *set, UV val, int sign) {
  if (sign == 0)
    set->type = ISET_TYPE_INVALID;
  else if (val > (UV)IV_MAX)
    set->type |= ((sign > 0) ? ISET_TYPE_UV : ISET_TYPE_IV);
  if (val == 0) {
    if (set->contains_zero)
      return 0;
    set->contains_zero = 1;
    set->size++;
  } else {
    size_t h = _iset_pos(set->arr, set->mask, val);
    if (set->arr[h] == val)
      return 0;
    set->arr[h] = val;
    if (++set->size > FILL_RATIO * (double)set->maxsize)
      _iset_resize(set);
  }
  return 1;
}

iset_t iset_create_from_array(UV* d, size_t dlen, int dsign) {
  iset_t s = iset_create(dlen);

  if (dsign != 0) {
    unsigned char typemask = ((dsign > 0) ? ISET_TYPE_UV : ISET_TYPE_IV);
    size_t i;
    for (i = 0; i < dlen; i++) {
      UV val = d[i];
      if (val == 0) {
        if (!s.contains_zero) { s.contains_zero = 1;  s.size++; }
      } else {
        size_t h = _iset_pos(s.arr, s.mask, val);
        if (s.arr[h] != val) {
          s.arr[h] = val;
          if (++s.size > FILL_RATIO * (double)s.maxsize)
            _iset_resize(&s);
        }
        if (val > (UV)IV_MAX)
          s.type |= typemask;
      }
    }
  }
  return s;
}

void iset_allvals(const iset_t set, UV* array) {
  size_t j, i = 0;
  if (set.contains_zero)
    array[i++] = 0;
  for (j = 0; j < set.maxsize; j++)
    if (set.arr[j] != 0)
      array[i++] = set.arr[j];
  if (i != set.size) croak("iset_allvals bad size");
  if (set.type == ISET_TYPE_IV) sort_iv_array((IV*)array, i);
  else                          sort_uv_array(array, i);
}

#if 0
void iset_minmax(const iset_t set, UV *min, UV *max) {
  size_t i;

  *min = *max = 0;
  if (set.type == ISET_TYPE_INVALID || set.size == 0)
    return;

  if (set.type != ISET_TYPE_IV) {
    if (!set.contains_zero)  { *min = UV_MAX; }
    for (i = 0; i < set.maxsize; i++) {
      UV v = set.arr[i];
      if (v != 0) {
        if (v < *min) *min = v;
        if (v > *max) *max = v;
      }
    }
  } else {
    IV smin = set.contains_zero ? 0 : IV_MAX;
    IV smax = set.contains_zero ? 0 : IV_MIN;
    for (i = 0; i < set.maxsize; i++) {
      IV sv = (IV) set.arr[i];
      if (sv != 0) {
        if (sv < smin) smin = sv;
        if (sv > smax) smax = sv;
      }
    }
    *min = (UV)smin;
    *max = (UV)smax;
  }
}
#endif


/******************************************************************************/

void iset_union_with(iset_t *set, const iset_t L) {
  size_t i, lsize;
  UV v, *larr;
  int lsign = iset_sign(L);

  lsize = L.maxsize;
  larr = L.arr;
  for (i = 0; i < lsize; i++)
    if (v = larr[i], v != 0)
      iset_add(set, v, lsign);
  if (L.contains_zero && !set->contains_zero)  iset_add(set,0,1);
}

void iset_intersect_with(iset_t *set, const iset_t L) {
  iset_t s = iset_intersection_of(*set, L);
  iset_destroy(set);
  *set = s;
}

void iset_difference_with(iset_t *set, const iset_t L) {
  iset_t s = iset_difference_of(*set, L);
  iset_destroy(set);
  *set = s;
}

void iset_symdiff_with(iset_t *set, const iset_t L) {
  iset_t s = iset_symdiff_of(*set, L);
  iset_destroy(set);
  *set = s;
}

/******************************************************************************/

iset_t iset_union_of(const iset_t A, const iset_t B) {
  size_t i;
  UV v;
  int asign = iset_sign(A), bsign = iset_sign(B);
  iset_t s = iset_create(A.size + B.size);

  for (i = 0; i < A.maxsize; i++)
    if (v = A.arr[i], v != 0)
      iset_add(&s, v, asign);
  for (i = 0; i < B.maxsize; i++)
    if (v = B.arr[i], v != 0)
      iset_add(&s, v, bsign);
  if (A.contains_zero || B.contains_zero)  iset_add(&s,0,1);
  return s;
}

iset_t iset_intersection_of(const iset_t A, const iset_t B) {
  int asign = iset_sign(A), bsign = iset_sign(B);
  int samesign = (asign == bsign);
  size_t i;
  UV v;
  iset_t s;

  if (A.size > B.size)               /* Swap for performance. */
    return iset_intersection_of(B,A);

  s = iset_create((A.size < B.size) ? A.size : B.size);

  for (i = 0; i < A.maxsize; i++)
    if (v = A.arr[i], v != 0)
      if ( !((v > (UV)IV_MAX) && !samesign) && iset_contains(B, v))
        iset_add(&s, v, asign);
  if (A.contains_zero && B.contains_zero)  iset_add(&s,0,1);
  return s;
}
iset_t iset_difference_of(const iset_t A, const iset_t B) {
  int asign = iset_sign(A), bsign = iset_sign(B);
  int samesign = (asign == bsign);
  size_t i;
  UV v;
  iset_t s = iset_create((A.size > B.size) ? A.size : B.size);

  for (i = 0; i < A.maxsize; i++)
    if (v = A.arr[i], v != 0)
      if ( ((v > (UV)IV_MAX) && !samesign) || !iset_contains(B, v) )
        iset_add(&s, v, asign);
  if (A.contains_zero && !B.contains_zero)  iset_add(&s,0,1);
  return s;
}
iset_t iset_symdiff_of(const iset_t A, const iset_t B) {
  int asign = iset_sign(A), bsign = iset_sign(B);
  int samesign = (asign == bsign);
  size_t i;
  UV v;
  iset_t s = iset_create((A.size > B.size) ? A.size : B.size);

  for (i = 0; i < A.maxsize; i++)
    if (v = A.arr[i], v != 0)
      if ( ((v > (UV)IV_MAX) && !samesign) || !iset_contains(B, v) )
        iset_add(&s, v, asign);
  for (i = 0; i < B.maxsize; i++)
    if (v = B.arr[i], v != 0)
      if ( ((v > (UV)IV_MAX) && !samesign) || !iset_contains(A, v) )
        iset_add(&s, v, bsign);
  if ((A.contains_zero + B.contains_zero) == 1)  iset_add(&s,0,1);
  return s;
}
bool iset_is_subset_of(const iset_t A, const iset_t B) {
  int samesign = (iset_sign(A) == iset_sign(B));
  size_t i;
  UV v;

  if (A.size > B.size)
    return 0;
  if (A.contains_zero && !B.contains_zero)
    return 0;
  for (i = 0; i < A.maxsize; i++)
    if (v = A.arr[i], v != 0)
      if ( ((v > (UV)IV_MAX) && !samesign) || !iset_contains(B, v) )
        return 0;
  return 1;
}

/******************************************************************************/

void iset_test(void) {
#if 0
  iset_t s;
  UV *S;
  size_t i;
  const size_t ts = 30000000;

  printf("create .. "); fflush(stdout);
  s = iset_create(0);
  printf("done\n"); fflush(stdout);
  for (i = ts/2; i < ts; i++) {
    iset_add(&s, i, 1);
  }
  printf("done adding.  size is %lu\n", (unsigned long)iset_size(s)); fflush(stdout);
  if (iset_contains(s,0) != 0) croak("fail 0");
  for (i = 0; i < ts; i++) {
    iset_add(&s, i, 1);
  }
  printf("done adding.  size is %lu\n", (unsigned long)iset_size(s)); fflush(stdout);

  if (iset_contains(s,1) != 1) croak("fail 1");
  if (iset_contains(s,ts-1) != 1) croak("fail 999");
  if (iset_contains(s,ts) != 0) croak("fail 1000");
  if (iset_contains(s,0) != 1) croak("fail 0");
  if (iset_sign(s) != 1) croak("fail sign");
  if (iset_is_invalid(s) != 0) croak("fail invalid");
  if (iset_size(s) != ts) croak("fail size");

  New(0,S,iset_size(s),UV);
  iset_allvals(s,S);
  for (i = 0; i < ts; i++)
    if (S[i] != i)
      croak("fail element %lu expected %lu got %lu\n", (unsigned long)i, (unsigned long)i, S[i]);
  iset_destroy(&s);
#endif
}