view release on metacpan or  search on metacpan

ds_iset.c  view on Meta::CPAN

}

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;