pmplib-commits

[Pmplib-commits] SF.net SVN: pmplib: [211] trunk/pmplib/lib/pmp_iriverplus3/idx.c

[<ny...@us...>]

Revision: 211
          http://svn.sourceforge.net/pmplib/?rev=211&view=rev
Author:   nyaochi
Date:     2006-12-27 11:22:33 -0800 (Wed, 27 Dec 2006)

Log Message:
-----------
Source code clean-up for idx.c

Modified Paths:
--------------
    trunk/pmplib/lib/pmp_iriverplus3/idx.c

Modified: trunk/pmplib/lib/pmp_iriverplus3/idx.c
===================================================================
--- trunk/pmplib/lib/pmp_iriverplus3/idx.c	2006-12-27 19:11:11 UTC (rev 210)
+++ trunk/pmplib/lib/pmp_iriverplus3/idx.c	2006-12-27 19:22:33 UTC (rev 211)
@@ -26,6 +26,9 @@
 - This file seems to have 12-bytes header
 - Indices consist of multiple binary search trees
 - The offset addresses to the root nodes are specified in db.dic
+
+Implementation note:
+- The AVL trees are 
 */
 
 #ifdef	HAVE_CONFIG_H
@@ -47,12 +50,6 @@
 
 #define	COMP(a, b)	((a)>(b))-((a)<(b))
 
-typedef struct {
-	uint32_t	size;
-	uint32_t	unknown1;
-	uint32_t	unknown2;
-} idx_header_t;
-
 struct tag_avlnode_t {
 	uint32_t left;
 	uint32_t right;
@@ -312,7 +309,6 @@
 		break;
 	}
 
-	memcpy(avlnode(avl, offset_key), key, size);
 	ret = avl_insert(avl, root, &offset_this, comp[type]);
 	if (ret != -1) {
 		/* A new key. */
@@ -326,19 +322,8 @@
 	}
 }
 
-static int avl_insert_keydata(avl_t* avl, const void* key, int type, uint32_t data, uint32_t* root)
-{
-	uint32_t offset = 0;
-	int ret = avl_insert_key(avl, key, type, &offset, root);
-	avlnode_t* node = avlnode(avl, offset);
-	uint32_t offset_tail = avltail_new(avl);
-	avltail_t* tail = (avltail_t*)avlnode(avl, offset_tail);
-	tail->data = data;
-	tail->next = node->tail;
-	node->tail = offset_tail;
-	return ret;
-}
 
+
 static void from_uint16be(uint16_t* value)
 {
 	uint8_t* src = (uint8_t*)value;
@@ -514,6 +499,9 @@
 	return height;
 }
 
+
+
+
 static void fprinti(FILE *fp, int n)
 {
 	while (n--)	fputc(' ', fp);
@@ -590,36 +578,13 @@
 	}
 }
 
-void avl_walk2(avl_t* avl, uint32_t offr, avl_comp_t comp)
-{
-	wchar_t* key = 0;
-	avlnode_t* root = avlnode(avl, offr);
-	avltail_t* tail = (avltail_t*)avlnode(avl, root->tail);
-	if (root->left) avl_walk2(avl, root->left, comp);
-	key = (wchar_t*)avlnode(avl, offr + sizeof(avlnode_t));
-	printf("%S: ", key);
-	for (;;) {
-		printf("%d ", tail->data);
-		if (!tail->next) {
-			break;
-		}
-		tail = (avltail_t*)avlnode(avl, tail->next);
-	}
-	printf("\n");
 
-	if (root->right) avl_walk2(avl, root->right, comp);
-}
 
-void avl_walk(avl_t* avl, uint32_t offr, avl_comp_t comp)
-{
-	wchar_t* key = 0;
-	avlnode_t* root = avlnode(avl, offr);
-	if (root->left) avl_walk(avl, root->left, comp);
-	key = (wchar_t*)avlnode(avl, offr + sizeof(avlnode_t));
-	printf("%S: ", key);
-	avl_walk2(avl, root->tail, comp);
-	if (root->right) avl_walk(avl, root->right, comp);
-}
+typedef struct {
+	uint32_t	size;
+	uint32_t	unknown1;
+	uint32_t	unknown2;
+} idx_header_t;
 
 idx_t *idx_new()
 {
@@ -656,7 +621,7 @@
 	from_uint32be(&header->unknown1);
 	from_uint32be(&header->unknown2);
 
-	/* Convert the byte order of AVL trees. */
+	/* Convert the byte order of values in AVL trees. */
 	for (i = 0;i < dic->music.num_indices;++i) {
 		uint32_t idx_root = dic_get_idxroot(dic, IP3DBIDX_MUSIC, i);
 		from_be_avltree(idx->avl, idx_root, &dic->music, i, 0);
@@ -673,14 +638,15 @@
 	int i;
 	idx_header_t* header = (idx_header_t*)idx->buffer;
 
+	/* The size fo db.idx equals to the maximum offset of the AVL trees. */
 	header->size = idx->avl->offset;
 
-	/* Convert the byte order of the header from big endian to the native one. */
+	/* Convert the byte order of the header to big endian from the native one. */
 	to_uint32be(&header->size);
 	to_uint32be(&header->unknown1);
 	to_uint32be(&header->unknown2);
 
-	/* Convert the byte order of AVL trees. */
+	/* Convert the byte order of values in AVL trees. */
 	for (i = 0;i < dic->music.num_indices;++i) {
 		uint32_t idx_root = dic_get_idxroot(dic, IP3DBIDX_MUSIC, i);
 		to_be_avltree(idx->avl, idx_root, &dic->music, i, 0);


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Pmplib-commits] SF.net SVN: pmplib: [223] trunk/pmplib/lib/pmp_iriverplus3/idx.c

[<ny...@us...>]

Revision: 223
          http://svn.sourceforge.net/pmplib/?rev=223&view=rev
Author:   nyaochi
Date:     2006-12-28 19:02:59 -0800 (Thu, 28 Dec 2006)

Log Message:
-----------
Skip articles ('a', 'an', 'the') when sorting strings. This is the required
specification for the comparison function in AVL trees.

Modified Paths:
--------------
    trunk/pmplib/lib/pmp_iriverplus3/idx.c

Modified: trunk/pmplib/lib/pmp_iriverplus3/idx.c
===================================================================
--- trunk/pmplib/lib/pmp_iriverplus3/idx.c	2006-12-29 01:59:32 UTC (rev 222)
+++ trunk/pmplib/lib/pmp_iriverplus3/idx.c	2006-12-29 03:02:59 UTC (rev 223)
@@ -320,12 +320,34 @@
 	return COMP(*x, *y);
 }
 
+static const ucs2char_t* skip_prefix(const ucs2char_t* str)
+{
+	int i = 0;
+	static const ucs2char_t ucs2cs_a[] = {'a',' ',0};
+	static const ucs2char_t ucs2cs_an[] = {'a','n',' ',0};
+	static const ucs2char_t ucs2cs_the[] = {'t','h','e',' ',0};
+	static const ucs2char_t *prefix[] = {
+		ucs2cs_a, ucs2cs_an, ucs2cs_the, NULL,
+	};
+
+	while (prefix[i]) {
+		if (ucs2incmp(str, prefix[i], ucs2len(prefix[i])) == 0) {
+			return str + ucs2len(prefix[i]);
+		}
+		++i;
+	}
+	return str;
+}
+
 static int avl_comp_ucs2string(avl_t* avl, uint32_t _x, uint32_t _y)
 {
-	ucs2char_t* x = (ucs2char_t*)(avl->buffer + _x);
-	ucs2char_t* y = (ucs2char_t*)(avl->buffer + _y);
 	ucs2char_t a, b;
+	const ucs2char_t* x = (const ucs2char_t*)(avl->buffer + _x);
+	const ucs2char_t* y = (const ucs2char_t*)(avl->buffer + _y);
 
+	x = skip_prefix(x);
+	y = skip_prefix(y);
+
 	do {
 		a = ucs2upper(*x);
 		b = ucs2upper(*y);


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Pmplib-commits] SF.net SVN: pmplib: [286] trunk/pmplib/lib/pmp_iriverplus3/idx.c

[<ny...@us...>]

Revision: 286
          http://svn.sourceforge.net/pmplib/?rev=286&view=rev
Author:   nyaochi
Date:     2007-01-26 05:27:21 -0800 (Fri, 26 Jan 2007)

Log Message:
-----------
[pmp_iriverplus3]
Fixed three bugs in db.idx generation:
- If two strings are identical by comparing without case, compare the strings again with case.
- Avoid the region for a page header because avl_rewind() may move the offset to a start position of a page.
- Do not dump an index whose root offset is 0, which means an empty member of the index.

Modified Paths:
--------------
    trunk/pmplib/lib/pmp_iriverplus3/idx.c

Modified: trunk/pmplib/lib/pmp_iriverplus3/idx.c
===================================================================
--- trunk/pmplib/lib/pmp_iriverplus3/idx.c	2007-01-26 10:09:27 UTC (rev 285)
+++ trunk/pmplib/lib/pmp_iriverplus3/idx.c	2007-01-26 13:27:21 UTC (rev 286)
@@ -116,10 +116,16 @@
 		memset(avl->buffer + avl->size, 0, PAGESIZE);
 		avl->offset = avl->size + sizeof(header_t);
 		avl->size = newsize;
-	} else if (((avl->offset + size) / PAGESIZE) != (avl->offset / PAGESIZE)) {
+	} else {
+		int forward = 0;
 		/* Avoid crossing a page boundary. */
-		uint32_t page = (avl->offset + size) / PAGESIZE;
-		avl->offset = PAGESIZE * page + sizeof(header_t);
+		forward |= (((avl->offset + size - 1) / PAGESIZE) != (avl->offset / PAGESIZE));
+		/* Avoid the region for a page header (caused by a rewind operation near a page boundary). */
+		forward |= (avl->offset % PAGESIZE < sizeof(header_t));
+		if (forward) {
+			uint32_t page = (avl->offset + size) / PAGESIZE;
+			avl->offset = PAGESIZE * page + sizeof(header_t);
+		}
 	}
 
 	/* Allocate a memory block. */
@@ -338,7 +344,7 @@
 	return str;
 }
 
-static int avl_comp_ucs2string(avl_t* avl, uint32_t _x, uint32_t _y)
+static int avl_comp_ucs2string_nocase(avl_t* avl, uint32_t _x, uint32_t _y)
 {
 	ucs2char_t a, b;
 	const ucs2char_t* x = (const ucs2char_t*)(avl->buffer + _x);
@@ -359,6 +365,34 @@
 	return COMP(a, b);
 }
 
+static int avl_comp_ucs2string(avl_t* avl, uint32_t _x, uint32_t _y)
+{
+	/* Compare strings, ignoring case. */
+	int ret = avl_comp_ucs2string_nocase(avl, _x, _y);
+	if (ret == 0) {
+		/* Compare strings with case. */
+		ucs2char_t a, b;
+		const ucs2char_t* x = (const ucs2char_t*)(avl->buffer + _x);
+		const ucs2char_t* y = (const ucs2char_t*)(avl->buffer + _y);
+
+		x = skip_prefix(x);
+		y = skip_prefix(y);
+
+		do {
+			a = *x;
+			b = *y;
+			if (!*x || !*y) {
+				break;
+			}
+			x++;
+			y++;
+		} while (a == b);
+		return COMP(a, b);
+	} else {
+		return ret;
+	}
+}
+
 static int avl_insert_key(avl_t* avl, const ip3db_variant_t* key, int type, uint32_t* offset, uint32_t* root)
 {
 	int ret = 0;
@@ -774,7 +808,9 @@
 		fprintf(fpo, "[");
 		dic_repr_index(dic, IP3DBIDX_MUSIC, i, fpo);
 		fprintf(fpo, "]\n");
-		avl_dump(idx->avl, idx_root, &dic->music, i, 0, fpo);
+		if (idx_root) {
+			avl_dump(idx->avl, idx_root, &dic->music, i, 0, fpo);
+		}
 	}
 	for (i = 0;i < dic->references.num_indices;++i) {
 		uint32_t idx_root = dic_get_idxroot(dic, IP3DBIDX_REFERENCES, i);
@@ -790,7 +826,9 @@
 		fprintf(fpo, "[");
 		dic_repr_index(dic, IP3DBIDX_OBJECTS, i, fpo);
 		fprintf(fpo, "]\n");
-		avl_dump(idx->avl, idx_root, &dic->objects, i, 0, fpo);
+		if (idx_root) {
+			avl_dump(idx->avl, idx_root, &dic->objects, i, 0, fpo);
+		}
 	}
 
 	fprintf(fpo, "\n");


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Pmplib-commits] SF.net SVN: pmplib: [307] trunk/pmplib/lib/pmp_iriverplus3/idx.c

[<ny...@us...>]

Revision: 307
          http://svn.sourceforge.net/pmplib/?rev=307&view=rev
Author:   nyaochi
Date:     2007-02-07 07:50:54 -0800 (Wed, 07 Feb 2007)

Log Message:
-----------
Append a new element at the bottom of the tail (linked list pointed by an AVL tree node), rather than at the
beginning of the tail. I'm not sure the specification about the ordering of elements in a tail at this moment,
but this can solve the problem where tracks in a playlist are arranged in reversed order. This is not a
perfect solution; I need to investigate the ordering later.

Modified Paths:
--------------
    trunk/pmplib/lib/pmp_iriverplus3/idx.c

Modified: trunk/pmplib/lib/pmp_iriverplus3/idx.c
===================================================================
--- trunk/pmplib/lib/pmp_iriverplus3/idx.c	2007-02-07 14:11:15 UTC (rev 306)
+++ trunk/pmplib/lib/pmp_iriverplus3/idx.c	2007-02-07 15:50:54 UTC (rev 307)
@@ -886,12 +886,24 @@
 	} else {
 		/*	The same here. We must obtain the pointer to the node after avltail_new() call.
 		 */
-		uint32_t offset_tail = avltail_new(idx->avl);
+		uint32_t offset_newelem = avltail_new(idx->avl);
 		avlnode_t* node = avlnode(idx->avl, offset);
-		avltail_t* tail = (avltail_t*)avlnode(idx->avl, offset_tail);
-		tail->data = entry->offset;
-		tail->next = node->tail;
-		node->tail = offset_tail;
+		avltail_t* newelem = (avltail_t*)avlnode(idx->avl, offset_newelem);
+		if (node->tail) {
+			/* Append to the end of the linked list. */
+			avltail_t* elem = (avltail_t*)avlnode(idx->avl, node->tail);
+			while (elem->next) {
+				elem = (avltail_t*)avlnode(idx->avl, elem->next);
+			}
+			elem->next = offset_newelem;
+			newelem->data = entry->offset;
+			newelem->next = 0;
+		} else {
+			/* The first element in the linked list. */
+			node->tail = offset_newelem;
+			newelem->data = entry->offset;
+			newelem->next = 0;
+		}
 	}
 }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.