Dictionary.c File Reference

#include <assert.h>
#include <stdarg.h>
#include <stdlib.h>
#include "Dictionary.h"
#include "Hash.h"
#include "String.h"
#include "Null.h"

Go to the source code of this file.

Macros
#define	_Class   _Dictionary
#define	DICTIONARY_DEFAULT_CAPACITY   64
#define	DICTIONARY_GROW_FACTOR   2.0
#define	DICTIONARY_MAX_LOAD   0.75f

Functions
Class *	_Dictionary (void)
static void	addEntriesFromDictionary (Dictionary *self, const Dictionary *dictionary)
static void	addEntriesFromDictionary_enumerator (const Dictionary *dict, ident obj, ident key, ident data)
	DictionaryEnumerator for addEntriesFromDictionary.
static Array *	allKeys (const Dictionary *self)
static void	allKeys_enumerator (const Dictionary *dict, ident obj, ident key, ident data)
	DictionaryEnumerator for allKeys.
static Array *	allObjects (const Dictionary *self)
static void	allObjects_enumerator (const Dictionary *dict, ident obj, ident key, ident data)
	DictionaryEnumerator for allObjects.
static bool	containsKey (const Dictionary *self, const ident key)
static bool	containsKeyPath (const Dictionary *self, const char *path)
static Object *	copy (const Object *self)
static void	dealloc (Object *self)
static String *	description (const Object *self)
static void	description_enumerator (const Dictionary *dict, ident obj, ident key, ident data)
	A DictionaryEnumerator for description.
static Dictionary *	dictionary (void)
static Dictionary *	dictionaryWithCapacity (size_t capacity)
static Dictionary *	dictionaryWithDictionary (const Dictionary *dictionary)
static Dictionary *	dictionaryWithObjectsAndKeys (ident obj,...)
static void	enumerateObjectsAndKeys (const Dictionary *self, DictionaryEnumerator enumerator, ident data)
static Dictionary *	filterObjectsAndKeys (const Dictionary *self, DictionaryPredicate predicate, ident data)
static int	hash (const Object *self)
static Dictionary *	init (Dictionary *self)
static void	initialize (Class *clazz)
static Dictionary *	initWithCapacity (Dictionary *self, size_t capacity)
static Dictionary *	initWithDictionary (Dictionary *self, const Dictionary *dictionary)
static Dictionary *	initWithObjectsAndKeys (Dictionary *self,...)
static bool	isEqual (const Object *self, const Object *other)
static ident	objectForKey (const Dictionary *self, const ident key)
static ident	objectForKeyPath (const Dictionary *self, const char *path)
static ident	objectForKeyPathWithClass (const Dictionary *self, const char *path, const Class *clazz)
static void	removeAllObjects (Dictionary *self)
static void	removeAllObjectsWithEnumerator (Dictionary *self, DictionaryEnumerator enumerator, ident data)
static void	removeObjectForKey (Dictionary *self, const ident key)
static void	removeObjectForKeyPath (Dictionary *self, const char *path)
static void	setObjectForKey (Dictionary *self, const ident obj, const ident key)
static void	setObjectForKey_resize (Dictionary *dict)
	A helper for resizing Dictionaries as pairs are added to them.
static void	setObjectForKeyPath (Dictionary *self, const ident obj, const char *path)
static void	setObjectsForKeyPaths (Dictionary *self,...)
static void	setObjectsForKeys (Dictionary *self,...)

Macro Definition Documentation

_Class

#define _Class   _Dictionary

Definition at line 33 of file Dictionary.c.

DICTIONARY_DEFAULT_CAPACITY

#define DICTIONARY_DEFAULT_CAPACITY   64

Definition at line 35 of file Dictionary.c.

DICTIONARY_GROW_FACTOR

#define DICTIONARY_GROW_FACTOR   2.0

Definition at line 36 of file Dictionary.c.

DICTIONARY_MAX_LOAD

#define DICTIONARY_MAX_LOAD   0.75f

Definition at line 37 of file Dictionary.c.

Function Documentation

_Dictionary()

Class * _Dictionary

(

void

)

Definition at line 762 of file Dictionary.c.

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

addEntriesFromDictionary()

static void addEntriesFromDictionary ( Dictionary *  self, const Dictionary *  dictionary  )

static

Definition at line 175 of file Dictionary.c.

                                                                                     {
 
  assert(dictionary);
 
  $(dictionary, enumerateObjectsAndKeys, addEntriesFromDictionary_enumerator, self);
}

addEntriesFromDictionary_enumerator()

static void addEntriesFromDictionary_enumerator ( const Dictionary *  dict, ident  obj, ident  key, ident  data  )

static

DictionaryEnumerator for addEntriesFromDictionary.

Definition at line 167 of file Dictionary.c.

                                                                                                          {
  $((Dictionary *) data, setObjectForKey, obj, key);
}

allKeys()

static Array * allKeys ( const Dictionary *  self )

static

Definition at line 193 of file Dictionary.c.

                                              {
 
  Array *keys = $(alloc(Array), initWithCapacity, self->count);
 
  $(self, enumerateObjectsAndKeys, allKeys_enumerator, keys);
 
  return (Array *) keys;
}

allKeys_enumerator()

static void allKeys_enumerator ( const Dictionary *  dict, ident  obj, ident  key, ident  data  )

static

DictionaryEnumerator for allKeys.

Definition at line 185 of file Dictionary.c.

                                                                                         {
  $((Array *) data, addObject, key);
}

allObjects()

static Array * allObjects ( const Dictionary *  self )

static

Definition at line 213 of file Dictionary.c.

                                                 {
 
  Array *objects = $(alloc(Array), initWithCapacity, self->count);
 
  $(self, enumerateObjectsAndKeys, allObjects_enumerator, objects);
 
  return (Array *) objects;
}

allObjects_enumerator()

static void allObjects_enumerator ( const Dictionary *  dict, ident  obj, ident  key, ident  data  )

static

DictionaryEnumerator for allObjects.

Definition at line 205 of file Dictionary.c.

                                                                                            {
  $((Array *) data, addObject, obj);
}

containsKey()

static bool containsKey ( const Dictionary *  self, const ident  key  )

static

Definition at line 226 of file Dictionary.c.

                                                                 {
  return $(self, objectForKey, key) != NULL;
}

containsKeyPath()

static bool containsKeyPath ( const Dictionary *  self, const char *  path  )

static

Definition at line 234 of file Dictionary.c.

                                                                      {
  return $(self, objectForKeyPath, path) != NULL;
}

copy()

static Object * copy ( const Object *  self )

static

See also

Object::copy(const Object *)

Definition at line 44 of file Dictionary.c.

                                        {
 
  const Dictionary *this = (const Dictionary *) self;
 
  Dictionary *that = $(alloc(Dictionary), initWithCapacity, this->capacity);
  if (that) {
    $(that, addEntriesFromDictionary, this);
  }
 
  return (Object *) that;
}

dealloc()

static void dealloc ( Object *  self )

static

See also

Object::dealloc(Object *)

Definition at line 59 of file Dictionary.c.

                                  {
 
  Dictionary *this = (Dictionary *) self;
 
  for (size_t i = 0; i < this->capacity; i++) {
    release(this->elements[i]);
  }
 
  free(this->elements);
 
  super(Object, self, dealloc);
}

description()

static String * description ( const Object *  self )

static

See also

Object::description(const Object *)

Definition at line 91 of file Dictionary.c.

                                               {
 
  const Dictionary *this = (Dictionary *) self;
 
  String *desc = $(alloc(String), init);
 
  $(desc, appendCharacters, "{");
 
  $(this, enumerateObjectsAndKeys, description_enumerator, desc);
 
  $(desc, appendCharacters, "}");
 
  return (String *) desc;
}

description_enumerator()

static void description_enumerator ( const Dictionary *  dict, ident  obj, ident  key, ident  data  )

static

A DictionaryEnumerator for description.

Definition at line 75 of file Dictionary.c.

                                                                                             {
 
  String *desc = (String *) data;
 
  String *objDesc = $((Object *) obj, description);
  String *keyDesc = $((Object *) key, description);
 
  $(desc, appendFormat, "%s: %s, ", keyDesc->chars, objDesc->chars);
 
  release(objDesc);
  release(keyDesc);
}

dictionary()

static Dictionary * dictionary ( void  )

static

Definition at line 242 of file Dictionary.c.

                                    {
 
  return $(alloc(Dictionary), init);
}

dictionaryWithCapacity()

static Dictionary * dictionaryWithCapacity ( size_t  capacity )

static

Definition at line 251 of file Dictionary.c.

                                                           {
 
  return $(alloc(Dictionary), initWithCapacity, capacity);
}

dictionaryWithDictionary()

static Dictionary * dictionaryWithDictionary ( const Dictionary *  dictionary )

static

Definition at line 260 of file Dictionary.c.

                                                                          {
 
  return $(alloc(Dictionary), initWithDictionary, dictionary);
}

dictionaryWithObjectsAndKeys()

static Dictionary * dictionaryWithObjectsAndKeys ( ident  obj,   ...  )

static

Definition at line 269 of file Dictionary.c.

                                                                {
 
  Dictionary *dict = (Dictionary *) $((Object *) alloc(Dictionary), init);
  if (dict) {
 
    va_list args;
    va_start(args, obj);
 
    while (obj) {
      ident key = va_arg(args, ident);
 
      $(dict, setObjectForKey, obj, key);
 
      obj = va_arg(args, ident);
    }
 
    va_end(args);
  }
 
  return dict;
}

enumerateObjectsAndKeys()

static void enumerateObjectsAndKeys ( const Dictionary *  self, DictionaryEnumerator  enumerator, ident  data  )

static

Definition at line 295 of file Dictionary.c.

                {
 
  assert(enumerator);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j += 2) {
 
        ident key = $(array, objectAtIndex, j);
        ident obj = $(array, objectAtIndex, j + 1);
 
        enumerator(self, obj, key, data);
      }
    }
  }
}

filterObjectsAndKeys()

static Dictionary * filterObjectsAndKeys ( const Dictionary *  self, DictionaryPredicate  predicate, ident  data  )

static

Definition at line 320 of file Dictionary.c.

                                                                                                           {
 
  assert(predicate);
 
  Dictionary *dictionary = $(alloc(Dictionary), init);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
 
      for (size_t j = 0; j < array->count; j += 2) {
 
        ident key = $(array, objectAtIndex, j);
        ident obj = $(array, objectAtIndex, j + 1);
 
        if (predicate(obj, key, data)) {
          $(dictionary, setObjectForKey, obj, key);
        }
      }
    }
  }
 
  return dictionary;
}

hash()

static int hash ( const Object *  self )

static

See also

Object::hash(const Object *)

Definition at line 109 of file Dictionary.c.

                                    {
 
  const Dictionary *this = (Dictionary *) self;
 
  int hash = HashForInteger(HASH_SEED, this->count);
 
  for (size_t i = 0; i < this->capacity; i++) {
    if (this->elements[i]) {
      hash = HashForObject(hash, this->elements[i]);
    }
  }
 
  return hash;
}

init()

static Dictionary * init ( Dictionary *  self )

static

Definition at line 350 of file Dictionary.c.

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

initialize()

static void initialize ( Class *  clazz )

static

See also

Class::initialize(Class *)

Definition at line 722 of file Dictionary.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;
 
  ((DictionaryInterface *) clazz->interface)->addEntriesFromDictionary = addEntriesFromDictionary;
  ((DictionaryInterface *) clazz->interface)->allKeys = allKeys;
  ((DictionaryInterface *) clazz->interface)->allObjects = allObjects;
  ((DictionaryInterface *) clazz->interface)->containsKey = containsKey;
  ((DictionaryInterface *) clazz->interface)->containsKeyPath = containsKeyPath;
  ((DictionaryInterface *) clazz->interface)->dictionary = dictionary;
  ((DictionaryInterface *) clazz->interface)->dictionaryWithCapacity = dictionaryWithCapacity;
  ((DictionaryInterface *) clazz->interface)->dictionaryWithDictionary = dictionaryWithDictionary;
  ((DictionaryInterface *) clazz->interface)->dictionaryWithObjectsAndKeys = dictionaryWithObjectsAndKeys;
  ((DictionaryInterface *) clazz->interface)->enumerateObjectsAndKeys = enumerateObjectsAndKeys;
  ((DictionaryInterface *) clazz->interface)->filterObjectsAndKeys = filterObjectsAndKeys;
  ((DictionaryInterface *) clazz->interface)->init = init;
  ((DictionaryInterface *) clazz->interface)->initWithCapacity = initWithCapacity;
  ((DictionaryInterface *) clazz->interface)->initWithDictionary = initWithDictionary;
  ((DictionaryInterface *) clazz->interface)->initWithObjectsAndKeys = initWithObjectsAndKeys;
  ((DictionaryInterface *) clazz->interface)->objectForKey = objectForKey;
  ((DictionaryInterface *) clazz->interface)->objectForKeyPath = objectForKeyPath;
  ((DictionaryInterface *) clazz->interface)->objectForKeyPathWithClass = objectForKeyPathWithClass;
  ((DictionaryInterface *) clazz->interface)->removeAllObjects = removeAllObjects;
  ((DictionaryInterface *) clazz->interface)->removeAllObjectsWithEnumerator = removeAllObjectsWithEnumerator;
  ((DictionaryInterface *) clazz->interface)->removeObjectForKey = removeObjectForKey;
  ((DictionaryInterface *) clazz->interface)->removeObjectForKeyPath = removeObjectForKeyPath;
  ((DictionaryInterface *) clazz->interface)->setObjectForKey = setObjectForKey;
  ((DictionaryInterface *) clazz->interface)->setObjectForKeyPath = setObjectForKeyPath;
  ((DictionaryInterface *) clazz->interface)->setObjectsForKeyPaths = setObjectsForKeyPaths;
  ((DictionaryInterface *) clazz->interface)->setObjectsForKeys = setObjectsForKeys;
}

initWithCapacity()

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

static

Definition at line 359 of file Dictionary.c.

                                                                       {
 
  self = (Dictionary *) super(Object, self, init);
  if (self) {
 
    self->capacity = capacity;
    if (self->capacity) {
 
      self->elements = calloc(self->capacity, sizeof(ident));
      assert(self->elements);
    }
  }
 
  return self;
}

initWithDictionary()

static Dictionary * initWithDictionary ( Dictionary *  self, const Dictionary *  dictionary  )

static

Definition at line 379 of file Dictionary.c.

                                                                                      {
 
  self = (Dictionary *) super(Object, self, init);
  if (self) {
    if (dictionary) {
 
      self->capacity = dictionary->capacity;
 
      self->elements = calloc(self->capacity, sizeof(ident));
      assert(self->elements);
 
      for (size_t i = 0; i < dictionary->capacity; i++) {
 
        Array *array = dictionary->elements[i];
        if (array) {
          self->elements[i] = $((Object *) array, copy);
        }
      }
 
      self->count = dictionary->count;
    }
  }
 
  return self;
}

initWithObjectsAndKeys()

static Dictionary * initWithObjectsAndKeys ( Dictionary *  self,   ...  )

static

Definition at line 409 of file Dictionary.c.

                                                                 {
 
  self = (Dictionary *) super(Object, self, init);
  if (self) {
 
    va_list args;
    va_start(args, self);
 
    while (true) {
 
      ident obj = va_arg(args, ident);
      if (obj) {
 
        ident key = va_arg(args, ident);
        $(self, setObjectForKey, obj, key);
      } else {
        break;
      }
    }
 
    va_end(args);
  }
 
  return self;
}

isEqual()

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

static

See also

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

Definition at line 127 of file Dictionary.c.

                                                             {
 
  if (super(Object, self, isEqual, other)) {
    return true;
  }
 
  if (other && $(other, isKindOfClass, _Dictionary())) {
 
    const Dictionary *this = (Dictionary *) self;
    const Dictionary *that = (Dictionary *) other;
 
    if (this->count == that->count) {
 
      Array *keys = $(this, allKeys);
 
      for (size_t i = 0; i < keys->count; i++) {
        const ident key = $(keys, objectAtIndex, i);
 
        const Object *thisObject = $(this, objectForKey, key);
        const Object *thatObject = $(that, objectForKey, key);
 
        if ($(thisObject, isEqual, thatObject) == false) {
          release(keys);
          return false;
        }
      }
 
      release(keys);
      return true;
    }
  }
 
  return false;
}

objectForKey()

static ident objectForKey ( const Dictionary *  self, const ident  key  )

static

Definition at line 439 of file Dictionary.c.

                                                                   {
 
  if (self->capacity == 0) {
    return NULL;
  }
  
  const size_t bin = HashForObject(HASH_SEED, key) % self->capacity;
 
  Array *array = self->elements[bin];
  if (array) {
 
    const ssize_t index = $(array, indexOfObject, key);
    if (index > -1 && (index & 1) == 0) {
      return $(array, objectAtIndex, index + 1);
    }
  }
 
  return NULL;
}

objectForKeyPath()

static ident objectForKeyPath ( const Dictionary *  self, const char *  path  )

static

Definition at line 463 of file Dictionary.c.

                                                                        {
 
  assert(path);
 
  String *key = str(path);
 
  ident obj = $(self, objectForKey, key);
 
  release(key);
 
  return obj;
}

objectForKeyPathWithClass()

static ident objectForKeyPathWithClass ( const Dictionary *  self, const char *  path, const Class *  clazz  )

static

Definition at line 480 of file Dictionary.c.

                                                                                                     {
 
  assert(path);
 
  const ident value = $(self, objectForKeyPath, path);
  if (value) {
    if (instanceof(Null, value)) {
      return NULL;
    } else {
      return _cast(clazz, value);
    }
  }
 
  return NULL;
}

removeAllObjects()

static void removeAllObjects ( Dictionary *  self )

static

Definition at line 500 of file Dictionary.c.

                                               {
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
      self->elements[i] = release(array);
    }
  }
 
  self->count = 0;
}

removeAllObjectsWithEnumerator()

static void removeAllObjectsWithEnumerator ( Dictionary *  self, DictionaryEnumerator  enumerator, ident  data  )

static

Definition at line 517 of file Dictionary.c.

                                                                                                          {
 
  assert(enumerator);
 
  for (size_t i = 0; i < self->capacity; i++) {
 
    Array *array = self->elements[i];
    if (array) {
      for (size_t j = array->count; j > 0; j -= 2) {
 
        ident obj = array->elements[j - 1];
        ident key = array->elements[j - 2];
 
        enumerator(self, obj, key, data);
 
        $((Array *) array, removeObjectAtIndex, j - 1);
        $((Array *) array, removeObjectAtIndex, j - 2);
      }
 
      self->elements[i] = release(array);
    }
  }
 
  self->count = 0;
}

removeObjectForKey()

static void removeObjectForKey ( Dictionary *  self, const ident  key  )

static

Definition at line 547 of file Dictionary.c.

                                                                  {
 
  if (self->capacity == 0) {
    return;
  }
  
  const size_t bin = HashForObject(HASH_SEED, key) % self->capacity;
 
  Array *array = self->elements[bin];
  if (array) {
 
    const ssize_t index = $((Array *) array, indexOfObject, key);
    if (index > -1) {
 
      $(array, removeObjectAtIndex, index);
      $(array, removeObjectAtIndex, index);
 
      if (((Array *) array)->count == 0) {
        self->elements[bin] = release(array);
      }
 
      self->count--;
    }
  }
}

removeObjectForKeyPath()

static void removeObjectForKeyPath ( Dictionary *  self, const char *  path  )

static

Definition at line 577 of file Dictionary.c.

                                                                       {
 
  String *key = $$(String, stringWithCharacters, path);
 
  $(self, removeObjectForKey, key);
 
  release(key);
}

setObjectForKey()

static void setObjectForKey ( Dictionary *  self, const ident  obj, const ident  key  )

static

Definition at line 634 of file Dictionary.c.

                                                                                {
 
  Dictionary *dict = self;
 
  setObjectForKey_resize(dict);
 
  const size_t bin = HashForObject(HASH_SEED, key) % dict->capacity;
 
  Array *array = dict->elements[bin];
  if (array == NULL) {
    array = dict->elements[bin] = $$(Array, arrayWithCapacity, (dict->capacity >> 2) + 1);
  }
 
  const ssize_t index = $((Array *) array, indexOfObject, key);
  if (index > -1 && (index & 1) == 0) {
    $(array, setObjectAtIndex, obj, index + 1);
  } else {
    $(array, addObject, key);
    $(array, addObject, obj);
 
    dict->count++;
  }
}

setObjectForKey_resize()

static void setObjectForKey_resize ( Dictionary *  dict )

static

A helper for resizing Dictionaries as pairs are added to them.

Remarks

Static method invocations are used for all operations.

Definition at line 590 of file Dictionary.c.

                                                     {
 
  if (dict->capacity) {
 
    const float load = dict->count / (float) dict->capacity;
    if (load >= DICTIONARY_MAX_LOAD) {
 
      size_t capacity = dict->capacity;
      ident *elements = dict->elements;
 
      dict->capacity = dict->capacity * DICTIONARY_GROW_FACTOR;
      dict->count = 0;
 
      dict->elements = calloc(dict->capacity, sizeof(ident));
      assert(dict->elements);
 
      for (size_t i = 0; i < capacity; i++) {
 
        Array *array = elements[i];
        if (array) {
 
          for (size_t j = 0; j < array->count; j += 2) {
 
            ident key = $(array, objectAtIndex, j);
            ident obj = $(array, objectAtIndex, j + 1);
 
            $$(Dictionary, setObjectForKey, dict, obj, key);
          }
 
          release(array);
        }
      }
 
      free(elements);
    }
  } else {
    $(dict, initWithCapacity, DICTIONARY_DEFAULT_CAPACITY);
  }
}

setObjectForKeyPath()

static void setObjectForKeyPath ( Dictionary *  self, const ident  obj, const char *  path  )

static

Definition at line 662 of file Dictionary.c.

                                                                                     {
 
  String *key = $$(String, stringWithCharacters, path);
 
  $(self, setObjectForKey, obj, key);
 
  release(key);
}

setObjectsForKeyPaths()

static void setObjectsForKeyPaths ( Dictionary *  self,   ...  )

static

Definition at line 675 of file Dictionary.c.

                                                         {
 
  va_list args;
  va_start(args, self);
 
  while (true) {
 
    ident obj = va_arg(args, ident);
    if (obj) {
      const char *path = va_arg(args, const char *);
      $(self, setObjectForKeyPath, obj, path);
    } else {
      break;
    }
  }
 
  va_end(args);
}

setObjectsForKeys()

static void setObjectsForKeys ( Dictionary *  self,   ...  )

static

Definition at line 698 of file Dictionary.c.

                                                     {
 
  va_list args;
  va_start(args, self);
 
  while (true) {
 
    ident obj = va_arg(args, ident);
    if (obj) {
      ident key = va_arg(args, ident);
      $(self, setObjectForKey, obj, key);
    } else {
      break;
    }
  }
 
  va_end(args);
}