← Back to branch summary

~diwic/ubuntu/lucid/pulseaudio/bugfixes

« back to all changes in this revision

Viewing changes to src/pulsecore/prioq.c

  • Committer: Bazaar Package Importer
  • Author(s): Luke Yelavich
  • Date: 2008-11-04 15:46:00 UTC
  • mfrom: (1.2.1 upstream) (1.1.6 lenny)
  • Revision ID: james.westby@ubuntu.com-20081104154600-hlzknpcazaam0nxm
Tags: 0.9.13-1ubuntu1
* Merge from Debian unstable, remaining changes:
  - Don't build against, and create jack package. Jack is not in main.
  - Remove --disable-per-user-esound-socket from configure flags, as we still
    want per user esound sockets.
  - Remove stop links from rc0 and rc6.
  - Change default resample algorithm and bubffer size.
  - Add alsa configuration files to route alsa applications via pulseaudio.
  - Move libasound2-plugins from Recommends to Depends.
* debian/pulseaudio.preinst: When upgrading from intrepid, remove
  /etc/X11/Xsession.d/70pulseaudio, as this was used to minimize a race
  condition when starting GNOME in intrepid. This race should not exist in
  jaunty once libcanberra is built to use pulseaudio as a backend.
* Do not spawn a pulseaudio server if clients fail to find a running server.
* Remove explicit version dependency for libspeex-dev to allow the package
  to be built for now.
* Regenerate autotools files to work with Ubuntu's newer libtool/libltdl.
* debian/control: libpulsecore5 -> libpulsecore8 to match the library
  soname.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 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
}