sparsevec.c

Serveez是一个服务器框架

    {
      for (chunk = spvec->last; chunk; chunk = chunk->prev)
	if (svz_spvec_range (chunk, index))
	  break;
    }
  else
    {
      for (chunk = spvec->first; chunk; chunk = chunk->next)
	if (svz_spvec_range (chunk, index))
	  break;
    }

  /* evaluate peeked chunk */
  if (!chunk)
    return NULL;
  idx = index - chunk->offset;

  /* is there any value at the given index ? */
  if (!(chunk->fill & (1 << idx)))
    return NULL;

  /* delete this value */
  chunk->fill &= ~(1 << idx);
  spvec->size--;
  spvec->length--;

  /* adjust chunk size */
  if (!(chunk->fill & ~((1 << idx) - 1)))
    {
      for (bit = 1 << idx; bit && !(chunk->fill & bit); bit >>= 1) 
	chunk->size--;
    }
  else
    chunk->size--;

  /* adjust sparse vector length */
  if (chunk == spvec->last)
    spvec->length = chunk->offset + chunk->size;

  value = chunk->value[idx];

  /* release this chunk if possible */
  if (chunk->size == 0)
    {
      assert (chunk->fill == 0);

      /* break here if the list is empty */
      if (spvec->size == 0)
	{
	  svz_free (chunk);
	  spvec->last = spvec->first = chunk = NULL;
	  spvec->length = 0;
	  return value;
	}

      /* rearrange sparse vector */
      svz_spvec_unhook (spvec, chunk);
      next = chunk->next;
      svz_free (chunk);
      chunk = next;
    }

  /* shuffle value data if necessary */
  else if (idx < chunk->size)
    {
      /* delete a bit */
      bit = (1 << idx) - 1;
      fill = chunk->fill;
      chunk->fill = (fill & bit) | ((fill >> 1) & ~bit);
      assert (chunk->fill);
	      
      /* delete a value */
      memmove (&chunk->value[idx], &chunk->value[idx + 1],
	       (chunk->size - idx) * sizeof (void *));
    }

  /* reduce array index offset by one */
  while (chunk)
    {
      if (chunk->offset > index)
	chunk->offset--;
      chunk = chunk->next;
    }

#if DEVEL
  sprintf (text, "post-delete (%lu) = %p", index, value);
  svz_spvec_validate (spvec, "delete");
#endif /* DEVEL */

  /* return deleted value */
  return value;
}

/*
 * Removes all of the elements whose index is between @var{from} (inclusive) 
 * and @var{to} (exclusive) from the sparse vector @var{spvec}. Returns the 
 * amount of actually deleted elements.
 */
unsigned long
svz_spvec_delete_range (svz_spvec_t *spvec, 
			unsigned long from, unsigned long to)
{
  unsigned long idx, n = 0;

#if DEVEL
  svz_spvec_validate (spvec, "delete range");
#endif /* DEVEL */

  /* swap the `to' and `from' indexes if necessary */
  if (to < from)
    {
      idx = to;
      to = from + 1;
      from = idx + 1;
    }

  /* return here if there is nothing to do */
  if (to > spvec->length)
    to = spvec->length;
  if (from > spvec->length)
    from = spvec->length;
  if (to == from)
    return 0;

  /* special case: delete all list elements */
  if (from == 0 && to == spvec->length)
    {
      n = spvec->size;
      svz_spvec_clear (spvec);
      return n;
    }

  /* go through the index range and delete each list item */
  for (idx = from; idx < to;)
    {
      if (svz_spvec_delete (spvec, idx))
	{
	  to--;
	  n++;
	}
      else
	idx++;
    }
  return n;
}

/*
 * Replaces the element at the specified position @var{index} in the sparse 
 * vector @var{spvec} by the specified element @var{value} and return its 
 * previous value.
 */
void *
svz_spvec_set (svz_spvec_t *spvec, unsigned long index, void *value)
{
  svz_spvec_chunk_t *chunk, *next;
  void *replace = NULL;
  unsigned long idx;

#if DEVEL
  svz_spvec_validate (spvec, "set");
#endif /* DEVEL */

  /* start at first or last chunk ? */
  chunk = svz_spvec_find_chunk (spvec, index);

  /* found a valid chunk ? */
  if (chunk)
    {
      idx = index - chunk->offset;

      /* already set ? */
      if (chunk->fill & (1 << idx))
	{
	  replace = chunk->value[idx];
	  chunk->value[idx] = value;
	  return replace;
	}
      /* no, just place the value there */
      else if (chunk->next == NULL || idx < chunk->size)
	{
	  chunk->fill |= (1 << idx);
	  if (idx >= chunk->size)
	    chunk->size = idx + 1;
	  spvec->size++;
	  if (spvec->length < chunk->offset + chunk->size)
	    spvec->length = chunk->offset + chunk->size;
	  chunk->value[idx] = value;
	  return replace;
	}
    }

  /* no chunk found, create one at the given offset */
  next = svz_spvec_create_chunk (index);
  next->value[0] = value;
  next->fill |= 1;
  next->size = 1;
  svz_spvec_hook (spvec, next);

  /* adjust list properties */
  spvec->size++;
  if (spvec->length <= next->offset)
    spvec->length = index + 1;

  /* return replaced value */
  return replace;
}

/*
 * Delete the element at the given position @var{index} from the sparse 
 * vector @var{spvec} but leave all following elements untouched 
 * (unlike @code{svz_spvec_delete()}). Return its previous value if there 
 * is one otherwise return @code{NULL}.
 */
void *
svz_spvec_unset (svz_spvec_t *spvec, unsigned long index)
{
  svz_spvec_chunk_t *chunk;
  void *unset = NULL;
  unsigned long idx, bit;

#if DEVEL
  svz_spvec_validate (spvec, "unset");
#endif /* DEVEL */

  /* return if index is invalid */
  if (index >= spvec->length)
    return NULL;

  /* find an appropriate chunk */
  if ((chunk = svz_spvec_find_chunk (spvec, index)) == NULL)
    return NULL;

  idx = index - chunk->offset;

  /* is there a value set ? */
  if (!(chunk->fill & (1 << idx)))
    return NULL;

  /* save unset value for returning it */
  unset = chunk->value[idx];

  /* delete this value */
  spvec->size--;
  chunk->fill &= ~(1 << idx);
  if (idx + 1 == chunk->size)
    for (bit = 1 << idx; bit && !(chunk->fill & bit); bit >>= 1)
      {
	chunk->size--;
	if (chunk == spvec->last)
	  spvec->length--;
      }
  if (chunk->size == 0)
    {
      svz_spvec_unhook (spvec, chunk);
      svz_free (chunk);
    }

  /* return unset value */
  return unset;
}

/*
 * Returns the number of elements in the sparse vector @var{spvec}.
 */
unsigned long
svz_spvec_size (svz_spvec_t *spvec)
{
#if DEVEL
  svz_spvec_validate (spvec, "size");
#endif /* DEVEL */

  return spvec->size;
}

/*
 * Returns the index of the last element of the sparse vector @var{spvec} 
 * plus one.
 */
unsigned long
svz_spvec_length (svz_spvec_t *spvec)
{
#if DEVEL
  svz_spvec_validate (spvec, "length");
#endif /* DEVEL */

  return spvec->length;
}

/*
 * Inserts the specified element @var{value} at the given position @var{index}
 * in the sparse vector @var{spvec}.
 */
void
svz_spvec_insert (svz_spvec_t *spvec, unsigned long index, void *value)
{
  svz_spvec_chunk_t *chunk, *next;
  unsigned long idx, fill, bit;

#if DEVEL
  svz_spvec_validate (spvec, "insert");
#endif /* DEVEL */

  /* start at first or last chunk ? */
  chunk = svz_spvec_find_chunk (spvec, index);

  /* found a valid chunk ? */
  if (chunk)
    {
      idx = index - chunk->offset;

      /* can the value be inserted here ? */
      if (chunk->size < SVZ_SPVEC_SIZE)
	{
	  /* adjust chunk size */
	  chunk->size++;
	  if (idx >= chunk->size)
	    chunk->size = idx + 1;

	  if (idx < chunk->size)
	    {
	      /* insert a bit */
	      bit = (1 << idx) - 1;
	      fill = chunk->fill;
	      chunk->fill = (fill & bit) | ((fill << 1) & ~bit);

	      /* shuffle value data */
	      memmove (&chunk->value[idx + 1], &chunk->value[idx],
		       (chunk->size - 1 - idx) * sizeof (void *));
	    }
	      
	  /* insert the value */
	  chunk->fill |= (1 << idx);
	  chunk->value[idx] = value;
	  chunk = chunk->next;
	}

      /* no, chunk is full, need to split the chunk */
      else
	{
	  next = svz_spvec_create_chunk (index + 1);

	  /* keep less indexes in old chunk and copy greater to next */
	  memcpy (next->value, &chunk->value[idx], 
		  (SVZ_SPVEC_SIZE - idx) * sizeof (void *));
	  next->fill = (chunk->fill >> idx);
	  next->size = SVZ_SPVEC_SIZE - idx;

	  chunk->value[idx] = value;
	  chunk->fill &= (1 << (idx + 1)) - 1;
	  chunk->fill |= (1 << idx);
	  chunk->size = idx + 1;

	  svz_spvec_hook (spvec, next);
	  chunk = next->next;
	}
    }

  /* add another chunk */
  else
    {
      next = svz_spvec_create_chunk (index);
      next->fill = 1;
      next->size = 1;
      next->value[0] = value;
      svz_spvec_hook (spvec, next);
      chunk = next->next;
    }

  /* adjust sparse vector properties here */
  if (++spvec->length < index + 1)
    spvec->length = index + 1;
  spvec->size++;

  /* increase offset of all later chunks */
  while (chunk)
    {
      if (chunk->offset > index)
	chunk->offset++;
      chunk = chunk->next;
    }
}

/*
 * Rearranges the given sparse vector @var{spvec}. After that there are no 
 * more gaps within the sparse vector. The index - value relationship gets 
 * totally lost by this operation.
 */
void
svz_spvec_pack (svz_spvec_t *spvec)
{
  svz_spvec_chunk_t *chunk, *next, *prev;
  unsigned long need2pack, bits, n, size;
  void **value;

#if DEVEL
  svz_spvec_validate (spvec, "pack");
#endif /* DEVEL */

  if (!spvec->size)
    return;

  /* first check if it is necessary to pack the chunks */
  for (need2pack = 0, chunk = spvec->first; chunk; chunk = chunk->next)
    {
      next = chunk->next;
      if (next && chunk->size == SVZ_SPVEC_SIZE)
	{
	  if (chunk->fill != SVZ_SPVEC_MASK ||
	      chunk->offset + SVZ_SPVEC_SIZE != next->offset)
	    {
	      need2pack = 1;
	      break;
	    }
	}
      if (next && chunk->size < SVZ_SPVEC_SIZE)
	{
	  need2pack = 1;
	  break;
	}
      if (!next)
	{
	  bits = (1 << (spvec->length - chunk->offset)) - 1;
	  if ((chunk->fill & bits) != bits)
	    {
	      need2pack = 1;
	      break;
	    }
	}
    }

  /* return if packing is not necessary */
  if (!need2pack)
    return;

  /* rebuild sparse vector */
  value = svz_spvec_values (spvec);
  size = svz_spvec_size (spvec);
  svz_spvec_clear (spvec);
  prev = spvec->first;
  for (n = 0; n <= size - SVZ_SPVEC_SIZE; n += SVZ_SPVEC_SIZE)
    {
      chunk = svz_spvec_create_chunk (n);
      chunk->fill = SVZ_SPVEC_MASK;
      chunk->size = SVZ_SPVEC_SIZE;
      spvec->size += SVZ_SPVEC_SIZE;
      memcpy (chunk->value, &value[n], SVZ_SPVEC_SIZE * sizeof (void *));
      if (!prev)
	spvec->first = chunk;
      else
	prev->next = chunk;
      chunk->prev = prev;
      prev = chunk;
    }
  if (size % SVZ_SPVEC_SIZE)
    {
      size %= SVZ_SPVEC_SIZE;
      chunk = svz_spvec_create_chunk (n);
      chunk->fill = (1 << size) - 1;
      chunk->size = size;
      spvec->size += size;
      memcpy (chunk->value, &value[n], size * sizeof (void *));
      if (!prev)
	spvec->first = chunk;
      else
	prev->next = chunk;
      chunk->prev = prev;
    }
  spvec->last = chunk;
  spvec->length = spvec->size;
  svz_free (value);
}

/*
 * Delivers all values within the given sparse vector @var{spvec} in a 
 * single linear chunk. You have to @code{svz_free()} it after usage.
 */
void **
svz_spvec_values (svz_spvec_t *spvec)
{
  svz_spvec_chunk_t *chunk;
  void **value;
  unsigned long index, bit, n;

#if DEVEL
  svz_spvec_validate (spvec, "values");
#endif /* DEVEL */

  if (!spvec->size) 
    return NULL;

  value = svz_malloc (spvec->size * sizeof (void *));
  for (index = 0, chunk = spvec->first; chunk; chunk = chunk->next) 
    {
      for (bit = 1, n = 0; n < chunk->size; bit <<= 1, n++)
	{
	  if (chunk->fill & bit)
	    value[index++] = chunk->value[n];
	  assert (index <= spvec->size);
	}
    }
  return value;
}