src/shared/prioq.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include "util.h"
  23 #include "prioq.h"
  24
  25 struct prioq_item {
  26         void *data;
  27         unsigned *idx;
  28 };
  29
  30 struct Prioq {
  31         compare_func_t compare_func;
  32         unsigned n_items, n_allocated;
  33
  34         struct prioq_item *items;
  35 };
  36
  37 Prioq *prioq_new(compare_func_t compare_func) {
  38         Prioq *q;
  39
  40         q = new0(Prioq, 1);
  41         if (!q)
  42                 return q;
  43
  44         q->compare_func = compare_func;
  45         return q;
  46 }
  47
  48 void prioq_free(Prioq *q) {
  49         if (!q)
  50                 return;
  51
  52         free(q->items);
  53         free(q);
  54 }
  55
  56 static void swap(Prioq *q, unsigned j, unsigned k) {
  57         void *saved_data;
  58         unsigned *saved_idx;
  59
  60         assert(q);
  61         assert(j < q->n_items);
  62         assert(k < q->n_items);
  63
  64         assert(!q->items[j].idx || *(q->items[j].idx) == j);
  65         assert(!q->items[k].idx || *(q->items[k].idx) == k);
  66
  67         saved_data = q->items[j].data;
  68         saved_idx = q->items[j].idx;
  69         q->items[j].data = q->items[k].data;
  70         q->items[j].idx = q->items[k].idx;
  71         q->items[k].data = saved_data;
  72         q->items[k].idx = saved_idx;
  73
  74         if (q->items[j].idx)
  75                 *q->items[j].idx = j;
  76
  77         if (q->items[k].idx)
  78                 *q->items[k].idx = k;
  79 }
  80
  81 static unsigned shuffle_up(Prioq *q, unsigned idx) {
  82         assert(q);
  83
  84         while (idx > 0) {
  85                 unsigned k;
  86
  87                 k = (idx-1)/2;
  88
  89                 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
  90                         break;
  91
  92                 swap(q, idx, k);
  93                 idx = k;
  94         }
  95
  96         return idx;
  97 }
  98
  99 static unsigned shuffle_down(Prioq *q, unsigned idx) {
 100         assert(q);
 101
 102         for (;;) {
 103                 unsigned j, k, s;
 104
 105                 k = (idx+1)*2; /* right child */
 106                 j = k-1;       /* left child */
 107
 108                 if (j >= q->n_items)
 109                         break;
 110
 111                 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
 112
 113                         /* So our left child is smaller than we are, let's
 114                          * remember this fact */
 115                         s = j;
 116                 else
 117                         s = idx;
 118
 119                 if (k < q->n_items &&
 120                     q->compare_func(q->items[k].data, q->items[s].data) < 0)
 121
 122                         /* So our right child is smaller than we are, let's
 123                          * remember this fact */
 124                         s = k;
 125
 126                 /* s now points to the smallest of the three items */
 127
 128                 if (s == idx)
 129                         /* No swap necessary, we're done */
 130                         break;
 131
 132                 swap(q, idx, s);
 133                 idx = s;
 134         }
 135
 136         return idx;
 137 }
 138
 139 int prioq_put(Prioq *q, void *data, unsigned *idx) {
 140         struct prioq_item *i;
 141         unsigned k;
 142
 143         assert(q);
 144
 145         if (q->n_items >= q->n_allocated) {
 146                 unsigned n;
 147                 struct prioq_item *j;
 148
 149                 n = MAX((q->n_items+1) * 2, 16);
 150                 j = realloc(q->items, sizeof(struct prioq_item) * n);
 151                 if (!j)
 152                         return -ENOMEM;
 153
 154                 q->items = j;
 155                 q->n_allocated = n;
 156         }
 157
 158         k = q->n_items++;
 159         i = q->items + k;
 160         i->data = data;
 161         i->idx = idx;
 162
 163         if (idx)
 164                 *idx = k;
 165
 166         shuffle_up(q, k);
 167
 168         return 0;
 169 }
 170
 171 static void remove_item(Prioq *q, struct prioq_item *i) {
 172         struct prioq_item *l;
 173
 174         assert(q);
 175         assert(i);
 176
 177         l = q->items + q->n_items - 1;
 178
 179         if (i == l)
 180                 /* Last entry, let's just remove it */
 181                 q->n_items--;
 182         else {
 183                 unsigned k;
 184
 185                 /* Not last entry, let's replace the last entry with
 186                  * this one, and reshuffle */
 187
 188                 k = i - q->items;
 189
 190                 i->data = l->data;
 191                 i->idx = l->idx;
 192                 if (i->idx)
 193                         *i->idx = k;
 194                 q->n_items--;
 195
 196                 k = shuffle_down(q, k);
 197                 shuffle_up(q, k);
 198         }
 199 }
 200
 201 static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
 202         struct prioq_item *i;
 203
 204         assert(q);
 205
 206         if (idx) {
 207                 assert(*idx < q->n_items);
 208                 i = q->items + *idx;
 209                 assert(i->data == data);
 210
 211                 return i;
 212         } else {
 213                 for (i = q->items; i < q->items + q->n_items; i++)
 214                         if (i->data == data)
 215                                 return i;
 216                 return NULL;
 217         }
 218 }
 219
 220 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
 221         struct prioq_item *i;
 222
 223         assert(q);
 224
 225         i = find_item(q, data, idx);
 226         if (!i)
 227                 return 0;
 228
 229         remove_item(q, i);
 230         return 1;
 231 }
 232
 233 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
 234         struct prioq_item *i;
 235         unsigned k;
 236
 237         assert(q);
 238
 239         i = find_item(q, data, idx);
 240         if (!i)
 241                 return 0;
 242
 243         k = i - q->items;
 244         k = shuffle_down(q, k);
 245         shuffle_up(q, k);
 246         return 1;
 247 }
 248
 249 void *prioq_peek(Prioq *q) {
 250         assert(q);
 251
 252         if (q->n_items <= 0)
 253                 return NULL;
 254
 255         return q->items[0].data;
 256 }
 257
 258 void *prioq_pop(Prioq *q) {
 259         void *data;
 260
 261         assert(q);
 262
 263         if (q->n_items <= 0)
 264                 return NULL;
 265
 266         data = q->items[0].data;
 267         remove_item(q, q->items);
 268         return data;
 269 }
 270
 271 unsigned prioq_size(Prioq *q) {
 272         assert(q);
 273
 274         return q->n_items;
 275
 276 }
 277 bool prioq_isempty(Prioq *q) {
 278         assert(q);
 279
 280         return q->n_items <= 0;
 281 }