stdcarr.c

来自「spines-ns」· C语言 代码 · 共 848 行 · 第 1/2 页

}

inline stdcarr_it *stdcarr_it_next(stdcarr_it *it) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
  STD_BOUNDS_CHECK(IS_VALID_IT(it));
  it->val = forward(it->carr, it->val, it->carr->vsize);
  return it;
}

inline stdcarr_it *stdcarr_it_advance(stdcarr_it *it, size_t num_advance) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
#ifdef STD_BOUNDS_CHECKS
  {
    stdcarr_it end;

    stdcarr_end(it->carr, &end);
    STD_BOUNDS_CHECK((size_t) stdcarr_it_compare(&end, it) >= num_advance);
  }
#endif
  it->val = forward(it->carr, it->val, num_advance * it->carr->vsize);
  return it;
}

inline stdcarr_it *stdcarr_it_prev(stdcarr_it *it) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
  STD_BOUNDS_CHECK(IS_LEGAL_IT(it) && it->val != it->carr->begin);
  it->val = backward(it->carr, it->val, it->carr->vsize);
  return it;
}

inline stdcarr_it *stdcarr_it_retreat(stdcarr_it *it, size_t num_retreat) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
#ifdef STD_BOUNDS_CHECKS
  {
    stdcarr_it begin;

    stdcarr_begin(it->carr, &begin);
    STD_BOUNDS_CHECK((size_t) stdcarr_it_compare(it, &begin) >= num_retreat);
  }
#endif
  it->val = backward(it->carr, it->val, num_retreat * it->carr->vsize);
  return it;
}

inline stdcarr_it *stdcarr_it_offset(stdcarr_it *it, stdssize_t offset) {
  return (offset >= 0 ? stdcarr_it_advance(it, (size_t) offset) :
	  stdcarr_it_retreat(it, (size_t) -offset));
}

/****************************** stdcarr interface *************************************/
/* Constructors, Destructor */
inline int stdcarr_construct(stdcarr *carr, size_t sizeof_val) {
  STD_CONSTRUCT_CHECK(!IS_CARR_INITED(carr));

  if (!(carr->vsize = sizeof_val))
    return STD_ERROR(STD_ILLEGAL_PARAM);

  carr->base       = 0;
  carr->endbase    = 0;
  carr->begin      = 0;
  carr->end        = 0;
  carr->size       = 0;
  carr->high_cap   = 0;
  carr->low_cap    = 0;
  carr->auto_alloc = stdtrue;

  INIT_CARR(carr);

  return STD_SUCCESS;
}

inline int stdcarr_copy_construct(stdcarr *dst, const stdcarr *src) {
  int ret;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(src));

  if ((ret = stdcarr_construct(dst, src->vsize)) != STD_SUCCESS)
    return STD_ERROR(ret);

  if ((dst->auto_alloc = src->auto_alloc)) {
    if (grow_mem(&dst->base, src->size, &dst->high_cap,
		 &dst->low_cap, src->vsize) == STD_MEM_FAILURE)
      return STD_ERROR(STD_MEM_FAILURE);
  } else {
    if (stdset_allocate(&dst->base, src->high_cap, &dst->high_cap,
			&dst->low_cap, src->vsize) == STD_MEM_FAILURE)
      return STD_ERROR(STD_MEM_FAILURE);
  }
  
  dst->endbase = dst->base + dst->high_cap * dst->vsize;
  dst->begin   = dst->base;
  dst->end     = copy_to_buf(dst->base, src, src->begin, src->end);
  dst->size    = src->size;

  return STD_SUCCESS;
}

inline void stdcarr_destruct(stdcarr *carr) {
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));

  if (carr->base) 
    free(carr->base); 

  UNINIT_CARR(carr);
}

/* Iterator Interface */
inline stdcarr_it *stdcarr_begin(const stdcarr *carr, stdcarr_it *it) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  it->carr = (stdcarr*) carr;
  it->val  = (char*) carr->begin;
  INIT_IT(it);
  return it;
}

inline stdcarr_it *stdcarr_last(const stdcarr *carr, stdcarr_it *it) {
  return stdcarr_it_prev(stdcarr_end(carr, it));
}

inline stdcarr_it *stdcarr_end(const stdcarr *carr, stdcarr_it *it) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  it->carr = (stdcarr*) carr;
  it->val  = (char*) carr->end;
  INIT_IT(it);
  return it;
}

inline stdcarr_it *stdcarr_get(const stdcarr *carr, stdcarr_it *it, size_t elem_num) { 
  return stdcarr_it_advance(stdcarr_begin(carr, it), elem_num);
}

/* Size and Capacity Information */
inline size_t stdcarr_size(const stdcarr *carr) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return carr->size; 
}

inline stdbool stdcarr_empty(const stdcarr *carr) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return carr->size == 0; 
}

/* carray can only fit carr->high_cap - 1 values before reallocation */
inline size_t stdcarr_high_capacity(const stdcarr *carr) {
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return carr->high_cap ? carr->high_cap - 1 : 0;
}

/* we reallocate when size equals low_cap (see comments from mem fcns) */
inline size_t stdcarr_low_capacity(const stdcarr *carr) {
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return carr->high_cap ? carr->low_cap + 1 : 0;
}

inline size_t stdcarr_max_size(const stdcarr *carr) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return STD_SIZE_T_MAX / carr->vsize; 
}

inline size_t stdcarr_val_size(const stdcarr *carr) { 
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return carr->vsize; 
}

/* Size and Capacity Operations */
inline int stdcarr_resize(stdcarr *carr, size_t num_elems) {
  stdssize_t delta_size;
  char *endptr;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));

  if ((delta_size = (num_elems - carr->size) * carr->vsize) <= 0) {
    delta_size = -delta_size;
    endptr = backward(carr, carr->end, delta_size);

    if (erase_shift(carr, &endptr, (size_t) delta_size, num_elems, stdfalse))
      return STD_ERROR(STD_MEM_FAILURE);
  } else { 
    endptr = carr->end;

    if (insert_shift(carr, &endptr, (size_t) delta_size, num_elems, stdtrue))
      return STD_ERROR(STD_MEM_FAILURE);
  }
  return STD_SUCCESS;
}

inline int stdcarr_clear(stdcarr *carr) {
  return stdcarr_resize(carr, 0);
}

inline int stdcarr_set_capacity(stdcarr *carr, size_t num_elems) {
  char *mem;
  stdssize_t diff;
  size_t new_cap = num_elems ? num_elems + 1 : 0;
  /* carray can only fit carr->high_cap - 1 values before reallocation */

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));

  switch (stdset_allocate(&mem, new_cap, &carr->high_cap, &carr->low_cap, carr->vsize)) {
  case STD_MEM_CHANGE:
    if ((diff = num_elems - carr->size) < 0) {
      carr->end  = backward(carr, carr->end, (size_t) -diff * carr->vsize);
      carr->size = num_elems;
    }
    if (carr->base) {
      copy_to_buf(mem, carr, carr->begin, carr->end);
      free(carr->base);
    }
    carr->base    = mem;
    carr->endbase = mem + carr->high_cap * carr->vsize;
    carr->begin   = mem;
    carr->end     = mem + carr->size * carr->vsize;
    return STD_SUCCESS;

  case STD_NO_MEM_CHANGE:
    return STD_SUCCESS;

  case STD_MEM_FAILURE:
    return STD_ERROR(STD_MEM_FAILURE);
    
  default:
    return STD_EXCEPTION(impossible value from stdset_allocate);
  }
}

inline int stdcarr_reserve(stdcarr *carr, size_t num_elems) {
  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  return (num_elems <= stdcarr_high_capacity(carr) ? STD_SUCCESS : 
	  stdcarr_set_capacity(carr, num_elems << 1));
}

inline int stdcarr_shrink_fit(stdcarr *carr) { 
  return stdcarr_set_capacity(carr, stdcarr_size(carr));
}

/* Stack Operations: amoritized O(1) operations */
inline int stdcarr_push_front(stdcarr *carr, const void *val) {
  return stdcarr_multi_push_front(carr, val, 1);
}

inline int stdcarr_pop_front(stdcarr *carr) {
  return stdcarr_multi_pop_front(carr, 1);
}

inline int stdcarr_push_back(stdcarr *carr, const void *val) {
  return stdcarr_multi_push_back(carr, val, 1);
}

inline int stdcarr_pop_back(stdcarr *carr) {
  return stdcarr_multi_pop_back(carr, 1);
}

inline int stdcarr_multi_push_front(stdcarr *carr, const void *vals, size_t num_push) {
  size_t delta = num_push * carr->vsize, new_size = carr->size + num_push, diff;
  char *begin_ptr = carr->begin;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  if (insert_shift(carr, &begin_ptr, delta, new_size, stdfalse))
    return STD_ERROR(STD_MEM_FAILURE);

  if ((diff = (size_t) (carr->endbase - carr->begin)) >= delta)
    memcpy(carr->begin, vals, delta);
  else {
    memcpy(carr->begin, vals, diff);
    memcpy(carr->base, (char*) vals + diff, (size_t) (delta - diff));
  }
  return STD_SUCCESS;
}

inline int stdcarr_multi_pop_front(stdcarr *carr, size_t num_pop) {
  size_t delta = num_pop * carr->vsize, new_size = carr->size - num_pop;
  char *begin_ptr = carr->begin;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  STD_BOUNDS_CHECK(num_pop <= stdcarr_size(carr));
  if (erase_shift(carr, &begin_ptr, delta, new_size, stdtrue))
    return STD_ERROR(STD_MEM_FAILURE);

  return STD_SUCCESS;
}

inline int stdcarr_multi_push_back(stdcarr *carr, const void *vals, size_t num_push) {
  size_t delta = num_push * carr->vsize, new_size = carr->size + num_push, diff;
  char *it = carr->end;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  if (insert_shift(carr, &it, delta, new_size, stdtrue))
    return STD_ERROR(STD_MEM_FAILURE);

  if ((diff = (size_t) (carr->endbase - it)) >= delta)
    memcpy(it, vals, delta);
  else {
    memcpy(it, vals, diff);
    memcpy(carr->base, (char*) vals + diff, (size_t) (delta - diff));
  }
  return STD_SUCCESS;
}

inline int stdcarr_multi_pop_back(stdcarr *carr, size_t num_pop) {
  size_t delta = num_pop * carr->vsize, new_size = carr->size - num_pop;
  char *end_ptr;

  STD_CONSTRUCT_CHECK(IS_CARR_INITED(carr));
  STD_BOUNDS_CHECK(num_pop <= stdcarr_size(carr));

  end_ptr = backward(carr, carr->end, delta);
  if (erase_shift(carr, &end_ptr, delta, new_size, stdfalse))
    return STD_ERROR(STD_MEM_FAILURE);

  return STD_SUCCESS;
}

/* List Operations: O(n) operations */
inline stdcarr_it *stdcarr_insert(stdcarr_it *it, const void *val) {
  return stdcarr_multi_insert(it, val, 1);
}

inline stdcarr_it *stdcarr_erase(stdcarr_it *it) {
  return stdcarr_multi_erase(it, 1);
}

inline stdcarr_it *stdcarr_repeat_insert(stdcarr_it *it, const void *val, size_t num_times) {
  size_t delta, new_size;
  char *tmp = it->val;     /* tmp is it->val */
  stdbool shift_right;
  stdssize_t diff;

  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
  STD_BOUNDS_CHECK(IS_LEGAL_IT(it));

  delta    = num_times * it->carr->vsize;
  new_size = it->carr->size + num_times;

  /* determine whether it is cheaper to shift_right or to shift_left */
  if ((diff = tmp - it->carr->begin) >= 0) /* it is above carr->begin */
    shift_right = (diff / it->carr->vsize > (stdcarr_size(it->carr) >> 1));
  else 
    shift_right = ((it->carr->end - tmp) / it->carr->vsize <= (stdcarr_size(it->carr) >> 1));

  if (insert_shift(it->carr, &tmp, delta, new_size, (stdbool) shift_right))
    return (stdcarr_it*) STD_ERROR(STD_MEM_FAILURE2);
  
  it->val = tmp;
  for (; num_times--; tmp = forward(it->carr, tmp, it->carr->vsize))
    memcpy(tmp, val, it->carr->vsize);
  
  return it;
}

inline stdcarr_it *stdcarr_multi_insert(stdcarr_it *it, const void *vals, size_t num_insert) {
  size_t delta, new_size;
  char *tmp = it->val;
  int shift_right;
  stdssize_t diff;

  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
  STD_BOUNDS_CHECK(IS_LEGAL_IT(it));

  delta    = num_insert * it->carr->vsize;
  new_size = it->carr->size + num_insert;

  /* determine whether it is cheaper to shift_right or to shift_left */
  if ((diff = tmp - it->carr->begin) >= 0) /* it is above carr->begin */
    shift_right = (diff / it->carr->vsize > stdcarr_size(it->carr) >> 1);
  else 
    shift_right = ((it->carr->end - tmp) / it->carr->vsize <= stdcarr_size(it->carr) >> 1);

  if (insert_shift(it->carr, &tmp, delta, new_size, (stdbool) shift_right))
    return (stdcarr_it*) STD_ERROR(STD_MEM_FAILURE2);

  it->val = tmp;
  if (((size_t)(diff = it->carr->endbase - tmp)) >= delta)
    memcpy(tmp, vals, delta);
  else {
    memcpy(tmp, vals, (size_t) diff);
    memcpy(it->carr->base, (char*) vals + diff, (size_t) (delta - diff));
  }
  return it;
}

inline stdcarr_it *stdcarr_multi_erase(stdcarr_it *it, size_t num_erase) {
  size_t delta, new_size;
  char *tmp = it->val;
  stdbool shift_right;
  stdssize_t diff;

  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_CARR_INITED(it->carr));
#ifdef STD_BOUNDS_CHECKS
  {
    stdcarr_it end;
    
    stdcarr_end(it->carr, &end);
    STD_BOUNDS_CHECK((size_t) stdcarr_it_compare(&end, it) >= num_erase);
  }
#endif

  delta    = num_erase * it->carr->vsize;
  new_size = it->carr->size - num_erase;

  /* determine whether it is cheaper to shift_right or to !shift_right */  
  if ((diff = tmp - it->carr->begin) >= 0) {
    shift_right = (diff / it->carr->vsize < ((stdcarr_size(it->carr) - num_erase) >> 1));
  } else
    /* although this looks wrong, it's right -- make sure you think really hard and work
       it out on paper before changing this */
    shift_right = ((it->carr->end - tmp) / it->carr->vsize >= 
		   ((stdcarr_size(it->carr) + num_erase) >> 1));

  if (erase_shift(it->carr, &tmp, delta, new_size, (stdbool) shift_right))
    return (stdcarr_it*) STD_ERROR(STD_MEM_FAILURE2);

  it->val = tmp;	     
  return it;
}

/* Data Structure Options */
inline stdbool stdcarr_get_auto_alloc(const stdcarr *arr) {
  return arr->auto_alloc;
}

inline void stdcarr_set_auto_alloc(stdcarr *arr, stdbool use_auto_alloc) { 
  arr->auto_alloc = use_auto_alloc;
}