Opened 7 years ago

Closed 7 years ago

#2105 closed task (fixed)

introduce node deleter of new RBTree

Reported by: jinmei Owned by: muks
Priority: medium Milestone: Sprint-20120807
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket: scalable inmemory
Estimated Difficulty: 4 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description (last modified by jinmei)

We are not going to store node data in the new RBTree in the form
of shared pointers, so the tree needs to take care of destroying
node data when it destructs the entire tree.

My suggestion is to make it a template parameter and call its
operator() via the destructor.

template <typename T, typename DeleterType>
class RBTree : public boost::noncopyable {
...
template <typename T, typename DeleterType>
RBTree<T>::~RBTree() {
    DeleterType deleter;
    deleteHelper(root_, segment_, deleter);
    assert(node_count_ == 0);
}

This depends on at least #2088 and #2090.

It'd also be better to hold off until #2091 is merged (or work on a
snapshot version of trac2091b).

Also, I guess this is the time to fork from the currently used version
of the code; beyond this point I suspect it won't be feasible to share
the same code base for the shared_ptr version and offset_ptr version.
So I propose making a copy of rbtree.h, moving it to datasrc/memory
with a copy of the test (and maybe rename the class to e.g.
DomainTree), and working on the copy version.

Subtickets

Change History (25)

comment:1 Changed 7 years ago by jinmei

  • Type changed from defect to task

comment:2 Changed 7 years ago by shane

  • Estimated Difficulty changed from 0 to 4

comment:3 Changed 7 years ago by jelte

  • Milestone set to Sprint-20120731

comment:4 Changed 7 years ago by jinmei

  • Description modified (diff)

comment:5 Changed 7 years ago by muks

  • Owner set to muks
  • Status changed from new to assigned

Picking

comment:6 Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned
  • Status changed from assigned to reviewing

Up for review.

comment:7 follow-up: Changed 7 years ago by jinmei

(Although I don't think I can take on full review) some things I've
noticed:

  • it didn't compile for me because DeleterType doesn't have the constructor explicitly defined. my compiler rejects a const instant of it without the default constructor:
    class DeleterType {
    public:
        DeleterType() {}
    ...
    };
    
  • I suspect we need to pass a MemorySegment to the deleter's operator() (or whatever actually deletes the data). We'll use a segment when we actually use it for RdataSet.
  • I'm not sure if it's a good behavior to autoamtically delete existing data on setData(). I'm also not sure if we can pass NULL to the deleter. please discuss this with the reviwer.

comment:8 follow-up: Changed 7 years ago by jinmei

And I've noticed there are some 'rbtree', etc in the code. If we
choose to rename it now, that cleanup should be comprehensive.

comment:9 Changed 7 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:10 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to jinmei:

  • I suspect we need to pass a MemorySegment to the deleter's operator() (or whatever actually deletes the data). We'll use a segment when we actually use it for RdataSet.

I'm not sure if it needs to go to the operator, or if we want to pass a deleter that already contains the segment to the tree, or something. But it is true the segment must get inside somehow.

  • I'm not sure if it's a good behavior to autoamtically delete existing data on setData(). I'm also not sure if we can pass NULL to the deleter. please discuss this with the reviwer.

Well, it kind of makes sense to me to delete it. If we automatically delete it upon destruction, it means we've taken the responsibility for the destruction and we should not say that we take only half of it ‒ then someone outside will still need to take care what to delete when and track pointers.

But, that being said, I think we need a way to take the data out somehow without destruction ‒ some kind of release method.

Deleting of NULL is usually a nop (both with delete and free()), so I think we can take an consistent approach. But then, I think it should be documented that it is required of the deleter.

Also, why is data_ set in the body of constructor, if it well could be done in the initializer list?

     flags_(FLAG_RED | FLAG_SUBTREE_ROOT),
     labels_capacity_(labels_capacity)
 {
+    data_ = NULL;
 }

And, the template parameter list ‒ I think we usually place a space after the comma there, so it should be DomainTree<T, DT>, not DomainTree<T,DT>.

With regards

comment:11 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi Jinmei

Replying to jinmei:

(Although I don't think I can take on full review) some things I've
noticed:

  • it didn't compile for me because DeleterType doesn't have the constructor explicitly defined. my compiler rejects a const instant of it without the default constructor:
    class DeleterType {
    public:
        DeleterType() {}
    ...
    };
    

This has been added now.

  • I suspect we need to pass a MemorySegment to the deleter's operator() (or whatever actually deletes the data). We'll use a segment when we actually use it for RdataSet.

Reading both this and vorner's later reply to this comment, I think it's best we leave it to whoever uses DomainTree to change the argument list when it's actually used. There's no interface enforced for DeleterType anyway.

  • I'm not sure if it's a good behavior to autoamtically delete existing data on setData(). I'm also not sure if we can pass NULL to the deleter. please discuss this with the reviwer.

When we call setData(), the ownership of the data passes to the tree (as we delete the data when we destroy the tree). So to keep it consistent, we have to destroy it if we replace the data with something else.

I agree with vorner we should allow NULL and let the DeleterType? handle it if necessary. I've added a comment for this. Maybe MemorySegment?'s doc can be updated too, to say that MemorySegment::deallocate() may be passed NULL. When the implementation uses free() or delete, it need not be checked.

Hi vorner

Replying to vorner:

But, that being said, I think we need a way to take the data out somehow without destruction ‒ some kind of release method.

This can be added trivially, but do we have a use-case when it has to be released (and not deleted during overwrite)?

Deleting of NULL is usually a nop (both with delete and free()), so I think we can take an consistent approach. But then, I think it should be documented that it is required of the deleter.

A comment has been added to explain this.

Also, why is data_ set in the body of constructor, if it well could be done in the initializer list?

     flags_(FLAG_RED | FLAG_SUBTREE_ROOT),
     labels_capacity_(labels_capacity)
 {
+    data_ = NULL;
 }

It has been moved to the initializer list now.

And, the template parameter list ‒ I think we usually place a space after the comma there, so it should be DomainTree<T, DT>, not DomainTree<T,DT>.

Done. :)

comment:12 in reply to: ↑ 8 Changed 7 years ago by muks

Replying to jinmei:

And I've noticed there are some 'rbtree', etc in the code. If we
choose to rename it now, that cleanup should be comprehensive.

This should be fixed now too.

comment:13 in reply to: ↑ 11 ; follow-ups: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to muks:

  • I suspect we need to pass a MemorySegment to the deleter's operator() (or whatever actually deletes the data). We'll use a segment when we actually use it for RdataSet.

Reading both this and vorner's later reply to this comment, I think it's best we leave it to whoever uses DomainTree to change the argument list when it's actually used. There's no interface enforced for DeleterType anyway.

Well, it is kind of enforced, by the code calling it. If you look at this:

template <typename T, typename DT>
void
DomainTree<T, DT>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
    const DT deleter;
    deleteHelper(mem_sgmt, root_.get(), deleter);
    root_ = NULL;
}

Then there's no way the deleter could know which mem_sgmt it should use. It can't be a template argument, since that would make it fixed for all the trees. And, as the one and currently only goal of this deleter is to use the memory segment, I the code should be changed to:

template <typename T, typename DT>
void
DomainTree<T, DT>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
    const DT deleter(mem_sgmt); // <- This is where it knows now
    deleteHelper(mem_sgmt, root_.get(), deleter);
    root_ = NULL;
}

(And similar changes to other places it is used)

Replying to vorner:

But, that being said, I think we need a way to take the data out somehow without destruction ‒ some kind of release method.

This can be added trivially, but do we have a use-case when it has to be released (and not deleted during overwrite)?

I don't know. We probably don't. But it depends on if the header should be for our use inside in-memory only, or if it would be of general public use. In the second case, the interface would be incomplete and as the release would be simple, it would make no sense to create a new ticket for it. But I have no idea what is the direction about public interfaces at all.

comment:14 Changed 7 years ago by muks

Note: merge #2054 into DomainTree? before merging this bug into master.

comment:15 in reply to: ↑ 13 Changed 7 years ago by muks

Replying to vorner:

Then there's no way the deleter could know which mem_sgmt it should use. It can't be a template argument, since that would make it fixed for all the trees. And, as the one and currently only goal of this deleter is to use the memory segment, I the code should be changed to:

template <typename T, typename DT>
void
DomainTree<T, DT>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
    const DT deleter(mem_sgmt); // <- This is where it knows now
    deleteHelper(mem_sgmt, root_.get(), deleter);
    root_ = NULL;
}

Isn't it better to send it as an argument to operator() ?

comment:16 Changed 7 years ago by muks

Also mem_sgmt is not available in DomainTreeNode, so that'll be a problem in setData() if we want to destroy the old data. We'll have to pass it to setData().

comment:17 in reply to: ↑ 13 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

This can be added trivially, but do we have a use-case when it has to be released (and not deleted during overwrite)?

I don't know. We probably don't. But it depends on if the header should be for our use inside in-memory only, or if it would be of general public use. In the second case, the interface would be incomplete and as the release would be simple, it would make no sense to create a new ticket for it. But I have no idea what is the direction about public interfaces at all.

I've updated setData() for this.

Also merged nodeFission() changes from #2054.

Let me know your opinion on the other points.

comment:18 in reply to: ↑ 17 ; follow-up: Changed 7 years ago by vorner

Hello

Replying to muks:

Replying to vorner:

template <typename T, typename DT>
void
DomainTree<T, DT>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
    const DT deleter(mem_sgmt); // <- This is where it knows now
    deleteHelper(mem_sgmt, root_.get(), deleter);
    root_ = NULL;
}

Isn't it better to send it as an argument to operator() ?

I don't know. I think that's just matter of personal preference.

Replying to muks:

Also mem_sgmt is not available in DomainTreeNode, so that'll be a problem in setData() if we want to destroy the old data. We'll have to pass it to setData().

Yes, of course, that would be needed too. But I think it is OK, because whoever calls setData, has the segment too, because they allocated the data.

Replying to muks:

Also merged nodeFission() changes from #2054.

They are reviewed there, right? I don't need to review them again.

Let me know your opinion on the other points.

Which points? About the segment ↑?

comment:19 Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Ups, forgot to pass the ticket.

comment:20 in reply to: ↑ 18 Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

Replying to vorner:

Isn't it better to send it as an argument to operator() ?

I don't know. I think that's just matter of personal preference.

I've passed it as an argument to operator() so that the deleter object is otherwise unused and const.

Replying to muks:

Also mem_sgmt is not available in DomainTreeNode, so that'll be a problem in setData() if we want to destroy the old data. We'll have to pass it to setData().

Yes, of course, that would be needed too. But I think it is OK, because whoever calls setData, has the segment too, because they allocated the data.

Done. :)

Replying to muks:

Also merged nodeFission() changes from #2054.

They are reviewed there, right? I don't need to review them again.

Cool.. I was just letting you know of the change.

Let me know your opinion on the other points.

Which points? About the segment ↑?

It was about the segment. I'm passing it back to you for review.

comment:21 follow-up: Changed 7 years ago by muks

One more change we can do is use a DT::delete() static method instead of operator() and not have to create instances of DT.

comment:22 in reply to: ↑ 21 ; follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to muks:

One more change we can do is use a DT::delete() static method instead of operator() and not have to create instances of DT.

Yes, we could. But is there an advantage to it?

Unless you want to do the change, I think it can be merged.

comment:23 in reply to: ↑ 22 Changed 7 years ago by muks

Replying to vorner:

Hello

Replying to muks:

One more change we can do is use a DT::delete() static method instead of operator() and not have to create instances of DT.

Yes, we could. But is there an advantage to it?

Unless you want to do the change, I think it can be merged.

Just that there's no need to create instances of the DeleterType?. Anyway, I'll leave it as it is for now.

comment:24 Changed 7 years ago by muks

The deleteHelper() changes from #2182 have been adapted for DomainTree and committed to the branch.

comment:25 Changed 7 years ago by muks

  • Resolution set to fixed
  • Status changed from reviewing to closed

Merged to master in commit c149373122712acd20af00d9e327e9449e4f81f3:

* 2b06246 [2105] Add #2182 (deleteHelper changes) into DomainTree
* 13b16c0 [2105] Pass memory segment to operator() of the deleter class
* 0ea32d7 [2105] Make setData() optionally return the old data
* 65976ab [2105] Add #2054 (nodeFission changes) into DomainTree
* 9d416b8 [2105] Document DT template parameter
* 1319a26 [2105] Rename other instances of rbtree/rbnode
* 5eb12ef [2105] Add space between template parameters
* ce3394f [2105] Set data_ in the initializer list
* 1fdb15b [2105] Add explicit default constructor for the DeleterType class
* ad0d2ac [2105] trivial style fix: adjusted place of *
* 9dfe092 [2105] Reindent code according to our coding style
* ff3f282 [2105] Introduce node deleter as a template parameter
* 26d871c [2105] Copy RBTree to DomainTree class in datasrc/memory; also copy tests

Resolving as fixed. Thank you for the reviews Michal and Jinmei.

Note: See TracTickets for help on using tickets.