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, 16u);
 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 _pure_ 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         if (!q)
 240                 return 0;
 241
 242         i = find_item(q, data, idx);
 243         if (!i)
 244                 return 0;
 245
 246         remove_item(q, i);
 247         return 1;
 248 }
 249
 250 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
 251         struct prioq_item *i;
 252         unsigned k;
 253
 254         assert(q);
 255
 256         i = find_item(q, data, idx);
 257         if (!i)
 258                 return 0;
 259
 260         k = i - q->items;
 261         k = shuffle_down(q, k);
 262         shuffle_up(q, k);
 263         return 1;
 264 }
 265
 266 void *prioq_peek(Prioq *q) {
 267
 268         if (!q)
 269                 return NULL;
 270
 271         if (q->n_items <= 0)
 272                 return NULL;
 273
 274         return q->items[0].data;
 275 }
 276
 277 void *prioq_pop(Prioq *q) {
 278         void *data;
 279
 280         if (!q)
 281                 return NULL;
 282
 283         if (q->n_items <= 0)
 284                 return NULL;
 285
 286         data = q->items[0].data;
 287         remove_item(q, q->items);
 288         return data;
 289 }
 290
 291 unsigned prioq_size(Prioq *q) {
 292
 293         if (!q)
 294                 return 0;
 295
 296         return q->n_items;
 297
 298 }
 299 bool prioq_isempty(Prioq *q) {
 300
 301         if (!q)
 302                 return true;
 303
 304         return q->n_items <= 0;
 305 }