proton-c/src/object/map.c

/*
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 */

#include <proton/object.h>
#include <stdlib.h>
#include <assert.h>

#define PNI_ENTRY_FREE (0)
#define PNI_ENTRY_LINK (1)
#define PNI_ENTRY_TAIL (2)

typedef struct {
  void *key;
  void *value;
  size_t next;
  uint8_t state;
} pni_entry_t;

struct pn_map_t {
  const pn_class_t *key;
  const pn_class_t *value;
  pni_entry_t *entries;
  size_t capacity;
  size_t addressable;
  size_t size;
  uintptr_t (*hashcode)(void *key);
  bool (*equals)(void *a, void *b);
  float load_factor;
};

static void pn_map_finalize(void *object)
{
  pn_map_t *map = (pn_map_t *) object;

  for (size_t i = 0; i < map->capacity; i++) {
    if (map->entries[i].state != PNI_ENTRY_FREE) {
      pn_class_decref(map->key, map->entries[i].key);
      pn_class_decref(map->value, map->entries[i].value);
    }
  }

  free(map->entries);
}

static uintptr_t pn_map_hashcode(void *object)
{
  pn_map_t *map = (pn_map_t *) object;

  uintptr_t hashcode = 0;

  for (size_t i = 0; i < map->capacity; i++) {
    if (map->entries[i].state != PNI_ENTRY_FREE) {
      void *key = map->entries[i].key;
      void *value = map->entries[i].value;
      hashcode += pn_hashcode(key) ^ pn_hashcode(value);
    }
  }

  return hashcode;
}

static void pni_map_allocate(pn_map_t *map)
{
  map->entries = (pni_entry_t *) malloc(map->capacity * sizeof (pni_entry_t));
  if (map->entries != NULL) {
    for (size_t i = 0; i < map->capacity; i++) {
      map->entries[i].key = NULL;
      map->entries[i].value = NULL;
      map->entries[i].next = 0;
      map->entries[i].state = PNI_ENTRY_FREE;
    }
  }
  map->size = 0;
}

static int pn_map_inspect(void *obj, pn_string_t *dst)
{
  assert(obj);
  pn_map_t *map = (pn_map_t *) obj;
  int err = pn_string_addf(dst, "{");
  if (err) return err;
  pn_handle_t entry = pn_map_head(map);
  bool first = true;
  while (entry) {
    if (first) {
      first = false;
    } else {
      err = pn_string_addf(dst, ", ");
      if (err) return err;
    }
    err = pn_class_inspect(map->key, pn_map_key(map, entry), dst);
    if (err) return err;
    err = pn_string_addf(dst, ": ");
    if (err) return err;
    err = pn_class_inspect(map->value, pn_map_value(map, entry), dst);
    if (err) return err;
    entry = pn_map_next(map, entry);
  }
  return pn_string_addf(dst, "}");
}

#define pn_map_initialize NULL
#define pn_map_compare NULL

pn_map_t *pn_map(const pn_class_t *key, const pn_class_t *value,
                 size_t capacity, float load_factor)
{
  static const pn_class_t clazz = PN_CLASS(pn_map);

  pn_map_t *map = (pn_map_t *) pn_class_new(&clazz, sizeof(pn_map_t));
  map->key = key;
  map->value = value;
  map->capacity = capacity ? capacity : 16;
  map->addressable = (size_t) (map->capacity * 0.86);
  if (!map->addressable) map->addressable = map->capacity;
  map->load_factor = load_factor;
  map->hashcode = pn_hashcode;
  map->equals = pn_equals;
  pni_map_allocate(map);
  return map;
}

size_t pn_map_size(pn_map_t *map)
{
  assert(map);
  return map->size;
}

static float pni_map_load(pn_map_t *map)
{
  return ((float) map->size) / ((float) map->addressable);
}

static bool pni_map_ensure(pn_map_t *map, size_t capacity)
{
  float load = pni_map_load(map);
  if (capacity <= map->capacity && load <= map->load_factor) {
    return false;
  }

  size_t oldcap = map->capacity;

  while (map->capacity < capacity || pni_map_load(map) > map->load_factor) {
    map->capacity *= 2;
    map->addressable = (size_t) (0.86 * map->capacity);
  }

  pni_entry_t *entries = map->entries;
  pni_map_allocate(map);

  for (size_t i = 0; i < oldcap; i++) {
    if (entries[i].state != PNI_ENTRY_FREE) {
      void *key = entries[i].key;
      void *value = entries[i].value;
      pn_map_put(map, key, value);
    }
  }

  for (size_t i = 0; i < oldcap; i++) {
    if (entries[i].state != PNI_ENTRY_FREE) {
      void *key = entries[i].key;
      void *value = entries[i].value;
      pn_class_decref(map->key, key);
      pn_class_decref(map->value, value);
    }
  }

  free(entries);
  return true;
}

static pni_entry_t *pni_map_entry(pn_map_t *map, void *key, pni_entry_t **pprev, bool create)
{
  uintptr_t hashcode = map->hashcode(key);

  pni_entry_t *entry = &map->entries[hashcode % map->addressable];
  pni_entry_t *prev = NULL;

  if (entry->state == PNI_ENTRY_FREE) {
    if (create) {
      entry->state = PNI_ENTRY_TAIL;
      entry->key = key;
      pn_class_incref(map->key, key);
      map->size++;
      return entry;
    } else {
      return NULL;
    }
  }

  while (true) {
    if (map->equals(entry->key, key)) {
      if (pprev) *pprev = prev;
      return entry;
    }

    if (entry->state == PNI_ENTRY_TAIL) {
      break;
    } else {
      prev = entry;
      entry = &map->entries[entry->next];
    }
  }

  if (create) {
    if (pni_map_ensure(map, map->size + 1)) {
      // if we had to grow the table we need to start over
      return pni_map_entry(map, key, pprev, create);
    }

    size_t empty = 0;
    for (size_t i = 0; i < map->capacity; i++) {
      size_t idx = map->capacity - i - 1;
      if (map->entries[idx].state == PNI_ENTRY_FREE) {
        empty = idx;
        break;
      }
    }
    entry->next = empty;
    entry->state = PNI_ENTRY_LINK;
    map->entries[empty].state = PNI_ENTRY_TAIL;
    map->entries[empty].key = key;
    pn_class_incref(map->key, key);
    if (pprev) *pprev = entry;
    map->size++;
    return &map->entries[empty];
  } else {
    return NULL;
  }
}

int pn_map_put(pn_map_t *map, void *key, void *value)
{
  assert(map);
  pni_entry_t *entry = pni_map_entry(map, key, NULL, true);
  void *dref_val = entry->value;
  entry->value = value;
  pn_class_incref(map->value, value);
  pn_class_decref(map->value, dref_val);
  return 0;
}

void *pn_map_get(pn_map_t *map, void *key)
{
  assert(map);
  pni_entry_t *entry = pni_map_entry(map, key, NULL, false);
  return entry ? entry->value : NULL;
}

static void pni_map_rehash(pn_map_t *map, size_t index)
{
  //reinsert entries in chain starting at index
  assert(map);
  size_t i = index;
  bool complete = false;
  while (!complete) {
    pni_entry_t *entry = &map->entries[i];
    assert(entry);
    assert(entry->state != PNI_ENTRY_FREE);
    size_t current = i;
    if (entry->state == PNI_ENTRY_TAIL) {
      complete = true;
    } else {
      assert(entry->state == PNI_ENTRY_LINK);
      i = entry->next;
    }
    uintptr_t hashcode = map->hashcode(entry->key);
    pni_entry_t *reloc = &map->entries[hashcode % map->addressable];
    if (reloc->state == PNI_ENTRY_FREE) {
      //correct addressable slot is available, copy into that...
      reloc->state = PNI_ENTRY_TAIL;
      reloc->key = entry->key;
      reloc->value = entry->value;
      //...then free the current entry
      entry->key = NULL;
      entry->value = NULL;
      entry->state = PNI_ENTRY_FREE;
      entry->next = 0;
    } else {
      //iterate to end of chain...
      while (reloc->state == PNI_ENTRY_LINK) {
        reloc = &map->entries[reloc->next];
      }
      assert(reloc->state == PNI_ENTRY_TAIL);
      //... and append current entry
      reloc->state = PNI_ENTRY_LINK;
      reloc->next = current;
      entry->state = PNI_ENTRY_TAIL;
      entry->next = 0;
    }
  }
}

void pn_map_del(pn_map_t *map, void *key)
{
  assert(map);
  pni_entry_t *prev = NULL;
  pni_entry_t *entry = pni_map_entry(map, key, &prev, false);
  if (entry) {
    uint8_t orig_state = entry->state;
    size_t orig_next = entry->next;

    void *dref_key = entry->key;
    void *dref_value = entry->value;
    if (prev) {
      prev->next = 0;
      prev->state = PNI_ENTRY_TAIL;
    }
    entry->state = PNI_ENTRY_FREE;
    entry->next = 0;
    entry->key = NULL;
    entry->value = NULL;
    map->size--;

    if (orig_state == PNI_ENTRY_LINK) {
      pni_map_rehash(map, orig_next);
    }

    // do this last as it may trigger further deletions
    pn_class_decref(map->key, dref_key);
    pn_class_decref(map->value, dref_value);
  }
}

pn_handle_t pn_map_head(pn_map_t *map)
{
  assert(map);
  for (size_t i = 0; i < map->capacity; i++)
  {
    if (map->entries[i].state != PNI_ENTRY_FREE) {
      return (pn_handle_t)(i + 1);
    }
  }

  return 0;
}

pn_handle_t pn_map_next(pn_map_t *map, pn_handle_t entry)
{
  for (size_t i = (size_t)entry; i < map->capacity; i++) {
    if (map->entries[i].state != PNI_ENTRY_FREE) {
      return (pn_handle_t)(i + 1);
    }
  }

  return 0;
}

void *pn_map_key(pn_map_t *map, pn_handle_t entry)
{
  assert(map);
  assert(entry);
  return map->entries[(size_t)entry - 1].key;
}

void *pn_map_value(pn_map_t *map, pn_handle_t entry)
{
  assert(map);
  assert(entry);
  return map->entries[(size_t)entry - 1].value;
}

struct pn_hash_t {
  pn_map_t map;
};

static uintptr_t pni_identity_hashcode(void *obj)
{
  return (uintptr_t ) obj;
}

static bool pni_identity_equals(void *a, void *b)
{
  return a == b;
}

#define CID_pni_uintptr CID_pn_void
static const pn_class_t *pni_uintptr_reify(void *object);
#define pni_uintptr_new NULL
#define pni_uintptr_free NULL
#define pni_uintptr_initialize NULL
static void pni_uintptr_incref(void *object) {}
static void pni_uintptr_decref(void *object) {}
static int pni_uintptr_refcount(void *object) { return -1; }
#define pni_uintptr_finalize NULL
#define pni_uintptr_hashcode NULL
#define pni_uintptr_compare NULL
#define pni_uintptr_inspect NULL

static const pn_class_t PN_UINTPTR[] = {PN_METACLASS(pni_uintptr)};

static const pn_class_t *pni_uintptr_reify(void *object)
{
  return PN_UINTPTR;
}

pn_hash_t *pn_hash(const pn_class_t *clazz, size_t capacity, float load_factor)
{
  pn_hash_t *hash = (pn_hash_t *) pn_map(PN_UINTPTR, clazz, capacity, load_factor);
  hash->map.hashcode = pni_identity_hashcode;
  hash->map.equals = pni_identity_equals;
  return hash;
}

size_t pn_hash_size(pn_hash_t *hash)
{
  return pn_map_size(&hash->map);
}

int pn_hash_put(pn_hash_t *hash, uintptr_t key, void *value)
{
  return pn_map_put(&hash->map, (void *) key, value);
}

void *pn_hash_get(pn_hash_t *hash, uintptr_t key)
{
  return pn_map_get(&hash->map, (void *) key);
}

void pn_hash_del(pn_hash_t *hash, uintptr_t key)
{
  pn_map_del(&hash->map, (void *) key);
}

pn_handle_t pn_hash_head(pn_hash_t *hash)
{
  return pn_map_head(&hash->map);
}

pn_handle_t pn_hash_next(pn_hash_t *hash, pn_handle_t entry)
{
  return pn_map_next(&hash->map, entry);
}

uintptr_t pn_hash_key(pn_hash_t *hash, pn_handle_t entry)
{
  return (uintptr_t) pn_map_key(&hash->map, entry);
}

void *pn_hash_value(pn_hash_t *hash, pn_handle_t entry)
{
  return pn_map_value(&hash->map, entry);
}