From d95b00a4d606b97469fb38c69de66915ae9a0dd0 Mon Sep 17 00:00:00 2001 From: waker Date: Tue, 26 Apr 2011 22:31:06 +0200 Subject: optimized search --- Makefile.am | 4 ++- metacache.c | 1 + playlist.c | 84 ++++++++++++++++++++++++++++++++++++++++++-------- plmeta.c | 55 ++++++++++++++++----------------- plugins/gtkui/search.c | 6 ---- utf8.c | 61 ++++++++++++++++++++++++++---------- utf8.h | 4 +++ 7 files changed, 152 insertions(+), 63 deletions(-) diff --git a/Makefile.am b/Makefile.am index 056b4a9d..bd39e68d 100644 --- a/Makefile.am +++ b/Makefile.am @@ -27,7 +27,9 @@ deadbeef_SOURCES =\ conf.c conf.h\ threading_pthread.c threading.h\ volume.c volume.h\ - junklib.h junklib.c utf8.c utf8.h u8_lc_map.h ConvertUTF/ConvertUTF.c ConvertUTF/ConvertUTF.h\ + junklib.h junklib.c utf8.c utf8.h\ + u8_lc_map.h\ + ConvertUTF/ConvertUTF.c ConvertUTF/ConvertUTF.h\ optmath.h\ vfs.c vfs.h vfs_stdio.c\ md5/md5.c md5/md5.h\ diff --git a/metacache.c b/metacache.c index d4e7b128..84acaa91 100644 --- a/metacache.c +++ b/metacache.c @@ -24,6 +24,7 @@ typedef struct metacache_str_s { struct metacache_str_s *next; uint32_t refcount; + char cmpidx; // positive means "equals", negative means "notequals" char str[1]; } metacache_str_t; diff --git a/playlist.c b/playlist.c index bf4743ae..26e5fc7b 100644 --- a/playlist.c +++ b/playlist.c @@ -3552,28 +3552,88 @@ void pl_search_process (const char *text) { LOCK; pl_search_reset (); + + // convert text to lowercase, to save some cycles + char lc[1000]; + int n = sizeof (lc)-1; + const char *p = text; + char *out = lc; + while (*p) { + int32_t i = 0; + char s[10]; + const char *next; + u8_nextchar (p, &i); + int l = u8_tolower (p, i, s); + n -= l; + if (n < 0) { + break; + } + memcpy (out, s, l); + p += i; + out += l; + } + *out = 0; + + const char *cuesheet = metacache_add_string ("cuesheet"); + const char *log = metacache_add_string("log"); + + static int cmpidx = 0; + cmpidx++; + if (cmpidx > 127) { + cmpidx = 1; + } + for (playItem_t *it = playlist->head[PL_MAIN]; it; it = it->next[PL_MAIN]) { it->selected = 0; if (*text) { - for (DB_metaInfo_t *m = it->meta; m; m = m->next) { - if (m->key[0] != ':' && m->key[0] != '_' && strcasecmp (m->key, "cuesheet") && utfcasestr (m->value, text)) { - //fprintf (stderr, "%s -> %s match (%s.%s)\n", text, m->value, pl_find_meta (it, ":URI"), m->key); - // add to list - it->next[PL_SEARCH] = NULL; - if (playlist->tail[PL_SEARCH]) { - playlist->tail[PL_SEARCH]->next[PL_SEARCH] = it; - playlist->tail[PL_SEARCH] = it; + DB_metaInfo_t *m = NULL; + for (m = it->meta; m; m = m->next) { + if (m->key[0] == ':' || m->key[0] == '_') { + break; + } + if (m->key!=cuesheet && m->key!=log) { + char cmp = *(m->value-1); + + if (abs (cmp) == cmpidx) { + if (cmp > 0) { + it->next[PL_SEARCH] = NULL; + if (playlist->tail[PL_SEARCH]) { + playlist->tail[PL_SEARCH]->next[PL_SEARCH] = it; + playlist->tail[PL_SEARCH] = it; + } + else { + playlist->head[PL_SEARCH] = playlist->tail[PL_SEARCH] = it; + } + it->selected = 1; + playlist->count[PL_SEARCH]++; + break; + } + } + else if (utfcasestr_fast (m->value, lc)) { + //fprintf (stderr, "%s -> %s match (%s.%s)\n", text, m->value, pl_find_meta (it, ":URI"), m->key); + // add to list + it->next[PL_SEARCH] = NULL; + if (playlist->tail[PL_SEARCH]) { + playlist->tail[PL_SEARCH]->next[PL_SEARCH] = it; + playlist->tail[PL_SEARCH] = it; + } + else { + playlist->head[PL_SEARCH] = playlist->tail[PL_SEARCH] = it; + } + it->selected = 1; + playlist->count[PL_SEARCH]++; + *((char *)m->value-1) = cmpidx; + break; } else { - playlist->head[PL_SEARCH] = playlist->tail[PL_SEARCH] = it; + *((char *)m->value-1) = -cmpidx; } - it->selected = 1; - playlist->count[PL_SEARCH]++; - break; } } } } + metacache_remove_string (cuesheet); + metacache_remove_string(log); UNLOCK; } diff --git a/plmeta.c b/plmeta.c index 6b287637..36e289e6 100644 --- a/plmeta.c +++ b/plmeta.c @@ -30,6 +30,8 @@ void pl_add_meta (playItem_t *it, const char *key, const char *value) { LOCK; // check if it's already set + DB_metaInfo_t *normaltail = NULL; + DB_metaInfo_t *propstart = NULL; DB_metaInfo_t *tail = NULL; DB_metaInfo_t *m = it->meta; while (m) { @@ -38,6 +40,15 @@ pl_add_meta (playItem_t *it, const char *key, const char *value) { UNLOCK; return; } + // find end of normal metadata + if (!normaltail && (m->key[0] == ':' || m->key[0] == '_')) { + normaltail = tail; + propstart = m; + if (key[0] != ':' && key[0] != '_') { + break; + } + } + // find end of properties tail = m; m = m->next; } @@ -46,40 +57,28 @@ pl_add_meta (playItem_t *it, const char *key, const char *value) { if (!value || !*value) { UNLOCK; return; -#if 0 - if (!strcasecmp (key, "title")) { - // cut filename without path and extension - const char *pext = pl_find_meta (it, ":URI") + strlen (pl_find_meta (it, ":URI")) - 1; - while (pext >= pl_find_meta (it, ":URI") && *pext != '.') { - pext--; - } - const char *pname = pext; - while (pname >= pl_find_meta (it, ":URI") && *pname != '/') { - pname--; - } - if (*pname == '/') { - pname++; - } - strncpy (str, pname, pext-pname); - str[pext-pname] = 0; - value = str; - } - else { - UNLOCK; - return; - } -#endif } m = malloc (sizeof (DB_metaInfo_t)); memset (m, 0, sizeof (DB_metaInfo_t)); - m->key = metacache_add_string (key); //key; - m->value = metacache_add_string (value); //strdup (value); + m->key = metacache_add_string (key); + m->value = metacache_add_string (value); - if (tail) { - tail->next = m; + if (key[0] == ':' || key[0] == '_') { + if (tail) { + tail->next = m; + } + else { + it->meta = m; + } } else { - it->meta = m; + m->next = propstart; + if (normaltail) { + normaltail->next = m; + } + else { + it->meta = m; + } } UNLOCK; } diff --git a/plugins/gtkui/search.c b/plugins/gtkui/search.c index eb7cb507..4f8eaec8 100644 --- a/plugins/gtkui/search.c +++ b/plugins/gtkui/search.c @@ -74,12 +74,6 @@ void on_searchentry_changed (GtkEditable *editable, gpointer user_data) { - // final implementation must work in separate thread, and catch up when - // value was changed - // but for alpha, let's do it in GTK thread - - // walk playlist starting with playlist_head, and populate list starting - // with search_head search_refresh (); main_refresh (); } diff --git a/utf8.c b/utf8.c index 6249f94a..3f703ae8 100644 --- a/utf8.c +++ b/utf8.c @@ -604,6 +604,18 @@ static const char lowerchars[] = "áéíñóúüäöåæøàçèêабвгдеё static const char upperchars[] = "ÁÉÍÑÓÚÜÄÖÅÆØÀÇÈÊАБВГДЕЁЖЗИЙКЛМНОРПСТУФХЦЧШЩЪЫЬЭЮЯ"; #endif +int +u8_tolower_slow (const char *input, int len, char *out) { + struct u8_case_map_t *lc = u8_lc_in_word_set (input, len); + if (lc) { + int ll = strlen (lc->lower); + memcpy (out, lc->lower, ll); + out[ll] = 0; + return ll; + } + return 0; +} + int u8_tolower (const signed char *c, int l, char *out) { if (*c >= 65 && *c <= 90) { @@ -617,24 +629,10 @@ u8_tolower (const signed char *c, int l, char *out) { return 1; } else { -#if 1 - struct u8_case_map_t *lc = u8_lc_in_word_set (c, l); - if (lc) { - int ll = 2;//strlen (lc->lower); - memcpy (out, lc->lower, ll); - out[ll] = 0; + int ll = u8_tolower_slow (c, l, out); + if (ll) { return ll; } -#else - for (int i = 0; i < sizeof (upperchars)-l; i++) { - if (!memcmp (upperchars+i, c, l)) { - // found! - memcpy (out, lowerchars+i, l); - out[l] = 0; - return l; - } - } -#endif memcpy (out, c, l); out[l] = 0; return l; @@ -688,6 +686,37 @@ utfcasestr (const char *s1, const char *s2) { return NULL; } +#define min(x,y) ((x)<(y)?(x):(y)) +// s2 must be lowercase +const char * +utfcasestr_fast (const char *s1, const char *s2) { + while (*s1) { + const char *p1 = s1; + const char *p2 = s2; + while (*p2 && *p1) { + int32_t i1 = 0; + int32_t i2 = 0; + char lw1[10]; + const char *next; + u8_nextchar (p1, &i1); + u8_nextchar (p2, &i2); + int l1 = u8_tolower (p1, i1, lw1); + if (memcmp (lw1, p2, min(i2,l1))) { + break; + } + p1 += i1; + p2 += i2; + } + if (*p2 == 0) { + return p1; + } + int32_t i = 0; + u8_nextchar (s1, &i); + s1 += i; + } + return NULL; +} + int u8_strcasecmp (const char *a, const char *b) { const char *p1 = a, *p2 = b; diff --git a/utf8.h b/utf8.h index 9deb08a3..d72d14a1 100644 --- a/utf8.h +++ b/utf8.h @@ -107,4 +107,8 @@ u8_strcasecmp (const char *a, const char *b); const char * utfcasestr (const char *s1, const char *s2); +// s2 must be lowercase +const char * +utfcasestr_fast (const char *s1, const char *s2); + #endif -- cgit v1.2.3