Kirill K. Smirnov : winhelp: Implement generic B+ tree search function.
Alexandre Julliard
julliard at winehq.org
Mon Dec 3 09:17:57 CST 2007
Module: wine
Branch: master
Commit: 6e002c59ce38a496ad27168defe26ad3ab50b031
URL: http://source.winehq.org/git/wine.git/?a=commit;h=6e002c59ce38a496ad27168defe26ad3ab50b031
Author: Kirill K. Smirnov <lich at math.spbu.ru>
Date: Sat Dec 1 19:00:24 2007 +0300
winhelp: Implement generic B+ tree search function.
---
programs/winhelp/hlpfile.c | 74 ++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 74 insertions(+), 0 deletions(-)
diff --git a/programs/winhelp/hlpfile.c b/programs/winhelp/hlpfile.c
index 8252446..af86690 100644
--- a/programs/winhelp/hlpfile.c
+++ b/programs/winhelp/hlpfile.c
@@ -75,6 +75,18 @@ static struct
HLPFILE_LINK* link;
} attributes;
+/*
+ * Compare function type for HLPFILE_BPTreeSearch function.
+ *
+ * PARAMS
+ * p [I] pointer to testing block (key + data)
+ * key [I] pointer to key value to look for
+ * leaf [I] whether this function called for index of leaf page
+ * next [O] pointer to pointer to next block
+ */
+typedef int (*HLPFILE_BPTreeCompare)(void *p, const void *key,
+ int leaf, void **next);
+
static BOOL HLPFILE_DoReadHlpFile(HLPFILE*, LPCSTR);
static BOOL HLPFILE_ReadFileToBuffer(HFILE);
static BOOL HLPFILE_FindSubFile(LPCSTR name, BYTE**, BYTE**);
@@ -93,6 +105,8 @@ static BOOL HLPFILE_Uncompress3(char*, const char*, const BYTE*, const BYTE*);
static void HLPFILE_UncompressRLE(const BYTE* src, const BYTE* end, BYTE** dst, unsigned dstsz);
static BOOL HLPFILE_ReadFont(HLPFILE* hlpfile);
+static void* HLPFILE_BPTreeSearch(BYTE*, const void*, HLPFILE_BPTreeCompare);
+
/***********************************************************************
*
* HLPFILE_PageByNumber
@@ -1904,6 +1918,66 @@ static void HLPFILE_UncompressRLE(const BYTE* src, const BYTE* end, BYTE** dst,
*dst - (sdst - dstsz), dstsz);
}
+/**************************************************************************
+ * HLPFILE_BPTreeSearch
+ *
+ * Searches for an element in B+ tree
+ *
+ * PARAMS
+ * buf [I] pointer to the embedded file structured as a B+ tree
+ * key [I] pointer to data to find
+ * comp [I] compare function
+ *
+ * RETURNS
+ * Pointer to block identified by key, or NULL if failure.
+ *
+ */
+static void* HLPFILE_BPTreeSearch(BYTE* buf, const void* key,
+ HLPFILE_BPTreeCompare comp)
+{
+ unsigned magic;
+ unsigned page_size;
+ unsigned cur_page;
+ unsigned level;
+ BYTE *pages, *ptr, *newptr;
+ int i, entries;
+ int ret;
+
+ magic = GET_USHORT(buf, 9);
+ if (magic != 0x293B)
+ {
+ WINE_ERR("Invalid magic in B+ tree: 0x%x\n", magic);
+ return NULL;
+ }
+ page_size = GET_USHORT(buf, 9+4);
+ cur_page = GET_USHORT(buf, 9+26);
+ level = GET_USHORT(buf, 9+32);
+ pages = buf + 9 + 38;
+ while (--level > 0)
+ {
+ ptr = pages + cur_page*page_size;
+ entries = GET_SHORT(ptr, 2);
+ ptr += 6;
+ for (i = 0; i < entries; i++)
+ {
+ if (comp(ptr, key, 0, (void **)&newptr) > 0) break;
+ ptr = newptr;
+ }
+ cur_page = GET_USHORT(ptr-2, 0);
+ }
+ ptr = pages + cur_page*page_size;
+ entries = GET_SHORT(ptr, 2);
+ ptr += 8;
+ for (i = 0; i < entries; i++)
+ {
+ ret = comp(ptr, key, 1, (void **)&newptr);
+ if (ret == 0) return ptr;
+ if (ret > 0) return NULL;
+ ptr = newptr;
+ }
+ return NULL;
+}
+
/******************************************************************
* HLPFILE_EnumBTreeLeaves
*
More information about the wine-cvs
mailing list