keyword_list.c

   1 #ifndef CGPERF_KEYWORD_LIST_C
   2 #define CGPERF_KEYWORD_LIST_C
   3 #include <stdlib.h>
   4
   5 #include "keyword.h"
   6 #include "keyword_list.h"
   7 /*------------------------------------------------------------------------------------------------*/
   8 #include "namespace/keyword.h"
   9 #include "namespace/keyword_list.h"
  10 /*------------------------------------------------------------------------------------------------*/
  11 /*{{{ kwl_new */
  12 static struct Keyword_List *kwl_new(struct Keyword *kw)
  13 {
  14         struct Keyword_List *t;
  15
  16         t = calloc(1, sizeof(*t));
  17         t->kw = kw;
  18         return t;
  19 }/*}}}*/
  20 /*{{{ kwextl_del */
  21 static void kwl_del(struct Keyword_List *t)
  22 {
  23         free(t);
  24 }/*}}}*/
  25 /*{{{ delete_list */
  26 static void delete_list(struct Keyword_List *list)
  27 {
  28         loop {
  29                 struct Keyword_List *next;
  30
  31                 if (list == 0)
  32                         break;
  33                 next = list->next;
  34                 kwl_del(list);
  35                 list = next;
  36         }
  37 }/*}}}*/
  38 /*{{{ copy_list_ext */
  39 static struct Keyword_List *copy_list(struct Keyword_List *list)
  40 {
  41         struct Keyword_List *result;
  42         struct Keyword_List **lastp;
  43
  44         lastp = &result;
  45         loop {
  46                 struct Keyword_List *new_cons;
  47
  48                 if (list == 0)
  49                         break;
  50                 new_cons = kwl_new(list->kw);
  51                 *lastp = new_cons;
  52                 lastp = &new_cons->next;
  53                 list = list->next;
  54         }
  55         *lastp = 0;
  56         return result;
  57 }/*}}}*/
  58 /*{{{ mergesort_list */
  59 /*
  60  * Sorts a linear list, given a comparison function.
  61  * Note: This uses a variant of mergesort that is *not* a stable sorting algorithm.
  62  */
  63 static struct Keyword_List *mergesort_list(struct Keyword_List *list, bool (*less)(
  64                                                         struct Keyword *kw1, struct Keyword *kw2))
  65 {
  66         struct Keyword_List *middle;
  67         struct Keyword_List *tmp;
  68         struct Keyword_List *right_half;
  69
  70         if (list == 0 || list->next == 0)
  71                 /* List of length 0 or 1. Nothing to do. */
  72                 return list;
  73         middle = list;
  74         tmp = list->next;
  75         loop {
  76                 tmp = tmp->next;
  77                 if (tmp == 0)
  78                         break;
  79                 tmp = tmp->next;
  80                 middle = middle->next;;
  81                 if (tmp == 0)
  82                         break;
  83         }
  84         /*
  85          * Cut the list into two halves.
  86          * If the list has n elements, the left half has ceiling(n/2) elements and the right half
  87          * has floor(n/2) elements.
  88          */
  89         right_half = middle->next;
  90         middle->next = 0;
  91         return merge(mergesort_list(list, less), mergesort_list(right_half, less), less);
  92 }/*}}}*/
  93 /*{{{ merge */
  94 static struct Keyword_List *merge(struct Keyword_List *list1, struct Keyword_List *list2, bool
  95                                         (*less)(struct Keyword *kw1, struct Keyword *kw2))
  96 {
  97         struct Keyword_List *result;
  98         struct Keyword_List **resultp;
  99
 100         resultp = &result;
 101         loop {
 102                 if (list1 == 0) {
 103                         *resultp = list2;
 104                         break;
 105                 }
 106                 if (list2 == 0) {
 107                         *resultp = list1;
 108                         break;
 109                 }
 110                 if (less(list2->kw, list1->kw)) {
 111                         *resultp = list2;
 112                         resultp = &list2->next;
 113                         /*
 114                          * We would have a stable sorting if the next line would read: list2 =
 115                          * *resultp;
 116                          */
 117                         list2 = list1;
 118                         list2 = *resultp;
 119                 } else {
 120                         *resultp = list1;
 121                         resultp = &list1->next;
 122                         list1 = *resultp;
 123                 }
 124         }
 125         return result;
 126 }/*}}}*/
 127 /*------------------------------------------------------------------------------------------------*/
 128 #define EPILOG
 129 #include "namespace/keyword.h"
 130 #include "namespace/keyword_list.h"
 131 #undef EPILOG
 132 /*------------------------------------------------------------------------------------------------*/
 133 #endif