commit 179bdf6ea54b4ef264d7c153d86e756f7759100b
parent 28bf62d7315fae68cad10591e627cf03643d0432
Author: Christophe Coustet <christophe.coustet@meso-star.com>
Date: Tue, 11 Sep 2018 15:55:00 +0200
Replace htables by bool arrays when collecting media
Diffstat:
3 files changed, 86 insertions(+), 67 deletions(-)
diff --git a/src/senc2d_enclosure_data.h b/src/senc2d_enclosure_data.h
@@ -21,6 +21,17 @@
#include <rsys/hash_table.h>
#include <rsys/dynamic_array.h>
+/* unsigned char array with init to zero */
+static FINLINE void
+zero_init_uchar
+ (struct mem_allocator* alloc, unsigned char* data)
+{
+ ASSERT(data); (void)alloc;
+ *data = 0;
+}
+#define DARRAY_FUNCTOR_INIT zero_init_uchar
+#include <rsys/dynamic_array_uchar.h>
+
#include "senc2d.h"
#include "senc2d_scene_c.h"
#include "senc2d_internal_types.h"
@@ -39,28 +50,29 @@ init_header(struct senc2d_enclosure_header* header)
header->is_infinite = CHAR_MAX;
}
-#define HTABLE_NAME media
-#define HTABLE_KEY medium_id_t
-#define HTABLE_DATA char
-#include <rsys/hash_table.h>
+#define DARRAY_NAME media
+#define DARRAY_DATA medium_id_t
+#include <rsys/dynamic_array.h>
static FINLINE res_T
-htable_media_merge
-(struct htable_media* dst,
- struct htable_media* src)
+bool_array_of_media_merge
+ (struct darray_uchar* dst,
+ const unsigned char* src,
+ const medium_id_t sz)
{
res_T res = RES_OK;
- struct htable_media_iterator it, end;
- char one = 1;
+ medium_id_t i;
+ unsigned char* data_dst;
+
ASSERT(src && dst);
- htable_media_begin(src, &it);
- htable_media_end(src, &end);
- while(!htable_media_iterator_eq(&it, &end)) {
- medium_id_t* k = htable_media_iterator_key_get(&it);
- res = htable_media_set(dst, k, &one);
- if(res != RES_OK) goto error;
- htable_media_iterator_next(&it);
+ OK(darray_uchar_resize(dst, sz));
+ data_dst = darray_uchar_data_get(dst);
+ ASSERT(sz <= MEDIUM_MAX__);
+ if(res != RES_OK) goto error;
+ FOR_EACH(i, 0, sz) {
+ if(!src[i]) continue;
+ data_dst[i] = 1;
}
end:
return res;
@@ -68,29 +80,27 @@ error:
goto end;
}
-#define DARRAY_NAME media
-#define DARRAY_DATA medium_id_t
-#include <rsys/dynamic_array.h>
-
static FINLINE res_T
-htable_media_to_darray_media
+bool_array_of_media_to_darray_media
(struct darray_media* dst,
- struct htable_media* src)
+ struct darray_uchar* src)
{
res_T res = RES_OK;
- struct htable_media_iterator it, end;
+ medium_id_t i;
+ size_t sz;
+ const unsigned char* data;
+
ASSERT(src && dst);
+ data = darray_uchar_cdata_get(src);
+ sz = darray_uchar_size_get(src);
+ ASSERT(sz <= MEDIUM_MAX__);
darray_media_clear(dst);
- res = darray_media_reserve(dst, htable_media_size_get(src));
if(res != RES_OK) goto error;
- htable_media_begin(src, &it);
- htable_media_end(src, &end);
- while(!htable_media_iterator_eq(&it, &end)) {
- medium_id_t* k = htable_media_iterator_key_get(&it);
- res = darray_media_push_back(dst, k);
+ FOR_EACH(i, 0, (medium_id_t)sz) {
+ if(!data[i]) continue;
+ res = darray_media_push_back(dst, &i);
if(res != RES_OK) goto error;
- htable_media_iterator_next(&it);
}
end:
return res;
@@ -105,7 +115,7 @@ struct enclosure_data {
/* Index of vertices in scene's unique vertices */
struct darray_vrtx_id vertices;
/* List of the enclosed media */
- struct htable_media tmp_enclosed_media;
+ struct darray_uchar tmp_enclosed_media;
struct darray_media enclosed_media;
/* Number of components involved in this enclosure */
component_id_t cc_count;
@@ -128,7 +138,7 @@ enclosure_data_init(struct mem_allocator* alloc, struct enclosure_data* enc) {
enc->side_count = 0;
darray_segment_in_init(alloc, &enc->sides);
darray_vrtx_id_init(alloc, &enc->vertices);
- htable_media_init(alloc, &enc->tmp_enclosed_media);
+ darray_uchar_init(alloc, &enc->tmp_enclosed_media);
darray_media_init(alloc, &enc->enclosed_media);
}
@@ -146,7 +156,7 @@ enclosure_data_copy
dst->side_count = src->side_count;
OK(darray_segment_in_copy(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy(&dst->vertices, &src->vertices));
- OK(htable_media_copy(&dst->tmp_enclosed_media, &src->tmp_enclosed_media));
+ OK(darray_uchar_copy(&dst->tmp_enclosed_media, &src->tmp_enclosed_media));
OK(darray_media_copy(&dst->enclosed_media, &src->enclosed_media));
error:
return res;
@@ -157,7 +167,7 @@ enclosure_data_release(struct enclosure_data* n) {
ASSERT(n);
darray_segment_in_release(&n->sides);
darray_vrtx_id_release(&n->vertices);
- htable_media_release(&n->tmp_enclosed_media);
+ darray_uchar_release(&n->tmp_enclosed_media);
darray_media_release(&n->enclosed_media);
}
@@ -175,7 +185,7 @@ enclosure_data_copy_and_release
dst->side_count = src->side_count;
OK(darray_segment_in_copy_and_release(&dst->sides, &src->sides));
OK(darray_vrtx_id_copy_and_release(&dst->vertices, &src->vertices));
- OK(htable_media_copy_and_release(&dst->tmp_enclosed_media,
+ OK(darray_uchar_copy_and_release(&dst->tmp_enclosed_media,
&src->tmp_enclosed_media));
OK(darray_media_copy_and_release(&dst->enclosed_media, &src->enclosed_media));
error:
diff --git a/src/senc2d_scene_analyze.c b/src/senc2d_scene_analyze.c
@@ -36,7 +36,8 @@
#define CC_DESCRIPTOR_NULL__ {\
CHAR_MAX, VRTX_NULL__, 0,\
CC_ID_NONE, CC_GROUP_ROOT_NONE, ENCLOSURE_NULL__,\
- { SEG_NULL__, 0}\
+ { SEG_NULL__, 0},\
+ NULL\
}
#ifdef COMPILER_GCC
#pragma GCC diagnostic push
@@ -150,7 +151,6 @@ extract_connex_components
int64_t mm;
struct darray_side_id stack;
struct darray_side_id ids_of_sides_around_max_y_vertex;
- struct htable_media tmp_media;
const union double2* positions;
const struct segment_tmp* segments_tmp;
struct segment_comp* segments_comp;
@@ -158,6 +158,8 @@ extract_connex_components
unsigned char* processed;
/* An array to store the component being processed */
struct darray_side_id current_component;
+ /* A bool array to store media of the component being processed */
+ unsigned char* current_media = NULL;
size_t ii, sz;
ASSERT(segsides && desc && connex_components && segments_tmp_array
@@ -170,8 +172,7 @@ extract_connex_components
darray_side_id_init(alloc, &stack);
darray_side_id_init(alloc, &ids_of_sides_around_max_y_vertex);
darray_side_id_init(alloc, ¤t_component);
- htable_media_init(alloc, &tmp_media);
- processed = calloc(scn->nusegs, sizeof(unsigned char));
+ processed = MEM_CALLOC(alloc, scn->nusegs, sizeof(unsigned char));
if(!processed) {
*p_res = RES_MEM_ERR;
return;
@@ -207,7 +208,6 @@ extract_connex_components
side_id_t first_side_not_in_component = media_use->first;
double max_y_ny;
const side_id_t last_side = media_use->last;
- char one = 1;
int component_canceled = 0;
res_T tmp_res = RES_OK;
ATOMIC id;
@@ -229,7 +229,6 @@ extract_connex_components
ASSERT(start_side_id == SIDE_NULL__ || start_side_id < 2 * scn->nusegs);
darray_side_id_clear(¤t_component);
- htable_media_clear(&tmp_media);
if(*p_res != RES_OK) break;
if(start_side_id == SIDE_NULL__)
@@ -245,7 +244,17 @@ extract_connex_components
}
#endif
- OK2(htable_media_set(&tmp_media, &m, &one));
+ /* Reuse array if possible, or create a new one */
+ if(current_media) {
+ memset(current_media, 0, scn->nmeds);
+ } else {
+ current_media = MEM_CALLOC(alloc, scn->nmeds, sizeof(unsigned char));
+ if(!current_media) {
+ *p_res = RES_MEM_ERR;
+ continue;
+ }
+ }
+ current_media[m] = 1;
for(;;) { /* Process all sides of this component */
int i;
enum side_flag crt_side_flag = SEGSIDE_2_SIDEFLAG(crt_side_id);
@@ -317,8 +326,7 @@ extract_connex_components
*nbour_used |= (unsigned char)nbour_side_id;
OK2(darray_side_id_push_back(&stack, &neighbour_id));
OK2(darray_side_id_push_back(¤t_component, &neighbour_id));
- if(neighbour->medium != m) /* Can be a new medium */
- htable_media_set(&tmp_media, &neighbour->medium, &one);
+ current_media[neighbour->medium] = 1;
}
sz = darray_side_id_size_get(&stack);
if(sz == 0) break; /* Empty stack => component is done! */
@@ -346,8 +354,10 @@ canceled:
cc->side_range.first = start_side_id;
cc->side_range.last = last_side_id;
cc->max_y_vrtx_id = max_y_vrtx_id;
- /* First medium of the component */
- htable_media_copy_and_clear(&cc->media, &tmp_media);
+ /* Tranfer ownership of the array to component */
+ ASSERT(!cc->media && current_media);
+ cc->media = current_media;
+ current_media = NULL;
/* Write component membership in the global structure
* No need for sync here as an unique thread write a given side */
@@ -419,11 +429,11 @@ canceled:
if(tmp_res != RES_OK) *p_res = tmp_res;
} /* No barrier here */
- free(processed);
+ MEM_RM(alloc, processed);
+ MEM_RM(alloc, current_media);
darray_side_id_release(¤t_component);
darray_side_id_release(&stack);
darray_side_id_release(&ids_of_sides_around_max_y_vertex);
- htable_media_release(&tmp_media);
/* The first thread here creates the s2d view */
#pragma omp single nowait
@@ -585,12 +595,13 @@ group_connex_components
if(tmp_res != RES_OK) {
*res = tmp_res;
} else {
+ struct enclosure_data* enclosures
+ = darray_enclosure_data_get(&desc->enclosures);
FOR_EACH(ccc, 0, cc_count) {
component_id_t c = (component_id_t)ccc;
struct cc_descriptor* const cc = descriptors[c];
const struct cc_descriptor* other_desc = cc;
- struct enclosure_data* enclosures
- = darray_enclosure_data_get(&desc->enclosures);
+ struct enclosure_data* enc;
while(other_desc->enclosure_id == CC_GROUP_ID_NONE) {
other_desc = *(darray_ptr_component_descriptor_cdata_get(connex_components)
@@ -600,16 +611,15 @@ group_connex_components
ASSERT(other_desc->enclosure_id != CC_GROUP_ID_NONE);
cc->cc_group_root = other_desc->cc_group_root;
cc->enclosure_id = other_desc->enclosure_id;
- ++enclosures[cc->enclosure_id].cc_count;
+ enc = enclosures + cc->enclosure_id;
+ ++enc->cc_count;
/* Linked list of componnents */
- enclosures[cc->enclosure_id].first_component = cc->cc_id;
- enclosures[cc->enclosure_id].side_range.first
- = MMIN(enclosures[cc->enclosure_id].side_range.first, cc->side_range.first);
- enclosures[cc->enclosure_id].side_range.last
- = MMAX(enclosures[cc->enclosure_id].side_range.last, cc->side_range.last);
- enclosures[cc->enclosure_id].side_count += cc->side_count;
- tmp_res = htable_media_merge(
- &enclosures[cc->enclosure_id].tmp_enclosed_media, &cc->media);
+ enc->first_component = cc->cc_id;
+ enc->side_range.first = MMIN(enc->side_range.first, cc->side_range.first);
+ enc->side_range.last = MMAX(enc->side_range.last, cc->side_range.last);
+ enc->side_count += cc->side_count;
+ tmp_res = bool_array_of_media_merge(&enc->tmp_enclosed_media, cc->media,
+ desc->scene->nmeds);
if(tmp_res != RES_OK) {
*res = tmp_res;
break;
@@ -859,13 +869,13 @@ build_result
== enc->header.enclosure_id);
enc->header.is_infinite = (e == 0);
- ASSERT(htable_media_size_get(&enc->tmp_enclosed_media) <= UINT_MAX);
- enc->header.enclosed_media_count
- = (unsigned)htable_media_size_get(&enc->tmp_enclosed_media);
+ ASSERT(darray_uchar_size_get(&enc->tmp_enclosed_media) <= UINT_MAX);
ASSERT(enc->header.enclosed_media_count <= desc->scene->nmeds);
- OK2(htable_media_to_darray_media
+ OK2(bool_array_of_media_to_darray_media
(&enc->enclosed_media, &enc->tmp_enclosed_media));
- htable_media_purge(&enc->tmp_enclosed_media);
+ enc->header.enclosed_media_count
+ = (unsigned)darray_media_size_get(&enc->enclosed_media);
+ darray_uchar_purge(&enc->tmp_enclosed_media);
/* Add this enclosure in relevant by-medium lists */
FOR_EACH(m, 0, enc->header.enclosed_media_count) {
diff --git a/src/senc2d_scene_analyze_c.h b/src/senc2d_scene_analyze_c.h
@@ -58,7 +58,7 @@ struct cc_descriptor {
/* Range of sides member of this component */
struct side_range side_range;
/* Media used by this component */
- struct htable_media media;
+ unsigned char* media;
};
extern const struct cc_descriptor CC_DESCRIPTOR_NULL;
@@ -70,7 +70,6 @@ cc_descriptor_init
ASSERT(data);
(void)alloc;
*data = CC_DESCRIPTOR_NULL;
- htable_media_init(alloc, &data->media);
}
static FINLINE void
@@ -101,7 +100,7 @@ custom_darray_ptr_component_descriptor_release
components = darray_ptr_component_descriptor_data_get(array);
FOR_EACH(c, 0, cc_count) {
if(!components[c]) continue;
- htable_media_release(&components[c]->media);
+ MEM_RM(array->allocator, components[c]->media);
MEM_RM(array->allocator, components[c]);
}
darray_ptr_component_descriptor_release(array);
