Changeset 0c8ab5e for messagelist.c


Ignore:
Timestamp:
Jan 23, 2007, 11:55:31 PM (14 years ago)
Author:
Alejandro R. Sedeño <asedeno@mit.edu>
Branches:
master, barnowl_perlaim, debian, 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:
1 edited

Legend:

Unmodified
Added
Removed
  • messagelist.c

    rbd3f232 r0c8ab5e  
    2121}
    2222
    23 owl_message *owl_messagelist_get_by_id(owl_messagelist *ml, int id)
     23owl_message *owl_messagelist_get_by_id(owl_messagelist *ml, int target_id)
    2424{
    2525  /* return the message with id == 'id'.  If it doesn't exist return NULL. */
    26   /* we could make this much more efficient at some point */
    27   int i, j;
     26  int first, last, mid, msg_id;
    2827  owl_message *m;
    2928
    30   j=owl_list_get_size(&(ml->list));
    31   for (i=0; i<j; i++) {
    32     m=owl_list_get_element(&(ml->list), i);
    33     if (owl_message_get_id(m)==id) return(m);
    34 
    35     /* the message id's have to be sequential.  If we've passed the
    36        one we're looking for just bail */
    37     if (owl_message_get_id(m) > id) return(NULL);
     29  first = 0;
     30  last = owl_list_get_size(&(ml->list)) - 1;
     31  while (first <= last) {
     32    mid = (first + last) / 2;
     33    m = owl_list_get_element(&(ml->list), mid);
     34    msg_id = owl_message_get_id(m);
     35    if (msg_id == target_id) {
     36      return(m);
     37    } else if (msg_id < target_id) {
     38      first = mid + 1;
     39    } else {
     40      last = mid - 1;
     41    }
    3842  }
    3943  return(NULL);
Note: See TracChangeset for help on using the changeset viewer.