IndexSet.c File Reference

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "Hash.h"
#include "IndexSet.h"

Go to the source code of this file.

Macros
#define	_Class   _IndexSet
#define	INDEX_SET_CHUNK_SIZE   8

Functions
Class *	_IndexSet (void)
static void	addIndex (IndexSet *self, size_t index)
static void	addIndexes (IndexSet *self, size_t *indexes, size_t count)
static void	addIndexesInRange (IndexSet *self, const Range range)
static size_t	compact (size_t *indexes, size_t count)
	Sorts and compacts the given array to contain only unique values.
static int	compare (const void *a, const void *b)
	qsort comparator for indexes.
static bool	containsIndex (const IndexSet *self, size_t index)
static Object *	copy (const Object *self)
static void	dealloc (Object *self)
static String *	description (const Object *self)
static int	hash (const Object *self)
static IndexSet *	init (IndexSet *self)
static void	initialize (Class *clazz)
static IndexSet *	initWithCapacity (IndexSet *self, size_t capacity)
static IndexSet *	initWithIndex (IndexSet *self, size_t index)
static IndexSet *	initWithIndexes (IndexSet *self, size_t *indexes, size_t count)
static bool	isEqual (const Object *self, const Object *other)
static void	removeAllIndexes (IndexSet *self)
static void	removeIndex (IndexSet *self, size_t index)
static void	removeIndexes (IndexSet *self, size_t *indexes, size_t count)
static void	removeIndexesInRange (IndexSet *self, const Range range)

Macro Definition Documentation

_Class

#define _Class   _IndexSet

Definition at line 65 of file IndexSet.c.

INDEX_SET_CHUNK_SIZE

#define INDEX_SET_CHUNK_SIZE   8

Definition at line 67 of file IndexSet.c.

Function Documentation

_IndexSet()

Class * _IndexSet

(

void

)

Definition at line 370 of file IndexSet.c.

                       {
  static Class *clazz;
  static Once once;
 
  do_once(&once, {
    clazz = _initialize(&(const ClassDef) {
      .name = "IndexSet",
      .superclass = _Object(),
      .instanceSize = sizeof(IndexSet),
      .interfaceOffset = offsetof(IndexSet, interface),
      .interfaceSize = sizeof(IndexSetInterface),
      .initialize = initialize,
    });
  });
 
  return clazz;
}

addIndex()

static void addIndex ( IndexSet *  self, size_t  index  )

static

Definition at line 205 of file IndexSet.c.

                                                   {
 
  IndexSet *this = self;
 
  size_t i;
  for (i = 0; i < this->count; i++) {
    if (this->indexes[i] == index) {
      return;
    }
    if (this->indexes[i] > index) {
      break;
    }
  }
 
  if (this->count == self->capacity) {
    self->capacity += INDEX_SET_CHUNK_SIZE;
 
    this->indexes = realloc(this->indexes, self->capacity * sizeof(size_t));
    assert(this->indexes);
  }
 
  for (size_t j = this->count; j > i; j--) {
    this->indexes[j] = this->indexes[j - 1];
  }
 
  this->indexes[i] = index;
  this->count++;
}

addIndexes()

static void addIndexes ( IndexSet *  self, size_t *  indexes, size_t  count  )

static

Definition at line 238 of file IndexSet.c.

                                                                      {
 
  for (size_t i = 0; i < count; i++) {
    $(self, addIndex, indexes[i]);
  }
}

addIndexesInRange()

static void addIndexesInRange ( IndexSet *  self, const Range  range  )

static

Definition at line 252 of file IndexSet.c.

                                                                 {
 
  for (size_t i = range.location; i < range.location + range.length; i++) {
    $(self, addIndex, i);
  }
}

compact()

static size_t compact ( size_t *  indexes, size_t  count  )

static

Sorts and compacts the given array to contain only unique values.

Definition at line 46 of file IndexSet.c.

                                                     {
 
  size_t size = 0;
 
  if (count) {
    qsort(indexes, count, sizeof(size_t), compare);
 
    for (size_t i = 1; i < count; i++) {
      if (indexes[i] != indexes[size]) {
        indexes[++size] = indexes[i];
      }
    }
 
    size++;
  }
 
  return size;
}

compare()

static int compare ( const void *  a, const void *  b  )

static

qsort comparator for indexes.

Definition at line 35 of file IndexSet.c.

                                                 {
 
  const size_t sa = *(size_t *) a;
  const size_t sb = *(size_t *) b;
 
  return sa < sb ? -1 : sa > sb ? 1 : 0;
}

containsIndex()

static bool containsIndex ( const IndexSet *  self, size_t  index  )

static

Definition at line 157 of file IndexSet.c.

                                                              {
 
  for (size_t i = 0; i < self->count; i++) {
    if (self->indexes[i] == index) {
      return true;
    }
  }
 
  return false;
}

copy()

static Object * copy ( const Object *  self )

static

See also

Object::copy(const Object *)

Definition at line 74 of file IndexSet.c.

                                        {
 
  IndexSet *this = (IndexSet *) self;
  IndexSet *that = $(alloc(IndexSet), initWithIndexes, this->indexes, this->count);
 
  return (Object *) that;
}

dealloc()

static void dealloc ( Object *  self )

static

See also

Object::dealloc(Object *)

Definition at line 85 of file IndexSet.c.

                                  {
 
  IndexSet *this = (IndexSet *) self;
 
  free(this->indexes);
 
  super(Object, self, dealloc);
}

description()

static String * description ( const Object *  self )

static

See also

Object::description(const Object *)

Definition at line 97 of file IndexSet.c.

                                               {
 
  const IndexSet *this = (IndexSet *) self;
  String *desc = str("[");
 
  for (size_t i = 0; i < this->count; i++) {
    $(desc, appendFormat, "%d", this->indexes[i]);
    if (i < this->count - 1) {
      $(desc, appendCharacters, ", ");
    }
  }
 
  $(desc, appendCharacters, "]");
  return (String *) desc;
}

hash()

static int hash ( const Object *  self )

static

See also

Object::hash(const Object *)

Definition at line 116 of file IndexSet.c.

                                    {
 
  int hash = HASH_SEED;
 
  const IndexSet *this = (IndexSet *) self;
 
  for (size_t i = 0; i < this->count; i++) {
    hash = HashForInteger(hash, this->indexes[i]);
  }
 
  return hash;
}

init()

static IndexSet * init ( IndexSet *  self )

static

Definition at line 263 of file IndexSet.c.

                                      {
  return $(self, initWithCapacity, INDEX_SET_CHUNK_SIZE);
}

initialize()

static void initialize ( Class *  clazz )

static

See also

Class::initialize(Class *)

Definition at line 344 of file IndexSet.c.

                                     {
 
  ((ObjectInterface *) clazz->interface)->copy = copy;
  ((ObjectInterface *) clazz->interface)->dealloc = dealloc;
  ((ObjectInterface *) clazz->interface)->description = description;
  ((ObjectInterface *) clazz->interface)->hash = hash;
  ((ObjectInterface *) clazz->interface)->isEqual = isEqual;
 
  ((IndexSetInterface *) clazz->interface)->containsIndex = containsIndex;
  ((IndexSetInterface *) clazz->interface)->addIndex = addIndex;
  ((IndexSetInterface *) clazz->interface)->addIndexes = addIndexes;
  ((IndexSetInterface *) clazz->interface)->addIndexesInRange = addIndexesInRange;
  ((IndexSetInterface *) clazz->interface)->init = init;
  ((IndexSetInterface *) clazz->interface)->initWithCapacity = initWithCapacity;
  ((IndexSetInterface *) clazz->interface)->initWithIndex = initWithIndex;
  ((IndexSetInterface *) clazz->interface)->initWithIndexes = initWithIndexes;
  ((IndexSetInterface *) clazz->interface)->removeAllIndexes = removeAllIndexes;
  ((IndexSetInterface *) clazz->interface)->removeIndex = removeIndex;
  ((IndexSetInterface *) clazz->interface)->removeIndexes = removeIndexes;
  ((IndexSetInterface *) clazz->interface)->removeIndexesInRange = removeIndexesInRange;
}

initWithCapacity()

static IndexSet * initWithCapacity ( IndexSet *  self, size_t  capacity  )

static

Definition at line 271 of file IndexSet.c.

                                                                   {
 
  self = (IndexSet *) super(Object, self, init);
  if (self) {
    self->capacity = capacity;
 
    self->indexes = malloc(self->capacity * sizeof(size_t));
    assert(self->indexes);
  }
 
  return self;
}

initWithIndex()

static IndexSet * initWithIndex ( IndexSet *  self, size_t  index  )

static

Definition at line 172 of file IndexSet.c.

                                                             {
  return $(self, initWithIndexes, &index, 1);
}

initWithIndexes()

static IndexSet * initWithIndexes ( IndexSet *  self, size_t *  indexes, size_t  count  )

static

Definition at line 180 of file IndexSet.c.

                                                                                {
 
  self = (IndexSet *) super(Object, self, init);
  if (self) {
 
    self->count = compact(indexes, count);
    self->capacity = self->count;
    if (self->count) {
 
      self->indexes = calloc(sizeof(size_t), self->count);
      assert(self->indexes);
 
      memcpy(self->indexes, indexes, sizeof(size_t) * self->count);
    }
  }
 
  return self;
}

isEqual()

static bool isEqual ( const Object *  self, const Object *  other  )

static

See also

Object::isEqual(const Object *, const Object *)

Definition at line 132 of file IndexSet.c.

                                                             {
 
  if (super(Object, self, isEqual, other)) {
    return true;
  }
 
  if (other && $(other, isKindOfClass, _IndexSet())) {
 
    const IndexSet *this = (IndexSet *) self;
    const IndexSet *that = (IndexSet *) other;
 
    if (this->count == that->count) {
      return memcmp(this->indexes, that->indexes, this->count * sizeof(size_t)) == 0;
    }
  }
 
  return false;
}

removeAllIndexes()

static void removeAllIndexes ( IndexSet *  self )

static

Definition at line 288 of file IndexSet.c.

                                             {
 
  IndexSet *this = self;
 
  free(this->indexes);
  this->indexes = NULL;
 
  this->count = 0;
  self->capacity = 0;
}

removeIndex()

static void removeIndex ( IndexSet *  self, size_t  index  )

static

Definition at line 303 of file IndexSet.c.

                                                      {
 
  IndexSet *this = self;
  for (size_t i = 0; i < this->count; i++) {
    if (this->indexes[i] == index) {
      this->count--;
      for (size_t j = i; j < this->count; j++) {
        this->indexes[j] = this->indexes[j + 1];
      }
      return;
    }
  }
}

removeIndexes()

static void removeIndexes ( IndexSet *  self, size_t *  indexes, size_t  count  )

static

Definition at line 321 of file IndexSet.c.

                                                                         {
 
  for (size_t i = 0; i < count; i++) {
    $(self, removeIndex, indexes[i]);
  }
}

removeIndexesInRange()

static void removeIndexesInRange ( IndexSet *  self, const Range  range  )

static

Definition at line 332 of file IndexSet.c.

                                                                    {
 
  for (size_t i = range.location; i < range.location + range.length; i++) {
    $(self, removeIndex, i);
  }
}