Program Listing for File hashmap.h

↰ Return to documentation for file (rcsw/ds/hashmap.h)

#pragma once

/*******************************************************************************
 * Includes
 ******************************************************************************/
#include "rcsw/ds/ds.h"
#include "rcsw/ds/darray.h"

/*******************************************************************************
 * Constant Definitions
 ******************************************************************************/
#define RCSW_HASHMAP_KEYSIZE 64

/*******************************************************************************
 * Structure Definitions
 ******************************************************************************/
struct hashmap_params {
  dptr_t *meta;

  dptr_t *elements;

  size_t elt_size;

  uint32_t flags;

  uint32_t (*hash)(const void *const key, size_t len);

  size_t bsize;

  size_t n_buckets;

  int sort_thresh;
};

struct hashmap_stats {
  size_t n_buckets;
  size_t n_nodes;
  size_t n_adds;
  size_t n_addfails;
  size_t n_collisions;
  double collision_ratio;
  bool_t sorted;
  double max_util;
  double min_util;
  double average_util;
};

struct hashmap_space_mgmt {
  dptr_t*               elements;
  struct allocm_entry*  db_map;
  dptr_t*               datablocks;
  struct hashnode*      hashnodes;

  struct darray           *buckets;

  uint8_t                 *nodes;
};

struct hashmap {
  uint32_t (*hash)(const void *const key, size_t len);

  struct darray *last_used;

  struct hashmap_space_mgmt space;

  size_t elt_size;

  size_t max_elts;

  size_t n_buckets;

  struct hashmap_stats stats;


  int sort_thresh;

  bool_t sorted;

  uint32_t flags;
};

struct RCSW_ATTR(packed, aligned (sizeof(dptr_t))) hashnode {
  uint8_t key[RCSW_HASHMAP_KEYSIZE];

  dptr_t *data;

  uint32_t hash;
};

/*******************************************************************************
 * API Functions
 ******************************************************************************/
BEGIN_C_DECLS

static inline size_t hashmap_element_space(size_t n_buckets,
                                           size_t bucket_size,
                                           size_t elt_size) {
  size_t max_elts = n_buckets * bucket_size;
  return ds_meta_space(max_elts) +
      darray_element_space(max_elts, sizeof(struct hashnode)) +
      ds_elt_space_simple(max_elts, elt_size);
}

static inline size_t hashmap_meta_space(size_t n_buckets) {
  return sizeof(struct darray) * n_buckets;
}


RCSW_API struct hashmap *hashmap_init(struct hashmap *map_in,
                                      const struct hashmap_params * params) RCSW_WUR;

RCSW_API void hashmap_destroy(struct hashmap *map);


RCSW_API status_t hashmap_sort(struct hashmap * map);

RCSW_API status_t hashmap_clear(const struct hashmap * map);

RCSW_API void *hashmap_data_get(struct hashmap * map, const void * key);

RCSW_API status_t hashmap_add(struct hashmap * map,
                              const void * key,
                              const void * data);

RCSW_API status_t hashmap_remove(struct hashmap * map, const void * key);

RCSW_API void hashmap_print(const struct hashmap * map);

RCSW_API status_t hashmap_gather(const struct hashmap * map,
                                 struct hashmap_stats * stats);

RCSW_API void hashmap_print_dist(const struct hashmap * map);

END_C_DECLS