1 /*
2  * Copyright (c) 2020, 2021, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  *
23  */
24 
25 #ifndef SHARE_UTILITIES_FILTERQUEUE_HPP
26 #define SHARE_UTILITIES_FILTERQUEUE_HPP
27 
28 #include "memory/allocation.hpp"
29 #include "runtime/atomic.hpp"
30 
31 // The FilterQueue is FIFO with the ability to skip over queued items.
32 // The skipping is controlled by using a filter when popping.
33 // It also supports lock free pushes, while popping (including contains())
34 // needs to be externally serialized.
35 template <class E>
36 class FilterQueue {
37  private:
38   class Node : public CHeapObj<mtInternal> {
39    public:
Node(const E & e)40     Node(const E& e): _next(NULL), _data(e) { }
41     Node*    _next;
42     E                   _data;
43   };
44 
45   Node* _first;
load_first()46   Node* load_first() {
47     return Atomic::load_acquire(&_first);
48   }
49 
match_all(E d)50   static bool match_all(E d) { return true; }
51 
52  public:
FilterQueue()53   FilterQueue() : _first(NULL) { }
54 
is_empty()55   bool is_empty() {
56     return load_first() == NULL;
57   }
58 
59   // Adds an item to the queue in a MT safe way, re-entrant.
60   void push(E data);
61 
62   // Applies the match_func to the items in the queue until match_func returns
63   // true and then returns true, or there is no more items and then returns
64   // false. Items pushed after execution starts will not have match_func
65   // applied. The method is not re-entrant and must be executed mutually
66   // exclusive to other contains and pops calls.
67   template <typename MATCH_FUNC>
68   bool contains(MATCH_FUNC& match_func);
69 
70   // Same as peek(MATCH_FUNC& match_func) but matches everything, thus returning
71   // the first inserted item.
peek()72   E peek() {
73     return peek(match_all);
74   }
75 
76   // Applies the match_func to each item in the queue and returns the first
77   // inserted item for which match_func returns true. Returns false if there are
78   // no matches or the queue is empty. Any pushed item before execution is
79   // complete may or may not have match_func applied. The method is not
80   // re-entrant and must be executed mutual exclusive to other contains and pops
81   // calls.
82   template <typename MATCH_FUNC>
83   E pop(MATCH_FUNC& match_func);
84 
85   template <typename MATCH_FUNC>
86   E peek(MATCH_FUNC& match_func);
87 };
88 
89 #endif
90