[jira] [Comment Edited] (TS-4537) Add erase to PriorityQueue

["Thomas Jackson (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/TS-4537?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15331184#comment-15331184 ] 

Thomas Jackson edited comment on TS-4537 at 6/15/16 5:43 AM:
-------------------------------------------------------------

That doesn't quite work though :/ Since we are erasing an entry (and each entry includes its index in the `_v`) we have to update all entries in the queue after us in the index. In addition, `_bubble_down` and `_bubble_up` don't seem to work all the time (probably to do with boundaries and not moving any items). Your patch is actually what I originally tried, and with that the tests segfault on me:

{code}
$ make test_tsutil && ./test_tsutil 
  CXX      test_PriorityQueue.o
  CXXLD    test_tsutil
REGRESSION_TEST initialization begun
REGRESSION TEST PriorityQueue_6 started
FATAL: PriorityQueue.h:181: failed assertion `false`
Aborted (core dumped)
{code}

Fixing the core dump is actually possible by correctly checking boundaries etc. but IMO using these bubble methods is wasteful-- since we don't need to check order again, since we just removed an item.


was (Author: jacksontj):
That doesn't quite work though :/ Since we are erasing an entry (and each entry includes its index in the `_v`) we have to update all entries in the queue after us in the index. In addition, `_bubble_down` and `_bubble_up` don't seem to work all the time (probably to do with boundaries and not moving any items). Your patch is actually what I originally tried, and with that the tests segfault on me:

{code}
$ make test_tsutil && ./test_tsutil 
  CXX      test_PriorityQueue.o
  CXXLD    test_tsutil
REGRESSION_TEST initialization begun
REGRESSION TEST PriorityQueue_6 started
FATAL: PriorityQueue.h:181: failed assertion `false`
Aborted (core dumped)
{code}

> Add erase to PriorityQueue
> --------------------------
>
>                 Key: TS-4537
>                 URL: https://issues.apache.org/jira/browse/TS-4537
>             Project: Traffic Server
>          Issue Type: New Feature
>            Reporter: Thomas Jackson
>            Assignee: Thomas Jackson
>             Fix For: 7.0.0
>
>
> The priorityqueue (really more of a sorted list...) doesn't have an erase method-- we probably should have one :)



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)