cuda/htable.h File Reference

Include dependency graph for cuda/htable.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hash_table_entry
struct	hash_table

Macros
#define	HTABLE_SUCCESS   ( 0)
#define	HTABLE_ENOVAL   (-1)
#define	HTABLE_EINVAL   (-2)
#define	HTABLE_ENOMEM   (-3)
#define	HTABLE_NEEDS_TO_GROW(table)   (table->size > 0 && table->capacity / table->size < 2)
#define	HTABLE_NEEDS_TO_SHRINK(table)   (table->size > 0 && table->capacity / table->size > 8)
#define	HTABLE_MIN_SIZE   (8)

Functions
static uint64_t	hash_func (const char *)
static int	create_table (uint64_t, struct hash_table **)
static int	destroy_table (struct hash_table *)
static int	rehash_table (struct hash_table *, struct hash_table *)
static int	move_table (struct hash_table *, struct hash_table *)
static int	check_n_resize_table (struct hash_table *)
static int	destroy_table_entries (struct hash_table *)
static int	create_table_entry (const char *, void *, struct hash_table_entry **)
static int	destroy_table_entry (struct hash_table_entry *)
static int	insert_table_entry (struct hash_table *, struct hash_table_entry *)
static int	delete_table_entry (struct hash_table *, struct hash_table_entry *)
static int	find_table_entry (struct hash_table *, const char *, struct hash_table_entry **)
static int	htable_init (void **handle)
static int	htable_shutdown (void *handle)
static int	htable_insert (void *handle, const char *key, void *in)
static int	htable_delete (void *handle, const char *key)
static int	htable_find (void *handle, const char *key, void **out)

Macro Definition Documentation

HTABLE_EINVAL

#define HTABLE_EINVAL   (-2)

Definition at line 19 of file cuda/htable.h.

HTABLE_ENOMEM

#define HTABLE_ENOMEM   (-3)

Definition at line 20 of file cuda/htable.h.

HTABLE_ENOVAL

#define HTABLE_ENOVAL   (-1)

Definition at line 18 of file cuda/htable.h.

HTABLE_MIN_SIZE

#define HTABLE_MIN_SIZE   (8)

HTABLE_NEEDS_TO_GROW

#define HTABLE_NEEDS_TO_GROW

(

table

)

(table->size > 0 && table->capacity / table->size < 2)

Definition at line 22 of file cuda/htable.h.

HTABLE_NEEDS_TO_SHRINK

#define HTABLE_NEEDS_TO_SHRINK

(

table

)

(table->size > 0 && table->capacity / table->size > 8)

Definition at line 23 of file cuda/htable.h.

HTABLE_SUCCESS

#define HTABLE_SUCCESS   ( 0)

Definition at line 17 of file cuda/htable.h.

Function Documentation

check_n_resize_table()

int check_n_resize_table ( struct hash_table *  table )

static

Definition at line 287 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table *new_table = NULL;
    char resize =
        (HTABLE_NEEDS_TO_GROW(table) << 1) | HTABLE_NEEDS_TO_SHRINK(table);
 
    if (resize) {
        uint64_t new_capacity = (resize & 0x2) ?
            table->capacity * 2 : table->capacity / 2;
        htable_errno = create_table(new_capacity, &new_table);
        if (htable_errno != HTABLE_SUCCESS) {
            goto fn_fail;
        }
 
        htable_errno = rehash_table(table, new_table);
        if (htable_errno != HTABLE_SUCCESS) {
            goto fn_fail;
        }
 
        move_table(new_table, table);
        destroy_table(new_table);
    }
 
  fn_exit:
    return htable_errno;
  fn_fail:
    if (new_table) {
        destroy_table(new_table);
    }
    goto fn_exit;
}

Here is the call graph for this function:

Here is the caller graph for this function:

create_table()

int create_table ( uint64_t  size, struct hash_table **  table  )

static

Definition at line 195 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
    *table = papi_calloc(1, sizeof(**table));
    if (table == NULL) {
        htable_errno = HTABLE_ENOMEM;
        goto fn_exit;
    }
 
    (*table)->buckets = papi_calloc(size, sizeof(*(*table)->buckets));
    if ((*table)->buckets == NULL) {
        htable_errno = HTABLE_ENOMEM;
        goto fn_exit;
    }
 
    (*table)->capacity = size;
 
  fn_exit:
    return htable_errno;
}

Here is the caller graph for this function:

create_table_entry()

int create_table_entry ( const char *  key, void *  val, struct hash_table_entry **  entry  )

static

Definition at line 321 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
    *entry = papi_calloc(1, sizeof(**entry));
    if (*entry == NULL) {
        return HTABLE_ENOMEM;
    }
    (*entry)->key = strdup(key);
    (*entry)->val = val;
    (*entry)->next = NULL;
 
    return htable_errno;
}

Here is the caller graph for this function:

delete_table_entry()

int delete_table_entry ( struct hash_table *  table, struct hash_table_entry *  entry  )

static

Definition at line 363 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
    uint64_t id = hash_func(entry->key) % table->capacity;
 
    if (table->buckets[id] == entry) {
        table->buckets[id] = entry->next;
        entry->next = NULL;
        goto fn_exit;
    }
 
    struct hash_table_entry *prev = table->buckets[id];
    struct hash_table_entry *curr = table->buckets[id]->next;
 
    while (curr) {
        if (curr == entry) {
            prev->next = curr->next;
            curr->next = NULL;
            break;
        }
        prev = prev->next;
        curr = curr->next;
    }
 
  fn_exit:
    --table->size;
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

destroy_table()

int destroy_table ( struct hash_table *  table )

static

Definition at line 218 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
    if (table && table->buckets) {
        papi_free(table->buckets);
    }
 
    if (table) {
        papi_free(table);
    }
 
    return htable_errno;
}

Here is the caller graph for this function:

destroy_table_entries()

int destroy_table_entries ( struct hash_table *  table )

static

Definition at line 267 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    uint64_t i;
 
    for (i = 0; i < table->capacity; ++i) {
        struct hash_table_entry *entry = table->buckets[i];
        struct hash_table_entry *tmp = NULL;
 
        while (entry) {
            tmp = entry;
            entry = entry->next;
            delete_table_entry(table, tmp);
            destroy_table_entry(tmp);
        }
    }
 
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

destroy_table_entry()

int destroy_table_entry ( struct hash_table_entry *  entry )

static

Definition at line 337 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    papi_free(entry->key);
    papi_free(entry);
    return htable_errno;
}

Here is the caller graph for this function:

find_table_entry()

int find_table_entry ( struct hash_table *  table, const char *  key, struct hash_table_entry **  entry  )

static

Definition at line 394 of file cuda/htable.h.

{
    int htable_errno;
 
    uint64_t id = hash_func(key) % table->capacity;
    struct hash_table_entry *head = table->buckets[id];
    if (head == NULL) {
        htable_errno = HTABLE_ENOVAL;
        goto fn_exit;
    }
 
    struct hash_table_entry *curr = head;
    while (curr && strcmp(curr->key, key)) {
        curr = curr->next;
    }
 
    *entry = curr;
    htable_errno = (curr) ? HTABLE_SUCCESS : HTABLE_ENOVAL;
 
  fn_exit:
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hash_func()

uint64_t hash_func ( const char *  string )

static

djb2 hash function

Definition at line 184 of file cuda/htable.h.

{
    uint64_t hash = 5381;
    int c;
    while ((c = *string++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

Here is the caller graph for this function:

htable_delete()

static int htable_delete ( void *  handle, const char *  key  )

inlinestatic

Definition at line 130 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table *table = (struct hash_table *) handle;
 
    if (table == NULL || key == NULL) {
        return HTABLE_EINVAL;
    }
 
    struct hash_table_entry *entry = NULL;
    htable_errno = find_table_entry(table, key, &entry);
    if (htable_errno != HTABLE_SUCCESS) {
        return htable_errno;
    }
 
    entry->val = NULL;
 
    htable_errno = delete_table_entry(table, entry);
    if (htable_errno != HTABLE_SUCCESS) {
        return htable_errno;
    }
 
    htable_errno = destroy_table_entry(entry);
    if (htable_errno != HTABLE_SUCCESS) {
        return htable_errno;
    }
 
    return check_n_resize_table(table);
}

Here is the call graph for this function:

Here is the caller graph for this function:

htable_find()

static int htable_find ( void *  handle, const char *  key, void **  out  )

inlinestatic

Definition at line 161 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table *table = (struct hash_table *) handle;
 
    if (table == NULL || key == NULL || out == NULL) {
        return HTABLE_EINVAL;
    }
 
    struct hash_table_entry *entry = NULL;
    htable_errno = find_table_entry(table, key, &entry);
    if (htable_errno != HTABLE_SUCCESS) {
        return htable_errno;
    }
 
    *out = entry->val;
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

htable_init()

static int htable_init ( void **  handle )

inlinestatic

Definition at line 55 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
#define HTABLE_MIN_SIZE (8)
    struct hash_table *table = NULL;
    htable_errno = create_table(HTABLE_MIN_SIZE, &table);
    if (htable_errno != HTABLE_SUCCESS) {
        goto fn_fail;
    }
 
    *handle = table;
 
  fn_exit:
    return htable_errno;
  fn_fail:
    *handle = NULL;
    goto fn_exit;
}

Here is the call graph for this function:

Here is the caller graph for this function:

htable_insert()

static int htable_insert ( void *  handle, const char *  key, void *  in  )

inlinestatic

Definition at line 92 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table *table = (struct hash_table *) handle;
 
    if (table == NULL || key == NULL) {
        return HTABLE_EINVAL;
    }
 
    struct hash_table_entry *entry = NULL;
    htable_errno = find_table_entry(table, key, &entry);
    if (htable_errno == HTABLE_SUCCESS) {
        entry->val = in;
        goto fn_exit;
    }
 
    htable_errno = create_table_entry(key, in, &entry);
    if (htable_errno != HTABLE_SUCCESS) {
        goto fn_fail;
    }
 
    htable_errno = insert_table_entry(table, entry);
    if (htable_errno != HTABLE_SUCCESS) {
        goto fn_fail;
    }
 
    htable_errno = check_n_resize_table(table);
 
  fn_exit:
    return htable_errno;
  fn_fail:
    if (entry) {
        papi_free(entry);
    }
    goto fn_exit;
}

Here is the call graph for this function:

Here is the caller graph for this function:

htable_shutdown()

static int htable_shutdown ( void *  handle )

inlinestatic

Definition at line 76 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table *table = (struct hash_table *) handle;
 
    if (table == NULL) {
        return HTABLE_EINVAL;
    }
 
    destroy_table_entries(table);
    destroy_table(table);
 
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

insert_table_entry()

int insert_table_entry ( struct hash_table *  table, struct hash_table_entry *  entry  )

static

Definition at line 346 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
 
    uint64_t id = hash_func(entry->key) % table->capacity;
 
    if (table->buckets[id]) {
        entry->next = table->buckets[id];
    }
 
    table->buckets[id] = entry;
    ++table->size;
 
    return htable_errno;
}

Here is the call graph for this function:

Here is the caller graph for this function:

move_table()

int move_table ( struct hash_table *  new_table, struct hash_table *  old_table  )

static

Definition at line 252 of file cuda/htable.h.

{
    int htable_errno = HTABLE_SUCCESS;
    struct hash_table_entry **old_buckets = old_table->buckets;
 
    old_table->capacity = new_table->capacity;
    old_table->size = new_table->size;
    old_table->buckets = new_table->buckets;
    new_table->buckets = NULL;
    papi_free(old_buckets);
 
    return htable_errno;
}

Here is the caller graph for this function:

rehash_table()

int rehash_table ( struct hash_table *  old_table, struct hash_table *  new_table  )

static

Definition at line 234 of file cuda/htable.h.

{
    uint64_t old_id;
    for (old_id = 0; old_id < old_table->capacity; ++old_id) {
        struct hash_table_entry *entry = old_table->buckets[old_id];
        struct hash_table_entry *next;
        while (entry) {
            next = entry->next;
            delete_table_entry(old_table, entry);
            insert_table_entry(new_table, entry);
            entry = next;
        }
    }
 
    return HTABLE_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function: