Opened 9 years ago

Closed 9 years ago

#461 closed enhancement (fixed)

Empty node processing in MemoryZone Easy Part

Reported by: hanfeng Owned by: hanfeng
Priority: high Milestone: A-Team-Sprint-20110126
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity:
Sub-Project: Feature Depending on Ticket:
Estimated Difficulty: 0.0 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description


Subtickets

Change History (13)

comment:1 Changed 9 years ago by hanfeng

branch trac461 has been modified which only including the easy part for non-empty node processing, which will provide policy to return empty node

comment:2 Changed 9 years ago by hanfeng

  • Component changed from Unclassified to data source
  • Owner changed from hanfeng to UnAssigned
  • Priority changed from major to critical
  • Status changed from new to reviewing
  • Summary changed from Empty node processing in MemoryZone to Empty node processing in MemoryZone Easy Part

comment:3 Changed 9 years ago by stephen

  • Milestone set to A-Team-Sprint-20110126

comment:4 Changed 9 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:5 follow-up: Changed 9 years ago by vorner

  • Owner changed from vorner to hanfeng

Hello

I have some comments:

It is not OK to place using namespace into a header file, since everyone who includes it is forced to it as well, even if he does not want.

This comment looks really strange:

/// \par Depending on different usage, rbtree will support different
/// search policy current implementation support whether empty
/// node is visible to end user or not This is as the last template
/// parameter for end user, choose ReturnEmptyNodePolicy to make
/// return non-empty, choose ReturnEmptyNodePolicy to get empty node

It seems to miss punctuation and some parts seem to be there twice. Therefore I have quite a lot trouble guessing what it should mean.

This is no longer true:

/// \note open problems:
/// - current find funciton only return non-empty nodes, so there
///   is no difference
///   between find one not exist name with empty non-terminal nodes,
///    but in DNS query

Also, you reformatted most of the documentation comments. You will probably have some trouble merging them with the comments currently in master, since they have been quite rewritten. Could you, please, merge master into your branch and resolve it? Also, you changed behaviour of insert, so the comment there should be updated to reflect that.

The whole concept of another class template argument is somehow overcomplicated. It is true that any recent compiller will inline it completely, therefore eliminate the:

if (SearchPolicy::returnEmptyNode() ||

condition, but that is hard to follow (even more as the class is forward-declared without any reason). I'd suggest either template specialization or having the template argument be bool, not class:

template<typename T, bool ReturnEmptyNode = false>

Is the #include <stack> used anywhere?

comment:6 in reply to: ↑ 5 Changed 9 years ago by hanfeng

Replying to vorner:

Hello

I have some comments:

It is not OK to place using namespace into a header file, since everyone who includes it is forced to it as well, even if he does not want.

This comment looks really strange:

/// \par Depending on different usage, rbtree will support different
/// search policy current implementation support whether empty
/// node is visible to end user or not This is as the last template
/// parameter for end user, choose ReturnEmptyNodePolicy to make
/// return non-empty, choose ReturnEmptyNodePolicy to get empty node

It seems to miss punctuation and some parts seem to be there twice. Therefore I have quite a lot trouble guessing what it should mean.

This is no longer true:

/// \note open problems:
/// - current find funciton only return non-empty nodes, so there
///   is no difference
///   between find one not exist name with empty non-terminal nodes,
///    but in DNS query

Also, you reformatted most of the documentation comments. You will probably have some trouble merging them with the comments currently in master, since they have been quite rewritten. Could you, please, merge master into your branch and resolve it? Also, you changed behaviour of insert, so the comment there should be updated to reflect that.

I have remove branch trac461 and use latest master to create trac461 again and modify the code base on it. Since the code has modified a lot comparing with origin trac461 which is created quite long time ago.

The whole concept of another class template argument is somehow overcomplicated. It is true that any recent compiller will inline it completely, therefore eliminate the:

if (SearchPolicy::returnEmptyNode() ||

condition, but that is hard to follow (even more as the class is forward-declared without any reason). I'd suggest either template specialization or having the template argument be bool, not class:

template<typename T, bool ReturnEmptyNode = false>

Using template parameter is the common way to do policy based programming, although current policy is quite simple, but the extensibility is better.
Also it's quite strange use bool as template parameter, if only one bool variable is needed, I prefer to use it as construction function parameter.

Is the #include <stack> used anywhere?

The hard part for this task needs stack, I don't remove it cleanly, now it is removed

comment:7 follow-up: Changed 9 years ago by vorner

I'm not sure if you wanted review, you didn't assign it back to me, but even if you want to continue your work, you can take this as part of it.

What's wrong with bool template parameter? It is completely valid, and is closer to what you actually pass inside. I know your way is more extensible, but do we expect we will need the extensibility? There are some 3 layers of hiding that the parameter is actually a boolean, which makes the code harder to read.

And, if you want to preserve the current way, could you, at last, declare the classes above the RBTree and RBNode completely, instead of forward-declaring them? There's no need to forward declare them, since they don't use the RBTree and RBNode and they are in the same header file.

Also, the documentation comments are wrong. They belong only to the first class, so you would either need to comment both, or put them into a group. And, as you put the comment both to the forward declaration and full declaration, you provided two documentation comments for the first class (and none for the second).

comment:8 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by hanfeng

Replying to vorner:

I'm not sure if you wanted review, you didn't assign it back to me, but even if you want to continue your work, you can take this as part of it.

I forget to change the assignment, it's my fault.

What's wrong with bool template parameter? It is completely valid, and is closer to what you actually pass inside. I know your way is more extensible, but do we expect we will need the extensibility? There are some 3 layers of hiding that the parameter is actually a boolean, which makes the code harder to read.

For template syntax, we can pass integer as template parameter, but it's not usual way.
For each feature, we can do quick hack, but if later, we need add more policy into the rbtree, all the place using rbtree has to change, but use template class, the modification is less. And the function name is clearly specify the purpose which I don't think decrease the readability.

And, if you want to preserve the current way, could you, at last, declare the classes above the RBTree and RBNode completely, instead of forward-declaring them? There's no need to forward declare them, since they don't use the RBTree and RBNode and they are in the same header file.

Also, the documentation comments are wrong. They belong only to the first class, so you would either need to comment both, or put them into a group. And, as you put the comment both to the forward declaration and full declaration, you provided two documentation comments for the first class (and none for the second).

Yes, the forward declaring is useless, I have remove it and move the policy class declare above rbtree class declare.

comment:9 Changed 9 years ago by hanfeng

  • Owner changed from hanfeng to vorner

comment:10 in reply to: ↑ 8 ; follow-up: Changed 9 years ago by jinmei

Replying to hanfeng:

What's wrong with bool template parameter? It is completely valid, and is closer to what you actually pass inside. I know your way is more extensible, but do we expect we will need the extensibility? There are some 3 layers of hiding that the parameter is actually a boolean, which makes the code harder to read.

For template syntax, we can pass integer as template parameter, but it's not usual way.
For each feature, we can do quick hack, but if later, we need add more policy into the rbtree, all the place using rbtree has to change, but use template class, the modification is less. And the function name is clearly specify the purpose which I don't think decrease the readability.

FWIW, I think I agree with Michal. I don't think we need (this type of)
extendability in rbtree; BIND 9 has proven that in its 10 year
history. (Besides, the use of rbtree may be our short term solution
and we'll probably revisit the data structure fundamentally.) Also,
while it's true the use of primitive type values as a tempate
parameter is less common, it's also a quite widely deployed technique
(we use it in some of our own BIND 10 code, too). Whether specific code
is readable or not is often a matter of opinion, so I'd leave this point
to you two, but if the use of boolean template parameter helps code simpler
and at least relatively more readable, I'd support the idea of using it.

comment:11 in reply to: ↑ 10 Changed 9 years ago by hanfeng

Replying to jinmei:

Replying to hanfeng:
FWIW, I think I agree with Michal. I don't think we need (this type of)
extendability in rbtree; BIND 9 has proven that in its 10 year
history. (Besides, the use of rbtree may be our short term solution
and we'll probably revisit the data structure fundamentally.) Also...

There is always someplace we think it's over design or it is quick hack. I still
don't prefer the bool way.
But anyway, if the bool template solution is acceptable and most people think it's ok.
I just modify it.

comment:12 Changed 9 years ago by vorner

  • Owner changed from vorner to hanfeng

Ok, thanks. Can you merge it, please?

Thanks.

comment:13 Changed 9 years ago by hanfeng

  • Resolution set to fixed
  • Status changed from reviewing to closed
Note: See TracTickets for help on using tickets.