src/dlist.c

   1 /*
   2  * Copyright 2013  Samsung Electronics Co., Ltd
   3  *
   4  * Licensed under the Flora License, Version 1.1 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://floralicense.org/license/
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <assert.h>
  20
  21 #include "dlist.h"
  22
  23 /*!
  24  * \brief
  25  * This dlist is called Modified Doubly Linked List.
  26  *
  27  * Noramlly, The dobule linked list contains address of previous and next element.
  28  * This dlist also contains them, but the tail element only contains prev address.
  29  *
  30  * The head element's prev pointer indicates the last element.
  31  * But the last element's next pointer indicates NIL.
  32  *
  33  * So we can find the last element while crawling this DList
  34  * But we have to remember the address of the head element.
  35  */
  36
  37 struct dlist {
  38         struct dlist *next;
  39         struct dlist *prev;
  40         void *data;
  41 };
  42
  43 struct dlist *dlist_append(struct dlist *list, void *data)
  44 {
  45         struct dlist *item;
  46
  47         item = malloc(sizeof(*item));
  48         if (!item) {
  49                 return NULL;
  50         }
  51
  52         item->next = NULL;
  53         item->data = data;
  54
  55         if (!list) {
  56                 item->prev = item;
  57
  58                 list = item;
  59         } else {
  60                 item->prev = list->prev;
  61                 item->prev->next = item;
  62                 list->prev = item;
  63         }
  64
  65         assert(!list->prev->next && "item NEXT");
  66
  67         return list;
  68 }
  69
  70 struct dlist *dlist_prepend(struct dlist *list, void *data)
  71 {
  72         struct dlist *item;
  73
  74         item = malloc(sizeof(*item));
  75         if (!item) {
  76                 return NULL;
  77         }
  78
  79         item->data = data;
  80
  81         if (!list) {
  82                 item->prev = item;
  83                 item->next = NULL;
  84         } else {
  85                 if (list->prev->next) {
  86                         list->prev->next = item;
  87                 }
  88
  89                 item->prev = list->prev;
  90                 item->next = list;
  91
  92                 list->prev = item;
  93
  94         }
  95
  96         return item;
  97 }
  98
  99 struct dlist *dlist_remove(struct dlist *list, struct dlist *l)
 100 {
 101         if (!list || !l) {
 102                 return NULL;
 103         }
 104
 105         if (l == list) {
 106                 list = l->next;
 107         } else {
 108                 l->prev->next = l->next;
 109         }
 110
 111         if (l->next) {
 112                 l->next->prev = l->prev;
 113         }
 114         /*!
 115          * \note
 116          * If the removed entry 'l' has no next element, it is the last element.
 117          * In this case, check the existence of the list first,
 118          * and if the list is not empty, update the 'prev' of the list (which is a head element of the list)
 119          *
 120          * If we didn't care about this, the head element(list) can indicates the invalid element.
 121          */
 122         else if (list) {
 123                 list->prev = l->prev;
 124         }
 125
 126         free(l);
 127         return list;
 128 }
 129
 130 struct dlist *dlist_find_data(struct dlist *list, void *data)
 131 {
 132         struct dlist *l;
 133         void *_data;
 134
 135         dlist_foreach(list, l, _data) {
 136                 if (data == _data) {
 137                         return l;
 138                 }
 139         }
 140
 141         return NULL;
 142 }
 143
 144 void *dlist_data(struct dlist *l)
 145 {
 146         return l ? l->data : NULL;
 147 }
 148
 149 struct dlist *dlist_next(struct dlist *l)
 150 {
 151         return l ? l->next : NULL;
 152 }
 153
 154 struct dlist *dlist_prev(struct dlist *l)
 155 {
 156         return l ? l->prev : NULL;
 157 }
 158
 159 int dlist_count(struct dlist *l)
 160 {
 161         register int i;
 162         struct dlist *n;
 163         void *data;
 164
 165         i = 0;
 166         dlist_foreach(l, n, data) {
 167                 i++;
 168         }
 169
 170         return i;
 171 }
 172
 173 struct dlist *dlist_nth(struct dlist *l, int nth)
 174 {
 175         register int i;
 176         struct dlist *n;
 177
 178         i = 0;
 179         for (n = l; n; n = n->next) {
 180                 if (i == nth) {
 181                         return n;
 182                 }
 183                 i++;
 184         }
 185
 186         return NULL;
 187 }
 188
 189 /* End of a file */