summaryrefslogtreecommitdiff
path: root/src/benchmarks/eina/Ecore_Data.h
blob: a085401242a72db1bad23e1123446e80cbd4d7c4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
#ifndef _ECORE_DATA_H
# define _ECORE_DATA_H

#include <stdio.h>
/* we need this for size_t */
#include <stddef.h>

#ifdef EAPI
# undef EAPI
#endif

#ifdef _WIN32
# ifdef EFL_BUILD
#  ifdef DLL_EXPORT
#   define EAPI __declspec(dllexport)
#  else
#   define EAPI
#  endif
# else
#  define EAPI __declspec(dllimport)
# endif
#else
# ifdef __GNUC__
#  if __GNUC__ >= 4
#   define EAPI __attribute__ ((visibility("default")))
#  else
#   define EAPI
#  endif
# else
#  define EAPI
# endif
#endif

/**
 * @file Ecore_Data.h
 * @brief Contains threading, list, hash, debugging and tree functions.
 */

# ifdef __cplusplus
extern "C" {
# endif


#ifndef TRUE
# define TRUE 1
#endif

#ifndef FALSE
# define FALSE 0
#endif

#ifdef FREE
# undef FREE
#endif
#define FREE(ptr) free(ptr); ptr = NULL;

#ifdef IF_FREE
# undef IF_FREE
#endif
#define IF_FREE(ptr) if (ptr) {free(ptr); } ptr = NULL;

/* convenience macros for checking pointer parameters for non-NULL */
#undef CHECK_PARAM_POINTER_RETURN
#define CHECK_PARAM_POINTER_RETURN(sparam, param, ret) \
   if (!(param)) \
     { \
        printf("***** Developer Warning ***** :\n" \
               "\tThis program is calling:\n\n" \
               "\t%s();\n\n" \
               "\tWith the parameter:\n\n" \
               "\t%s\n\n" \
               "\tbeing NULL. Please fix your program.", __func__, sparam); \
        if (getenv("ECORE_ERROR_ABORT")) { abort(); } \
        return ret; \
     }

#undef CHECK_PARAM_POINTER
#define CHECK_PARAM_POINTER(sparam, param) \
   if (!(param)) \
     { \
        printf("***** Developer Warning ***** :\n" \
               "\tThis program is calling:\n\n" \
               "\t%s();\n\n" \
               "\tWith the parameter:\n\n" \
               "\t%s\n\n" \
               "\tbeing NULL. Please fix your program.", __func__, sparam); \
        if (getenv("ECORE_ERROR_ABORT")) { abort(); } \
        return; \
     }


# ifdef __sgi
#  define __func__ "unknown"
#  ifndef __cplusplus
#   define inline
#  endif
# endif

# define ECORE_SORT_MIN 0
# define ECORE_SORT_MAX 1

typedef void (*Ecore_For_Each)(void *value, void *user_data);
# define ECORE_FOR_EACH(function) ((Ecore_For_Each)function)

typedef void (*Ecore_Free_Cb)(void *data);
# define ECORE_FREE_CB(func) ((Ecore_Free_Cb)func)

typedef unsigned int (*Ecore_Hash_Cb)(const void *key);
# define ECORE_HASH_CB(function) ((Ecore_Hash_Cb)function)

typedef int (*Ecore_Compare_Cb)(const void *data1, const void *data2);
# define ECORE_COMPARE_CB(function) ((Ecore_Compare_Cb)function)

typedef struct _ecore_list Ecore_List;
# define ECORE_LIST(list) ((Ecore_List *)list)

typedef struct _ecore_list_node Ecore_List_Node;
# define ECORE_LIST_NODE(node) ((Ecore_List_Node *)node)

typedef struct _ecore_strbuf Ecore_Strbuf;
# define ECORE_STRBUF(buf) ((Ecore_Strbuf *)buf)

struct _ecore_list_node
{
   void *data;
   struct _ecore_list_node *next;
};

struct _ecore_list
{
   Ecore_List_Node *first; /* The first node in the list */
   Ecore_List_Node *last; /* The last node in the list */
   Ecore_List_Node *current; /* The current node in the list */

   Ecore_Free_Cb free_func; /* The callback to free data in nodes */

   int nodes; /* The number of nodes in the list */
   int index; /* The position from the front of the
                 list of current node */
};

EAPI int              ecore_direct_compare(const void *key1, const void *key2);
EAPI int              ecore_str_compare(const void *key1, const void *key2);

EAPI unsigned int     ecore_direct_hash(const void *key);
EAPI unsigned int     ecore_str_hash(const void *key);

/* Creating and initializing new list structures */
EAPI Ecore_List *     ecore_list_new(void);
EAPI int              ecore_list_init(Ecore_List *list);

/* Adding items to the list */
EAPI int              ecore_list_append(Ecore_List *list, void *_data);
EAPI int              ecore_list_prepend(Ecore_List *list, void *_data);
EAPI int              ecore_list_insert(Ecore_List *list, void *_data);
EAPI int              ecore_list_append_list(Ecore_List *list,
                                             Ecore_List *append);
EAPI int              ecore_list_prepend_list(Ecore_List *list,
                                              Ecore_List *prepend);

/* Removing items from the list */
EAPI int              ecore_list_remove_destroy(Ecore_List *list);
EAPI void *           ecore_list_remove(Ecore_List *list);
EAPI void *           ecore_list_first_remove(Ecore_List *list);
EAPI void *           ecore_list_last_remove(Ecore_List *list);

/* Retrieve the current position in the list */
EAPI void *           ecore_list_current(Ecore_List *list);
EAPI void *           ecore_list_first(Ecore_List *list);
EAPI void *           ecore_list_last(Ecore_List *list);
EAPI int              ecore_list_index(Ecore_List *list);
EAPI int              ecore_list_count(Ecore_List *list);

/* Traversing the list */
EAPI int              ecore_list_for_each(Ecore_List *list,
                                          Ecore_For_Each function,
                                          void *user_data);
EAPI void *           ecore_list_first_goto(Ecore_List *list);
EAPI void *           ecore_list_last_goto(Ecore_List *list);
EAPI void *           ecore_list_index_goto(Ecore_List *list, int index);
EAPI void *           ecore_list_goto(Ecore_List *list, const void *_data);

/* Traversing the list and returning data */
EAPI void *           ecore_list_next(Ecore_List *list);
EAPI void *           ecore_list_find(Ecore_List *list,
                                      Ecore_Compare_Cb function,
                                      const void *user_data);

/* Sorting the list */
EAPI int              ecore_list_sort(Ecore_List *list,
                                      Ecore_Compare_Cb compare,
                                      char order);
EAPI int              ecore_list_mergesort(Ecore_List *list,
                                           Ecore_Compare_Cb compare,
                                           char order);
EAPI int              ecore_list_heapsort(Ecore_List *list,
                                          Ecore_Compare_Cb compare,
                                          char order);
EAPI void             ecore_list_merge(Ecore_List *list, Ecore_List *l2,
                                       Ecore_Compare_Cb, char order);

/* Check to see if there is any data in the list */
EAPI int              ecore_list_empty_is(Ecore_List *list);

/* Remove every node in the list without freeing the list itself */
EAPI int              ecore_list_clear(Ecore_List *list);
/* Free the list and its contents */
EAPI void             ecore_list_destroy(Ecore_List *list);

/* Creating and initializing list nodes */
EAPI Ecore_List_Node *ecore_list_node_new(void);
EAPI int              ecore_list_node_init(Ecore_List_Node *newNode);

/* Destroying nodes */
EAPI int              ecore_list_node_destroy(Ecore_List_Node *_e_node,
                                              Ecore_Free_Cb free_func);

EAPI int              ecore_list_free_cb_set(Ecore_List *list,
                                             Ecore_Free_Cb free_func);

typedef Ecore_List Ecore_DList;
# define ECORE_DLIST(dlist) ((Ecore_DList *)dlist)

typedef struct _ecore_dlist_node Ecore_DList_Node;
# define ECORE_DLIST_NODE(dlist) ((Ecore_DList_Node *)dlist)

struct _ecore_dlist_node
{
   Ecore_List_Node single;
   Ecore_DList_Node *previous;
};

/* Creating and initializing new list structures */
EAPI Ecore_DList *ecore_dlist_new(void);
EAPI int          ecore_dlist_init(Ecore_DList *list);
EAPI void         ecore_dlist_destroy(Ecore_DList *list);

/* Adding items to the list */
EAPI int          ecore_dlist_append(Ecore_DList *_e_dlist, void *_data);
EAPI int          ecore_dlist_prepend(Ecore_DList *_e_dlist, void *_data);
EAPI int          ecore_dlist_insert(Ecore_DList *_e_dlist, void *_data);
EAPI int          ecore_dlist_append_list(Ecore_DList *_e_dlist,
                                          Ecore_DList *append);
EAPI int          ecore_dlist_prepend_list(Ecore_DList *_e_dlist,
                                           Ecore_DList *prepend);

/* Info about list's state */
# define ecore_dlist_first(list) ecore_list_first(list)
# define ecore_dlist_last(list) ecore_list_last(list)
EAPI void *            ecore_dlist_current(Ecore_DList *list);
EAPI int               ecore_dlist_index(Ecore_DList *list);
# define ecore_dlist_count(list) ecore_list_count(list)

/* Removing items from the list */
EAPI void *            ecore_dlist_remove(Ecore_DList *_e_dlist);
EAPI void *            ecore_dlist_first_remove(Ecore_DList *_e_dlist);
EAPI int               ecore_dlist_remove_destroy(Ecore_DList *list);
EAPI void *            ecore_dlist_last_remove(Ecore_DList *_e_dlist);

/* Traversing the list */
# define ecore_dlist_for_each(list, function, user_data) \
   ecore_list_for_each(list, function, user_data)
EAPI void *            ecore_dlist_first_goto(Ecore_DList *_e_dlist);
EAPI void *            ecore_dlist_last_goto(Ecore_DList *_e_dlist);
EAPI void *            ecore_dlist_index_goto(Ecore_DList *_e_dlist, int index);
EAPI void *            ecore_dlist_goto(Ecore_DList *_e_dlist, void *_data);

/* Traversing the list and returning data */
EAPI void *            ecore_dlist_next(Ecore_DList *list);
EAPI void *            ecore_dlist_previous(Ecore_DList *list);

/* Sorting the list */
EAPI int               ecore_dlist_sort(Ecore_DList *list,
                                        Ecore_Compare_Cb compare,
                                        char order);
EAPI int               ecore_dlist_mergesort(Ecore_DList *list,
                                             Ecore_Compare_Cb compare,
                                             char order);
# define ecore_dlist_heapsort(list, compare, order) \
   ecore_list_heapsort(list, compare, order)
EAPI void              ecore_dlist_merge(Ecore_DList *list, Ecore_DList *l2,
                                         Ecore_Compare_Cb, char order);

/* Check to see if there is any data in the list */
EAPI int               ecore_dlist_empty_is(Ecore_DList *_e_dlist);

/* Remove every node in the list without free'ing it */
EAPI int               ecore_dlist_clear(Ecore_DList *_e_dlist);

/* Creating and initializing list nodes */
EAPI int               ecore_dlist_node_init(Ecore_DList_Node *node);
EAPI Ecore_DList_Node *ecore_dlist_node_new(void);

/* Destroying nodes */
EAPI int               ecore_dlist_node_destroy(Ecore_DList_Node *node,
                                                Ecore_Free_Cb free_func);

EAPI int               ecore_dlist_free_cb_set(Ecore_DList *dlist,
                                               Ecore_Free_Cb free_func);



/*
 * Hash Table Implementation:
 *
 * Traditional hash table implementation. I had tried a list of tables
 * approach to save on the realloc's but it ended up being much slower than
 * the traditional approach.
 */

typedef struct _ecore_hash_node Ecore_Hash_Node;
# define ECORE_HASH_NODE(hash) ((Ecore_Hash_Node *)hash)

struct _ecore_hash_node
{
   Ecore_Hash_Node *next; /* Pointer to the next node in the bucket list */
   void *key; /* The key for the data node */
   void *value; /* The value associated with this node */
};

typedef struct _ecore_hash Ecore_Hash;
# define ECORE_HASH(hash) ((Ecore_Hash *)hash)

struct _ecore_hash
{
   Ecore_Hash_Node **buckets;
   int size; /* An index into the table of primes to
                determine size */
   int nodes; /* The number of nodes currently in the hash */

   int index; /* The current index into the bucket table */

   Ecore_Compare_Cb compare; /* The function used to compare node values */
   Ecore_Hash_Cb hash_func; /* The callback function to determine hash */

   Ecore_Free_Cb free_key; /* The callback function to free key */
   Ecore_Free_Cb free_value; /* The callback function to free value */
};

/* Create and initialize a hash */
EAPI Ecore_Hash *ecore_hash_new(Ecore_Hash_Cb hash_func,
                                Ecore_Compare_Cb compare);
EAPI int         ecore_hash_init(Ecore_Hash *hash,
                                 Ecore_Hash_Cb hash_func,
                                 Ecore_Compare_Cb compare);

/* Functions related to freeing the data in the hash table */
EAPI int         ecore_hash_free_key_cb_set(Ecore_Hash *hash,
                                            Ecore_Free_Cb function);
EAPI int         ecore_hash_free_value_cb_set(Ecore_Hash *hash,
                                              Ecore_Free_Cb function);
EAPI void        ecore_hash_destroy(Ecore_Hash *hash);

EAPI int         ecore_hash_count(Ecore_Hash *hash);
EAPI int         ecore_hash_for_each_node(Ecore_Hash *hash,
                                          Ecore_For_Each for_each_func,
                                          void *user_data);
EAPI Ecore_List *ecore_hash_keys(Ecore_Hash *hash);

/* Retrieve and store data into the hash */
EAPI void *      ecore_hash_get(Ecore_Hash *hash, const void *key);
EAPI int         ecore_hash_set(Ecore_Hash *hash, void *key, void *value);
EAPI int         ecore_hash_hash_set(Ecore_Hash *hash, Ecore_Hash *set);
EAPI void *      ecore_hash_remove(Ecore_Hash *hash, const void *key);
EAPI void *      ecore_hash_find(Ecore_Hash *hash,
                                 Ecore_Compare_Cb compare,
                                 const void *value);
EAPI void        ecore_hash_dump_graph(Ecore_Hash *hash);
EAPI void        ecore_hash_dump_stats(Ecore_Hash *hash);


typedef struct _ecore_heap Ecore_Sheap;
# define ECORE_HEAP(heap) ((Ecore_Sheap *)heap)

struct _ecore_heap
{
   void **data;
   int size;
   int space;

   char order, sorted;

   /* Callback for comparing node values, default is direct comparison */
   Ecore_Compare_Cb compare;

   /* Callback for freeing node data, default is NULL */
   Ecore_Free_Cb free_func;
};

EAPI Ecore_Sheap *ecore_sheap_new(Ecore_Compare_Cb compare, int size);
EAPI void         ecore_sheap_destroy(Ecore_Sheap *heap);
EAPI int          ecore_sheap_init(Ecore_Sheap *heap,
                                   Ecore_Compare_Cb compare,
                                   int size);
EAPI int          ecore_sheap_free_cb_set(Ecore_Sheap *heap,
                                          Ecore_Free_Cb free_func);
EAPI int          ecore_sheap_insert(Ecore_Sheap *heap, void *data);
EAPI void *       ecore_sheap_extract(Ecore_Sheap *heap);
EAPI void *       ecore_sheap_extreme(Ecore_Sheap *heap);
EAPI int          ecore_sheap_change(Ecore_Sheap *heap,
                                     void *item,
                                     void *newval);
EAPI int          ecore_sheap_compare_set(Ecore_Sheap *heap,
                                          Ecore_Compare_Cb compare);
EAPI void         ecore_sheap_order_set(Ecore_Sheap *heap, char order);
EAPI void         ecore_sheap_sort(Ecore_Sheap *heap);

EAPI void *       ecore_sheap_item(Ecore_Sheap *heap, int i);


typedef struct _ecore_string Ecore_String;
struct _ecore_string
{
   char *string;
   int references;
};

EAPI int         ecore_string_init();
EAPI int         ecore_string_shutdown();
EAPI const char *ecore_string_instance(const char *string);
EAPI void        ecore_string_release(const char *string);

typedef struct _Ecore_Tree_Node Ecore_Tree_Node;
# define ECORE_TREE_NODE(object) ((Ecore_Tree_Node *)object)
struct _Ecore_Tree_Node
{

   /* The actual data for each node */
   void *key;
   void *value;

   /* Pointers to surrounding nodes */
   Ecore_Tree_Node *parent;
   Ecore_Tree_Node *left_child;
   Ecore_Tree_Node *right_child;

   /* Book keeping information for quicker balancing of the tree */
   int max_right;
   int max_left;
};

typedef struct _Ecore_Tree Ecore_Tree;
# define ECORE_TREE(object) ((Ecore_Tree *)object)
struct _Ecore_Tree
{
   /* Nodes of the tree */
   Ecore_Tree_Node *tree;

   /* Callback for comparing node values, default is direct comparison */
   Ecore_Compare_Cb compare_func;

   /* Callback for freeing node data, default is NULL */
   Ecore_Free_Cb free_value;
   /* Callback for freeing node key, default is NULL */
   Ecore_Free_Cb free_key;
};

/* Some basic tree functions */
/* Allocate and initialize a new tree */
EAPI Ecore_Tree *     ecore_tree_new(Ecore_Compare_Cb compare_func);
/* Initialize a new tree */
EAPI int              ecore_tree_init(Ecore_Tree *tree,
                                      Ecore_Compare_Cb compare_func);

/* Free the tree */
EAPI int              ecore_tree_destroy(Ecore_Tree *tree);
/* Check to see if the tree has any nodes in it */
EAPI int              ecore_tree_empty_is(Ecore_Tree *tree);

/* Retrieve the value associated with key */
EAPI void *           ecore_tree_get(Ecore_Tree *tree, const void *key);
EAPI Ecore_Tree_Node *ecore_tree_get_node(Ecore_Tree *tree, const void *key);
/* Retrieve the value of node with key greater than or equal to key */
EAPI void *           ecore_tree_closest_larger_get(Ecore_Tree *tree,
                                                    const void *key);
/* Retrieve the value of node with key less than or equal to key */
EAPI void *           ecore_tree_closest_smaller_get(Ecore_Tree *tree,
                                                     const void *key);

/* Set the value associated with key to value */
EAPI int              ecore_tree_set(Ecore_Tree *tree, void *key, void *value);
/* Remove the key from the tree */
EAPI int              ecore_tree_remove(Ecore_Tree *tree, const void *key);

/* Add a node to the tree */
EAPI int              ecore_tree_node_add(Ecore_Tree *tree,
                                          Ecore_Tree_Node *node);
/* Remove a node from the tree */
EAPI int              ecore_tree_node_remove(Ecore_Tree *tree,
                                             Ecore_Tree_Node *node);

/* For each node in the tree perform the for_each_func function */
/* For this one pass in the node */
EAPI int              ecore_tree_for_each_node(Ecore_Tree *tree,
                                               Ecore_For_Each for_each_func,
                                               void *user_data);
/* And here pass in the node's value */
EAPI int              ecore_tree_for_each_node_value(
   Ecore_Tree *tree,
   Ecore_For_Each
   for_each_func,
   void *user_data);

/* Some basic node functions */
/* Initialize a node */
EAPI int              ecore_tree_node_init(Ecore_Tree_Node *new_node);
/* Allocate and initialize a new node */
EAPI Ecore_Tree_Node *ecore_tree_node_new(void);
/* Free the desired node */
EAPI int              ecore_tree_node_destroy(Ecore_Tree_Node *node,
                                              Ecore_Free_Cb free_value,
                                              Ecore_Free_Cb free_key);

/* Set the node's key to key */
EAPI int              ecore_tree_node_key_set(Ecore_Tree_Node *node, void *key);
/* Retrieve the key in node */
EAPI void *           ecore_tree_node_key_get(Ecore_Tree_Node *node);

/* Set the node's value to value */
EAPI int              ecore_tree_node_value_set(Ecore_Tree_Node *node,
                                                void *value);
/* Retrieve the value in node */
EAPI void *           ecore_tree_node_value_get(Ecore_Tree_Node *node);

/* Add a function to free the data stored in nodes */
EAPI int              ecore_tree_free_value_cb_set(Ecore_Tree *tree,
                                                   Ecore_Free_Cb free_value);
/* Add a function to free the keys stored in nodes */
EAPI int              ecore_tree_free_key_cb_set(Ecore_Tree *tree,
                                                 Ecore_Free_Cb free_key);


EAPI Ecore_Strbuf *   ecore_strbuf_new(void);
EAPI void             ecore_strbuf_free(Ecore_Strbuf *buf);
EAPI void             ecore_strbuf_append(Ecore_Strbuf *buf, const char *str);
EAPI void             ecore_strbuf_append_char(Ecore_Strbuf *buf, char c);
EAPI void             ecore_strbuf_insert(Ecore_Strbuf *buf, const char *str,
                                          size_t pos);
# define ecore_strbuf_prepend(buf, str) ecore_strbuf_insert(buf, str, 0)
EAPI const char *     ecore_strbuf_string_get(Ecore_Strbuf *buf);
EAPI size_t           ecore_strbuf_length_get(Ecore_Strbuf *buf);
EAPI int              ecore_strbuf_replace(Ecore_Strbuf *buf, const char *str,
                                           const char *with, unsigned int n);
# define ecore_strbuf_replace_first(buf, str, with) \
   ecore_strbuf_replace(buf, str, with, 1)
EAPI int              ecore_strbuf_replace_all(Ecore_Strbuf *buf,
                                               const char *str,
                                               const char *with);

extern int            ecore_str_compare(const void *key1, const void *key2);
extern int            ecore_direct_compare(const void *key1, const void *key2);
extern unsigned int   ecore_str_hash(const void *key);

#ifdef __cplusplus
}
#endif
#endif /* _ECORE_DATA_H */