legacy-libs/grpc/deps/grpc/src/core/lib/gpr/mpscq.h

   1 /*
   2  *
   3  * Copyright 2016 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #ifndef GRPC_CORE_LIB_GPR_MPSCQ_H
  20 #define GRPC_CORE_LIB_GPR_MPSCQ_H
  21
  22 #include <grpc/support/port_platform.h>
  23
  24 #include <grpc/support/atm.h>
  25 #include <grpc/support/sync.h>
  26 #include <stdbool.h>
  27 #include <stddef.h>
  28
  29 // Multiple-producer single-consumer lock free queue, based upon the
  30 // implementation from Dmitry Vyukov here:
  31 // http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue
  32
  33 // List node (include this in a data structure at the top, and add application
  34 // fields after it - to simulate inheritance)
  35 typedef struct gpr_mpscq_node {
  36   gpr_atm next;
  37 } gpr_mpscq_node;
  38
  39 // Actual queue type
  40 typedef struct gpr_mpscq {
  41   // make sure head & tail don't share a cacheline
  42   union {
  43     char padding[GPR_CACHELINE_SIZE];
  44     gpr_atm head;
  45   };
  46   gpr_mpscq_node* tail;
  47   gpr_mpscq_node stub;
  48 } gpr_mpscq;
  49
  50 void gpr_mpscq_init(gpr_mpscq* q);
  51 void gpr_mpscq_destroy(gpr_mpscq* q);
  52 // Push a node
  53 // Thread safe - can be called from multiple threads concurrently
  54 // Returns true if this was possibly the first node (may return true
  55 // sporadically, will not return false sporadically)
  56 bool gpr_mpscq_push(gpr_mpscq* q, gpr_mpscq_node* n);
  57 // Pop a node (returns NULL if no node is ready - which doesn't indicate that
  58 // the queue is empty!!)
  59 // Thread compatible - can only be called from one thread at a time
  60 gpr_mpscq_node* gpr_mpscq_pop(gpr_mpscq* q);
  61 // Pop a node; sets *empty to true if the queue is empty, or false if it is not
  62 gpr_mpscq_node* gpr_mpscq_pop_and_check_end(gpr_mpscq* q, bool* empty);
  63
  64 // An mpscq with a lock: it's safe to pop from multiple threads, but doing
  65 // only one thread will succeed concurrently
  66 typedef struct gpr_locked_mpscq {
  67   gpr_mpscq queue;
  68   gpr_mu mu;
  69 } gpr_locked_mpscq;
  70
  71 void gpr_locked_mpscq_init(gpr_locked_mpscq* q);
  72 void gpr_locked_mpscq_destroy(gpr_locked_mpscq* q);
  73 // Push a node
  74 // Thread safe - can be called from multiple threads concurrently
  75 // Returns true if this was possibly the first node (may return true
  76 // sporadically, will not return false sporadically)
  77 bool gpr_locked_mpscq_push(gpr_locked_mpscq* q, gpr_mpscq_node* n);
  78
  79 // Pop a node (returns NULL if no node is ready - which doesn't indicate that
  80 // the queue is empty!!)
  81 // Thread safe - can be called from multiple threads concurrently
  82 gpr_mpscq_node* gpr_locked_mpscq_try_pop(gpr_locked_mpscq* q);
  83
  84 // Pop a node.  Returns NULL only if the queue was empty at some point after
  85 // calling this function
  86 gpr_mpscq_node* gpr_locked_mpscq_pop(gpr_locked_mpscq* q);
  87
  88 #endif /* GRPC_CORE_LIB_GPR_MPSCQ_H */