Use a merge sort from Simon Tatham to sort wireless scans into

alphabetical order.
Based on an initial patch by Simon Long.

diff --git a/src/libdhcpcd/wpa.c b/src/libdhcpcd/wpa.c
index f287c79ce835ca43f96f6a8a3dcb2c1e32be44e5..f73c9418354082b78ec2435dcd37357a6325b3f4 100644 (file)
--- a/src/libdhcpcd/wpa.c
+++ b/src/libdhcpcd/wpa.c
@@ -354,6 +354,107 @@ dhcpcd_wpa_scans_read(DHCPCD_WPA *wpa)
        return wis;
 }
 
        return wis;
 }
 

+/*
+ * This function is copyright 2001 Simon Tatham.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+static DHCPCD_WI_SCAN *
+dhcpcd_wi_scan_sort(DHCPCD_WI_SCAN *list)
+{
+       DHCPCD_WI_SCAN *p, *q, *e, *tail;
+       size_t insize, nmerges, psize, qsize, i;
+
+       /* Silly special case: if `list' was passed in as NULL, return
+        * NULL immediately. */
+       if (!list)
+               return NULL;
+
+       insize = 1;
+
+       for (;;) {
+               p = list;
+               list = tail = NULL;
+               nmerges = 0;  /* count number of merges we do in this pass */
+
+               while (p) {
+                       nmerges++;  /* there exists a merge to be done */
+                       /* step `insize' places along from p */
+                       q = p;
+                       psize = 0;
+                       for (i = 0; i < insize; i++) {
+                               psize++;
+                               q = q->next;
+                               if (!q)
+                                       break;
+                       }
+
+                       /* if q hasn't fallen off end,
+                        * we have two lists to merge */
+                       qsize = insize;
+
+                       /* now we have two lists; merge them */
+                       while (psize > 0 || (qsize > 0 && q)) {
+                               /* decide whether next element of merge comes
+                                * from p or q */
+                               if (psize == 0) {
+                                       /* p is empty; e must come from q. */
+                                       e = q; q = q->next; qsize--;
+                               } else if (qsize == 0 || !q) {
+                                       /* q is empty; e must come from p. */
+                                       e = p; p = p->next; psize--;
+                               } else if (strcasecmp(p->ssid,q->ssid) <= 0) {
+                                       /* First element of p is lower
+                                        * (or same); e must come from p. */
+                                       e = p; p = p->next; psize--;
+                               } else {
+                                       /* First element of q is lower;
+                                        * e must come from q. */
+                                       e = q; q = q->next; qsize--;
+                               }
+
+                               /* add the next element to the merged list */
+                               if (tail)
+                                       tail->next = e;
+                               else
+                                       list = e;
+                               tail = e;
+                       }
+
+                       /* now p has stepped `insize' places along,
+                        * and q has too */
+                       p = q;
+               }
+               tail->next = NULL;
+
+               /* If we have done only one merge, we're finished. */
+               if (nmerges <= 1)   /* allow for nmerges==0, the empty list */
+                       return list;
+
+               /* Otherwise repeat, merging lists twice the size */
+               insize *= 2;
+       }
+}
+

 DHCPCD_WI_SCAN *
 dhcpcd_wi_scans(DHCPCD_IF *i)
 {
 DHCPCD_WI_SCAN *
 dhcpcd_wi_scans(DHCPCD_IF *i)
 {


@@ -366,6 +467,10 @@ dhcpcd_wi_scans(DHCPCD_IF *i)
        if (wpa == NULL)
                return NULL;
        wis = dhcpcd_wpa_scans_read(wpa);
        if (wpa == NULL)
                return NULL;
        wis = dhcpcd_wpa_scans_read(wpa);

+
+       /* Sort the resultant list alphabetically */
+       wis = dhcpcd_wi_scan_sort(wis);
+

        for (w = wis; w; w = w->next) {
                nh = 1;
                hl = NULL;
        for (w = wis; w; w = w->next) {
                nh = 1;
                hl = NULL;