[
https://issues.apache.org/jira/browse/TS-4295?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15219248#comment-15219248
]
ASF GitHub Bot commented on TS-4295:
------------------------------------
Github user masaori335 commented on a diff in the pull request:
https://github.com/apache/trafficserver/pull/537#discussion_r57996067
--- Diff: lib/ts/PriorityQueue.h ---
@@ -0,0 +1,191 @@
+/** @file
+
+ Priority Queue Implimentation using Min Heap.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+ */
+
+#ifndef __PRIORITY_QUEUE_H__
+#define __PRIORITY_QUEUE_H__
+
+#include "ts/Diags.h"
+#include "ts/Vec.h"
+
+template <typename T> struct PriorityQueueEntry {
+ PriorityQueueEntry(T n) : index(0), node(n) {}
+
+ uint32_t index;
+ T node;
+};
+
+template <typename T> class PriorityQueue
+{
+public:
+ PriorityQueue() {}
+ ~PriorityQueue() {}
+
+ const bool empty();
+ PriorityQueueEntry<T> *top();
+ void pop();
+ void push(PriorityQueueEntry<T> *);
+ void update(PriorityQueueEntry<T> *, bool);
+ const Vec<PriorityQueueEntry<T> *> &dump() const;
+
+private:
+ Vec<PriorityQueueEntry<T> *> _v;
+
+ void _swap(uint32_t, uint32_t);
+ void _bubble_up(uint32_t);
+ void _bubble_down(uint32_t);
+};
+
+template <typename T>
+const Vec<PriorityQueueEntry<T> *> &
+PriorityQueue<T>::dump() const
+{
+ return _v;
+}
+
+template <typename T>
+const bool
+PriorityQueue<T>::empty()
+{
+ return _v.length() == 0;
+}
+
+template <typename T>
+void
+PriorityQueue<T>::push(PriorityQueueEntry<T> *entry)
+{
+ ink_release_assert(entry != NULL);
+
+ int len = _v.length();
+ _v.push_back(entry);
+ entry->index = len;
+
+ _bubble_up(len);
+}
+
+template <typename T>
+PriorityQueueEntry<T> *
+PriorityQueue<T>::top()
+{
+ if (empty()) {
+ return NULL;
+ } else {
+ return _v[0];
+ }
+}
+
+template <typename T>
+void
+PriorityQueue<T>::pop()
+{
+ if (empty()) {
+ return;
+ }
+
+ _v[0] = _v[_v.length() - 1];
+ _v.pop();
+ _bubble_down(0);
+}
+
+template <typename T>
+void
+PriorityQueue<T>::update(PriorityQueueEntry<T> *entry, bool increased =
true)
+{
+ ink_release_assert(entry != NULL);
+
+ if (empty()) {
+ return;
+ }
+
+ if (increased) {
--- End diff --
Ah, if both of them are called, one of them works and other does nothing.
> Add Priority Queue in lib/ts/
> -----------------------------
>
> Key: TS-4295
> URL: https://issues.apache.org/jira/browse/TS-4295
> Project: Traffic Server
> Issue Type: Improvement
> Reporter: Masaori Koshiba
> Assignee: Masaori Koshiba
> Fix For: 6.2.0
>
>
> TS-3535 needs Priority Queue using Binary Heap.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
