summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-04-28 00:43:23 +0200
committerJérémy Zurcher <jeremy@asynk.ch>2013-04-28 00:43:53 +0200
commit994318eebe032447f9457a77fe446b5978480cd7 (patch)
tree6472eec0133ff0e4beb37d9e12d638ee0cd0b6fa
parent41dc1764f342691916b7015fb40036b883d7bcc5 (diff)
eo_ptr_ind: pack ptr, active flag and generation all together
use of an array of the below struct instead of 3 separate arrays leads to better cache performance and smaller memory usage typedef struct { _Eo *ptr; unsigned int active : 1; unsigned int generation : BITS_FOR_GENERATION_COUNTER; } _Eo_Id_Entry;
-rw-r--r--src/lib/eo/eo_ptr_indirection.c111
1 files changed, 56 insertions, 55 deletions
diff --git a/src/lib/eo/eo_ptr_indirection.c b/src/lib/eo/eo_ptr_indirection.c
index ce2fc6e..32e3781 100644
--- a/src/lib/eo/eo_ptr_indirection.c
+++ b/src/lib/eo/eo_ptr_indirection.c
@@ -32,9 +32,10 @@
32 * occur when accessing with the old id. 32 * occur when accessing with the old id.
33 * 33 *
34 * Each table is composed of: 34 * Each table is composed of:
35 * - pointers to the objects 35 * - entries composed of
36 * - generations assigned to the objects 36 * - a pointer to the object
37 * - a boolean table indicating if an entry is active 37 * - a flag indicating if the entry is active
38 * - a generation assigned to the object
38 * - an index 'start' indicating which entry is the next one to use. 39 * - an index 'start' indicating which entry is the next one to use.
39 * - a queue that will help us to store the unused entries. It stores only the 40 * - a queue that will help us to store the unused entries. It stores only the
40 * entries that have been used at least one time. The entries that have 41 * entries that have been used at least one time. The entries that have
@@ -112,7 +113,7 @@ _eo_id_mem_alloc(size_t size)
112 return (void *)(((unsigned char *)ptr) + MEM_HEADER_SIZE); 113 return (void *)(((unsigned char *)ptr) + MEM_HEADER_SIZE);
113#else 114#else
114 return malloc(size); 115 return malloc(size);
115#endif 116#endif
116} 117}
117 118
118static void * 119static void *
@@ -142,15 +143,22 @@ _eo_id_mem_free(void *ptr)
142#endif 143#endif
143} 144}
144 145
146/* Entry */
147typedef struct
148{
149 /* Pointer to the object */
150 _Eo *ptr;
151 /* Active flag */
152 unsigned int active : 1;
153 /* Generation */
154 unsigned int generation : BITS_FOR_GENERATION_COUNTER;
155} _Eo_Id_Entry;
156
145/* Table */ 157/* Table */
146typedef struct 158typedef struct
147{ 159{
148 /* Pointers of objects stored in table */ 160 /* Entries of the table holding real pointers and generations */
149 _Eo *ptrs[MAX_IDS_PER_TABLE]; 161 _Eo_Id_Entry entries[MAX_IDS_PER_TABLE];
150 /* Generations */
151 Table_Index generation[MAX_IDS_PER_TABLE];
152 /* Active flags */
153 char active[MAX_IDS_PER_TABLE >> 3];
154 /* Queue to handle free entries */ 162 /* Queue to handle free entries */
155 Eina_Trash *queue; 163 Eina_Trash *queue;
156 /* Indicates where start the "never used" entries */ 164 /* Indicates where start the "never used" entries */
@@ -163,20 +171,6 @@ _Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL };
163/* Next generation to use when assigning a new entry to a Eo pointer */ 171/* Next generation to use when assigning a new entry to a Eo pointer */
164Table_Index _eo_generation_counter; 172Table_Index _eo_generation_counter;
165 173
166/* Internal macro for active flag manipulation */
167#define _ENTRY_ACTIVE_DO_OP(table, id_in_table, op) \
168 (table)->active[(id_in_table) >> 3] op (1 << ((id_in_table) % 8))
169
170/* Macro that indicates if an entry is active */
171#define IS_ENTRY_ACTIVE(table, id_in_table) \
172 (_ENTRY_ACTIVE_DO_OP(table, id_in_table, &))
173/* Macro that activates an entry */
174#define ACTIVATE_ENTRY(table, id_in_table) \
175 _ENTRY_ACTIVE_DO_OP(table, id_in_table, |=)
176/* Macro that de-activates an entry */
177#define DEACTIVATE_ENTRY(table, id_in_table) \
178 _ENTRY_ACTIVE_DO_OP(table, id_in_table, &=~)
179
180/* Macro used to compose an Eo id */ 174/* Macro used to compose an Eo id */
181#define EO_COMPOSE_ID(TABLE, INTER_TABLE, ENTRY, GENERATION) \ 175#define EO_COMPOSE_ID(TABLE, INTER_TABLE, ENTRY, GENERATION) \
182 (Eo_Id)(((TABLE & (MAX_IDS_TABLES - 1)) << SHIFT_FOR_IDS_TABLE) | \ 176 (Eo_Id)(((TABLE & (MAX_IDS_TABLES - 1)) << SHIFT_FOR_IDS_TABLE) | \
@@ -198,14 +192,18 @@ _Eo *
198_eo_obj_pointer_get(const Eo_Id obj_id) 192_eo_obj_pointer_get(const Eo_Id obj_id)
199{ 193{
200#ifdef HAVE_EO_ID 194#ifdef HAVE_EO_ID
195 _Eo_Id_Entry *entry;
201 Table_Index table_id, int_table_id, entry_id, generation; 196 Table_Index table_id, int_table_id, entry_id, generation;
202 197
203 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); 198 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation);
204 199
205 /* Checking the validity of the entry */ 200 /* Checking the validity of the entry */
206 if (_eo_ids_tables[table_id] && ID_TABLE && IS_ENTRY_ACTIVE(ID_TABLE, entry_id) && 201 if (_eo_ids_tables[table_id] && ID_TABLE)
207 ID_TABLE->generation[entry_id] == generation) 202 {
208 return ID_TABLE->ptrs[entry_id]; 203 entry = &(ID_TABLE->entries[entry_id]);
204 if (entry && entry->active && (entry->generation == generation))
205 return entry->ptr;
206 }
209 207
210 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", 208 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.",
211 (void *)obj_id); 209 (void *)obj_id);
@@ -220,7 +218,7 @@ Eo_Id
220_eo_id_allocate(const _Eo *obj) 218_eo_id_allocate(const _Eo *obj)
221{ 219{
222#ifdef HAVE_EO_ID 220#ifdef HAVE_EO_ID
223 Eo_Id ret = 0; 221 _Eo_Id_Entry *entry = NULL;
224 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++) 222 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++)
225 { 223 {
226 if (!_eo_ids_tables[table_id]) 224 if (!_eo_ids_tables[table_id])
@@ -230,44 +228,43 @@ _eo_id_allocate(const _Eo *obj)
230 } 228 }
231 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++) 229 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++)
232 { 230 {
233 _Eo **ptr;
234 if (!ID_TABLE) 231 if (!ID_TABLE)
235 { 232 {
236 /* We allocate a new intermediate table */ 233 /* We allocate a new intermediate table */
237 ID_TABLE = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table)); 234 ID_TABLE = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table));
238 eina_trash_init(&(ID_TABLE->queue)); 235 eina_trash_init(&(ID_TABLE->queue));
239 /* We select directly the first entry of the new table */ 236 /* We select directly the first entry of the new table */
240 ptr = &(ID_TABLE->ptrs[0]); 237 entry = &(ID_TABLE->entries[0]);
241 ID_TABLE->start = 1; 238 ID_TABLE->start = 1;
242 } 239 }
243 else 240 else
244 { 241 {
245 /* We try to pop from the queue an unused entry */ 242 /* We try to pop from the queue an unused entry */
246 ptr = (_Eo **)eina_trash_pop(&(ID_TABLE->queue)); 243 entry = (_Eo_Id_Entry *)eina_trash_pop(&(ID_TABLE->queue));
247 } 244 }
248 245
249 if (!ptr && ID_TABLE->start < MAX_IDS_PER_TABLE) 246 if (!entry && ID_TABLE->start < MAX_IDS_PER_TABLE)
250 { 247 {
251 /* No more unused entries in the trash but still empty entries in the table */ 248 /* No more unused entries in the trash but still empty entries in the table */
252 ptr = &(ID_TABLE->ptrs[ID_TABLE->start]); 249 entry = &(ID_TABLE->entries[ID_TABLE->start]);
253 ID_TABLE->start++; 250 ID_TABLE->start++;
254 } 251 }
255 252
256 if (ptr) 253 if (entry)
257 { 254 {
258 /* An entry was found - need to find the entry id and fill it */ 255 /* An entry was found - need to find the entry id and fill it */
259 Table_Index id = ptr - ID_TABLE->ptrs; 256 entry->ptr = (_Eo *)obj;
260 ID_TABLE->generation[id] = _eo_generation_counter; 257 entry->active = 1;
261 ACTIVATE_ENTRY(ID_TABLE, id); 258 entry->generation = _eo_generation_counter;
262 *ptr = (_Eo *)obj;
263 ret = EO_COMPOSE_ID(table_id, int_table_id, id, _eo_generation_counter);
264 _eo_generation_counter++; 259 _eo_generation_counter++;
265 _eo_generation_counter %= MAX_GENERATIONS; 260 _eo_generation_counter %= MAX_GENERATIONS;
266 return ret; 261 return EO_COMPOSE_ID(table_id, int_table_id,
262 (entry - ID_TABLE->entries),
263 entry->generation);
267 } 264 }
268 } 265 }
269 } 266 }
270 return ret; 267 return 0;
271#else 268#else
272 return (Eo_Id)obj; 269 return (Eo_Id)obj;
273#endif 270#endif
@@ -277,22 +274,24 @@ void
277_eo_id_release(const Eo_Id obj_id) 274_eo_id_release(const Eo_Id obj_id)
278{ 275{
279#ifdef HAVE_EO_ID 276#ifdef HAVE_EO_ID
277 _Eo_Id_Entry *entry;
280 Table_Index table_id, int_table_id, entry_id, generation; 278 Table_Index table_id, int_table_id, entry_id, generation;
281 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); 279 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation);
282 280
283 /* Checking the validity of the entry */ 281 /* Checking the validity of the entry */
284 if (!_eo_ids_tables[table_id]) goto error; 282 if (_eo_ids_tables[table_id] && ID_TABLE)
285 if (!ID_TABLE) goto error; 283 {
286 if (ID_TABLE->generation[entry_id] != generation) goto error; 284 entry = &(ID_TABLE->entries[entry_id]);
287 285 if (entry && entry->active && (entry->generation == generation))
288 /* Disable the entry */ 286 {
289 DEACTIVATE_ENTRY(ID_TABLE, entry_id); 287 /* Disable the entry */
290 /* Push the entry into the queue */ 288 entry->active = 0;
291 eina_trash_push(&(ID_TABLE->queue), &(ID_TABLE->ptrs[entry_id])); 289 /* Push the entry into the queue */
292 290 eina_trash_push(&(ID_TABLE->queue), entry);
293 return; 291 return;
292 }
293 }
294 294
295error:
296 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id); 295 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id);
297#else 296#else
298 (void) obj_id; 297 (void) obj_id;
@@ -323,6 +322,7 @@ _eo_free_ids_tables()
323void 322void
324_eo_print() 323_eo_print()
325{ 324{
325 _Eo_Id_Entry *entry;
326 unsigned long obj_number = 0; 326 unsigned long obj_number = 0;
327 for (Table_Index table_id = 0; table_id < MAX_IDS_TABLES; table_id++) 327 for (Table_Index table_id = 0; table_id < MAX_IDS_TABLES; table_id++)
328 { 328 {
@@ -334,12 +334,13 @@ _eo_print()
334 { 334 {
335 for (Table_Index entry_id = 0; entry_id < MAX_IDS_PER_TABLE; entry_id++) 335 for (Table_Index entry_id = 0; entry_id < MAX_IDS_PER_TABLE; entry_id++)
336 { 336 {
337 if (IS_ENTRY_ACTIVE(ID_TABLE, entry_id)) 337 entry = &(ID_TABLE->entries[entry_id]);
338 if (entry->active)
338 { 339 {
339 printf("%ld: %p -> (%p, %p, %p, %p)\n", obj_number++, 340 printf("%ld: %p -> (%p, %p, %p, %p)\n", obj_number++,
340 ID_TABLE->ptrs[entry_id], 341 entry->ptr,
341 (void *)table_id, (void *)int_table_id, (void *)entry_id, 342 (void *)table_id, (void *)int_table_id, (void *)entry_id,
342 (void *)ID_TABLE->generation[entry_id]); 343 (void *)entry->generation);
343 } 344 }
344 } 345 }
345 } 346 }