src/pulsecore/prioq.c

   1 /***
   2   This file is part of PulseAudio.
   3
   4   Copyright 2008 Lennart Poettering
   5
   6   PulseAudio is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU Lesser General Public License as published
   8   by the Free Software Foundation; either version 2.1 of the License,
   9   or (at your option) any later version.
  10
  11   PulseAudio is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public License
  17   along with PulseAudio; if not, write to the Free Software
  18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  19   USA.
  20 ***/
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <pulse/xmalloc.h>
  27
  28 #include <pulsecore/flist.h>
  29
  30 #include "prioq.h"
  31
  32 struct pa_prioq_item {
  33     void *value;
  34     unsigned idx;
  35 };
  36
  37 struct pa_prioq {
  38     pa_prioq_item **items;
  39     unsigned n_items;
  40     unsigned n_allocated;
  41     pa_compare_func_t compare_func;
  42 };
  43
  44 PA_STATIC_FLIST_DECLARE(items, 0, pa_xfree);
  45
  46 pa_prioq *pa_prioq_new(pa_compare_func_t compare_func) {
  47
  48     pa_prioq *q;
  49
  50     q = pa_xnew(pa_prioq, 1);
  51     q->compare_func = compare_func;
  52     q->n_items = 0;
  53     q->n_allocated = 64;
  54     q->items = pa_xnew(pa_prioq_item*, q->n_allocated);
  55
  56     return q;
  57 }
  58
  59 void pa_prioq_free(pa_prioq *q, pa_free2_cb_t free_cb, void *userdata) {
  60     pa_prioq_item **i, **e;
  61
  62     pa_assert(q);
  63
  64     for (i = q->items, e = q->items + q->n_items; i < e; i++) {
  65
  66         if (!*i)
  67             continue;
  68
  69         if (free_cb)
  70             free_cb((*i)->value, userdata);
  71
  72         pa_xfree(*i);
  73     }
  74
  75     pa_xfree(q->items);
  76     pa_xfree(q);
  77 }
  78
  79 static void shuffle_up(pa_prioq *q, pa_prioq_item *i) {
  80     unsigned j;
  81
  82     pa_assert(q);
  83     pa_assert(i);
  84
  85     j = i->idx;
  86
  87     while (j > 0) {
  88         unsigned k;
  89
  90         k = (j-1)/2;
  91
  92         if (q->compare_func(q->items[k]->value, i->value) < 0)
  93             break;
  94
  95         q->items[k]->idx = j;
  96         q->items[j] = q->items[k];
  97
  98         j = k;
  99     }
 100
 101     i->idx = j;
 102     q->items[j] = i;
 103
 104 }
 105
 106 pa_prioq_item* pa_prioq_put(pa_prioq *q, void *p) {
 107     pa_prioq_item *i;
 108
 109     pa_assert(q);
 110
 111     if (q->n_items >= q->n_allocated) {
 112         q->n_allocated = PA_MAX(q->n_items+1, q->n_allocated)*2;
 113         q->items = pa_xrealloc(q->items, sizeof(pa_prioq_item*) * q->n_allocated);
 114     }
 115
 116     if (!(i = pa_flist_pop(PA_STATIC_FLIST_GET(items))))
 117         i = pa_xnew(pa_prioq_item, 1);
 118
 119     i->value = p;
 120     i->idx = q->n_items++;
 121
 122     shuffle_up(q, i);
 123
 124     return i;
 125 }
 126
 127 void* pa_prioq_peek(pa_prioq *q) {
 128     pa_assert(q);
 129
 130     if (q->n_items <= 0)
 131         return NULL;
 132
 133     return q->items[0]->value;
 134 }
 135
 136 void* pa_prioq_pop(pa_prioq *q){
 137     pa_assert(q);
 138
 139     if (q->n_items <= 0)
 140         return NULL;
 141
 142     return pa_prioq_remove(q, q->items[0]);
 143 }
 144
 145 static void swap(pa_prioq *q, unsigned j, unsigned k) {
 146     pa_prioq_item *t;
 147
 148     pa_assert(q);
 149     pa_assert(j < q->n_items);
 150     pa_assert(k < q->n_items);
 151
 152     pa_assert(q->items[j]->idx == j);
 153     pa_assert(q->items[k]->idx == k);
 154
 155     t = q->items[j];
 156
 157     q->items[j]->idx = k;
 158     q->items[j] = q->items[k];
 159
 160     q->items[k]->idx = j;
 161     q->items[k] = t;
 162 }
 163
 164 static void shuffle_down(pa_prioq *q, unsigned idx) {
 165
 166     pa_assert(q);
 167     pa_assert(idx < q->n_items);
 168
 169     for (;;) {
 170         unsigned j, k, s;
 171
 172         k = (idx+1)*2; /* right child */
 173         j = k-1;       /* left child */
 174
 175         if (j >= q->n_items)
 176             break;
 177
 178         if (q->compare_func(q->items[j]->value, q->items[idx]->value) < 0)
 179
 180             /* So our left child is smaller than we are, let's
 181              * remember this fact */
 182             s = j;
 183         else
 184             s = idx;
 185
 186         if (k < q->n_items &&
 187             q->compare_func(q->items[k]->value, q->items[s]->value) < 0)
 188
 189             /* So our right child is smaller than we are, let's
 190              * remember this fact */
 191             s = k;
 192
 193         /* s now points to the smallest of the three items */
 194
 195         if (s == idx)
 196             /* No swap necessary, we're done */
 197             break;
 198
 199         swap(q, idx, s);
 200         idx = s;
 201     }
 202 }
 203
 204 void* pa_prioq_remove(pa_prioq *q, pa_prioq_item *i) {
 205     void *p;
 206
 207     pa_assert(q);
 208     pa_assert(i);
 209     pa_assert(q->n_items >= 1);
 210
 211     p = i->value;
 212
 213     if (q->n_items-1 == i->idx) {
 214         /* We are the last entry, so let's just remove us and good */
 215         q->n_items--;
 216
 217     } else {
 218
 219         /* We are not the last entry, we need to replace ourselves
 220          * with the last node and reshuffle */
 221
 222         q->items[i->idx] = q->items[q->n_items-1];
 223         q->items[i->idx]->idx = i->idx;
 224         q->n_items--;
 225
 226         shuffle_down(q, i->idx);
 227     }
 228
 229     if (pa_flist_push(PA_STATIC_FLIST_GET(items), i) < 0)
 230         pa_xfree(i);
 231
 232     return p;
 233 }
 234
 235 unsigned pa_prioq_size(pa_prioq *q) {
 236     pa_assert(q);
 237
 238     return q->n_items;
 239 }
 240
 241 pa_bool_t pa_prioq_isempty(pa_prioq *q) {
 242     pa_assert(q);
 243
 244     return q->n_items == 0;
 245 }
 246
 247 void pa_prioq_reshuffle(pa_prioq *q, pa_prioq_item *i) {
 248     pa_assert(q);
 249     pa_assert(i);
 250
 251     /* This will move the entry down as far as necessary */
 252     shuffle_down(q, i->idx);
 253
 254     /* And this will move the entry up as far as necessary */
 255     shuffle_up(q, i);
 256 }