~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/sys/lists/sort.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**@(#)List sorting (generic)
  2  */
  3 
  4 #include <stdio.h>
  5 #include <tina/sys.h>
  6 #include <tina/sysfuncs.h>
  7 
  8 /* key sorting algorithm */
  9 
 10 void    sort_keys_simple(int *key, float *val, int n)
 11 {
 12     int     i, j;
 13     int     nm1 = n - 1;
 14 
 15     for (i = 0; i < n; ++i)     /* initialise keys */
 16         key[i] = i;
 17 
 18     for (i = 0; i < nm1; ++i)
 19     {
 20         float   minval = val[key[i]];
 21         int     minkey = i;
 22 
 23         for (j = i + 1; j < n; ++j)
 24             if (val[key[j]] < minval)
 25             {
 26                 minkey = j;
 27                 minval = val[key[j]];
 28             }
 29         if (minkey != i)
 30         {
 31             int     temp = key[i];
 32 
 33             key[i] = key[minkey];
 34             key[minkey] = temp;
 35         }
 36     }
 37 }
 38 
 39 List   *sort_list(List * list, double (*valfunc) ( /* ??? */ ), void *data)
 40 {
 41     int     i, n;
 42     float  *val;
 43     int    *key;
 44     List  **listel;
 45     List   *lptr;
 46     List   *sorted;
 47     List   *link_addtostart();
 48 
 49     if (list == NULL)
 50         return (NULL);
 51 
 52     for (lptr = list, n = 0; lptr != NULL; lptr = lptr->next)
 53         ++n;
 54 
 55     val = (float *) ralloc((unsigned) n * sizeof(float));
 56     key = (int *) ralloc((unsigned) n * sizeof(int));
 57     listel = (List **) ralloc((unsigned) n * sizeof(List *));
 58 
 59     for (i = 0, lptr = list; i < n; ++i, lptr = lptr->next)
 60     {
 61         val[i] = (float) valfunc(lptr->to, lptr->type, data);
 62         listel[i] = lptr;
 63     }
 64 
 65     sort_keys_simple(key, val, n);
 66 
 67     sorted = NULL;
 68     for (i = n - 1; i >= 0; --i)
 69         sorted = link_addtostart(sorted, listel[key[i]]);
 70 
 71     rfree((void *) val);
 72     rfree((void *) key);
 73     rfree((void *) listel);
 74     return (sorted);
 75 }
 76 
 77 List *sort_ddlist(List * list, double (*valfunc) ( /* ??? */ ), void *data)
 78 {
 79     int     i, n;
 80     float  *val;
 81     int    *key;
 82     List **listel;
 83     List *lptr;
 84     List *sorted;
 85     List *dd_link_addtostart();
 86 
 87     if (list == NULL)
 88         return (NULL);
 89 
 90     for (lptr = list, n = 0; lptr != NULL; lptr = lptr->next)
 91         ++n;
 92 
 93     val = (float *) ralloc((unsigned) n * sizeof(float));
 94     key = (int *) ralloc((unsigned) n * sizeof(int));
 95     listel = (List **) ralloc((unsigned) n * sizeof(List *));
 96 
 97     for (i = 0, lptr = list; i < n; ++i, lptr = lptr->next)
 98     {
 99         val[i] = (float) valfunc(lptr->to, lptr->type, data);
100         listel[i] = lptr;
101     }
102 
103     sort_keys_simple(key, val, n);
104 
105     sorted = NULL;
106     for (i = n - 1; i >= 0; --i)
107         sorted = dd_link_addtostart(sorted, listel[key[i]]);
108 
109     rfree((void *) val);
110     rfree((void *) key);
111     rfree((void *) listel);
112     return (sorted);
113 }
114 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.