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 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
  57         assert(q);
  58
  59         if (*q)
  60                 return 0;
  61
  62         *q = prioq_new(compare_func);
  63         if (!*q)
  64                 return -ENOMEM;
  65
  66         return 0;
  67 }
  68
  69 static void swap(Prioq *q, unsigned j, unsigned k) {
  70         void *saved_data;
  71         unsigned *saved_idx;
  72
  73         assert(q);
  74         assert(j < q->n_items);
  75         assert(k < q->n_items);
  76
  77         assert(!q->items[j].idx || *(q->items[j].idx) == j);
  78         assert(!q->items[k].idx || *(q->items[k].idx) == k);
  79
  80         saved_data = q->items[j].data;
  81         saved_idx = q->items[j].idx;
  82         q->items[j].data = q->items[k].data;
  83         q->items[j].idx = q->items[k].idx;
  84         q->items[k].data = saved_data;
  85         q->items[k].idx = saved_idx;
  86
  87         if (q->items[j].idx)
  88                 *q->items[j].idx = j;
  89
  90         if (q->items[k].idx)
  91                 *q->items[k].idx = k;
  92 }
  93
  94 static unsigned shuffle_up(Prioq *q, unsigned idx) {
  95         assert(q);
  96
  97         while (idx > 0) {
  98                 unsigned k;
  99
 100                 k = (idx-1)/2;
 101
 102                 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
 103                         break;
 104
 105                 swap(q, idx, k);
 106                 idx = k;
 107         }
 108
 109         return idx;
 110 }
 111
 112 static unsigned shuffle_down(Prioq *q, unsigned idx) {
 113         assert(q);
 114
 115         for (;;) {
 116                 unsigned j, k, s;
 117
 118                 k = (idx+1)*2; /* right child */
 119                 j = k-1;       /* left child */
 120
 121                 if (j >= q->n_items)
 122                         break;
 123
 124                 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
 125
 126                         /* So our left child is smaller than we are, let's
 127                          * remember this fact */
 128                         s = j;
 129                 else
 130                         s = idx;
 131
 132                 if (k < q->n_items &&
 133                     q->compare_func(q->items[k].data, q->items[s].data) < 0)
 134
 135                         /* So our right child is smaller than we are, let's
 136                          * remember this fact */
 137                         s = k;
 138
 139                 /* s now points to the smallest of the three items */
 140
 141                 if (s == idx)
 142                         /* No swap necessary, we're done */
 143                         break;
 144
 145                 swap(q, idx, s);
 146                 idx = s;
 147         }
 148
 149         return idx;
 150 }
 151
 152 int prioq_put(Prioq *q, void *data, unsigned *idx) {
 153         struct prioq_item *i;
 154         unsigned k;
 155
 156         assert(q);
 157
 158         if (q->n_items >= q->n_allocated) {
 159                 unsigned n;
 160                 struct prioq_item *j;
 161
 162                 n = MAX((q->n_items+1) * 2, 16);
 163                 j = realloc(q->items, sizeof(struct prioq_item) * n);
 164                 if (!j)
 165                         return -ENOMEM;
 166
 167                 q->items = j;
 168                 q->n_allocated = n;
 169         }
 170
 171         k = q->n_items++;
 172         i = q->items + k;
 173         i->data = data;
 174         i->idx = idx;
 175
 176         if (idx)
 177                 *idx = k;
 178
 179         shuffle_up(q, k);
 180
 181         return 0;
 182 }
 183
 184 static void remove_item(Prioq *q, struct prioq_item *i) {
 185         struct prioq_item *l;
 186
 187         assert(q);
 188         assert(i);
 189
 190         l = q->items + q->n_items - 1;
 191
 192         if (i == l)
 193                 /* Last entry, let's just remove it */
 194                 q->n_items--;
 195         else {
 196                 unsigned k;
 197
 198                 /* Not last entry, let's replace the last entry with
 199                  * this one, and reshuffle */
 200
 201                 k = i - q->items;
 202
 203                 i->data = l->data;
 204                 i->idx = l->idx;
 205                 if (i->idx)
 206                         *i->idx = k;
 207                 q->n_items--;
 208
 209                 k = shuffle_down(q, k);
 210                 shuffle_up(q, k);
 211         }
 212 }
 213
 214 static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
 215         struct prioq_item *i;
 216
 217         assert(q);
 218
 219         if (idx) {
 220                 if (*idx > q->n_items)
 221                         return NULL;
 222
 223                 i = q->items + *idx;
 224                 if (i->data != data)
 225                         return NULL;
 226
 227                 return i;
 228         } else {
 229                 for (i = q->items; i < q->items + q->n_items; i++)
 230                         if (i->data == data)
 231                                 return i;
 232                 return NULL;
 233         }
 234 }
 235
 236 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
 237         struct prioq_item *i;
 238
 239         assert(q);
 240
 241         i = find_item(q, data, idx);
 242         if (!i)
 243                 return 0;
 244
 245         remove_item(q, i);
 246         return 1;
 247 }
 248
 249 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
 250         struct prioq_item *i;
 251         unsigned k;
 252
 253         assert(q);
 254
 255         i = find_item(q, data, idx);
 256         if (!i)
 257                 return 0;
 258
 259         k = i - q->items;
 260         k = shuffle_down(q, k);
 261         shuffle_up(q, k);
 262         return 1;
 263 }
 264
 265 void *prioq_peek(Prioq *q) {
 266         assert(q);
 267
 268         if (q->n_items <= 0)
 269                 return NULL;
 270
 271         return q->items[0].data;
 272 }
 273
 274 void *prioq_pop(Prioq *q) {
 275         void *data;
 276
 277         assert(q);
 278
 279         if (q->n_items <= 0)
 280                 return NULL;
 281
 282         data = q->items[0].data;
 283         remove_item(q, q->items);
 284         return data;
 285 }
 286
 287 unsigned prioq_size(Prioq *q) {
 288         assert(q);
 289
 290         return q->n_items;
 291
 292 }
 293 bool prioq_isempty(Prioq *q) {
 294         assert(q);
 295
 296         return q->n_items <= 0;
 297 }