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