libix2: support nested area searches

See 6ea78c53 in libix3 for more info, this replicates the change to
keep them in something resembling API parity.

3 files changed, 39 insertions, 23 deletions

diff --git a/src/ix2.c b/src/ix2.c
index a7aea16..e87cf2c 100644
--- a/src/ix2.c
+++ b/src/ix2.c
@@ -40,16 +40,12 @@ typedef struct ix2_node_t ix2_node_t;
 
 typedef struct ix2_object_t {
 	list_head_t	references;	/* list of all ix2_node references to this object */
-	list_head_t	hits;		/* node on hit list for non-point searches, to prevent potential double hits like when an object and search both span nodes */
-					/* XXX: note this makes non-point searches non-reentrant! i.e. you can't perform another non-point search on the same ix2
-					 * from a search callback operating on the same ix2.  TODO investigate efficient solutions.  An obvious one is to simply put
-					 * multiple of these nodes in every object and support a small number of simultaneous non-point searches, which may suffice.
-					 */
 	v2f_t		position;	/* position of this object's AABB in space (may leave as 0 if .aabb is absolute) */
 	v2f_t		origin;		/* origin of position within object's AABB, 0,0 = center, -1,-1 = min 1,1 = max */
 	bb2f_t		aabb;		/* AABB of this object */
 	float		aabb_len_sq;	/* length(aabb.max - aabb.min)^2 TODO: this isn't utilized yet, optimization potential */
 	void		*object;	/* user handle linking this object to the index */
+	list_head_t	hits[];		/* hit list nodes for area (non-point) searches, sized by ix2->max_asip */
 } ix2_object_t;
 
 typedef struct ix2_object_ref_t {
@@ -73,6 +69,8 @@ typedef struct ix2_t {
 	bb2f_t		aabb;		/* spatial bounds of ix2 root */
 	unsigned	max_per_node;	/* maximum number of objects to put in a node until max_depth reached */
 	unsigned	max_depth;	/* maximum depth of ix2 tree where nodes cease being divided further */
+	unsigned	max_asip;	/* maximum area-searches-in-progress to allow */
+	unsigned	asip;		/* area-search-in-progress count to index ix2_oject_t.hits and enforce max_asip */
 	ix2_node_t	root;		/* root node of ix2 quadtree */
 } ix2_t;
 
@@ -405,11 +403,20 @@ _fail:
 }
 
 
+/* helper for computing the ix2_object_t size for the supplied ix2 */
+static inline size_t sizeof_object(const ix2_t *ix2)
+{
+	return sizeof(ix2_object_t) + ix2->max_asip * sizeof(list_head_t);
+}
+
+
 /* Create a new ix2 index with bounds aabb, splitting nodes > max_per_node until max_depth
  * If the supplied aabb is NULL, a default one of -1,-1...1,1 is used.
+ * max_asip specifies the maximum number of area (non-point) searches to support on the ix2,
+ * a value of 0 disables *any* area searches, 2 is generally sufficient.
  * Returns NULL on failure.
  */
-ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth)
+ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip)
 {
 	bb2f_t	default_aabb = {{-1.f, -1.f}, {1.f, 1.f}};
 	ix2_t	*ix2;
@@ -426,6 +433,7 @@ ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth)
 	ix2->aabb = *aabb;
 	ix2->max_per_node = max_per_node;
 	ix2->max_depth = max_depth;
+	ix2->max_asip = max_asip;
 
 	ix2->node_pad = pad_new(sizeof(ix2_node_t) * 8, PAD_FLAGS_ZERO);
 	if (!ix2->node_pad)
@@ -435,7 +443,7 @@ ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth)
 	if (!ix2->ref_pad)
 		goto fail_ref_pad;
 
-	ix2->object_pad = pad_new(sizeof(ix2_object_t) * 32, PAD_FLAGS_ZERO);
+	ix2->object_pad = pad_new(sizeof_object(ix2) * 32, PAD_FLAGS_ZERO);
 	if (!ix2->object_pad)
 		goto fail_object_pad;
 
@@ -493,12 +501,13 @@ ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *object_position, v2f_t *object_
 	assert(object_aabb->min.x <= object_aabb->max.x);
 	assert(object_aabb->min.y <= object_aabb->max.y);
 
-	o = pad_get(ix2->object_pad, sizeof(ix2_object_t));
+	o = pad_get(ix2->object_pad, sizeof_object(ix2));
 	if (!o)
 		return NULL;
 
 	INIT_LIST_HEAD(&o->references);
-	INIT_LIST_HEAD(&o->hits);
+	for (int i = 0; i < ix2->max_asip; i++)
+		INIT_LIST_HEAD(&o->hits[i]);
 
 	if (object_position)
 		o->position = *object_position;
@@ -644,7 +653,7 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb *cb, void *
 /* recursively search the specified node for objects overlapping with search_aabb,
  * add hits to the list @ hits.
  */
-static void search_node_by_aabb(ix2_node_t *node, bb2f_t *node_aabb, v2f_t *search_position, v2f_t *search_origin, bb2f_t *search_aabb, list_head_t *hits)
+static void search_node_by_aabb(const ix2_t *ix2, ix2_node_t *node, bb2f_t *node_aabb, v2f_t *search_position, v2f_t *search_origin, bb2f_t *search_aabb, list_head_t *hits)
 {
 	ix2_object_ref_t	*ref, *_ref;
 
@@ -660,7 +669,7 @@ static void search_node_by_aabb(ix2_node_t *node, bb2f_t *node_aabb, v2f_t *sear
 		init_quadrants(quadrants, node_aabb, &node->center);
 		for (i = 0; i < 4; i++) {
 			if (aabb_overlap(NULL, NULL, &quadrants[i], search_position, search_origin, search_aabb))
-				search_node_by_aabb(&node->children[i], &quadrants[i], search_position, search_origin, search_aabb, hits);
+				search_node_by_aabb(ix2, &node->children[i], &quadrants[i], search_position, search_origin, search_aabb, hits);
 		}
 
 		return;
@@ -670,7 +679,7 @@ static void search_node_by_aabb(ix2_node_t *node, bb2f_t *node_aabb, v2f_t *sear
 		if (!aabb_overlap(&ref->object->position, &ref->object->origin, &ref->object->aabb, search_position, search_origin, search_aabb))
 			continue;
 
-		list_move_tail(&ref->object->hits, hits);
+		list_move_tail(&ref->object->hits[ix2->asip - 1], hits);
 	}
 }
 
@@ -685,9 +694,12 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or
 
 	assert(ix2);
 	assert(search_aabb);
+	assert(ix2->asip < ix2->max_asip);
+
+	ix2->asip++;
 
 	if (!aabb_overlap(NULL, NULL, &ix2->aabb, search_position, search_origin, search_aabb))
-		return 0;
+		goto finish;
 
 	/* XXX: for the aabb-based search a list of hits is first constructed,
 	 * this prevents multiple callbacks on the same object by first
@@ -698,6 +710,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or
 	 * There are two unfortunate consquences to this approach:
 	 * 1. No nested/reentrant aabb searches on the same ix2, as the hit list
 	 *    node is embedded in the ix2_object_t.
+	 *    XXX: ^^^ this is no longer the case since adding ix2->(max_)asip
 	 * 2. No way to terminate the search from the callback.
 	 *    This may be mitigated by adding a limit count to the search
 	 *    function, but that can't address scenarios where you want to
@@ -712,10 +725,10 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or
 	 *   it if not before calling the callback.  This strikes me as very
 	 *   heavyweight.
 	 */
-	search_node_by_aabb(&ix2->root, &ix2->aabb, search_position, search_origin, search_aabb, &hits);
+	search_node_by_aabb(ix2, &ix2->root, &ix2->aabb, search_position, search_origin, search_aabb, &hits);
 
-	list_for_each_entry_safe(o, _o, &hits, hits) {
-		list_del_init(&o->hits);
+	list_for_each_entry_safe(o, _o, &hits, hits[ix2->asip - 1]) {
+		list_del_init(&o->hits[ix2->asip - 1]);
 
 		if (cb) {
 			ix2_search_status_t	r;
@@ -726,11 +739,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or
 				n_hits++;
 
 			case IX2_SEARCH_STOP_MISS:
-				/* XXX: this is necessary, the hits nodes must be kept movable */
-				list_for_each_entry_safe(o, _o, &hits, hits)
-					list_del_init(&o->hits);
-
-				return n_hits;
+				goto finish;
 
 			case IX2_SEARCH_MORE_HIT:
 				n_hits++;
@@ -746,5 +755,12 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or
 		n_hits++;
 	}
 
+finish:
+	/* XXX: this is necessary, the hits nodes must be kept movable */
+	list_for_each_entry_safe(o, _o, &hits, hits[ix2->asip - 1])
+		list_del_init(&o->hits[ix2->asip - 1]);
+
+	ix2->asip--;
+
 	return n_hits;
 }
diff --git a/src/ix2.h b/src/ix2.h
index 2785f36..d41216e 100644
--- a/src/ix2.h
+++ b/src/ix2.h
@@ -31,7 +31,7 @@ typedef enum ix2_search_status_t {
 
 typedef ix2_search_status_t (ix2_search_cb)(void *cb_context, ix2_object_t *ix2_object, v2f_t *ix2_object_position, bb2f_t *ix2_object_aabb, void *object);
 
-ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth);
+ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip);
 void ix2_reset(ix2_t *ix2);
 void ix2_free(ix2_t *ix2);
 ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *position, v2f_t *origin, bb2f_t *aabb, void *object);
diff --git a/src/test.c b/src/test.c
index 1d14a98..89bd671 100644
--- a/src/test.c
+++ b/src/test.c
@@ -57,7 +57,7 @@ int main(int argc, char *argv[])
 	ix2_object_t	*o, *j;
 	ix2_t		*ix2;
 
-	ix2 = ix2_new(&aabb, 2, 8);
+	ix2 = ix2_new(&aabb, 2, 8, 1);
 	if (!ix2) {
 		fprintf(stderr, "unable to create index\n");
 		return 1;