Sort a block of lines

Declare line structure (line)

Structure declaration

Segment Source

  76: /* Lines are held in core as counted strings. */
  77: struct line
  78: {
  79:   char *text;                   /* Text of the line. */
  80:   int length;                   /* Length not including final newline. */
  81:   char *keybeg;                 /* Start of first key. */
  82:   char *keylim;                 /* Limit of first key. */
  83: };
  84: 

Declare lines structure (lines)

Structure declaration

Segment Source

  85: /* Arrays of lines. */
  86: struct lines
  87: {
  88:   struct line *lines;           /* Dynamically allocated array of lines. */
  89:   int used;                     /* Number of slots used. */
  90:   int alloc;                    /* Number of slots allocated. */
  91:   int limit;                    /* Max number of slots to allocate.  */
  92: };
  93: 

Declare sortlines()

Function definition

Notes

The implements a merge sort algorithm. Merge sort is used to ensure that a stable sort can be executed when requested.

Segment Source

1451: /* Sort the array LINES with NLINES members, using TEMP for temporary space. */
1452: 
1453: static void
1454: sortlines (struct line *lines, int nlines, struct line *temp)
1455: {
1456:   register struct line *lo, *hi, *t;
1457:   register int nlo, nhi;
1458: 
1459:   if (nlines == 2)
1460:     {
1461:       if (compare (&lines[0], &lines[1]) > 0)
1462:         *temp = lines[0], lines[0] = lines[1], lines[1] = *temp;
1463:       return;
1464:     }
1465: 
1466:   nlo = nlines / 2;
1467:   lo = lines;
1468:   nhi = nlines - nlo;
1469:   hi = lines + nlo;
1470: 
1471:   if (nlo > 1)
1472:     sortlines (lo, nlo, temp);
1473: 
1474:   if (nhi > 1)
1475:     sortlines (hi, nhi, temp);
1476: 
1477:   t = temp;
1478: 
1479:   while (nlo && nhi)
1480:     if (compare (lo, hi) <= 0)
1481:       *t++ = *lo++, --nlo;
1482:     else
1483:       *t++ = *hi++, --nhi;
1484:   while (nlo--)
1485:     *t++ = *lo++;
1486: 
1487:   for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)
1488:     *lo++ = *t++;
1489: }
1490: