diff --git a/glib/gmain.c b/glib/gmain.c
index e04c7b5..001e87e 100644
--- a/glib/gmain.c
+++ b/glib/gmain.c
@@ -134,6 +134,7 @@ struct _GMainContext
 
   guint next_id;
   GSource *source_list;
+  GList *insertion_points; /* List of last source at each priority */
   gint in_check_or_prepare;
 
   GPollRec *poll_records;
@@ -366,6 +367,7 @@ g_main_context_unref (GMainContext *context)
       g_source_destroy_internal (source, context, FALSE);
       source = next;
     }
+  g_assert(context->insertion_points == NULL);
 
 #ifdef G_THREADS_ENABLED  
   g_static_mutex_free (&context->mutex);
@@ -734,31 +736,108 @@ g_source_new (GSourceFuncs *source_funcs,
   return source;
 }
 
+static GList*
+find_insertion_point(GMainContext *context,
+                     int           priority)
+{
+  GList *tmp_list;
+  GList *last_list;
+
+  /* Find last insertion point with <= priority than desired.
+   * We have to go after that point.
+   */
+  last_list = NULL;
+  for (tmp_list = context->insertion_points;
+       tmp_list != NULL;
+       tmp_list = tmp_list->next)
+    {
+      GSource *source = tmp_list->data;
+      if (source->priority > priority)
+        break;
+      last_list = tmp_list;
+    }
+
+  /* If last_list is NULL, then all priorities are higher
+   * than us, so we go at the start of the list.
+   */
+
+  return last_list;
+}
+
 /* Holds context's lock
  */
 static void
 g_source_list_add (GSource      *source,
 		   GMainContext *context)
 {
-  GSource *tmp_source, *last_source;
-  
-  last_source = NULL;
-  tmp_source = context->source_list;
-  while (tmp_source && tmp_source->priority <= source->priority)
+  GList *insertion_point;
+
+  insertion_point = find_insertion_point(context,
+                                         source->priority);
+  if (insertion_point == NULL)
     {
-      last_source = tmp_source;
-      tmp_source = tmp_source->next;
-    }
+      /* All existing sources have a higher priority, so
+       * we have to go before them. There may be no
+       * sources.
+       */
+      source->next = context->source_list;
+      if (context->source_list)
+        context->source_list->prev = source;
+      context->source_list = source;
+
+      /* save a new insertion point for this priority. We
+       * are the lowest priority so we go at the front of
+       * the list.
+       */
+      context->insertion_points = g_list_prepend(context->insertion_points,
+                                                 source);
 
-  source->next = tmp_source;
-  if (tmp_source)
-    tmp_source->prev = source;
-  
-  source->prev = last_source;
-  if (last_source)
-    last_source->next = source;
+    }
   else
-    context->source_list = source;
+    {
+      GSource *prev_source;
+
+      prev_source = insertion_point->data;
+      g_assert(prev_source->priority <= source->priority);
+
+      if (prev_source->priority == source->priority)
+        {
+          /* we become the new insertion point for this priority
+           * (this should be the common case and fortunately
+           * is very fast)
+           */
+          insertion_point->data = source;
+        }
+      else
+        {
+          /* we are higher priority and need to be a new insertion point
+           * for that higher priority, right after the lower-priority
+           * insertion point.
+           */
+          g_assert(prev_source->priority < source->priority);
+
+          /* g_list_insert_before(list, NULL, foo) is O(n)
+           * so we do a little song and dance. There should
+           * be an insert_after() for this reason perhaps.
+           */
+          if (insertion_point->next)
+            {
+              context->insertion_points =
+                g_list_insert_before(context->insertion_points,
+                                     insertion_point->next,
+                                     source);
+            }
+          else
+            {
+              insertion_point->next = g_list_prepend(NULL, source);
+              insertion_point->next->prev = insertion_point;
+            }
+        }
+
+      source->next = prev_source->next;
+      prev_source->next = source;
+      source->prev = prev_source;
+    }
 }
 
 /* Holds context's lock
@@ -767,6 +846,34 @@ static void
 g_source_list_remove (GSource      *source,
 		      GMainContext *context)
 {
+  GList *insertion_point;
+
+  insertion_point = find_insertion_point(context,
+                                         source->priority);
+  /* since source exists, there must be an insertion point
+   * at source->priority
+   */
+  g_assert(insertion_point != NULL);
+
+  if (insertion_point->data == source)
+    {
+      /* if we were the insertion point, we need to replace ourselves
+       * or possibly remove this priority from insertion point list.
+       */
+      /* insertion point is always the last source at a given priority */
+      g_assert(source->next == NULL || source->next->priority > source->priority);
+      if (source->prev && source->prev->priority == source->priority)
+        {
+          insertion_point->data = source->prev;
+        }
+      else
+        {
+          context->insertion_points =
+            g_list_delete_link(context->insertion_points,
+                               insertion_point);
+        }
+    }
+
   if (source->prev)
     source->prev->next = source->next;
   else
