Pileus Git - wmpus/blob - util.c

   1 /*
   2  * Copyright (c) 2011, Andy Spencer <andy753421@gmail.com>
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  */
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <stdarg.h>
  19
  20 #include "util.h"
  21
  22 /* Doubly linked lists */
  23 list_t *list_insert(list_t *next, void *data)
  24 {
  25         list_t *node = new0(list_t);
  26         node->data = data;
  27         node->next = next;
  28         node->prev = next ? next->prev : NULL;
  29         if (node->next) node->next->prev = node;
  30         if (node->prev) node->prev->next = node;
  31         return node;
  32 }
  33
  34 void list_insert_after(list_t *prev, void *data)
  35 {
  36         // prev must be valid,
  37         // as we cannot return the original list head
  38         list_t *node = new0(list_t);
  39         node->data = data;
  40         node->prev = prev;
  41         node->next = prev->next;
  42         prev->next = node;
  43         if (node->next) node->next->prev = node;
  44 }
  45
  46 list_t *list_append(list_t *head, void *data)
  47 {
  48         list_t *last = head;
  49         while (last && last->next)
  50                 last = last->next;
  51         list_t *node = new0(list_t);
  52         node->data = data;
  53         node->prev = last;
  54         if (last) last->next = node;
  55         return last ? head : node;
  56 }
  57
  58 list_t *list_remove(list_t *head, list_t *node, int freedata)
  59 {
  60         list_t *next = node->next;
  61         list_t *prev = node->prev;
  62         if (next) next->prev = prev;
  63         if (prev) prev->next = next;
  64         if (freedata)
  65                 free(node->data);
  66         free(node);
  67         return head == node ? next : head;
  68 }
  69
  70 int list_length(list_t *node)
  71 {
  72         int len = 0;
  73         for (; node; node = node->next)
  74                 len++;
  75         return len;
  76 }
  77
  78 list_t *list_last(list_t *list)
  79 {
  80         while (list && list->next)
  81                 list = list->next;
  82         return list;
  83 }
  84
  85 list_t *list_find(list_t *list, void *data)
  86 {
  87         for (list_t *cur = list; cur; cur = cur->next)
  88                 if (cur->data == data)
  89                         return cur;
  90         return NULL;
  91 }
  92
  93 list_t *list_sort(list_t *list, int rev, int (*func)(void *a, void*b))
  94 {
  95         if (list == NULL || list->next == NULL)
  96                 return list;
  97
  98         /* Split list */
  99         list_t *sides[2] = {NULL, NULL};
 100         for (int i = 0; list; i=(i+1)%2) {
 101                 list_t *head = list;
 102                 list = list->next;
 103                 head->next = sides[i];
 104                 sides[i]   = head;
 105         }
 106
 107         /* Sort sides */
 108         sides[0] = list_sort(sides[0], !rev, func);
 109         sides[1] = list_sort(sides[1], !rev, func);
 110
 111         /* Merge sides */
 112         while (sides[0] || sides[1]) {
 113                 int i = sides[0] == NULL ? 1 :
 114                         sides[1] == NULL ? 0 :
 115                         func(sides[0]->data,
 116                              sides[1]->data) > 0 ? !!rev : !rev;
 117                 list_t *head = sides[i];
 118                 sides[i] = sides[i]->next;
 119                 head->next = list;
 120                 head->prev = NULL;
 121                 if (list)
 122                         list->prev = head;
 123                 list = head;
 124         }
 125         return list;
 126 }
 127
 128 /* Misc */
 129 int str2num(char *str, int def)
 130 {
 131         char *end = NULL;
 132         int num = strtol(str, &end, 10);
 133         return end && *end == '\0' ? num : def;
 134 }
 135
 136 int error(char *fmt, ...)
 137 {
 138         va_list ap;
 139         va_start(ap, fmt);
 140         fprintf(stderr, "Error: ");
 141         vfprintf(stderr, fmt, ap);
 142         fprintf(stderr, "\n");
 143         va_end(ap);
 144         exit(1);
 145         return 0;
 146 }