Mercurial > hg > xmms-sid

comparison src/xs_length.c @ 509:81756f412b43

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Changes based on patch from Heikki 'shd' Orsila: Fix a crash on 64-bit big-endian platforms due to inproper mixing of guint and size_t types; Use bsearch() instead of my own implementation of binary search in xs_length.c and xs_stil.c; Remove useless(?) use of feof().
author Matti Hamalainen <ccr@tnsp.org>
date Sun, 28 Jan 2007 15:09:04 +0000
parents c67a7f2fd586
children 20cb21c4cb3c
comparison
equal deleted inserted replaced
508:338332aeb5a4 509:81756f412b43
206 } 206 }
207 207
208 /* Read and parse the data */ 208 /* Read and parse the data */
209 lineNum = 0; 209 lineNum = 0;
210 210
211 while (!feof(inFile) && fgets(inLine, XS_BUF_SIZE, inFile)) { 211 while (fgets(inLine, XS_BUF_SIZE, inFile) != NULL) {
212 size_t linePos; 212 size_t linePos;
213 inLine[XS_BUF_SIZE - 1] = 0;
214 linePos = 0; 213 linePos = 0;
215 lineNum++; 214 lineNum++;
216 215
217 xs_findnext(inLine, &linePos); 216 xs_findnext(inLine, &linePos);
218 217
263 262
264 return d; 263 return d;
265 } 264 }
266 265
267 266
268 /* Get node from db index via binary search
269 */
270 static t_xs_sldb_node *xs_sldb_get_node(t_xs_sldb * db, t_xs_md5hash pHash)
271 {
272 gint iStartNode, iEndNode, iQNode, r, i;
273 gboolean iFound;
274 t_xs_sldb_node *pResult;
275
276 /* Check the database pointers */
277 if (!db || !db->pNodes || !db->ppIndex)
278 return NULL;
279
280 /* Look-up via index using binary search */
281 pResult = NULL;
282 iStartNode = 0;
283 iEndNode = (db->n - 1);
284 iQNode = (iEndNode / 2);
285 iFound = FALSE;
286
287 while ((!iFound) && ((iEndNode - iStartNode) > XS_BIN_BAILOUT)) {
288 r = xs_sldb_cmphash(pHash, db->ppIndex[iQNode]->md5Hash);
289 if (r < 0) {
290 /* Hash was in the <- LEFT side */
291 iEndNode = iQNode;
292 iQNode = iStartNode + ((iEndNode - iStartNode) / 2);
293 } else if (r > 0) {
294 /* Hash was in the RIGHT -> side */
295 iStartNode = iQNode;
296 iQNode = iStartNode + ((iEndNode - iStartNode) / 2);
297 } else
298 iFound = TRUE;
299 }
300
301 /* If not found already */
302 if (!iFound) {
303 /* Search the are linearly */
304 iFound = FALSE;
305 i = iStartNode;
306 while ((i <= iEndNode) && (!iFound)) {
307 if (xs_sldb_cmphash(pHash, db->ppIndex[i]->md5Hash) == 0)
308 iFound = TRUE;
309 else
310 i++;
311 }
312
313 /* Check the result */
314 if (iFound)
315 pResult = db->ppIndex[i];
316
317 } else {
318 /* Found via binary search */
319 pResult = db->ppIndex[iQNode];
320 }
321
322 return pResult;
323 }
324
325
326 /* Compare two nodes 267 /* Compare two nodes
327 */ 268 */
328 static gint xs_sldb_cmp(const void *pNode1, const void *pNode2) 269 static gint xs_sldb_cmp(const void *pNode1, const void *pNode2)
329 { 270 {
330 /* We assume here that we never ever get NULL-pointers or similar */ 271 /* We assume here that we never ever get NULL-pointers or similar */
337 /* (Re)create index 278 /* (Re)create index
338 */ 279 */
339 gint xs_sldb_index(t_xs_sldb * db) 280 gint xs_sldb_index(t_xs_sldb * db)
340 { 281 {
341 t_xs_sldb_node *pCurr; 282 t_xs_sldb_node *pCurr;
342 gint i; 283 size_t i;
343 assert(db); 284 assert(db);
344 285
345 /* Free old index */ 286 /* Free old index */
346 if (db->ppIndex) { 287 if (db->ppIndex) {
347 g_free(db->ppIndex); 288 g_free(db->ppIndex);
548 489
549 return 0; 490 return 0;
550 } 491 }
551 492
552 493
553 /* Get song lengths 494 /* Get node from db index via binary search
554 */ 495 */
555 t_xs_sldb_node *xs_sldb_get(t_xs_sldb *db, const gchar *pcFilename) 496 t_xs_sldb_node *xs_sldb_get(t_xs_sldb *db, const gchar *pcFilename)
556 { 497 {
557 t_xs_sldb_node *pResult; 498 t_xs_sldb_node keyItem, *key, **item;
558 t_xs_md5hash dbHash; 499
500 /* Check the database pointers */
501 if (!db || !db->pNodes || !db->ppIndex)
502 return NULL;
559 503
560 /* Get the hash and then look up from db */ 504 /* Get the hash and then look up from db */
561 if (xs_get_sid_hash(pcFilename, dbHash) == 0) 505 if (xs_get_sid_hash(pcFilename, keyItem.md5Hash) == 0) {
562 pResult = xs_sldb_get_node(db, dbHash); 506 key = &keyItem;
563 else 507 item = bsearch(&key, db->ppIndex, db->n,
564 pResult = NULL; 508 sizeof(db->ppIndex[0]), xs_sldb_cmp);
565 509
566 return pResult; 510 if (item)
567 } 511 return *item;
512 else
513 return NULL;
514 } else
515 return NULL;
516 }
517
518