home *** CD-ROM | disk | FTP | other *** search
/ The Hacker's Encyclopedia 1998 / hackers_encyclopedia.iso / hacking / unix / crackunx.txt / Sources / crack-sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-25  |  5.3 KB  |  215 lines
  1. #include "crack.h"
  2. #define Compare(a,b)     (strcmp(a,b))
  3.  
  4. /*
  5.  * Sort a list of struct DICT by using an iterative bottom-up merge sort.
  6.  * This particular piece of code took me ages to do (well, 2 days + 3 weeks
  7.  * research) and provides a FAST way of sorting a linked list without the
  8.  * overhead of increasing memory usage via malloc() or brk(). Why ? Because I
  9.  * have to assume that there is no more memory, thats why. It's all Brian
  10.  * Thompsett's fault! Really! Filling the swapspace on a SparcStation2 and
  11.  * expecting Crack to survive! Argh! 8-)
  12.  */
  13.  
  14. /* Since this code is so nice, I'll comment it fairly thoroughly */
  15.  
  16. struct DICT *
  17. SortDict (chain3, listlength)
  18.     register struct DICT *chain3;
  19.     long int listlength;
  20. {
  21.     /* misc counters */
  22.     register int i;
  23.     long int discarded;
  24.  
  25.     /* 2^n for n = 0..x */
  26.     long int n;
  27.  
  28.     /* head of the first extracted subchain */
  29.     register struct DICT *chain1;
  30.  
  31.     /* head of second subchain */
  32.     register struct DICT *chain2;
  33.  
  34.     /* useful temp pointer */
  35.     register struct DICT *scratch;
  36.  
  37.     /* PTR TO ELEMENT containing TAIL of unsorted list pre-merging */
  38.     struct DICT *lead_in;
  39.  
  40.     /* PTR TO HEAD of unsorted list after extracting chains */
  41.     struct DICT *lead_out;
  42.  
  43.     /* dummy structures used as fenceposts */
  44.     struct DICT dummy1;
  45.     struct DICT dummy2;
  46.  
  47.     /* Put the incoming list into 'dummy1' posthole */
  48.     dummy1.next = chain3;
  49.  
  50.     /* For values of n = 2^(0..30) limited by listlength */
  51.     for (n = 1L; n < listlength; n *= 2)
  52.     {
  53.     /* Store place to get/put head of list in 'lead_in' */
  54.     lead_in = &dummy1;
  55.  
  56.     /* Set chain1 to the head of unsorted list */
  57.     for (chain1 = lead_in -> next; chain1; chain1 = lead_in -> next)
  58.     {
  59.         /* Break connection head and chain1 */
  60.         lead_in -> next = (struct DICT *) 0;
  61.  
  62.         /* Extract up to length 'n', park on last element before chain2 */
  63.         for (i = n - 1, scratch = chain1;
  64.          i && scratch -> next;
  65.          scratch = scratch -> next)
  66.         {
  67.         i--;
  68.         };
  69.  
  70.         /* If chain1 is undersized/exact, there is no chain2 */
  71.         if (i || !scratch -> next)
  72.         {
  73.         /* put chain1 back where you got it and break */
  74.         lead_in -> next = chain1;
  75.         break;
  76.         }
  77.         /* Get pointer to head of chain2 */
  78.         chain2 = scratch -> next;
  79.  
  80.         /* Break connection between chain1 & chain2 */
  81.         scratch -> next = (struct DICT *) 0;
  82.  
  83.         /* Extract up to length 'n', park on last element of chain2 */
  84.         for (i = n - 1, scratch = chain2;
  85.          i && scratch -> next;
  86.          scratch = scratch -> next)
  87.         {
  88.         i--;
  89.         };
  90.  
  91.         /* Even if it's NULL, store rest of list in 'lead_out' */
  92.         lead_out = scratch -> next;
  93.  
  94.         /* Break connection between chain2 & tail of unsorted list */
  95.         scratch -> next = (struct DICT *) 0;
  96.  
  97.         /* Now, mergesort chain1 & chain2 to chain3 */
  98.  
  99.         /* Set up dummy list fencepost */
  100.         chain3 = &dummy2;
  101.         chain3 -> next = (struct DICT *) 0;
  102.  
  103.         /* While there is something in each list */
  104.         while (chain1 && chain2)
  105.         {
  106.         /* Compare them */
  107.         i = Compare (chain1 -> word, chain2 -> word);
  108.  
  109.         if (i < 0)
  110.         {
  111.             /* a < b */
  112.             chain3 -> next = chain1;
  113.             chain3 = chain1;
  114.             chain1 = chain1 -> next;
  115.         } else if (i > 0)
  116.         {
  117.             /* a > b */
  118.             chain3 -> next = chain2;
  119.             chain3 = chain2;
  120.             chain2 = chain2 -> next;
  121.         } else
  122.         {
  123.             /*
  124.              * a == b. Link them both in. Don't try to get rid of the
  125.              * multiple copies here, because if you free up any
  126.              * elements at this point the listsize changes and the
  127.              * algorithm runs amok.
  128.              */
  129.             chain3 -> next = chain1;
  130.             chain3 = chain1;
  131.             chain1 = chain1 -> next;
  132.             chain3 -> next = chain2;
  133.             chain3 = chain2;
  134.             chain2 = chain2 -> next;
  135.         }
  136.         }
  137.  
  138.         /*
  139.          * Whatever is left is sorted and therefore linkable straight
  140.          * onto the end of the current list.
  141.          */
  142.  
  143.         if (chain1)
  144.         {
  145.         chain3 -> next = chain1;
  146.         } else
  147.         {
  148.         chain3 -> next = chain2;
  149.         }
  150.  
  151.         /* Skip to the end of the sorted list */
  152.         while (chain3 -> next)
  153.         {
  154.         chain3 = chain3 -> next;
  155.         }
  156.  
  157.         /* Append this lot to where you got chain1 from ('lead_in') */
  158.         lead_in -> next = dummy2.next;
  159.  
  160.         /* Append rest of unsorted list to chain3 */
  161.         chain3 -> next = lead_out;
  162.  
  163.         /* Set 'lead_in' for next time to last element of 'chain3' */
  164.         lead_in = chain3;
  165.     }
  166.     }
  167.  
  168.     /* Now, Uniq the list */
  169.     discarded = 0;
  170.  
  171.     /* Chain1 to the head of the list, Chain2 to the next */
  172.     chain1 = dummy1.next;
  173.     chain2 = chain1 -> next;
  174.  
  175.     /* While not at end of list */
  176.     while (chain2)
  177.     {
  178.     /* Whilst (chain1) == (chain2) */
  179.     while (!Compare (chain1 -> word, chain2 -> word))
  180.     {
  181.         /* Bump the discard count */
  182.         discarded++;
  183.  
  184.         /* Store the next element */
  185.         scratch = chain2 -> next;
  186.  
  187.         /* Get some memory back */
  188.         free (chain2);    /* ...<snigger>... */
  189.  
  190.         /* Assign the skip, break if you run off the end of list */
  191.         if (!(chain2 = scratch))
  192.         {
  193.         break;
  194.         }
  195.     }
  196.  
  197.     /* Set comparison ptr to new element or terminate */
  198.     chain1 -> next = chain2;
  199.  
  200.     /* If not terminated */
  201.     if (chain2)
  202.     {
  203.         /* set the compared pointer to its successor */
  204.         chain1 = chain2;
  205.         chain2 = chain2 -> next;
  206.     }
  207.     }
  208.  
  209.     Log ("Sort discarded %ld words; FINAL DICTIONARY SIZE: %ld\n",
  210.      discarded,
  211.      listlength - discarded);
  212.  
  213.     return (dummy1.next);
  214. }
  215.