dynamicbox_viewer/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 */