Changeset 0c8ab5e

Timestamp:

Jan 23, 2007, 11:55:31 PM (17 years ago)

Author:

Alejandro R. Sedeño <asedeno@mit.edu>

Branches:

master, barnowl_perlaim, debian, release-1.10, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9

Children:

eeeef20

Parents:

1bdffcb

Message:

Binary search to find a message with a specific id.

File:

• messagelist.c (modified) (1 diff)

messagelist.c

@@ -21 +21 @@
 }
 
-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);