ARGOBOTS  dce6e727ffc4ca5b3ffc04cb9517c6689be51ec5
hashtable.c
Go to the documentation of this file.
1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
2 /*
3  * See COPYRIGHT in top-level directory.
4  */
5 
6 #include "abti.h"
7 
8 static inline ABTU_hashtable_element *
9 get_element(const ABTU_hashtable *p_hashtable, size_t entry_index)
10 {
11  char *p_buffer = (char *)p_hashtable;
12  const size_t data_size = p_hashtable->data_size;
13  const size_t hashtable_size = sizeof(ABTU_hashtable);
14  const size_t hashtable_element_size =
15  ABTU_roundup_size(sizeof(ABTU_hashtable_element) + data_size,
17  return (ABTU_hashtable_element *)(p_buffer + hashtable_size +
18  hashtable_element_size * entry_index);
19 }
20 
21 ABTU_ret_err int ABTU_hashtable_create(size_t num_entries, size_t data_size,
22  ABTU_hashtable **pp_hashtable)
23 {
24  const size_t hashtable_size = sizeof(ABTU_hashtable);
25  const size_t hashtable_element_size =
26  ABTU_roundup_size(sizeof(ABTU_hashtable_element) + data_size,
28  const size_t size = hashtable_size + hashtable_element_size * num_entries;
29 
30  char *p_buffer;
31  int ret = ABTU_calloc(1, size, (void **)&p_buffer);
32  ABTI_CHECK_ERROR(ret);
33 
34  ABTU_hashtable *p_hashtable = (ABTU_hashtable *)p_buffer;
35  p_buffer += hashtable_size;
36  p_hashtable->num_entries = num_entries;
37  p_hashtable->data_size = data_size;
38  *pp_hashtable = p_hashtable;
39  return ABT_SUCCESS;
40 }
41 
43 {
44  size_t i;
45  for (i = 0; i < p_hashtable->num_entries; i++) {
46  ABTU_hashtable_element *p_element = get_element(p_hashtable, i)->p_next;
47  while (p_element) {
48  ABTU_hashtable_element *p_next = p_element->p_next;
49  ABTU_free(p_element);
50  p_element = p_next;
51  }
52  }
53  ABTU_free(p_hashtable);
54 }
55 
56 void ABTU_hashtable_get(const ABTU_hashtable *p_hashtable, int key, void *data,
57  int *found)
58 {
59  const size_t num_entries = p_hashtable->num_entries;
60  const size_t data_size = p_hashtable->data_size;
61  const ssize_t entry_index_tmp = ((ssize_t)key) % ((ssize_t)num_entries);
62  const size_t entry_index = entry_index_tmp < 0
63  ? (ssize_t)(entry_index_tmp + num_entries)
64  : (ssize_t)entry_index_tmp;
65  ABTU_hashtable_element *p_element = get_element(p_hashtable, entry_index);
66  if (!p_element->data) {
67  /* No data */
68  if (found)
69  *found = 0;
70  return;
71  } else {
72  /* Iterate the list. */
73  while (p_element) {
74  if (p_element->key == key) {
75  if (data) {
76  memcpy(data, p_element->data, data_size);
77  }
78  if (found)
79  *found = 1;
80  return;
81  } else if (!p_element->p_next) {
82  if (found)
83  *found = 0;
84  return;
85  }
86  p_element = p_element->p_next;
87  }
88  }
89 }
90 
92  const void *data, int *overwritten)
93 {
94  ABTI_ASSERT(data);
95  const size_t num_entries = p_hashtable->num_entries;
96  const size_t data_size = p_hashtable->data_size;
97  const ssize_t entry_index_tmp = ((ssize_t)key) % ((ssize_t)num_entries);
98  const size_t entry_index = entry_index_tmp < 0
99  ? (ssize_t)(entry_index_tmp + num_entries)
100  : (ssize_t)entry_index_tmp;
101  ABTU_hashtable_element *p_element = get_element(p_hashtable, entry_index);
102  if (!p_element->data) {
103  /* No data */
104  p_element->key = key;
105  p_element->data = ((char *)p_element) + sizeof(ABTU_hashtable_element);
106  memcpy(p_element->data, data, data_size);
107  if (overwritten)
108  *overwritten = 0;
109  return ABT_SUCCESS;
110  } else {
111  /* Iterate the list. */
112  while (p_element) {
113  if (p_element->key == key) {
114  if (data) {
115  memcpy(p_element->data, data, data_size);
116  }
117  if (overwritten)
118  *overwritten = 1;
119  return ABT_SUCCESS;
120  } else if (!p_element->p_next) {
121  const size_t hashtable_element_size =
123  data_size,
125  ABTU_hashtable_element *p_new_element;
126  int ret = ABTU_calloc(1, hashtable_element_size,
127  (void **)&p_new_element);
128  ABTI_CHECK_ERROR(ret);
129  p_new_element->key = key;
130  p_new_element->data =
131  ((char *)p_new_element) + sizeof(ABTU_hashtable_element);
132  memcpy(p_new_element->data, data, data_size);
133  p_element->p_next = p_new_element;
134  if (overwritten)
135  *overwritten = 0;
136  return ABT_SUCCESS;
137  }
138  p_element = p_element->p_next;
139  }
140  }
141  return ABT_SUCCESS;
142 }
143 
144 void ABTU_hashtable_delete(ABTU_hashtable *p_hashtable, int key, int *deleted)
145 {
146  const size_t num_entries = p_hashtable->num_entries;
147  const size_t data_size = p_hashtable->data_size;
148  const ssize_t entry_index_tmp = ((ssize_t)key) % ((ssize_t)num_entries);
149  const size_t entry_index = entry_index_tmp < 0
150  ? (ssize_t)(entry_index_tmp + num_entries)
151  : (ssize_t)entry_index_tmp;
152  ABTU_hashtable_element *p_element = get_element(p_hashtable, entry_index);
153  if (!p_element->data) {
154  /* No data */
155  if (deleted)
156  *deleted = 0;
157  return;
158  } else if (p_element->key == key) {
159  ABTU_hashtable_element *p_next = p_element->p_next;
160  if (p_next) {
161  const size_t hashtable_element_size =
162  ABTU_roundup_size(sizeof(ABTU_hashtable_element) + data_size,
164  memcpy(p_element, p_next, hashtable_element_size);
165  /* Recalculate p_element->data. */
166  p_element->data =
167  ((char *)p_element) + sizeof(ABTU_hashtable_element);
168  ABTU_free(p_next);
169  } else {
170  p_element->data = NULL;
171  }
172  if (deleted)
173  *deleted = 1;
174  return;
175  } else {
176  /* Iterate the list. */
177  ABTU_hashtable_element **pp_element = &p_element->p_next;
178  p_element = *pp_element;
179  while (p_element) {
180  if (p_element->key == key) {
181  *pp_element = p_element->p_next;
182  ABTU_free(p_element);
183  if (deleted)
184  *deleted = 1;
185  return;
186  } else if (!p_element->p_next) {
187  if (deleted)
188  *deleted = 0;
189  return;
190  }
191  pp_element = &p_element->p_next;
192  p_element = *pp_element;
193  }
194  }
195 }
ABTU_hashtable_set
ABTU_ret_err int ABTU_hashtable_set(ABTU_hashtable *p_hashtable, int key, const void *data, int *overwritten)
Definition: hashtable.c:91
ABTU_roundup_size
static size_t ABTU_roundup_size(size_t val, size_t multiple)
Definition: abtu.h:95
ABTU_hashtable_delete
void ABTU_hashtable_delete(ABTU_hashtable *p_hashtable, int key, int *deleted)
Definition: hashtable.c:144
ABTU_hashtable_get
void ABTU_hashtable_get(const ABTU_hashtable *p_hashtable, int key, void *data, int *found)
Definition: hashtable.c:56
ABTU_hashtable_element
struct ABTU_hashtable_element ABTU_hashtable_element
abti.h
ABTU_hashtable::num_entries
size_t num_entries
Definition: abtu.h:348
ABTU_hashtable_create
ABTU_ret_err int ABTU_hashtable_create(size_t num_entries, size_t data_size, ABTU_hashtable **pp_hashtable)
Definition: hashtable.c:21
get_element
static ABTU_hashtable_element * get_element(const ABTU_hashtable *p_hashtable, size_t entry_index)
Definition: hashtable.c:9
ABTU_hashtable
struct ABTU_hashtable ABTU_hashtable
ABTU_calloc
static ABTU_ret_err int ABTU_calloc(size_t num, size_t size, void **p_ptr)
Definition: abtu.h:244
ABT_CONFIG_STATIC_CACHELINE_SIZE
#define ABT_CONFIG_STATIC_CACHELINE_SIZE
Definition: abt_config.h:81
ABT_SUCCESS
#define ABT_SUCCESS
Error code: the routine returns successfully.
Definition: abt.h:92
ABTU_hashtable_element::key
int key
Definition: abtu.h:342
ABTU_ret_err
#define ABTU_ret_err
Definition: abtu.h:155
ABTU_hashtable_free
void ABTU_hashtable_free(ABTU_hashtable *p_hashtable)
Definition: hashtable.c:42
ABTU_hashtable_element
Definition: abtu.h:341
ABTU_free
static void ABTU_free(void *ptr)
Definition: abtu.h:228
ABTU_hashtable_element::p_next
struct ABTU_hashtable_element * p_next
Definition: abtu.h:343
ABTU_hashtable::data_size
size_t data_size
Definition: abtu.h:349
ABTU_hashtable
Definition: abtu.h:347