libopkg/void_list.c

   1 /* void_list.c - the opkg package management system
   2
   3    Carl D. Worth
   4
   5    Copyright (C) 2001 University of Southern California
   6
   7    This program is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU General Public License as
   9    published by the Free Software Foundation; either version 2, or (at
  10    your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16 */
  17
  18 #include "includes.h"
  19 #include <errno.h>
  20
  21 #include "void_list.h"
  22
  23 int void_list_elt_init(void_list_elt_t *elt, void *data)
  24 {
  25     elt->next = NULL;
  26     elt->data = data;
  27
  28     return 0;
  29 }
  30
  31 void void_list_elt_deinit(void_list_elt_t *elt)
  32 {
  33     void_list_elt_init(elt, NULL);
  34 }
  35
  36 int void_list_init(void_list_t *list)
  37 {
  38     void_list_elt_init(&list->pre_head, NULL);
  39     list->head = NULL;
  40     list->pre_head.next = list->head;
  41     list->tail = NULL;
  42
  43     return 0;
  44 }
  45
  46 void void_list_deinit(void_list_t *list)
  47 {
  48     void_list_elt_t *elt;
  49
  50     while (list->head) {
  51         elt = void_list_pop(list);
  52         void_list_elt_deinit(elt);
  53         /* malloced in void_list_append */
  54         free(elt);
  55     }
  56 }
  57
  58 int void_list_append(void_list_t *list, void *data)
  59 {
  60     void_list_elt_t *elt;
  61
  62     /* freed in void_list_deinit */
  63     elt = calloc(1, sizeof(void_list_elt_t));
  64     if (elt == NULL) {
  65         fprintf(stderr, "%s: out of memory\n", __FUNCTION__);
  66         return ENOMEM;
  67     }
  68
  69     void_list_elt_init(elt, data);
  70
  71     if (list->tail) {
  72         list->tail->next = elt;
  73         list->tail = elt;
  74     } else {
  75         list->head = elt;
  76         list->pre_head.next = list->head;
  77         list->tail = elt;
  78     }
  79
  80     return 0;
  81 }
  82
  83 int void_list_push(void_list_t *list, void *data)
  84 {
  85     void_list_elt_t *elt;
  86
  87     elt = calloc(1, sizeof(void_list_elt_t));
  88     if (elt == NULL) {
  89         fprintf(stderr, "%s: out of memory\n", __FUNCTION__);
  90         return ENOMEM;
  91     }
  92
  93     void_list_elt_init(elt, data);
  94
  95     elt->next = list->head;
  96     list->head->next = elt;
  97     if (list->tail == NULL) {
  98         list->tail = list->head;
  99     }
 100
 101     return 0;
 102 }
 103
 104 void_list_elt_t *void_list_pop(void_list_t *list)
 105 {
 106     void_list_elt_t *elt;
 107
 108     elt = list->head;
 109
 110     if (list->head) {
 111         list->head = list->head->next;
 112         list->pre_head.next = list->head;
 113         if (list->head == NULL) {
 114             list->tail = NULL;
 115         }
 116     }
 117
 118     return elt;
 119 }
 120
 121 void *void_list_remove(void_list_t *list, void_list_elt_t **iter)
 122 {
 123     void_list_elt_t *prior;
 124     void_list_elt_t *old_elt;
 125     void *old_data;
 126
 127     old_elt = *iter;
 128     old_data = old_elt->data;
 129
 130     if (old_elt == list->head) {
 131         prior = &list->pre_head;
 132         void_list_pop(list);
 133     } else {
 134         for (prior = list->head; prior; prior = prior->next) {
 135             if (prior->next == old_elt) {
 136                 break;
 137             }
 138         }
 139         if (prior == NULL || prior->next != old_elt) {
 140             fprintf(stderr, "%s: ERROR: element not found in list\n", __FUNCTION__);
 141             return NULL;
 142         }
 143         prior->next = old_elt->next;
 144
 145         if (old_elt == list->tail) {
 146             list->tail = prior;
 147         }
 148     }
 149
 150     void_list_elt_deinit(old_elt);
 151     *iter = prior;
 152
 153     return old_data;
 154 }
 155
 156 /* remove element containing elt data, using cmp(elt->data, target_data) == 0. */
 157 void *void_list_remove_elt(void_list_t *list, const void *target_data, void_list_cmp_t cmp)
 158 {
 159      void_list_elt_t *prior;
 160      void_list_elt_t *old_elt = NULL;
 161      void *old_data = NULL;
 162
 163      if (!list) {
 164           fprintf(stderr, "Error: void_list_remove_elt list is NULL\n");
 165           return NULL;
 166      }
 167      if (!target_data) {
 168           fprintf(stderr, "Error: void_list_remove_elt target_data is NULL\n");
 169           return NULL;
 170      }
 171
 172      /* first element */
 173      if (list->head && list->head->data && (cmp(list->head->data, target_data) == 0)) {
 174           old_elt = list->head;
 175           old_data = list->head->data;
 176           void_list_pop(list);
 177      } else {
 178           int found = 0;
 179           for (prior = list->head; prior && prior->next; prior = prior->next) {
 180                if (prior->next->data && (cmp(prior->next->data, target_data) == 0)) {
 181                     old_elt = prior->next;
 182                     old_data = old_elt->data;
 183                     found = 1;
 184                     break;
 185                }
 186           }
 187           if (!found) {
 188                return NULL;
 189           }
 190           prior->next = old_elt->next;
 191
 192           if (old_elt == list->tail) {
 193                list->tail = prior;
 194           }
 195      }
 196      if (old_elt)
 197           void_list_elt_deinit(old_elt);
 198
 199      if (old_data)
 200           return old_data;
 201      else
 202           return NULL;
 203 }