src/dlist.c

   1 /*
   2  * Copyright 2012  Samsung Electronics Co., Ltd
   3  *
   4  * Licensed under the Flora License, Version 1.0 (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://www.tizenopensource.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         item->next = NULL;
  52         item->data = data;
  53
  54         if (!list) {
  55                 item->prev = item;
  56
  57                 list = item;
  58         } else {
  59                 item->prev = list->prev;
  60                 item->prev->next = item;
  61                 list->prev = item;
  62         }
  63
  64         assert(!list->prev->next && "item NEXT");
  65
  66         return list;
  67 }
  68
  69 struct dlist *dlist_prepend(struct dlist *list, void *data)
  70 {
  71         struct dlist *item;
  72
  73         item = malloc(sizeof(*item));
  74         if (!item)
  75                 return NULL;
  76
  77         item->data = data;
  78
  79         if (!list) {
  80                 item->prev = item;
  81                 item->next = NULL;
  82         } else {
  83                 if (list->prev->next)
  84                         list->prev->next = item;
  85
  86                 item->prev = list->prev;
  87                 item->next = list;
  88
  89                 list->prev = item;
  90
  91         }
  92
  93         return item;
  94 }
  95
  96 struct dlist *dlist_remove(struct dlist *list, struct dlist *l)
  97 {
  98         if (!list || !l)
  99                 return NULL;
 100
 101         if (l == list)
 102                 list = l->next;
 103         else
 104                 l->prev->next = l->next;
 105
 106         if (l->next)
 107                 l->next->prev = l->prev;
 108         /*!
 109          * \note
 110          * If the removed entry 'l' has no next element, it is the last element.
 111          * In this case, check the existence of the list first,
 112          * and if the list is not empty, update the 'prev' of the list (which is a head element of the list)
 113          *
 114          * If we didn't care about this, the head element(list) can indicates the invalid element.
 115          */
 116         else if (list)
 117                 list->prev = l->prev;
 118
 119         free(l);
 120         return list;
 121 }
 122
 123 struct dlist *dlist_find_data(struct dlist *list, void *data)
 124 {
 125         struct dlist *l;
 126         void *_data;
 127
 128         dlist_foreach(list, l, _data) {
 129                 if (data == _data)
 130                         return l;
 131         }
 132
 133         return NULL;
 134 }
 135
 136 void *dlist_data(struct dlist *l)
 137 {
 138         return l ? l->data : NULL;
 139 }
 140
 141 struct dlist *dlist_next(struct dlist *l)
 142 {
 143         return l ? l->next : NULL;
 144 }
 145
 146 struct dlist *dlist_prev(struct dlist *l)
 147 {
 148         return l ? l->prev : NULL;
 149 }
 150
 151 int dlist_count(struct dlist *l)
 152 {
 153         register int i;
 154         struct dlist *n;
 155         void *data;
 156
 157         i = 0;
 158         dlist_foreach(l, n, data) {
 159                 i++;
 160         }
 161
 162         return i;
 163 }
 164
 165 struct dlist *dlist_nth(struct dlist *l, int nth)
 166 {
 167         register int i;
 168         struct dlist *n;
 169
 170         i = 0;
 171         for (n = l; n; n = n->next) {
 172                 if (i == nth)
 173                         return n;
 174                 i++;
 175         }
 176
 177         return NULL;
 178 }
 179
 180 /* End of a file */