diff options
author | Thomas Martitz <kugel@rockbox.org> | 2011-07-18 18:55:20 +0000 |
---|---|---|
committer | Thomas Martitz <kugel@rockbox.org> | 2011-07-18 18:55:20 +0000 |
commit | 74ab227b58ee3eae152c1142eb9144ee5332a7d9 (patch) | |
tree | 0a3b90bc96169a3ed00fc51120d5009d443bd8c0 /apps/tagtree.c | |
parent | e0970817b0d8b426f4b26090017868067d0f516e (diff) | |
download | rockbox-74ab227b58ee3eae152c1142eb9144ee5332a7d9.tar.gz rockbox-74ab227b58ee3eae152c1142eb9144ee5332a7d9.zip |
Introduce bsearch() and use it in tagtree.c.
bsearch() is a general purpose binary search function for arrays.
It's supposedly faster than looping over arrays.
The array needs to be sorted in ascending order under the provided
comparison function. If the key and array element are of the same kind,
then the same compare function can be used for qsort() and bsearch().
Code taken from glibc.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@30155 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps/tagtree.c')
-rw-r--r-- | apps/tagtree.c | 134 |
1 files changed, 69 insertions, 65 deletions
diff --git a/apps/tagtree.c b/apps/tagtree.c index 3df8d9db2b..1bdc0550a6 100644 --- a/apps/tagtree.c +++ b/apps/tagtree.c | |||
@@ -29,6 +29,7 @@ | |||
29 | #include <stdio.h> | 29 | #include <stdio.h> |
30 | #include <stdlib.h> | 30 | #include <stdlib.h> |
31 | #include "string-extra.h" | 31 | #include "string-extra.h" |
32 | #include "bsearch.h" | ||
32 | #include "config.h" | 33 | #include "config.h" |
33 | #include "system.h" | 34 | #include "system.h" |
34 | #include "kernel.h" | 35 | #include "kernel.h" |
@@ -160,6 +161,13 @@ struct match | |||
160 | int symbol; | 161 | int symbol; |
161 | }; | 162 | }; |
162 | 163 | ||
164 | static int compare_match(const void* _key, const void* _elem) | ||
165 | { | ||
166 | const char* key = _key; | ||
167 | const struct match *elem = _elem; | ||
168 | return strcasecmp(key, elem->str); | ||
169 | } | ||
170 | |||
163 | /* Statusbar text of the current view. */ | 171 | /* Statusbar text of the current view. */ |
164 | static char current_title[MAX_TAGS][128]; | 172 | static char current_title[MAX_TAGS][128]; |
165 | 173 | ||
@@ -221,42 +229,42 @@ static int get_token_str(char *buf, int size) | |||
221 | static int get_tag(int *tag) | 229 | static int get_tag(int *tag) |
222 | { | 230 | { |
223 | static const struct match get_tag_match[] = | 231 | static const struct match get_tag_match[] = |
224 | { | 232 | { /* sorted by ascii (case insensitive) for bsearch */ |
225 | {"album", tag_album}, | 233 | { "%format", var_format }, |
226 | {"artist", tag_artist}, | 234 | { "%include", var_include }, |
227 | {"bitrate", tag_bitrate}, | 235 | { "%limit", var_limit }, |
228 | {"composer", tag_composer}, | 236 | {"%menu_start",var_menu_start}, |
229 | {"comment", tag_comment}, | 237 | {"%root_menu",var_rootmenu}, |
230 | {"albumartist", tag_albumartist}, | 238 | { "%sort", var_sorttype }, |
231 | {"ensemble", tag_albumartist}, | 239 | { "%strip", var_strip }, |
232 | {"grouping", tag_grouping}, | 240 | {"->",menu_next}, |
233 | {"genre", tag_genre}, | 241 | { "==>", menu_load }, |
234 | {"length", tag_length}, | 242 | { "album", tag_album }, |
235 | {"Lm", tag_virt_length_min}, | 243 | { "albumartist", tag_albumartist }, |
236 | {"Ls", tag_virt_length_sec}, | 244 | { "artist", tag_artist }, |
237 | {"Pm", tag_virt_playtime_min}, | 245 | { "autoscore", tag_virt_autoscore }, |
238 | {"Ps", tag_virt_playtime_sec}, | 246 | { "bitrate", tag_bitrate }, |
239 | {"title", tag_title}, | 247 | { "comment", tag_comment }, |
240 | {"filename", tag_filename}, | 248 | { "commitid", tag_commitid }, |
241 | {"tracknum", tag_tracknumber}, | 249 | { "composer", tag_composer }, |
242 | {"discnum", tag_discnumber}, | 250 | { "discnum", tag_discnumber }, |
243 | {"year", tag_year}, | 251 | { "ensemble", tag_albumartist }, |
244 | {"playcount", tag_playcount}, | 252 | { "entryage", tag_virt_entryage }, |
245 | {"rating", tag_rating}, | 253 | { "filename", tag_filename }, |
246 | {"lastplayed", tag_lastplayed}, | 254 | { "genre", tag_genre }, |
247 | {"lastoffset", tag_lastoffset}, | 255 | { "grouping", tag_grouping }, |
248 | {"commitid", tag_commitid}, | 256 | { "lastoffset", tag_lastoffset }, |
249 | {"entryage", tag_virt_entryage}, | 257 | { "lastplayed", tag_lastplayed }, |
250 | {"autoscore", tag_virt_autoscore}, | 258 | { "length", tag_length }, |
251 | {"%sort", var_sorttype}, | 259 | { "Lm", tag_virt_length_min }, |
252 | {"%limit", var_limit}, | 260 | { "Ls", tag_virt_length_sec }, |
253 | {"%strip", var_strip}, | 261 | { "playcount", tag_playcount }, |
254 | {"%menu_start", var_menu_start}, | 262 | { "Pm", tag_virt_playtime_min }, |
255 | {"%include", var_include}, | 263 | { "Ps", tag_virt_playtime_sec }, |
256 | {"%root_menu", var_rootmenu}, | 264 | { "rating", tag_rating }, |
257 | {"%format", var_format}, | 265 | { "title", tag_title }, |
258 | {"->", menu_next}, | 266 | { "tracknum", tag_tracknumber }, |
259 | {"==>", menu_load} | 267 | { "year", tag_year }, |
260 | }; | 268 | }; |
261 | char buf[128]; | 269 | char buf[128]; |
262 | unsigned int i; | 270 | unsigned int i; |
@@ -277,15 +285,13 @@ static int get_tag(int *tag) | |||
277 | } | 285 | } |
278 | buf[i] = '\0'; | 286 | buf[i] = '\0'; |
279 | 287 | ||
280 | for (i = 0; i < ARRAYLEN(get_tag_match); i++) | 288 | struct match *elem = bsearch(buf, get_tag_match, ARRAYLEN(get_tag_match), |
289 | sizeof(struct match), compare_match); | ||
290 | if (elem) | ||
281 | { | 291 | { |
282 | if (!strcasecmp(buf, get_tag_match[i].str)) | 292 | *tag = elem->symbol; |
283 | { | 293 | return 1; |
284 | *tag = get_tag_match[i].symbol; | ||
285 | return 1; | ||
286 | } | ||
287 | } | 294 | } |
288 | |||
289 | logf("NO MATCH: %s\n", buf); | 295 | logf("NO MATCH: %s\n", buf); |
290 | if (buf[0] == '?') | 296 | if (buf[0] == '?') |
291 | return 0; | 297 | return 0; |
@@ -296,21 +302,21 @@ static int get_tag(int *tag) | |||
296 | static int get_clause(int *condition) | 302 | static int get_clause(int *condition) |
297 | { | 303 | { |
298 | static const struct match get_clause_match[] = | 304 | static const struct match get_clause_match[] = |
299 | { | 305 | { /* sorted by ascii (case insensitive) for bsearch */ |
300 | {"=", clause_is}, | 306 | { "!$", clause_not_ends_with }, |
301 | {"==", clause_is}, | 307 | { "!=", clause_is_not }, |
302 | {"!=", clause_is_not}, | 308 | { "!^", clause_not_begins_with }, |
303 | {">", clause_gt}, | 309 | { "!~", clause_not_contains }, |
304 | {">=", clause_gteq}, | 310 | { "$", clause_ends_with }, |
305 | {"<", clause_lt}, | 311 | { "<", clause_lt }, |
306 | {"<=", clause_lteq}, | 312 | { "<=", clause_lteq }, |
307 | {"~", clause_contains}, | 313 | { "=", clause_is }, |
308 | {"!~", clause_not_contains}, | 314 | { "==", clause_is }, |
309 | {"^", clause_begins_with}, | 315 | { ">", clause_gt }, |
310 | {"!^", clause_not_begins_with}, | 316 | { ">=", clause_gteq }, |
311 | {"$", clause_ends_with}, | 317 | { "@", clause_oneof }, |
312 | {"!$", clause_not_ends_with}, | 318 | { "^", clause_begins_with }, |
313 | {"@", clause_oneof} | 319 | { "~", clause_contains }, |
314 | }; | 320 | }; |
315 | 321 | ||
316 | char buf[4]; | 322 | char buf[4]; |
@@ -332,15 +338,13 @@ static int get_clause(int *condition) | |||
332 | } | 338 | } |
333 | buf[i] = '\0'; | 339 | buf[i] = '\0'; |
334 | 340 | ||
335 | for (i = 0; i < ARRAYLEN(get_clause_match); i++) | 341 | struct match *elem = bsearch(buf, get_clause_match, ARRAYLEN(get_clause_match), |
342 | sizeof(struct match), compare_match); | ||
343 | if (elem) | ||
336 | { | 344 | { |
337 | if (!strcasecmp(buf, get_clause_match[i].str)) | 345 | *condition = elem->symbol; |
338 | { | 346 | return 1; |
339 | *condition = get_clause_match[i].symbol; | ||
340 | return 1; | ||
341 | } | ||
342 | } | 347 | } |
343 | |||
344 | return 0; | 348 | return 0; |
345 | } | 349 | } |
346 | 350 | ||