dlist.c

   1 #include <stdlib.h>
   2 #include <unistd.h>
   3 #include <stdio.h>
   4 #include "dlist.h"
   5
   6 static inline struct dlist_entry *dlist_mkentry(void *data) {
   7         struct dlist_entry *le;
   8
   9         if ((le = calloc(1, sizeof(*le))))
  10                 le->data = data;
  11
  12         return le;
  13 }
  14
  15 struct dlist_entry *dlist_create_entry(void *data) {
  16         return dlist_mkentry(data);
  17 }
  18
  19 struct dlist_entry *dlist_insert(struct dlist_entry *list, void *data)
  20 {
  21         struct dlist_entry *le;
  22
  23         if (!(le = dlist_mkentry(data)))
  24                 return NULL;
  25
  26         if (list) {
  27                 if (list->dlist_prev)
  28                         list->dlist_prev->dlist_next = le;
  29                 le->dlist_prev = list->dlist_prev;
  30                 le->dlist_next = list;
  31                 list->dlist_prev = le;
  32         }
  33
  34         return le;
  35 }
  36
  37 struct dlist_entry *dlist_append(struct dlist_entry *list, void *data)
  38 {
  39         struct dlist_entry *le;
  40
  41         if (!list)
  42                 return dlist_insert(list, data);
  43
  44         if (!(le = dlist_mkentry(data)))
  45                 return NULL;
  46
  47         if (list) {
  48                 if (list->dlist_next)
  49                         list->dlist_next->dlist_prev = le;
  50                 le->dlist_next = list->dlist_next;
  51                 le->dlist_prev = list;
  52                 list->dlist_next = le;
  53         }
  54
  55         return le;
  56 }
  57
  58 void *dlist_remove(struct dlist_entry **head, struct dlist_entry *entry)
  59 {
  60         void *data;
  61
  62         if (!entry)
  63                 return NULL;
  64         if (head && *head == entry) {
  65                 *head = entry->dlist_prev ? entry->dlist_prev : entry->dlist_next;
  66         }
  67
  68         if (entry->dlist_prev)
  69                 entry->dlist_prev->dlist_next = entry->dlist_next;
  70         if (entry->dlist_next)
  71                 entry->dlist_next->dlist_prev = entry->dlist_prev;
  72
  73         data = entry->data;
  74         free(entry);
  75
  76         return data;
  77 }
  78
  79 struct dlist_entry *dlist_find(struct dlist_entry *entry, void *data, int (*cmp)(void *, void *, size_t), size_t size) {
  80         struct dlist_entry *it;
  81
  82         if (!entry)
  83                 return NULL;
  84
  85         /* search forwards... */
  86         dlist_foreach(entry, it) {
  87                 if (it->data == data)
  88                         return it;
  89                 if (it->data && data && !cmp(it->data, data, size))
  90                         return it;
  91         }
  92
  93         /* ... and backwards */
  94         dlist_foreach(entry->dlist_prev, it) {
  95                 if (it->data == data)
  96                         return it;
  97                 if (it->data && data && !cmp(it->data, data, size))
  98                         return it;
  99         }
 100
 101         return NULL;
 102 }
 103
 104 struct dlist_entry *dlist_insert_unique(struct dlist_entry *list, void *data, int (*cmp)(void *, void *, size_t), size_t size)
 105 {
 106         if (dlist_find(list, data, cmp, size))
 107                 return NULL;
 108         return dlist_insert(list, data);
 109 }
 110
 111 struct dlist_entry *dlist_append_unique(struct dlist_entry *list, void *data, int (*cmp)(void *, void *, size_t), size_t size)
 112 {
 113         if (dlist_find(list, data, cmp, size))
 114                 return NULL;
 115         return dlist_append(list, data);
 116 }
 117
 118 void dlist_destroy_entry(struct dlist_entry **head, struct dlist_entry *entry, void (*destructor)(void *))
 119 {
 120         void *data;
 121
 122         if (!entry)
 123                 return;
 124
 125         data = dlist_remove(head, entry);
 126         if (data && destructor)
 127                 destructor(data);
 128 }
 129
 130 void dlist_destroy_list(struct dlist_entry **list, void (*destructor)(void *))
 131 {
 132         struct dlist_entry *cur, *next;
 133
 134         if (!list || !*list)
 135                 return;
 136
 137         /*
 138          * Hoisting the if makes this more efficient. I guess gcc
 139          * optimizes poorly in the first pass due to conditionals
 140          * in the _safe macros :-/
 141          */
 142         if (!destructor) {
 143                 dlist_foreach_safe((*list)->dlist_next, cur, next)
 144                 free(cur);
 145                 dlist_foreach_safe_reverse(*list, cur, next)
 146                 free(cur);
 147                 *list = NULL;
 148                 return;
 149         }
 150         dlist_foreach_safe((*list)->dlist_next, cur, next) {
 151                 destructor(cur->data);
 152                 free(cur);
 153         }
 154         dlist_foreach_safe_reverse(*list, cur, next) {
 155                 destructor(cur->data);
 156                 free(cur);
 157         }
 158         *list = NULL;
 159 }