src/pulsecore/flist.c

   1 /***
   2   This file is part of PulseAudio.
   3
   4   Copyright 2006-2008 Lennart Poettering
   5   Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
   6   Copyright (C) 2012 Canonical Ltd.
   7
   8   Contact: Jyri Sarha <Jyri.Sarha@nokia.com>
   9
  10   PulseAudio is free software; you can redistribute it and/or modify
  11   it under the terms of the GNU Lesser General Public License as
  12   published by the Free Software Foundation; either version 2.1 of the
  13   License, or (at your option) any later version.
  14
  15   PulseAudio is distributed in the hope that it will be useful, but
  16   WITHOUT ANY WARRANTY; without even the implied warranty of
  17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18   Lesser General Public License for more details.
  19
  20   You should have received a copy of the GNU Lesser General Public
  21   License along with PulseAudio; if not, write to the Free Software
  22   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  23   USA.
  24 ***/
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include <config.h>
  28 #endif
  29
  30 #include <pulse/xmalloc.h>
  31
  32 #include <pulsecore/atomic.h>
  33 #include <pulsecore/log.h>
  34 #include <pulsecore/macro.h>
  35 #include <pulsecore/core-util.h>
  36 #include <pulsecore/macro.h>
  37
  38 #include "flist.h"
  39
  40 #define FLIST_SIZE 128
  41
  42 /* Atomic table indices contain
  43    sign bit = if set, indicates empty/NULL value
  44    tag bits (to avoid the ABA problem)
  45    actual index bits
  46 */
  47
  48 /* Lock free single linked list element. */
  49 struct pa_flist_elem {
  50     pa_atomic_t next;
  51     pa_atomic_ptr_t ptr;
  52 };
  53
  54 typedef struct pa_flist_elem pa_flist_elem;
  55
  56 struct pa_flist {
  57     char *name;
  58     unsigned size;
  59
  60     pa_atomic_t current_tag;
  61     int index_mask;
  62     int tag_shift;
  63     int tag_mask;
  64
  65     /* Stack that contains pointers stored into free list */
  66     pa_atomic_t stored;
  67     /* Stack that contains empty list elements */
  68     pa_atomic_t empty;
  69     pa_flist_elem table[];
  70 };
  71
  72 /* Lock free pop from linked list stack */
  73 static pa_flist_elem *stack_pop(pa_flist *flist, pa_atomic_t *list) {
  74     pa_flist_elem *popped;
  75     int idx;
  76     pa_assert(list);
  77
  78     do {
  79         idx = pa_atomic_load(list);
  80         if (idx < 0)
  81             return NULL;
  82         popped = &flist->table[idx & flist->index_mask];
  83     } while (!pa_atomic_cmpxchg(list, idx, pa_atomic_load(&popped->next)));
  84
  85     return popped;
  86 }
  87
  88 /* Lock free push to linked list stack */
  89 static void stack_push(pa_flist *flist, pa_atomic_t *list, pa_flist_elem *new_elem) {
  90     int tag, newindex, next;
  91     pa_assert(list);
  92
  93     tag = pa_atomic_inc(&flist->current_tag);
  94     newindex = new_elem - flist->table;
  95     pa_assert(newindex >= 0 && newindex < (int) flist->size);
  96     newindex |= (tag << flist->tag_shift) & flist->tag_mask;
  97
  98     do {
  99         next = pa_atomic_load(list);
 100         pa_atomic_store(&new_elem->next, next);
 101     } while (!pa_atomic_cmpxchg(list, next, newindex));
 102 }
 103
 104 pa_flist *pa_flist_new_with_name(unsigned size, const char *name) {
 105     pa_flist *l;
 106     unsigned i;
 107     pa_assert(name);
 108
 109     if (!size)
 110         size = FLIST_SIZE;
 111
 112     l = pa_xmalloc0(sizeof(pa_flist) + sizeof(pa_flist_elem) * size);
 113
 114     l->name = pa_xstrdup(name);
 115     l->size = size;
 116
 117     while (1 << l->tag_shift < (int) size)
 118         l->tag_shift++;
 119     l->index_mask = (1 << l->tag_shift) - 1;
 120     l->tag_mask = INT_MAX - l->index_mask;
 121
 122     pa_atomic_store(&l->stored, -1);
 123     pa_atomic_store(&l->empty, -1);
 124     for (i=0; i < size; i++) {
 125         stack_push(l, &l->empty, &l->table[i]);
 126     }
 127     return l;
 128 }
 129
 130 pa_flist *pa_flist_new(unsigned size) {
 131     return pa_flist_new_with_name(size, "unknown");
 132 }
 133
 134 void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) {
 135     pa_assert(l);
 136     pa_assert(l->name);
 137
 138     if (free_cb) {
 139         pa_flist_elem *elem;
 140         while((elem = stack_pop(l, &l->stored)))
 141             free_cb(pa_atomic_ptr_load(&elem->ptr));
 142     }
 143
 144     pa_xfree(l->name);
 145     pa_xfree(l);
 146 }
 147
 148 int pa_flist_push(pa_flist *l, void *p) {
 149     pa_flist_elem *elem;
 150     pa_assert(l);
 151     pa_assert(p);
 152
 153     elem = stack_pop(l, &l->empty);
 154     if (elem == NULL) {
 155         if (pa_log_ratelimit(PA_LOG_DEBUG))
 156             pa_log_debug("%s flist is full (don't worry)", l->name);
 157         return -1;
 158     }
 159     pa_atomic_ptr_store(&elem->ptr, p);
 160     stack_push(l, &l->stored, elem);
 161
 162     return 0;
 163 }
 164
 165 void* pa_flist_pop(pa_flist *l) {
 166     pa_flist_elem *elem;
 167     void *ptr;
 168     pa_assert(l);
 169
 170     elem = stack_pop(l, &l->stored);
 171     if (elem == NULL)
 172         return NULL;
 173
 174     ptr = pa_atomic_ptr_load(&elem->ptr);
 175
 176     stack_push(l, &l->empty, elem);
 177
 178     return ptr;
 179 }