1 /* EINA - EFL data type library
2 * Copyright (C) 2011 Cedric Bail
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library;
16 * if not, see <http://www.gnu.org/licenses/>.
25 #include "eina_private.h"
26 #include "eina_inlist.h"
27 #include "eina_rbtree.h"
28 #include "eina_mempool.h"
29 #include "eina_trash.h"
31 #include "eina_stringshare.h"
32 #include "eina_lock.h"
34 #include "eina_object.h"
36 /*============================================================================*
38 *============================================================================*/
44 /* If we are on a 64bits computer user bigger generation and ID */
45 /* FIXME: make it GCC independant */
46 /* FIXME: maybe having 2^32 objects doesn't make sense and 2^24 are enough
47 so instead of increasing the object count, we could just add a magic
48 to first check if the pointer is valid at all (and maybe use a pointer
49 that will always trigger a segv if we try to use it directly).
52 typedef unsigned long Eina_Object_ID;
53 typedef unsigned short Eina_Object_Generation;
54 # define EINA_GEN_OFFSET 48
55 # define EINA_ID_STR "%lu"
57 typedef unsigned __int64 Eina_Object_ID;
58 typedef unsigned short Eina_Object_Generation;
59 # define EINA_GEN_OFFSET 48
60 # define EINA_ID_STR "%I64u"
62 typedef unsigned int Eina_Object_ID;
63 typedef unsigned char Eina_Object_Generation;
64 # define EINA_GEN_OFFSET 24
65 # define EINA_ID_STR "%u"
68 typedef struct _Eina_Class_Range Eina_Class_Range;
69 typedef struct _Eina_Object_Item Eina_Object_Item;
70 typedef struct _Eina_Range Eina_Range;
71 typedef struct _Eina_Class_Top Eina_Class_Top;
81 struct _Eina_Object_Item
84 Eina_Class_Range *range;
86 Eina_Object_Item *parent;
92 struct _Eina_Class_Range
100 unsigned int empty_count;
105 Eina_Object_Item **pointer_array;
106 Eina_Object_Generation generation_array[1];
109 struct _Eina_Class_Top
111 Eina_Class *top_parent;
113 Eina_Inlist *available;
115 unsigned int upper_limit;
129 Eina_Class_Callback constructor;
130 Eina_Class_Callback destructor;
133 Eina_Inlist *allocated_range;
135 Eina_Mempool *mempool;
136 unsigned int class_size;
137 unsigned int object_size;
138 unsigned int pool_size;
140 Eina_Bool repack_needed : 1;
142 #ifdef EINA_HAVE_THREADS
143 # ifdef EINA_HAVE_DEBUG_THREADS
152 static const char EINA_MAGIC_CLASS_STR[] = "Eina Class";
154 static Eina_Mempool *_eina_class_mp = NULL;
155 static Eina_Mempool *_eina_top_mp = NULL;
156 static Eina_Mempool *_eina_range_mp = NULL;
157 static int _eina_object_log_dom = -1;
158 static unsigned int _eina_object_item_size = 0;
163 #define ERR(...) EINA_LOG_DOM_ERR(_eina_object_log_dom, __VA_ARGS__)
168 #define DBG(...) EINA_LOG_DOM_DBG(_eina_object_log_dom, __VA_ARGS__)
170 #define EINA_MAGIC_CHECK_CLASS(d, ...) \
172 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_CLASS)) \
174 EINA_MAGIC_FAIL(d, EINA_MAGIC_CLASS); \
175 return __VA_ARGS__; \
180 _eina_rbtree_cmp_range(const Eina_Rbtree *node, const void *key,
181 __UNUSED__ int length, __UNUSED__ void *data)
183 Eina_Class_Range *range;
186 range = EINA_RBTREE_CONTAINER_GET(node, Eina_Class_Range);
187 id = (Eina_Object_ID) key;
189 if (id < range->start) return -1;
190 else if (id >= range->end) return 1;
194 static Eina_Rbtree_Direction
195 _eina_class_direction_range(const Eina_Rbtree *left,
196 const Eina_Rbtree *right,
197 __UNUSED__ void *data)
199 Eina_Class_Range *rl;
200 Eina_Class_Range *rr;
202 rl = EINA_RBTREE_CONTAINER_GET(left, Eina_Class_Range);
203 rr = EINA_RBTREE_CONTAINER_GET(right, Eina_Class_Range);
205 if (rl->start < rr->start) return EINA_RBTREE_LEFT;
206 return EINA_RBTREE_RIGHT;
209 /* really destroying a range and handling that case is a complex
210 problem to solve. Not handling it right now, exposing myself to
213 _eina_range_cleanup(Eina_Class_Range *range)
220 _eina_object_constructor_call(Eina_Class *class, void *object)
222 if (class->parent) _eina_object_constructor_call(class->parent, object);
224 if (class->constructor) class->constructor(class, object, class->data);
228 _eina_object_destructor_call(Eina_Class *class, void *object)
230 if (class->destructor) class->destructor(class, object, class->data);
232 if (class->parent) _eina_object_destructor_call(class->parent, object);
236 _eina_object_get(Eina_Object_Item *item)
238 Eina_Object_Generation gen;
241 if (!item) return NULL;
243 gen = item->range->generation_array[item->index];
245 id = ((Eina_Object_ID) gen << EINA_GEN_OFFSET) + item->range->start + item->index;
247 return (Eina_Object *) id;
250 static Eina_Object_Item *
251 _eina_object_find_item(Eina_Class *class, Eina_Object *object)
253 Eina_Class_Range *matched;
254 Eina_Object_Item *item;
257 Eina_Object_Generation generation;
261 id = (Eina_Object_ID) object;
262 idx = id & (((Eina_Object_ID) 1 << EINA_GEN_OFFSET) - 1);
263 generation = id & !(((Eina_Object_ID) 1 << EINA_GEN_OFFSET) - 1);
265 /* Try to find the ID */
266 match = eina_rbtree_inline_lookup(class->top->range,
267 (void*) idx, sizeof (Eina_Object_ID),
268 _eina_rbtree_cmp_range, NULL);
269 /* ID not found, invalid pointer ! */
272 ERR("%p: ID ["EINA_ID_STR"] not found in class hiearchy of [%s].",
273 object, idx, class->name);
276 matched = EINA_RBTREE_CONTAINER_GET(match, Eina_Class_Range);
278 /* generation mismatch, invalid pointer ! */
279 if (generation != matched->generation_array[idx - matched->start])
281 ERR("%p: generation mismatch [%i] vs [%i].",
282 object, generation, matched->generation_array[idx - matched->start]);
286 /* does it belong to the right class ? */
287 for (search = matched->type; search && search != class; search = search->parent)
290 /* class match request or invalid pointer ! */
293 ERR("%p: from class [%s] is not in the hierarchie of [%s].",
294 object, matched->type->name, class->name);
298 /* retrieve pointer */
299 item = matched->pointer_array[id - matched->start];
300 /* allocated or invalid pointer ? */
303 ERR("%p: ID is not allocated.", object);
307 /* be aware, that because we use eina_trash to store empty pointer after first use,
308 pointer could be != NULL and still be empty. Need another pool of data somewhere
309 to store the state of the allocation... Is it needed ?
316 _eina_object_item_del(Eina_Object_Item *item)
320 class = item->range->type;
321 _eina_object_destructor_call(class,
322 (unsigned char*) item + _eina_object_item_size);
324 eina_trash_push(&item->range->empty, item->range->pointer_array + item->index);
325 item->range->generation_array[item->index]++;
326 item->range->empty_count++;
328 if (item->range->empty_count == item->range->end - item->range->start)
329 _eina_range_cleanup(item->range);
333 item->parent->link = eina_inlist_remove(item->parent->link, EINA_INLIST_GET(item));
338 Eina_Object_Item *child;
340 child = EINA_INLIST_CONTAINER_GET(item->link, Eina_Object_Item);
341 _eina_object_item_del(child);
344 eina_mempool_free(class->mempool, item);
347 static Eina_Class_Range *
348 _eina_class_empty_range_get(Eina_Inlist *list)
352 Eina_Class_Range *range;
354 range = EINA_INLIST_CONTAINER_GET(list, Eina_Class_Range);
355 if (range->empty_count > 0)
364 static Eina_Class_Range *
365 _eina_class_range_add(Eina_Class *class)
367 Eina_Class_Range *range;
369 Eina_Range *av = NULL;
371 range = malloc(sizeof (Eina_Class_Range)
372 + sizeof (Eina_Object_Item*) * class->pool_size
373 + sizeof (Eina_Object_Generation) * (class->pool_size - 1));
374 if (!range) return NULL;
376 tmp = (void*) (range + 1);
377 tmp += sizeof (Eina_Object_Generation) * (class->pool_size - 1);
379 range->pointer_array = (Eina_Object_Item**) tmp;
381 /* no need to fix generation to a specific value as random value should be just fine */
382 memset(range->pointer_array, 0, sizeof (Eina_Object_Item*) * class->pool_size);
388 /* and now find an empty block */
389 EINA_INLIST_FOREACH(class->top->available, av)
390 if (av->end - av->start == class->pool_size)
395 range->start = av->start;
396 range->end = av->end;
398 class->top->available = eina_inlist_remove(class->top->available,
399 EINA_INLIST_GET(av));
400 eina_mempool_free(_eina_range_mp, av);
404 range->start = class->top->upper_limit;
405 range->end = range->start + class->pool_size;
406 class->top->upper_limit = range->end;
413 _eina_class_range_del(Eina_Class_Range *range)
418 top = range->type->top;
420 keep = eina_mempool_malloc(_eina_range_mp, sizeof (Eina_Range));
423 ERR("Not enougth memory to keep track of allocated range.");
424 goto delete_class_range;
427 keep->start = range->start;
428 keep->end = range->end;
430 top->available = eina_inlist_prepend(top->available,
431 EINA_INLIST_GET(keep));
434 top->range = eina_rbtree_inline_remove(top->range, EINA_RBTREE_GET(range),
435 _eina_class_direction_range, NULL);
436 range->type->allocated_range = eina_inlist_remove(range->type->allocated_range,
437 EINA_INLIST_GET(range));
442 _eina_class_range_repack(void *dst, void *src, void *data)
444 Eina_Object_Item *di = dst;
445 Eina_Object_Item *si = src;
446 Eina_Class *class = data;
450 si->range->pointer_array[si->index] = di;
452 /* FIXME: We could just lock the right Eina_Class_Range
453 here instead of locking all the Class */
461 eina_object_init(void)
463 _eina_object_log_dom = eina_log_domain_register("eina_object",
464 EINA_LOG_COLOR_DEFAULT);
465 if (_eina_object_log_dom < 0)
467 EINA_LOG_ERR("Could not register log domain: eina_list");
471 _eina_class_mp = eina_mempool_add("chained_mempool", "class",
472 NULL, sizeof (Eina_Class), 64);
475 ERR("ERROR: Mempool for Eina_Class cannot be allocated in object init.");
479 _eina_top_mp = eina_mempool_add("chained_mempool", "top",
480 NULL, sizeof (Eina_Class_Top), 64);
483 ERR("ERROR: Mempool for Eina_Class_Top cannot be allocated in object init.");
487 _eina_range_mp = eina_mempool_add("chained_mempool", "range",
488 NULL, sizeof (Eina_Range), 64);
491 ERR("ERROR: Mempool for Eina_Class_Top cannot be allocated in object init.");
495 #define EMS(n) eina_magic_string_static_set(n, n ## _STR)
496 EMS(EINA_MAGIC_CLASS);
499 _eina_object_item_size = eina_mempool_alignof(sizeof (Eina_Object_Item));
504 eina_log_domain_unregister(_eina_object_log_dom);
505 _eina_object_log_dom = -1;
509 eina_mempool_del(_eina_top_mp);
515 eina_mempool_del(_eina_class_mp);
516 _eina_class_mp = NULL;
523 eina_object_shutdown(void)
525 eina_mempool_del(_eina_class_mp);
526 eina_mempool_del(_eina_top_mp);
528 eina_log_domain_unregister(_eina_object_log_dom);
529 _eina_object_log_dom = -1;
534 eina_class_new(const char *name,
535 unsigned int class_size,
536 unsigned int pool_size,
537 Eina_Class_Callback constructor,
538 Eina_Class_Callback destructor,
543 unsigned int object_size = class_size;
545 if (parent) EINA_MAGIC_CHECK_CLASS(parent, NULL);
547 c = eina_mempool_malloc(_eina_class_mp, sizeof (Eina_Class));
553 parent->childs = eina_inlist_append(parent->childs,
555 c->top = parent->top;
559 c->top = eina_mempool_malloc(_eina_top_mp, sizeof (Eina_Class_Top));
561 c->top->top_parent = c;
562 c->top->range = NULL;
563 c->top->available = NULL;
564 c->top->upper_limit = 0;
567 /* Build complete object size and find top parent */
568 if (parent) object_size += parent->object_size;
570 c->name = eina_stringshare_add(name);
571 c->class_size = class_size;
572 c->pool_size = pool_size;
573 c->object_size = object_size;
574 c->mempool = eina_mempool_add("chained_mempool", "range",
576 _eina_object_item_size + object_size, pool_size);
578 c->constructor = constructor;
579 c->destructor = destructor;
582 c->allocated_range = NULL;
585 #ifdef EINA_HAVE_THREADS
586 # ifdef EINA_HAVE_DEBUG_THREADS
587 c->self = pthread_self();
589 eina_lock_new(&c->mutex);
592 EINA_MAGIC_SET(c, EINA_MAGIC_CLASS);
598 eina_class_name_get(Eina_Class *class)
600 EINA_MAGIC_CHECK_CLASS(class, NULL);
606 eina_class_size_get(Eina_Class *class)
608 EINA_MAGIC_CHECK_CLASS(class, 0);
610 return class->class_size;
614 eina_class_object_size_get(Eina_Class *class)
616 EINA_MAGIC_CHECK_CLASS(class, 0);
618 return class->object_size;
622 eina_class_del(Eina_Class *class)
624 EINA_MAGIC_CHECK_CLASS(class);
626 EINA_MAGIC_SET(class, 0);
628 while (class->allocated_range)
629 _eina_class_range_del(EINA_INLIST_CONTAINER_GET(class->allocated_range,
632 while (class->childs)
636 child = EINA_INLIST_CONTAINER_GET(class->childs, Eina_Class);
637 eina_class_del(child);
642 class->parent->childs = eina_inlist_remove(class->parent->childs,
643 EINA_INLIST_GET(class));
647 while (class->top->available)
651 range = EINA_INLIST_CONTAINER_GET(class->top->available, Eina_Range);
652 class->top->available = eina_inlist_remove(class->top->available,
653 class->top->available);
654 eina_mempool_free(_eina_range_mp, range);
658 #ifdef EINA_HAVE_THREADS
659 # ifdef EINA_HAVE_DEBUG_THREADS
660 assert(pthread_equal(class->self, pthread_self()));
662 eina_lock_free(&class->mutex);
665 eina_mempool_del(class->mempool);
666 eina_mempool_free(_eina_class_mp, class);
670 eina_class_repack(Eina_Class *class)
674 EINA_MAGIC_CHECK_CLASS(class);
676 if (!eina_lock_take(&class->mutex))
678 #ifdef EINA_HAVE_DEBUG_THREADS
680 assert(pthread_equal(class->self, pthread_self()));
684 eina_mempool_repack(class->mempool, _eina_class_range_repack, class);
686 eina_lock_release(&class->mutex);
688 EINA_INLIST_FOREACH(class->childs, child)
689 eina_class_repack(child);
693 eina_object_add(Eina_Class *class)
695 Eina_Class_Range *range;
696 Eina_Object_Item **object;
699 EINA_MAGIC_CHECK_CLASS(class, NULL);
701 /* No need to lock the class as we don't access/modify the pointer inside
704 range = _eina_class_empty_range_get(class->allocated_range);
705 if (!range) range = _eina_class_range_add(class);
707 if (range->empty_count == 0)
709 ERR("The impossible happen, range is empty when it should not !");
713 range->empty_count--;
715 object = eina_trash_pop(&range->empty);
716 if (!object) object = range->pointer_array + range->current++;
718 localid = object - range->pointer_array;
720 *object = eina_mempool_malloc(class->mempool,
721 class->object_size + _eina_object_item_size);
723 (*object)->index = localid;
724 (*object)->link = NULL;
725 (*object)->range = range;
727 _eina_object_constructor_call(class,
728 ((unsigned char*)(*object)) + _eina_object_item_size);
730 if (!(++range->generation_array[localid]))
731 ++range->generation_array[localid];
733 return _eina_object_get(*object);
737 eina_object_pointer_get(Eina_Class *class,
740 Eina_Object_Item *item;
741 unsigned char *mem = NULL;
743 if (!object) return NULL;
744 EINA_MAGIC_CHECK_CLASS(class, NULL);
746 if (!eina_lock_take(&class->mutex))
748 #ifdef EINA_HAVE_DEBUG_THREADS
749 assert(pthread_equal(class->self, pthread_self()));
753 item = _eina_object_find_item(class, object);
754 if (!item) goto on_error;
756 mem = (unsigned char*) item + _eina_object_item_size;
759 eina_lock_release(&class->mutex);
765 eina_object_del(Eina_Class *class,
768 Eina_Object_Item *item;
770 if (!object) return ;
771 EINA_MAGIC_CHECK_CLASS(class);
773 if (!eina_lock_take(&class->mutex))
775 #ifdef EINA_HAVE_DEBUG_THREADS
776 assert(pthread_equal(class->self, pthread_self()));
780 item = _eina_object_find_item(class, object);
781 if (!item) goto on_error;
783 _eina_object_item_del(item);
786 eina_lock_release(&class->mutex);
790 eina_object_parent_set(Eina_Class *parent_class, Eina_Object *parent,
791 Eina_Class *object_class, Eina_Object *object)
793 Eina_Object_Item *parent_item;
794 Eina_Object_Item *object_item;
796 if (!parent) return EINA_FALSE;
797 if (!object) return EINA_FALSE;
798 EINA_MAGIC_CHECK_CLASS(parent_class, EINA_FALSE);
799 EINA_MAGIC_CHECK_CLASS(object_class, EINA_FALSE);
801 if (!eina_lock_take(&parent_class->mutex))
803 #ifdef EINA_HAVE_DEBUG_THREADS
804 assert(pthread_equal(parent_class->self, pthread_self()));
808 if (!eina_lock_take(&object_class->mutex))
810 #ifdef EINA_HAVE_DEBUG_THREADS
811 assert(pthread_equal(object_class->self, pthread_self()));
815 parent_item = _eina_object_find_item(parent_class, parent);
816 if (!parent_item) return EINA_FALSE;
818 object_item = _eina_object_find_item(object_class, object);
819 if (!object_item) return EINA_FALSE;
821 if (object_item->parent)
822 object_item->parent->link = eina_inlist_remove(object_item->parent->link,
823 EINA_INLIST_GET(object_item));
825 object_item->parent = parent_item;
826 parent_item->link = eina_inlist_append(parent_item->link,
827 EINA_INLIST_GET(object_item));
829 eina_lock_release(&parent_class->mutex);
830 eina_lock_release(&object_class->mutex);
836 eina_object_parent_get(Eina_Class *class, Eina_Object *object)
838 Eina_Object_Item *object_item;
839 Eina_Object *or = NULL;
841 if (!object) return EINA_FALSE;
842 EINA_MAGIC_CHECK_CLASS(class, EINA_FALSE);
844 if (!eina_lock_take(&class->mutex))
846 #ifdef EINA_HAVE_DEBUG_THREADS
847 assert(pthread_equal(class->self, pthread_self()));
851 object_item = _eina_object_find_item(class, object);
853 or = _eina_object_get(object_item->parent);
855 eina_lock_release(&class->mutex);