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