[PATCH BlueZ 0/5] Add const access to linked list for efficiency

[PATCH BlueZ 0/5] Add const access to linked list for efficiency

[Michael Janssen]

In many cases, queue_foreach is being used to find a specific item not easily
locatable using queue_find or can be finished early.  This set adds
queue_get_entries which gives a method for manual iteration of the queue.

The other patches use this feature to improve efficiency of some iterations.

Michael Janssen (5):
  shared/queue: Add queue_get_entries
  shared/queue: clarify queue_match_func_t arguments
  android/health: improve search efficiency
  monitor/keys: use queue_find over queue_foreach
  shared/gatt-db: manual iteration when appopriate

 android/health.c     | 153 +++++++++++++++++++++------------------------------
 monitor/keys.c       |  37 ++++---------
 src/shared/gatt-db.c | 150 ++++++++++++++++++++------------------------------
 src/shared/queue.c   |  14 +++--
 src/shared/queue.h   |  10 +++-
 5 files changed, 151 insertions(+), 213 deletions(-)

-- 
2.2.0.rc0.207.ga3a616c

[PATCH BlueZ 1/5] shared/queue: Add queue_get_entries

[Michael Janssen]

Function which is useful for iterating through entries with complex
search parameters and terminating the searches early.
---
 src/shared/queue.c | 14 ++++++++------
 src/shared/queue.h |  8 ++++++++
 2 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/src/shared/queue.c b/src/shared/queue.c
index a5155e7..ccf2f07 100644
--- a/src/shared/queue.c
+++ b/src/shared/queue.c
@@ -28,12 +28,6 @@
 #include "src/shared/util.h"
 #include "src/shared/queue.h"
 
-struct queue_entry {
-	int ref_count;
-	void *data;
-	struct queue_entry *next;
-};
-
 struct queue {
 	int ref_count;
 	struct queue_entry *head;
@@ -401,6 +395,14 @@ unsigned int queue_remove_all(struct queue *queue, queue_match_func_t function,
 	return count;
 }
 
+const struct queue_entry *queue_get_entries(struct queue *queue)
+{
+	if (!queue)
+		return NULL;
+
+	return queue->head;
+}
+
 unsigned int queue_length(struct queue *queue)
 {
 	if (!queue)
diff --git a/src/shared/queue.h b/src/shared/queue.h
index 602b0ce..0d5a9a5 100644
--- a/src/shared/queue.h
+++ b/src/shared/queue.h
@@ -27,6 +27,12 @@ typedef void (*queue_destroy_func_t)(void *data);
 
 struct queue;
 
+struct queue_entry {
+	int ref_count;
+	void *data;
+	struct queue_entry *next;
+};
+
 struct queue *queue_new(void);
 void queue_destroy(struct queue *queue, queue_destroy_func_t destroy);
 
@@ -53,5 +59,7 @@ void *queue_remove_if(struct queue *queue, queue_match_func_t function,
 unsigned int queue_remove_all(struct queue *queue, queue_match_func_t function,
 				void *user_data, queue_destroy_func_t destroy);
 
+const struct queue_entry *queue_get_entries(struct queue *queue);
+
 unsigned int queue_length(struct queue *queue);
 bool queue_isempty(struct queue *queue);
-- 
2.2.0.rc0.207.ga3a616c

[PATCH BlueZ 2/5] shared/queue: clarify queue_match_func_t arguments

[Michael Janssen]

The queue_match_func_t just looking at the API, it's easy to assume that
both arguments come from internal, while one is provided by the user.
---
 src/shared/queue.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/shared/queue.h b/src/shared/queue.h
index 0d5a9a5..3bc8d2e 100644
--- a/src/shared/queue.h
+++ b/src/shared/queue.h
@@ -48,7 +48,7 @@ typedef void (*queue_foreach_func_t)(void *data, void *user_data);
 void queue_foreach(struct queue *queue, queue_foreach_func_t function,
 							void *user_data);
 
-typedef bool (*queue_match_func_t)(const void *a, const void *b);
+typedef bool (*queue_match_func_t)(const void *data, const void *match_data);
 
 void *queue_find(struct queue *queue, queue_match_func_t function,
 							const void *match_data);
-- 
2.2.0.rc0.207.ga3a616c

[PATCH BlueZ 3/5] android/health: improve search efficiency

[Michael Janssen]

Iterate through the entries manually to return early for efficiency.
---
 android/health.c | 153 +++++++++++++++++++++++--------------------------------
 1 file changed, 64 insertions(+), 89 deletions(-)

diff --git a/android/health.c b/android/health.c
index 75811aa..f2895a2 100644
--- a/android/health.c
+++ b/android/health.c
@@ -302,133 +302,108 @@ static bool match_app_by_id(const void *data, const void *user_data)
 	return app->id == app_id;
 }
 
-/*
- * Helper struct and utility to search channel when only channel id
- * is the option. i.e. destroy_channel call from HAL is passing only
- * channel id.
- */
-struct channel_search {
-	uint16_t channel_id;
-	struct mcap_mdl *mdl;
-	struct health_channel *channel;
-};
-
-static void device_search_channel(void *data, void *user_data)
-{
-	struct health_device *dev = data;
-	struct channel_search *search = user_data;
-
-	if (search->channel)
-		return;
-
-	if (search->channel_id)
-		search->channel = queue_find(dev->channels, match_channel_by_id,
-						INT_TO_PTR(search->channel_id));
-	else if (search->mdl)
-		search->channel = queue_find(dev->channels,
-						match_channel_by_mdl,
-						search->mdl);
-}
-
-static void app_search_channel(void *data, void *user_data)
+static struct health_channel *search_channel_by_id(uint16_t id)
 {
-	struct health_app *app = data;
-	struct channel_search *search = user_data;
+	const struct queue_entry *apps_entry, *devices_entry;
+	struct health_app *app;
+	struct health_channel *channel;
+	struct health_device *dev;
 
-	if (search->channel)
-		return;
+	DBG("");
 
-	queue_foreach(app->devices, device_search_channel, search);
-}
+	apps_entry = queue_get_entries(apps);
+	while (apps_entry) {
+		app = apps_entry->data;
+		devices_entry = queue_get_entries(app->devices);
+		while (devices_entry) {
+			dev = devices_entry->data;
+			channel = queue_find(dev->channels, match_channel_by_id,
+								INT_TO_PTR(id));
 
-static struct health_channel *search_channel_by_id(uint16_t id)
-{
-	struct channel_search search;
+			if (channel)
+				return channel;
 
-	DBG("");
+			devices_entry = devices_entry->next;
+		}
 
-	search.channel_id = id;
-	search.mdl = NULL;
-	search.channel = NULL;
-	queue_foreach(apps, app_search_channel, &search);
+		apps_entry = apps_entry->next;
+	}
 
-	return search.channel;
+	return NULL;
 }
 
 static struct health_channel *search_channel_by_mdl(struct mcap_mdl *mdl)
 {
-	struct channel_search search;
+	const struct queue_entry *apps_entry, *devices_entry;
+	struct health_app *app;
+	struct health_channel *channel;
+	struct health_device *dev;
 
 	DBG("");
 
-	search.channel_id = 0;
-	search.mdl = mdl;
-	search.channel = NULL;
-	queue_foreach(apps, app_search_channel, &search);
+	apps_entry = queue_get_entries(apps);
+	while (apps_entry) {
+		app = apps_entry->data;
+		devices_entry = queue_get_entries(app->devices);
+		while (devices_entry) {
+			dev = devices_entry->data;
+			channel = queue_find(dev->channels,
+						match_channel_by_mdl, mdl);
 
-	return search.channel;
-}
+			if (channel)
+				return channel;
 
-struct mcl_search {
-	struct mcap_mcl *mcl;
-	struct health_device *dev;
-};
-
-static void app_search_dev(void *data, void *user_data)
-{
-	struct health_app *app = data;
-	struct mcl_search *search = user_data;
+			devices_entry = devices_entry->next;
+		}
 
-	if (search->dev)
-		return;
+		apps_entry = apps_entry->next;
+	}
 
-	search->dev = queue_find(app->devices, match_dev_by_mcl, search->mcl);
+	return NULL;
 }
 
 static struct health_device *search_dev_by_mcl(struct mcap_mcl *mcl)
 {
-	struct mcl_search search;
+	const struct queue_entry *apps_entry;
+	struct health_app *app;
+	struct health_device *dev;
 
 	DBG("");
 
-	search.mcl = mcl;
-	search.dev = NULL;
+	apps_entry = queue_get_entries(apps);
+	while (apps_entry) {
+		app = apps_entry->data;
 
-	queue_foreach(apps, app_search_dev, &search);
+		dev = queue_find(app->devices, match_dev_by_mcl, mcl);
 
-	return search.dev;
-}
-
-struct app_search {
-	uint8_t mdepid;
-	struct health_app *app;
-};
-
-static void app_search_mdep(void *data, void *user_data)
-{
-	struct health_app *app = data;
-	struct app_search *search = user_data;
+		if (dev)
+			return dev;
 
-	if (search->app)
-		return;
+		apps_entry = apps_entry->next;
+	}
 
-	if (queue_find(app->mdeps, match_mdep_by_id,
-						INT_TO_PTR(search->mdepid)))
-		search->app = app;
+	return NULL;
 }
 
 static struct health_app *search_app_by_mdepid(uint8_t mdepid)
 {
-	struct app_search search;
+	const struct queue_entry *apps_entry;
+	struct health_app *app;
 
 	DBG("");
 
-	search.mdepid = mdepid;
-	search.app = NULL;
+	apps_entry = queue_get_entries(apps);
+	while (apps_entry) {
+		app = apps_entry->data;
 
-	queue_foreach(apps, app_search_mdep, &search);
+		if (queue_find(app->mdeps, match_mdep_by_id,
+							INT_TO_PTR(mdepid)))
+			return app;
 
-	return search.app;
+		apps_entry = apps_entry->next;
+	}
+
+	return NULL;
 }
 
 static int register_service_protocols(sdp_record_t *rec,
-- 
2.2.0.rc0.207.ga3a616c

[PATCH BlueZ 4/5] monitor/keys: use queue_find over queue_foreach

[Michael Janssen]

Use queue_find instead of visiting all queue items.
---
 monitor/keys.c | 37 ++++++++++---------------------------
 1 file changed, 10 insertions(+), 27 deletions(-)

diff --git a/monitor/keys.c b/monitor/keys.c
index 4ccef22..e60aa93 100644
--- a/monitor/keys.c
+++ b/monitor/keys.c
@@ -99,44 +99,27 @@ void keys_update_identity_addr(const uint8_t addr[6], uint8_t addr_type)
 	}
 }
 
-struct resolve_data {
-	bool found;
-	uint8_t addr[6];
-	uint8_t ident[6];
-	uint8_t ident_type;
-};
-
-static void try_resolve_irk(void *data, void *user_data)
+static bool match_resolve_irk(const void *data, const void *match_data)
 {
-	struct irk_data *irk = data;
-	struct resolve_data *result = user_data;
+	const struct irk_data *irk = data;
+	const uint8_t *addr = match_data;
 	uint8_t local_hash[3];
 
-	if (result->found)
-		return;
-
-	bt_crypto_ah(crypto, irk->key, result->addr + 3, local_hash);
+	bt_crypto_ah(crypto, irk->key, addr + 3, local_hash);
 
-	if (!memcmp(result->addr, local_hash, 3)) {
-		result->found = true;
-		memcpy(result->ident, irk->addr, 6);
-		result->ident_type = irk->addr_type;
-	}
+	return !memcmp(addr, local_hash, 3);
 }
 
 bool keys_resolve_identity(const uint8_t addr[6], uint8_t ident[6],
 							uint8_t *ident_type)
 {
-	struct resolve_data result;
-
-	result.found = false;
-	memcpy(result.addr, addr, 6);
+	struct irk_data *irk;
 
-	queue_foreach(irk_list, try_resolve_irk, &result);
+	irk = queue_find(irk_list, match_resolve_irk, addr);
 
-	if (result.found) {
-		memcpy(ident, result.ident, 6);
-		*ident_type = result.ident_type;
+	if (irk) {
+		memcpy(ident, irk->addr, 6);
+		*ident_type = irk->addr_type;
 		return true;
 	}
 
-- 
2.2.0.rc0.207.ga3a616c

[PATCH BlueZ 5/5] shared/gatt-db: manual iteration when appopriate

[Michael Janssen]

Uses queue_get_entries where it is appopriate to do so: focus on
places where there are an unnecessary amount of extra iteration.
---
 src/shared/gatt-db.c | 150 +++++++++++++++++++++------------------------------
 1 file changed, 60 insertions(+), 90 deletions(-)

diff --git a/src/shared/gatt-db.c b/src/shared/gatt-db.c
index 98fb8a0..fce3854 100644
--- a/src/shared/gatt-db.c
+++ b/src/shared/gatt-db.c
@@ -444,39 +444,36 @@ bool gatt_db_clear_range(struct gatt_db *db, uint16_t start_handle,
 	return true;
 }
 
-struct insert_loc_data {
-	struct gatt_db_service *cur;
-	uint16_t start, end;
-	bool fail;
-	bool done;
-};
-
-static void search_for_insert_loc(void *data, void *user_data)
+static bool find_insert_loc(struct gatt_db *db, uint16_t start, uint16_t end,
+						struct gatt_db_service **after)
 {
-	struct insert_loc_data *loc_data = user_data;
-	struct gatt_db_service *service = data;
+	const struct queue_entry *services_entry;
+	struct gatt_db_service *service;
 	uint16_t cur_start, cur_end;
 
-	if (loc_data->done)
-		return;
+	*after = NULL;
 
-	gatt_db_service_get_handles(service, &cur_start, &cur_end);
+	services_entry = queue_get_entries(db->services);
 
-	/* Abort if the requested range overlaps with an existing service. */
-	if ((loc_data->start >= cur_start && loc_data->start <= cur_end) ||
-		(loc_data->end >= cur_start && loc_data->end <= cur_end)) {
-		loc_data->fail = true;
-		loc_data->done = true;
-		return;
-	}
+	while (services_entry) {
+		service = services_entry->data;
 
-	/* Check if this is where the service should be inserted. */
-	if (loc_data->end < cur_start) {
-		loc_data->done = true;
-		return;
+		gatt_db_service_get_handles(service, &cur_start, &cur_end);
+
+		if (start >= cur_start && start <= cur_end)
+			return false;
+
+		if (end >= cur_start && end <= cur_end)
+			return false;
+
+		if (end < cur_start)
+			return true;
+
+		*after = service;
+		services_entry = services_entry->next;
 	}
 
-	loc_data->cur = service;
+	return true;
 }
 
 struct gatt_db_attribute *gatt_db_insert_service(struct gatt_db *db,
@@ -485,8 +482,9 @@ struct gatt_db_attribute *gatt_db_insert_service(struct gatt_db *db,
 							bool primary,
 							uint16_t num_handles)
 {
-	struct insert_loc_data data;
-	struct gatt_db_service *service;
+	struct gatt_db_service *service, *after;
+
+	after = NULL;
 
 	if (!db || handle < 1)
 		return NULL;
@@ -494,25 +492,19 @@ struct gatt_db_attribute *gatt_db_insert_service(struct gatt_db *db,
 	if (num_handles < 1 || (handle + num_handles - 1) > UINT16_MAX)
 		return NULL;
 
-	memset(&data, 0, sizeof(data));
-
-	data.start = handle;
-	data.end = handle + num_handles - 1;
-
-	queue_foreach(db->services, search_for_insert_loc, &data);
-
-	if (data.fail)
+	if (!find_insert_loc(db, handle, handle + num_handles - 1, &after))
 		return NULL;
 
 	service = gatt_db_service_create(uuid, primary, num_handles);
+
 	if (!service)
 		return NULL;
 
-	if (data.cur) {
-		if (!queue_push_after(db->services, data.cur, service))
+	if (after) {
+		if (!queue_push_after(db->services, after, service))
 			goto fail;
 	} else if (!queue_push_head(db->services, service)) {
-			goto fail;
+		goto fail;
 	}
 
 	service->db = db;
@@ -782,70 +774,48 @@ bool gatt_db_service_set_active(struct gatt_db_attribute *attrib, bool active)
 	return true;
 }
 
-struct read_by_group_type_data {
-	struct queue *queue;
-	bt_uuid_t uuid;
-	uint16_t start_handle;
-	uint16_t end_handle;
-	uint16_t uuid_size;
-	bool stop_search;
-};
-
-static void read_by_group_type(void *data, void *user_data)
+void gatt_db_read_by_group_type(struct gatt_db *db, uint16_t start_handle,
+							uint16_t end_handle,
+							const bt_uuid_t type,
+							struct queue *queue)
 {
-	struct read_by_group_type_data *search_data = user_data;
-	struct gatt_db_service *service = data;
-	uint16_t grp_start, grp_end;
+	const struct queue_entry *services_entry;
+	struct gatt_db_service *service;
+	uint16_t grp_start, grp_end, uuid_size;
 
-	if (!service->active)
-		return;
+	uuid_size = 0;
 
-	/* Don't want more results as they have different size */
-	if (search_data->stop_search)
-		return;
+	services_entry = queue_get_entries(db->services);
 
-	if (bt_uuid_cmp(&search_data->uuid, &service->attributes[0]->uuid))
-		return;
+	while (services_entry) {
+		service = services_entry->data;
 
-	grp_start = service->attributes[0]->handle;
-	grp_end = grp_start + service->num_handles - 1;
+		if (!service->active)
+			goto next_service;
 
-	if (grp_end < search_data->start_handle ||
-				grp_start > search_data->end_handle)
-		return;
+		if (bt_uuid_cmp(&type, &service->attributes[0]->uuid))
+			goto next_service;
 
-	if (service->attributes[0]->handle < search_data->start_handle ||
-		service->attributes[0]->handle > search_data->end_handle)
-		return;
+		grp_start = service->attributes[0]->handle;
+		grp_end = grp_start + service->num_handles - 1;
 
-	/* Remember size of uuid */
-	if (!search_data->uuid_size) {
-		search_data->uuid_size = service->attributes[0]->value_len;
-	} else if (search_data->uuid_size !=
-					service->attributes[0]->value_len) {
-		/* Don't want more results. This is last */
-		search_data->stop_search = true;
-		return;
-	}
+		if (grp_end < start_handle || grp_start > end_handle)
+			goto next_service;
 
-	queue_push_tail(search_data->queue, service->attributes[0]);
-}
+		if (grp_start < start_handle || grp_start > end_handle)
+			goto next_service;
 
-void gatt_db_read_by_group_type(struct gatt_db *db, uint16_t start_handle,
-							uint16_t end_handle,
-							const bt_uuid_t type,
-							struct queue *queue)
-{
-	struct read_by_group_type_data data;
+		if (!uuid_size) {
+			uuid_size = service->attributes[0]->value_len;
+		} else if (uuid_size != service->attributes[0]->value_len) {
+			return;
+		}
 
-	data.uuid = type;
-	data.start_handle = start_handle;
-	data.end_handle = end_handle;
-	data.queue = queue;
-	data.uuid_size = 0;
-	data.stop_search = false;
+		queue_push_tail(queue, service->attributes[0]);
 
-	queue_foreach(db->services, read_by_group_type, &data);
+next_service:
+		services_entry = services_entry->next;
+	}
 }
 
 struct find_by_type_value_data {
-- 
2.2.0.rc0.207.ga3a616c

Re: [PATCH BlueZ 0/5] Add const access to linked list for efficiency

[Luiz Augusto von Dentz]

Hi Michael,

On Tue, Dec 16, 2014 at 3:03 AM, Michael Janssen <jamuraa@chromium.org> wrote:
> In many cases, queue_foreach is being used to find a specific item not easily
> locatable using queue_find or can be finished early.  This set adds
> queue_get_entries which gives a method for manual iteration of the queue.
>
> The other patches use this feature to improve efficiency of some iterations.
>
> Michael Janssen (5):
>   shared/queue: Add queue_get_entries
>   shared/queue: clarify queue_match_func_t arguments
>   android/health: improve search efficiency
>   monitor/keys: use queue_find over queue_foreach
>   shared/gatt-db: manual iteration when appopriate
>
>  android/health.c     | 153 +++++++++++++++++++++------------------------------
>  monitor/keys.c       |  37 ++++---------
>  src/shared/gatt-db.c | 150 ++++++++++++++++++++------------------------------
>  src/shared/queue.c   |  14 +++--
>  src/shared/queue.h   |  10 +++-
>  5 files changed, 151 insertions(+), 213 deletions(-)
>
> --
> 2.2.0.rc0.207.ga3a616c

Applied, thanks.


-- 
Luiz Augusto von Dentz