summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMiika Pekkarinen <miipekk@ihme.org>2006-04-18 18:56:56 +0000
committerMiika Pekkarinen <miipekk@ihme.org>2006-04-18 18:56:56 +0000
commitfa893c6b88d823dcdd3c746a94cfcde9765342cd (patch)
tree3aea16925a89b78f80dce844ce48d8e8fea60a22
parent2b18727a8abe08cf5f9d267d5f664bff13bd1cb2 (diff)
downloadrockbox-fa893c6b88d823dcdd3c746a94cfcde9765342cd.tar.gz
rockbox-fa893c6b88d823dcdd3c746a94cfcde9765342cd.tar.bz2
rockbox-fa893c6b88d823dcdd3c746a94cfcde9765342cd.zip
Performance optimizations for tagcache commit. Still more left to be done.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@9721 a1c6a512-1295-4272-9138-f99709370657
-rw-r--r--apps/tagcache.c295
-rw-r--r--apps/tagcache.h24
-rw-r--r--firmware/SOURCES1
-rw-r--r--firmware/common/crc32.c57
-rw-r--r--firmware/include/crc32.h25
5 files changed, 279 insertions, 123 deletions
diff --git a/apps/tagcache.c b/apps/tagcache.c
index 1c4ab6f3af..7bd0a819df 100644
--- a/apps/tagcache.c
+++ b/apps/tagcache.c
@@ -33,6 +33,7 @@
#include "tagcache.h"
#include "buffer.h"
#include "atoi.h"
+#include "crc32.h"
/* Tag Cache thread. */
static struct event_queue tagcache_queue;
@@ -66,19 +67,12 @@ static bool tagcache_init_done = false;
static int init_step;
/* Queue commands. */
-#define Q_STOP_SCAN 0
-#define Q_START_SCAN 1
-#define Q_FORCE_UPDATE 2
-
-/* Tag database files. */
-#define TAGCACHE_FILE_TEMP ROCKBOX_DIR "/tagcache_tmp.tcd"
-#define TAGCACHE_FILE_MASTER ROCKBOX_DIR "/tagcache_idx.tcd"
-#define TAGCACHE_FILE_INDEX ROCKBOX_DIR "/tagcache_%d.tcd"
-
-/* Tag Cache Header version 'TCHxx' */
-#define TAGCACHE_MAGIC 0x54434802
+enum tagcache_queue {
+ Q_STOP_SCAN = 0,
+ Q_START_SCAN,
+ Q_FORCE_UPDATE,
+};
-#define TAGCACHE_RESERVE 32768
/* Tag database structures. */
@@ -92,6 +86,7 @@ struct tagfile_entry {
/* Fixed-size tag entry in master db index. */
struct index_entry {
long tag_seek[TAG_COUNT];
+ long flag;
};
/* Header is the same in every file. */
@@ -868,6 +863,19 @@ bool tagcache_retrieve(struct tagcache_search *tcs, int idxid,
}
#if 0
+
+static bool tagcache_delete(const char *filename)
+{
+ struct index_entry *entry;
+
+ entry = find_entry_disk(filename, true);
+ if (entry == NULL)
+ {
+ logf("not found: %s", filename);
+ return false;
+ }
+}
+
void tagcache_modify(struct tagcache_search *tcs, int type, const char *text)
{
struct tagentry *entry;
@@ -1111,7 +1119,7 @@ static bool tempbuf_insert(char *str, int id, int idx_id)
return false;
index[tempbufidx].id = (struct tempbuf_id *)&tempbuf[tempbuf_pos];
-#ifdef ROCKBOX_STRICT_ALIGN
+#ifdef TAGCACHE_STRICT_ALIGN
/* Make sure the entry is long aligned. */
if ((long)index[tempbufidx].id & 0x03)
{
@@ -1141,41 +1149,51 @@ static bool tempbuf_unique_insert(char *str, int id)
struct tempbuf_searchidx *index = (struct tempbuf_searchidx *)tempbuf;
struct tempbuf_id *idp;
int i;
+ unsigned crc32;
+ unsigned *crcbuf = (unsigned *)&tempbuf[tempbuf_size-4];
- /* Check if string already exists. */
+ crc32 = crc_32(str, strlen(str), 0xffffffff);
+
+ /* Check if the crc does not exist -> entry does not exist for sure. */
for (i = 0; i < tempbufidx; i++)
{
- if (!strcasecmp(str, index[i].str))
+ if (*(crcbuf--) == crc32)
{
- tempbuf_left -= sizeof(struct tempbuf_id);
- if (tempbuf_left - 4 < 0)
- return false;
-
- idp = index[i].id;
- while (idp->next != NULL)
- idp = idp->next;
-
- idp->next = (struct tempbuf_id *)&tempbuf[tempbuf_pos];
-#ifdef ROCKBOX_STRICT_ALIGN
- /* Make sure the entry is long aligned. */
- if ((long)idp->next & 0x03)
+ if (!strcasecmp(str, index[i].str))
{
- int fix = 4 - ((long)idp->next & 0x03);
- tempbuf_left -= fix;
- tempbuf_pos += fix;
- idp->next = (struct tempbuf_id *)((
- (long)idp->next & ~0x03) + 0x04);
- }
+ tempbuf_left -= sizeof(struct tempbuf_id);
+ if (tempbuf_left - 4 < 0)
+ return false;
+
+ idp = index[i].id;
+ while (idp->next != NULL)
+ idp = idp->next;
+
+ idp->next = (struct tempbuf_id *)&tempbuf[tempbuf_pos];
+#if TAGCACHE_STRICT_ALIGN
+ /* Make sure the entry is long aligned. */
+ if ((long)idp->next & 0x03)
+ {
+ int fix = 4 - ((long)idp->next & 0x03);
+ tempbuf_left -= fix;
+ tempbuf_pos += fix;
+ idp->next = (struct tempbuf_id *)
+ (((long)idp->next & ~0x03) + 0x04);
+ }
#endif
- idp = idp->next;
- idp->id = id;
- idp->next = NULL;
- tempbuf_pos += sizeof(struct tempbuf_id);
-
- return true;
+ idp = idp->next;
+ idp->id = id;
+ idp->next = NULL;
+ tempbuf_pos += sizeof(struct tempbuf_id);
+
+ return true;
+ }
}
}
+ /* Insert and quit. */
+ *crcbuf = crc32;
+ tempbuf_left -= 4;
return tempbuf_insert(str, id, -1);
}
@@ -1200,7 +1218,7 @@ static int tempbuf_sort(int fd)
struct tagfile_entry fe;
int i;
int length;
-#ifdef ROCKBOX_STRICT_ALIGN
+#ifdef TAGCACHE_STRICT_ALIGN
int fix;
#endif
@@ -1213,7 +1231,7 @@ static int tempbuf_sort(int fd)
fe.tag_length = length;
fe.idx_id = index[i].idx_id;
-#ifdef ROCKBOX_STRICT_ALIGN
+#ifdef TAGCACHE_STRICT_ALIGN
/* Make sure the entry is long aligned. */
if (index[i].seek & 0x03)
{
@@ -1241,7 +1259,7 @@ static int tempbuf_sort(int fd)
return -2;
}
-#ifdef ROCKBOX_STRICT_ALIGN
+#ifdef TAGCACHE_STRICT_ALIGN
/* Write some padding. */
if (fix)
write(fd, "XXX", fix);
@@ -1251,15 +1269,21 @@ static int tempbuf_sort(int fd)
return i;
}
-
-static struct tempbuf_searchidx* tempbuf_locate(int id)
+inline static struct tempbuf_searchidx* tempbuf_locate(int id)
{
struct tempbuf_searchidx *index = (struct tempbuf_searchidx *)tempbuf;
struct tempbuf_id *idp;
+ static int last_id = 0;
int i;
+ try_again:
+
+ if (last_id >= tempbufidx)
+ last_id = 0;
+
/* Check if string already exists. */
- for (i = 0; i < tempbufidx; i++)
+ /* FIXME: This check is extremely slow, O(n^2) */
+ for (i = last_id; i < tempbufidx; i++)
{
idp = index[i].id;
while (idp != NULL)
@@ -1270,11 +1294,14 @@ static struct tempbuf_searchidx* tempbuf_locate(int id)
}
}
+ if (last_id)
+ goto try_again;
+
return NULL;
}
-static int tempbuf_find_location(int id)
+inline static int tempbuf_find_location(int id)
{
struct tempbuf_searchidx *entry;
@@ -1380,12 +1407,13 @@ static bool build_numeric_index(int index_type, struct tagcache_header *h, int t
return true;
}
-
+
static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
{
int i;
struct tagcache_header tch;
- struct index_entry idx;
+ struct index_entry idxbuf[IDX_BUF_DEPTH];
+ int idxbuf_pos;
char buf[MAX_PATH];
int fd = -1, masterfd;
bool error = false;
@@ -1425,6 +1453,7 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
*/
if (tagcache_is_sorted_tag(index_type))
{
+ logf("loading tags...");
for (i = 0; i < tch.entry_count; i++)
{
struct tagfile_entry entry;
@@ -1460,6 +1489,7 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
tempbuf_insert(buf, loc + TAGFILE_MAX_ENTRIES, entry.idx_id);
yield();
}
+ logf("done");
}
else
tempbufidx = tch.entry_count;
@@ -1555,6 +1585,7 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
{
lseek(tmpfd, sizeof(struct tagcache_header), SEEK_SET);
/* h is the header of the temporary file containing new tags. */
+ logf("inserting new tags...");
for (i = 0; i < h->entry_count; i++)
{
struct temp_file_entry entry;
@@ -1600,6 +1631,7 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
entry.tag_length[index_type], SEEK_CUR);
yield();
}
+ logf("done");
/* Sort the buffer data and write it to the index file. */
lseek(fd, sizeof(struct tagcache_header), SEEK_SET);
@@ -1611,128 +1643,146 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
/**
* Now update all indexes in the master lookup file.
*/
+ logf("updating indices...");
lseek(masterfd, sizeof(struct tagcache_header), SEEK_SET);
- for (i = 0; i < tch.entry_count; i++)
+ for (i = 0; i < tch.entry_count; i += idxbuf_pos)
{
+ int j;
int loc = lseek(masterfd, 0, SEEK_CUR);
-
- if (read(masterfd, &idx, sizeof(struct index_entry)) !=
- sizeof(struct index_entry))
+
+ idxbuf_pos = MIN(tch.entry_count - i, IDX_BUF_DEPTH);
+
+ if (read(masterfd, idxbuf, sizeof(struct index_entry)*idxbuf_pos) !=
+ (int)sizeof(struct index_entry)*idxbuf_pos)
{
logf("read fail #2");
error = true;
goto error_exit ;
}
- idx.tag_seek[index_type] = tempbuf_find_location(
- idx.tag_seek[index_type]+TAGFILE_MAX_ENTRIES);
- if (idx.tag_seek[index_type] < 0)
+ lseek(masterfd, loc, SEEK_SET);
+
+ for (j = 0; j < idxbuf_pos; j++)
{
- logf("update error: %d/%d", i, tch.entry_count);
- error = true;
- goto error_exit;
+ idxbuf[j].tag_seek[index_type] = tempbuf_find_location(
+ idxbuf[j].tag_seek[index_type]+TAGFILE_MAX_ENTRIES);
+
+ if (idxbuf[j].tag_seek[index_type] < 0)
+ {
+ logf("update error: %d/%d", i+j, tch.entry_count);
+ error = true;
+ goto error_exit;
+ }
+ yield();
}
-
+
/* Write back the updated index. */
- lseek(masterfd, loc, SEEK_SET);
- if (write(masterfd, &idx, sizeof(struct index_entry)) !=
- sizeof(struct index_entry))
+ if (write(masterfd, idxbuf, sizeof(struct index_entry)*idxbuf_pos) !=
+ (int)sizeof(struct index_entry)*idxbuf_pos)
{
logf("write fail");
error = true;
goto error_exit;
}
- yield();
}
+ logf("done");
}
/**
* Walk through the temporary file containing the new tags.
*/
// build_normal_index(h, tmpfd, masterfd, idx);
+ logf("updating new indices...");
lseek(masterfd, masterfd_pos, SEEK_SET);
lseek(tmpfd, sizeof(struct tagcache_header), SEEK_SET);
lseek(fd, 0, SEEK_END);
- for (i = 0; i < h->entry_count; i++)
+ for (i = 0; i < h->entry_count; i += idxbuf_pos)
{
+ int j;
+
+ idxbuf_pos = MIN(h->entry_count - i, IDX_BUF_DEPTH);
if (init)
{
- memset(&idx, 0, sizeof(struct index_entry));
+ memset(idxbuf, 0, sizeof(struct index_entry)*IDX_BUF_DEPTH);
}
else
{
- if (read(masterfd, &idx, sizeof(struct index_entry)) !=
- sizeof(struct index_entry))
+ int loc = lseek(masterfd, 0, SEEK_CUR);
+
+ if (read(masterfd, idxbuf, sizeof(struct index_entry)*idxbuf_pos) !=
+ (int)sizeof(struct index_entry)*idxbuf_pos)
{
logf("read fail #2");
error = true;
break ;
}
- lseek(masterfd, -sizeof(struct index_entry), SEEK_CUR);
+ lseek(masterfd, loc, SEEK_SET);
}
/* Read entry headers. */
- if (!tagcache_is_sorted_tag(index_type))
+ for (j = 0; j < idxbuf_pos; j++)
{
- struct temp_file_entry entry;
- struct tagfile_entry fe;
-
- if (read(tmpfd, &entry, sizeof(struct temp_file_entry)) !=
- sizeof(struct temp_file_entry))
- {
- logf("read fail #1");
- error = true;
- break ;
- }
-
- /* Read data. */
- if (entry.tag_length[index_type] >= (int)sizeof(buf))
+ if (!tagcache_is_sorted_tag(index_type))
{
- logf("too long entry!");
- logf("length=%d", entry.tag_length[index_type]);
- logf("pos=0x%02x", lseek(tmpfd, 0, SEEK_CUR));
- error = true;
- break ;
- }
+ struct temp_file_entry entry;
+ struct tagfile_entry fe;
+
+ if (read(tmpfd, &entry, sizeof(struct temp_file_entry)) !=
+ sizeof(struct temp_file_entry))
+ {
+ logf("read fail #1");
+ error = true;
+ break ;
+ }
+
+ /* Read data. */
+ if (entry.tag_length[index_type] >= (int)sizeof(buf))
+ {
+ logf("too long entry!");
+ logf("length=%d", entry.tag_length[index_type]);
+ logf("pos=0x%02x", lseek(tmpfd, 0, SEEK_CUR));
+ error = true;
+ break ;
+ }
+
+ lseek(tmpfd, entry.tag_offset[index_type], SEEK_CUR);
+ if (read(tmpfd, buf, entry.tag_length[index_type]) !=
+ entry.tag_length[index_type])
+ {
+ logf("read fail #3");
+ logf("offset=0x%02x", entry.tag_offset[index_type]);
+ logf("length=0x%02x", entry.tag_length[index_type]);
+ error = true;
+ break ;
+ }
- lseek(tmpfd, entry.tag_offset[index_type], SEEK_CUR);
- if (read(tmpfd, buf, entry.tag_length[index_type]) !=
- entry.tag_length[index_type])
- {
- logf("read fail #3");
- logf("offset=0x%02x", entry.tag_offset[index_type]);
- logf("length=0x%02x", entry.tag_length[index_type]);
- error = true;
- break ;
+ /* Write to index file. */
+ idxbuf[j].tag_seek[index_type] = lseek(fd, 0, SEEK_CUR);
+ fe.tag_length = entry.tag_length[index_type];
+ fe.idx_id = tch.entry_count + i + j;
+ write(fd, &fe, sizeof(struct tagfile_entry));
+ write(fd, buf, fe.tag_length);
+ tempbufidx++;
+
+ /* Skip to next. */
+ lseek(tmpfd, entry.data_length - entry.tag_offset[index_type] -
+ entry.tag_length[index_type], SEEK_CUR);
}
-
- /* Write to index file. */
- idx.tag_seek[index_type] = lseek(fd, 0, SEEK_CUR);
- fe.tag_length = entry.tag_length[index_type];
- fe.idx_id = tch.entry_count + i;
- write(fd, &fe, sizeof(struct tagfile_entry));
- write(fd, buf, fe.tag_length);
- tempbufidx++;
-
- /* Skip to next. */
- lseek(tmpfd, entry.data_length - entry.tag_offset[index_type] -
- entry.tag_length[index_type], SEEK_CUR);
- }
- else
- {
- /* Locate the correct entry from the sorted array. */
- idx.tag_seek[index_type] = tempbuf_find_location(i);
- if (idx.tag_seek[index_type] < 0)
+ else
{
- logf("entry not found (%d)");
- error = true;
- break ;
+ /* Locate the correct entry from the sorted array. */
+ idxbuf[j].tag_seek[index_type] = tempbuf_find_location(i + j);
+ if (idxbuf[j].tag_seek[index_type] < 0)
+ {
+ logf("entry not found (%d)");
+ error = true;
+ break ;
+ }
}
}
-
/* Write index. */
- if (write(masterfd, &idx, sizeof(struct index_entry)) !=
- sizeof(struct index_entry))
+ if (write(masterfd, idxbuf, sizeof(struct index_entry)*idxbuf_pos) !=
+ (int)sizeof(struct index_entry)*idxbuf_pos)
{
logf("tagcache: write fail #4");
error = true;
@@ -1741,7 +1791,8 @@ static bool build_index(int index_type, struct tagcache_header *h, int tmpfd)
yield();
}
-
+ logf("done");
+
/* Finally write the uniqued tag index file. */
if (tagcache_is_sorted_tag(index_type))
{
diff --git a/apps/tagcache.h b/apps/tagcache.h
index 468c48c45d..1ac96b4bad 100644
--- a/apps/tagcache.h
+++ b/apps/tagcache.h
@@ -31,16 +31,38 @@ enum tag_type { tag_artist = 0, tag_album, tag_genre, tag_title,
#define HAVE_TC_RAMCACHE 1
#endif
-/* Allow a little drift to the filename ordering. */
+/* Allow a little drift to the filename ordering (should not be too high/low). */
#define POS_HISTORY_COUNT 4
+/* How much to pre-load entries while committing to prevent seeking. */
+#define IDX_BUF_DEPTH 64
+
+/* Tag Cache Header version 'TCHxx'. Increment when changing internal structures. */
+#define TAGCACHE_MAGIC 0x54434803
+
+/* How much to allocate extra space for ramcache. */
+#define TAGCACHE_RESERVE 32768
+
/* How many entries we can create in one tag file (for sorting). */
#define TAGFILE_MAX_ENTRIES 20000
+/* How many entries to fetch to the seek table at once while searching. */
#define SEEK_LIST_SIZE 50
+
+/* Always strict align entries for best performance and binary compatability. */
+#define TAGCACHE_STRICT_ALIGN 1
+
#define TAGCACHE_MAX_FILTERS 3
#define TAGCACHE_MAX_CLAUSES 10
+/* Tag database files. */
+#define TAGCACHE_FILE_TEMP ROCKBOX_DIR "/tagcache_tmp.tcd"
+#define TAGCACHE_FILE_MASTER ROCKBOX_DIR "/tagcache_idx.tcd"
+#define TAGCACHE_FILE_INDEX ROCKBOX_DIR "/tagcache_%d.tcd"
+
+/* Flags */
+#define FLAG_DELETED 0x0001
+
enum clause { clause_none, clause_is, clause_gt, clause_gteq, clause_lt,
clause_lteq, clause_contains, clause_begins_with, clause_ends_with };
enum modifiers { clause_mod_none, clause_mod_not };
diff --git a/firmware/SOURCES b/firmware/SOURCES
index 4b2e63d378..07f4ffd796 100644
--- a/firmware/SOURCES
+++ b/firmware/SOURCES
@@ -5,6 +5,7 @@ logf.c
backlight.c
buffer.c
common/atoi.c
+common/crc32.c
common/ctype.c
#ifndef SIMULATOR
common/dir.c
diff --git a/firmware/common/crc32.c b/firmware/common/crc32.c
new file mode 100644
index 0000000000..18ee6ac710
--- /dev/null
+++ b/firmware/common/crc32.c
@@ -0,0 +1,57 @@
+/***************************************************************************
+ * __________ __ ___.
+ * Open \______ \ ____ ____ | | _\_ |__ _______ ___
+ * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
+ * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
+ * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
+ * \/ \/ \/ \/ \/
+ * $Id$
+ *
+ * Copyright (C) 2003 Jörg Hohensohn [IDC]Dragon
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+/* Code copied from firmware_flash plugin. */
+
+/* Tool function to calculate a CRC32 across some buffer */
+/* third argument is either 0xFFFFFFFF to start or value from last piece */
+unsigned crc_32(unsigned char* buf, unsigned len, unsigned crc32)
+{
+ /* CCITT standard polynomial 0x04C11DB7 */
+ static const unsigned crc32_lookup[16] =
+ { /* lookup table for 4 bits at a time is affordable */
+ 0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
+ 0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
+ 0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
+ 0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
+ };
+
+ unsigned char byte;
+ unsigned t;
+
+ while (len--)
+ {
+ byte = *buf++; /* get one byte of data */
+
+ /* upper nibble of our data */
+ t = crc32 >> 28; /* extract the 4 most significant bits */
+ t ^= byte >> 4; /* XOR in 4 bits of data into the extracted bits */
+ crc32 <<= 4; /* shift the CRC register left 4 bits */
+ crc32 ^= crc32_lookup[t]; /* do the table lookup and XOR the result */
+
+ /* lower nibble of our data */
+ t = crc32 >> 28; /* extract the 4 most significant bits */
+ t ^= byte & 0x0F; /* XOR in 4 bits of data into the extracted bits */
+ crc32 <<= 4; /* shift the CRC register left 4 bits */
+ crc32 ^= crc32_lookup[t]; /* do the table lookup and XOR the result */
+ }
+
+ return crc32;
+}
+
diff --git a/firmware/include/crc32.h b/firmware/include/crc32.h
new file mode 100644
index 0000000000..5e998ab1b9
--- /dev/null
+++ b/firmware/include/crc32.h
@@ -0,0 +1,25 @@
+/***************************************************************************
+ * __________ __ ___.
+ * Open \______ \ ____ ____ | | _\_ |__ _______ ___
+ * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
+ * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
+ * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
+ * \/ \/ \/ \/ \/
+ * $Id$
+ *
+ * Copyright (C) 2003 Jörg Hohensohn [IDC]Dragon
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+#ifndef _CRC32_H
+#define _CRC32_H
+
+unsigned crc_32(unsigned char* buf, unsigned len, unsigned crc32);
+
+#endif
+