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
Hi Michael,
On Tue, Dec 16, 2014 at 3:03 AM, Michael Janssen <[email protected]> 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
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
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
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
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
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