list.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3
   4
   5 #include <list.h>
   6
   7 list* freelist = NULL;
   8
   9
  10 list* make_new(list* next, void* item){
  11         list* ptr;
  12
  13         if(freelist == NULL){
  14                 ptr = malloc(sizeof(struct list));
  15         }
  16         else{
  17                 ptr = freelist;
  18                 freelist = ptr->next;
  19         }
  20
  21         ptr->next = next;
  22         ptr->item = item;
  23         return ptr;
  24 }
  25
  26 void remove_from_list(list* prev, list* node){
  27         prev->next = node->next;
  28         node->item = NULL;
  29         node->next = freelist;
  30         freelist = node;
  31 }
  32
  33
  34 list* empty(){
  35         return make_new(NULL, NULL);
  36 }
  37
  38 void push(list* L, void* item){
  39         list* ptr = make_new(L->next, item);
  40         L->next = ptr;
  41 }
  42
  43 void* pop(list* L){
  44         if(L->next){
  45                 void* item = L->next->item;
  46                 remove_from_list(L, L->next);
  47                 return item;
  48         }
  49         else{
  50                 return NULL;
  51         }
  52 }
  53
  54 void append(list* L, void* item){
  55         list* ptr = L;
  56         while(ptr->next){
  57                 ptr = ptr->next;
  58         }
  59         ptr->next = make_new(NULL, item);
  60 }
  61
  62 void recycle(list* L){
  63         list* ptr = L;
  64         while(ptr->next){
  65                 ptr->next->item = NULL;
  66                 ptr = ptr->next;
  67         }
  68         ptr->next = freelist;
  69         freelist = L;
  70 }
  71
  72 int length(list* L){
  73         list* ptr = L->next;
  74         int c = 0;
  75         while(ptr){
  76                 c += 1;
  77                 ptr = ptr->next;
  78         }
  79         return c;
  80 }
  81
  82
  83 /* merge sort */
  84 static void split(list* L, list** left, list** right){
  85         list* ptr = L;
  86         int c = 0;
  87
  88         if(L == NULL){
  89                 *left = NULL;
  90                 *right = NULL;
  91         }
  92
  93         while(ptr){
  94                 c++;
  95                 ptr = ptr->next;
  96         }
  97
  98         ptr = L;
  99         c /= 2;
 100         c -= 1;
 101         while(c > 0){
 102                 c--;
 103                 ptr = ptr->next;
 104         }
 105
 106         *left = L;
 107         *right = ptr->next;
 108         ptr->next = NULL;
 109 }
 110
 111 static list* merge(list* left, list* right, compare_func cmp){
 112         /* merges right into left */
 113         list* tmp;
 114         list* ptr;
 115
 116         if(left == NULL) return right;
 117
 118         if(right && cmp(right->item, left->item) > 0){
 119                 tmp = right;
 120                 right = right->next;
 121                 tmp->next = left;
 122                 left = tmp;
 123         }
 124
 125         ptr = left;
 126         while(right && ptr->next){
 127                 if(cmp(right->item, ptr->next->item) > 0){
 128                         tmp = right;
 129                         right = right->next;
 130                         tmp->next = ptr->next;
 131                         ptr->next = tmp;
 132                         ptr = ptr->next;
 133                 }
 134                 else{
 135                         ptr = ptr->next;
 136                 }
 137         }
 138
 139         if(ptr->next == NULL)
 140                 ptr->next = right;
 141
 142         return left;
 143 }
 144
 145 static list* merge_sort(list* L, compare_func cmp){
 146         list* left;
 147         list* right;
 148
 149         if(L == NULL) return NULL;
 150         if(L->next == NULL) return L;
 151
 152         split(L, &left, &right);
 153
 154         return merge(
 155                 merge_sort(left, cmp),
 156                 merge_sort(right, cmp),
 157                 cmp
 158         );
 159 }
 160
 161 void sort(list* L, compare_func cmp){
 162         L->next = merge_sort(L->next, cmp);
 163 }
 164 /* end merge sort */
 165
 166
 167 void print_list(list* L, void (*print)(void* item)){
 168         list* ptr = L->next;
 169         printf("(");
 170         while(ptr){
 171                 print(ptr->item);
 172                 if(ptr->next)
 173                         printf(", ");
 174                 ptr = ptr->next;
 175         }
 176         printf(")");
 177 }
 178
 179 void println_list(list* L, void (*print)(void* item)){
 180         print_list(L, print);
 181         printf("\n");
 182 }
 183
 184 void list_print_free(){
 185         list* ptr = freelist;
 186         printf("(");
 187         while(ptr){
 188                 printf("_");
 189                 if(ptr->next){
 190                         printf(", ");
 191                 }
 192                 ptr = ptr->next;
 193         }
 194         printf(")\n");
 195 }
 196
 197 void print(void* item){
 198         char* s = item;
 199         printf("%s", s);
 200 }
 201