[427] in BarnOwl Developers
[D-O-H] r558 - trunk/owl
daemon@ATHENA.MIT.EDU (asedeno@MIT.EDU)
Thu Oct 29 18:06:02 2009
Resent-From: nelhage@mit.edu
Resent-To: barnowl-dev-mtg@charon.mit.edu
To: dirty-owl-hackers@mit.edu
From: asedeno@MIT.EDU
Reply-to: dirty-owl-hackers@MIT.EDU
Date: Tue, 23 Jan 2007 23:55:31 -0500 (EST)
Author: asedeno
Date: 2007-01-23 23:55:31 -0500 (Tue, 23 Jan 2007)
New Revision: 558
Modified:
trunk/owl/messagelist.c
Log:
Binary search to find a message with a specific id.
Modified: trunk/owl/messagelist.c
===================================================================
--- trunk/owl/messagelist.c 2007-01-24 04:49:14 UTC (rev 557)
+++ trunk/owl/messagelist.c 2007-01-24 04:55:31 UTC (rev 558)
@@ -20,21 +20,25 @@
return(owl_list_get_element(&(ml->list), n));
}
-owl_message *owl_messagelist_get_by_id(owl_messagelist *ml, int id)
+owl_message *owl_messagelist_get_by_id(owl_messagelist *ml, int target_id)
{
/* return the message with id == 'id'. If it doesn't exist return NULL. */
- /* we could make this much more efficient at some point */
- int i, j;
+ int first, last, mid, msg_id;
owl_message *m;
- j=owl_list_get_size(&(ml->list));
- for (i=0; i<j; i++) {
- m=owl_list_get_element(&(ml->list), i);
- if (owl_message_get_id(m)==id) return(m);
-
- /* the message id's have to be sequential. If we've passed the
- one we're looking for just bail */
- if (owl_message_get_id(m) > id) return(NULL);
+ first = 0;
+ last = owl_list_get_size(&(ml->list)) - 1;
+ while (first <= last) {
+ mid = (first + last) / 2;
+ m = owl_list_get_element(&(ml->list), mid);
+ msg_id = owl_message_get_id(m);
+ if (msg_id == target_id) {
+ return(m);
+ } else if (msg_id < target_id) {
+ first = mid + 1;
+ } else {
+ last = mid - 1;
+ }
}
return(NULL);
}
