code.vuplus.com Git - vuplus_xbmc/blob - xbmc/threads/LockFree.h

   1 /*
   2  *      Copyright (C) 2005-2013 Team XBMC
   3  *      http://xbmc.org
   4  *
   5  *  This Program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2, or (at your option)
   8  *  any later version.
   9  *
  10  *  This Program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with XBMC; see the file COPYING.  If not, see
  17  *  <http://www.gnu.org/licenses/>.
  18  *
  19  */
  20
  21 #ifndef __LOCK_FREE_H__
  22 #define __LOCK_FREE_H__
  23
  24 #include <cstring>
  25 #include "Atomics.h"
  26
  27 #define SPINLOCK_ACQUIRE(l) while(cas(&l, 0, 1)) {}
  28 #define SPINLOCK_RELEASE(l) l = 0
  29
  30 // A unique-valued pointer. Version is incremented with each write.
  31 union atomic_ptr
  32 {
  33 #if !defined(__ppc__) && !defined(__powerpc__) && !defined(__arm__)
  34   long long d;
  35   struct {
  36     void* ptr;
  37     long version;
  38   };
  39 #else
  40   long d;
  41   struct {
  42     void* ptr;
  43   };
  44 #endif
  45 };
  46
  47 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
  48   #define atomic_ptr_to_long(p) (long) *((long*)&p)
  49 #else
  50   // This is ugly but correct as long as sizeof(void*) == sizeof(long)...
  51   #define atomic_ptr_to_long_long(p) (long long) *((long long*)&p)
  52 #endif
  53
  54 struct lf_node
  55 {
  56   atomic_ptr next;
  57 };
  58
  59 ///////////////////////////////////////////////////////////////////////////
  60 // Fast Stack
  61 ///////////////////////////////////////////////////////////////////////////
  62
  63
  64 struct lf_stack
  65 {
  66   atomic_ptr top;
  67   long count;
  68 };
  69
  70
  71 void lf_stack_init(lf_stack* pStack);
  72 void lf_stack_push(lf_stack* pStack, lf_node* pNode);
  73 lf_node* lf_stack_pop(lf_stack* pStack);
  74
  75 ///////////////////////////////////////////////////////////////////////////
  76 // Fast Heap for Fixed-size Blocks
  77 ///////////////////////////////////////////////////////////////////////////
  78 struct lf_heap_chunk
  79 {
  80   lf_heap_chunk* next;
  81   long size;
  82 };
  83
  84 struct lf_heap
  85 {
  86   lf_stack free_list;
  87   long alloc_lock;
  88   lf_heap_chunk* top_chunk;
  89   long block_size;
  90 };
  91
  92
  93 void lf_heap_init(lf_heap* pHeap, size_t blockSize, size_t initialSize = 0);
  94 void lf_heap_grow(lf_heap* pHeap, size_t size = 0);
  95 void lf_heap_deinit(lf_heap* pHeap);
  96 void* lf_heap_alloc(lf_heap* pHeap);
  97 void lf_heap_free(lf_heap* pHeap, void* p);
  98
  99 ///////////////////////////////////////////////////////////////////////////
 100 // Lock-free queue
 101 ///////////////////////////////////////////////////////////////////////////
 102 struct lf_queue_node
 103 {
 104   atomic_ptr next;
 105   void* value; // TODO: Convert to a template
 106 };
 107
 108 struct lf_queue
 109 {
 110   atomic_ptr head;
 111   atomic_ptr tail;
 112   lf_heap node_heap;
 113   long len;
 114 };
 115
 116 #define lf_queue_new_node(q) (lf_queue_node*)lf_heap_alloc(&q->node_heap)
 117 #define lf_queue_free_node(q,n) lf_heap_free(&q->node_heap, n)
 118
 119 void lf_queue_init(lf_queue* pQueue);
 120 void lf_queue_deinit(lf_queue* pQueue);
 121 void lf_queue_enqueue(lf_queue* pQueue, void* pVal);
 122 void* lf_queue_dequeue(lf_queue* pQueue);
 123
 124 #endif