SIONlib  1.7.7
Scalable I/O library for parallel access to task-local files
sion_keyvalue_table.c
Go to the documentation of this file.
1 /****************************************************************************
2 ** SIONLIB http://www.fz-juelich.de/jsc/sionlib **
3 *****************************************************************************
4 ** Copyright (c) 2008-2019 **
5 ** Forschungszentrum Juelich, Juelich Supercomputing Centre **
6 ** **
7 ** See the file COPYRIGHT in the package base directory for details **
8 ****************************************************************************/
9 
14 #define _XOPEN_SOURCE 700
15 
16 #include <stdlib.h>
17 #include <stdio.h>
18 #include <string.h>
19 #include <time.h>
20 
21 #include <sys/types.h>
22 #include <sys/stat.h>
23 #include <fcntl.h>
24 #include <unistd.h>
25 #include <assert.h>
26 
27 
28 #include "sion.h"
29 #include "sion_debug.h"
30 #include "sion_error_handler.h"
31 #include "sion_internal.h"
32 #include "sion_printts.h"
33 #include "sion_keyvalue_table.h"
34 
35 typedef enum {
36  KEYVALUE_TABLE_ENTRY_STATE_USED,
37  KEYVALUE_TABLE_ENTRY_STATE_FREE,
38  KEYVALUE_TABLE_ENTRY_STATE_UNKNOWN
39 } sion_keyvalue_table_entry_state_t;
40 
42 
44  int used;
45  int size;
46  int num_added_entries;
47 
48  /* for iterator by index */
49  int iterator_lastreadindex;
50  _sion_keyvalue_table_entry* iterator_lastreadentry;
51 
52  /* for iterator by store orde */
53  _sion_keyvalue_table_entry* iterator_next;
54  _sion_keyvalue_table_entry* iterator_head;
55  _sion_keyvalue_table_entry* iterator_tail;
56 
58 };
59 
61  sion_keyvalue_table_entry_state_t state;
62  sion_table_key_t key;
63  _sion_keyvalue_table_entry *iterator_next;
65  void *data;
66 };
67 
68 #define HASH_FCT_SIMPLE_not
69 #define HASH_FCT_SPLIT
70 
71 #define DFUNCTION "_sion_keyvalue_table_hash_fct"
72 unsigned int _sion_keyvalue_table_hash_fct(sion_table_key_t key, int tab_size) {
73  unsigned int index=0;
74 
75 #if defined(HASH_FCT_SIMPLE)
76  /* simple modulo */
77  {
78  index = (unsigned int) key % tab_size;
79  }
80 #elif defined(HASH_FCT_SPLIT)
81  {
82  /* split modulo */
83  uint32_t upper =( uint32_t) (key >> 32);
84  uint32_t lower =( uint32_t) (key & 0xffffffff);
85  DPRINTFP((2, DFUNCTION, -1, "key %ld -> %d %d \n",(long) key, (int) upper, (int) lower));
86  index = (unsigned int) (
87  (unsigned int) upper % tab_size
88  + (unsigned int) lower % tab_size
89  ) % tab_size;
90  }
91 #endif
92 
93  return(index);
94 }
95 #undef DFUNCTION
96 
97 #define DFUNCTION "_sion_keyvalue_table_init"
98 _sion_keyvalue_table* _sion_keyvalue_table_init(int size) {
99  _sion_keyvalue_table* table=NULL;
100  _sion_keyvalue_table_entry* entries=NULL;
101  int i;
102 
103  DPRINTFP((2, DFUNCTION, -1, "enter init size=%d\n",size));
104 
105  table = malloc(sizeof(_sion_keyvalue_table));
106  if (table == NULL) {
107  _sion_errorprint(0,_SION_ERROR_RETURN,"cannot allocate internal keyvalue table of size %lu , aborting ...\n", (unsigned long) sizeof(_sion_keyvalue_table));
108  return(NULL);
109  }
110 
111  entries = malloc(size * sizeof(_sion_keyvalue_table_entry));
112  if (entries == NULL) {
113  _sion_errorprint(0,_SION_ERROR_RETURN,"cannot allocate internal keyvalue table entries of size %lu , aborting ...\n", (unsigned long) size);
114  free(table);
115  return(NULL);
116  }
117  table->entries=entries;
118 
119  table->size=size;
120  table->used=0;
121  table->num_added_entries=0;
122  table->iterator_lastreadindex=-1;
123  table->iterator_lastreadentry=NULL;
124  table->iterator_next=NULL;
125  table->iterator_head=NULL;
126  table->iterator_tail=NULL;
127  for(i=0;i<table->size;i++) {
128  table->entries[i].state=KEYVALUE_TABLE_ENTRY_STATE_FREE;
129  table->entries[i].key=0;
130  table->entries[i].iterator_next=NULL;
131  table->entries[i].next=NULL;
132  table->entries[i].data=NULL;
133  }
134 
135 
136  DPRINTFP((2, DFUNCTION, -1, "leave\n"));
137  return (table);
138 }
139 #undef DFUNCTION
140 
141 #define DFUNCTION "_sion_keyvalue_table_destroy"
142 int _sion_keyvalue_table_destroy(_sion_keyvalue_table** table) {
143  size_t rc=SION_SUCCESS;
144  int i;
145  _sion_keyvalue_table_entry *entry,*next_entry;
146 
147  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
148  if((*table)->entries) {
149 
150 
151  for(i=0;i<(*table)->size;i++) {
152  /* free entry data */
153  if(((*table)->entries[i].state!=KEYVALUE_TABLE_ENTRY_STATE_FREE) && ((*table)->entries[i].data!=NULL)) {
154  _SION_SAFE_FREE((*table)->entries[i].data, NULL);
155  }
156  /* free linked list */
157  entry=(*table)->entries[i].next;
158  while (entry != NULL) {
159  if((entry->state!=KEYVALUE_TABLE_ENTRY_STATE_FREE) && (entry->data!=NULL)) {
160  _SION_SAFE_FREE(entry->data, NULL);
161  }
162  next_entry=entry->next;
163  _SION_SAFE_FREE(entry, NULL);
164  entry = next_entry;
165  }
166  }
167 
168  free((*table)->entries);
169  (*table)->entries=NULL;
170  }
171  free(*table);
172  *table = NULL;
173 
174 
175  DPRINTFP((2, DFUNCTION, -1, "leave rc=%d\n",rc));
176  return (rc);
177 }
178 #undef DFUNCTION
179 
180 #define DFUNCTION "_sion_keyvalue_table_store"
181 int _sion_keyvalue_table_store(_sion_keyvalue_table* table, sion_table_key_t key, void *data) {
182  size_t rc=SION_SUCCESS;
183  unsigned int index;
184  _sion_keyvalue_table_entry *new_entry;
185 
186  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
187 
188  index = _sion_keyvalue_table_hash_fct(key,table->size);
189  DPRINTFP((2, DFUNCTION, -1, "store entry with key %ld index=%d\n", (long) key, index));
190 
191  new_entry = &table->entries[index];
192  if (new_entry->state != KEYVALUE_TABLE_ENTRY_STATE_FREE) {
193  while (new_entry->next != NULL) {
194  new_entry = new_entry->next;
195  }
196  new_entry->next = (_sion_keyvalue_table_entry*) malloc(sizeof(_sion_keyvalue_table_entry));
197  if (new_entry->next == NULL) {
198  return(_sion_errorprint(SION_NOT_SUCCESS,_SION_ERROR_RETURN,"cannot allocate internal keyvalue table entry, aborting ...\n"));
199  }
200  DPRINTFP((2, DFUNCTION, -1, "add new entry to next list\n"));
201  table->num_added_entries++;
202  new_entry = new_entry->next;
203  }
204  table->used++;
205 
206  new_entry->state= KEYVALUE_TABLE_ENTRY_STATE_USED;
207  new_entry->key = key;
208  new_entry->data = data;
209  new_entry->next = NULL;
210  new_entry->iterator_next = NULL;
211 
212  if ( (table->iterator_head==NULL) && (table->iterator_tail==NULL) ) {
213  /* first entry */
214  table->iterator_next=table->iterator_head=table->iterator_tail=new_entry;
215  } else {
216  table->iterator_tail->iterator_next=new_entry;
217  table->iterator_tail=table->iterator_tail->iterator_next; /* advance tail */
218  }
219 
220 
221  DPRINTFP((2, DFUNCTION, -1, "new entry successfully added (key %ld index=%d)\n", (long) key, index));
222  DPRINTFP((2, DFUNCTION, -1, "TABLE[slots %d of %d, +%d, total %d] \n", table->used - table->num_added_entries,table->size,table->num_added_entries,table->used));
223 
224  DPRINTFP((2, DFUNCTION, -1, "leave rc=%d\n",rc));
225  return (rc);
226 }
227 #undef DFUNCTION
228 
229 #define DFUNCTION "_sion_keyvalue_table_lookup"
230 void * _sion_keyvalue_table_lookup(_sion_keyvalue_table* table, sion_table_key_t key) {
231  unsigned int index;
233 
234  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
235 
236  index = _sion_keyvalue_table_hash_fct(key,table->size);
237  DPRINTFP((2, DFUNCTION, -1, "lookup entry with key %ld index=%d\n", (long) key, index));
238 
239  entry = &(table->entries[index]);
240  while (entry != NULL) {
241 
242  DPRINTFP((2, DFUNCTION, -1, "search: state=%ld\n",(long) entry->state ));
243 
244  if (entry->state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
245  if(entry->key == key) {
246  DPRINTFP((2, DFUNCTION, -1, "key found %ld in key list\n",(long) entry->key ));
247  return(entry->data);
248  } else {
249  DPRINTFP((2, DFUNCTION, -1, "skip this key another key found %ld in list\n",(long) entry->key ));
250  entry = entry->next;
251  }
252  } else {
253  /* slot is empty */
254  return(NULL);
255  }
256  }
257  DPRINTFP((2, DFUNCTION, -1, "leave:entry not found\n"));
258  return(NULL);
259 
260 }
261 #undef DFUNCTION
262 
263 #define DFUNCTION "_sion_keyvalue_table_iterator_reset"
264 int _sion_keyvalue_table_iterator_reset(_sion_keyvalue_table* table) {
265 
266  int rc=SION_SUCCESS;
267 
268  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
269  table->iterator_lastreadindex=-1;
270  table->iterator_lastreadentry=NULL;
271  table->iterator_next=table->iterator_head;
272  DPRINTFP((2, DFUNCTION, -1, "leave\n"));
273 
274  return(rc);
275 }
276 #undef DFUNCTION
277 
278 #define DFUNCTION "_sion_keyvalue_table_iterator_next_in_store_order"
279 int _sion_keyvalue_table_iterator_next_in_store_order(_sion_keyvalue_table* table, sion_table_key_t *key, void **data) {
281 
282  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
283  if(table->used==0) {
284  return(SION_NOT_SUCCESS);
285  }
286  entry=table->iterator_next;
287 
288  if(entry != NULL) {
289  *key=entry->key;
290  *data=entry->data;
291  DPRINTFP((2, DFUNCTION, -1, "found entry with key %ld\n",(long) *key));
292  table->iterator_next=entry->iterator_next; /* move forward in iterator list */
293  return(SION_SUCCESS);
294  } else {
295  return(SION_NOT_SUCCESS);
296  }
297 }
298 #undef DFUNCTION
299 
300 #define DFUNCTION "_sion_keyvalue_table_iterator_next"
301 int _sion_keyvalue_table_iterator_next(_sion_keyvalue_table* table, sion_table_key_t *key, void **data) {
302 
303  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
304  if(table->used==0) {
305  return(SION_NOT_SUCCESS);
306  }
307  if(table->iterator_lastreadindex==-1) {
308  /* search first entry which must be there (used>0) */
309  DPRINTFP((2, DFUNCTION, -1, "start first\n"));
310  table->iterator_lastreadindex++;
311  while(table->iterator_lastreadindex < table->size) {
312  if (table->entries[table->iterator_lastreadindex].state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
313  table->iterator_lastreadentry = &table->entries[table->iterator_lastreadindex];
314  break;
315  }
316  table->iterator_lastreadindex++;
317  }
318  DPRINTFP((2, DFUNCTION, -1, "start first, found entry at index %d\n",table->iterator_lastreadindex));
319 
320  } else {
321 
322  /* another entry in list? */
323  if(table->iterator_lastreadentry->next != NULL) {
324  table->iterator_lastreadentry=table->iterator_lastreadentry->next;
325  DPRINTFP((2, DFUNCTION, -1, "found another entry in list at index %d\n",table->iterator_lastreadindex));
326  } else {
327  /* search forward */
328  table->iterator_lastreadindex++;
329  while(table->iterator_lastreadindex < table->size) {
330  if (table->entries[table->iterator_lastreadindex].state == KEYVALUE_TABLE_ENTRY_STATE_USED) {
331  table->iterator_lastreadentry = &table->entries[table->iterator_lastreadindex];
332  DPRINTFP((2, DFUNCTION, -1, "found entry at another index %d\n",table->iterator_lastreadindex));
333  break;
334  }
335  table->iterator_lastreadindex++;
336  }
337  }
338  }
339  if(table->iterator_lastreadindex < table->size) {
340  *key=table->iterator_lastreadentry->key;
341  *data=table->iterator_lastreadentry->data;
342  DPRINTFP((2, DFUNCTION, -1, "leave: entry found\n"));
343  return(SION_SUCCESS);
344  } else {
345  DPRINTFP((2, DFUNCTION, -1, "leave: next entry not found\n"));
346  return(SION_NOT_SUCCESS);
347  }
348 }
349 #undef DFUNCTION
350 
351 #define DFUNCTION "_sion_keyvalue_table_get_size"
352 int _sion_keyvalue_table_get_size(_sion_keyvalue_table* table) {
353  size_t help_bytes, bytes=0;
354  int i;
356 
357  DPRINTFP((2, DFUNCTION, -1, "enter\n"));
358 
359  help_bytes= sizeof(_sion_keyvalue_table);
360  DPRINTFP((2, DFUNCTION, -1, " sizeof key_table= %5d\n", help_bytes));
361  bytes+=help_bytes;
362 
363  if(table->entries) {
364 
365  help_bytes= table->size*sizeof(_sion_keyvalue_table_entry);
366  DPRINTFP((2, DFUNCTION, -1, " sizeof key_entries= %5d\n", help_bytes));
367  bytes+=help_bytes;
368 
369  help_bytes=0;
370  for(i=0;i<table->size;i++) {
371  entry=table->entries[i].next;
372  while (entry != NULL) {
373  help_bytes+=sizeof(_sion_keyvalue_table_entry);
374  entry = entry->next;
375  }
376  }
377 
378  DPRINTFP((2, DFUNCTION, -1, " sizeof key_addentries= %5d\n", help_bytes));
379  bytes+=help_bytes;
380 
381  }
382 
383  DPRINTFP((2, DFUNCTION, -1, "leave bytes=%d\n",bytes));
384  return (bytes);
385 }
386 #undef DFUNCTION
Sion Time Stamp Header.