1.7 KiB
jami-daemon-0002: std::find (algorithm) used on std::set members — bypasses O(log n) set.find()
Target: savoirfairelinux/jami-daemon
Severity: LOW
CWE: CWE-407 (Inefficient Algorithmic Complexity)
File: src/jamidht/conversation_module.cpp
Lines: 2341, 2501, 2797
Status: PATCHED
Description
ConvInfo::members is declared as std::set<std::string> (conversation.h:133).
Three sites in conversation_module.cpp call the generic std::find() algorithm
from <algorithm> on its iterators instead of calling the set's own .find()
member, which uses the tree structure for O(log n) lookup.
std::find(set.begin(), set.end(), key) degrades to O(n) linear scan because
the algorithm iterator does not know about the underlying red-black tree.
| Site | Function | Pattern |
|---|---|---|
| line 2341 | syncConversations() |
std::find(conv->info.members.begin(), ..., peer) |
| line 2501 | needsSyncingWith() |
std::find(ci->info.members.begin(), ..., memberUri) |
| line 2797 | removeContact() lambda |
std::find(members.begin(), ..., uri) |
needsSyncingWith() is called inside a loop over all conversations, making
the total work O(conversations × members) instead of O(conversations × log members).
Fix
// Before (O(n)):
std::find(conv->info.members.begin(), conv->info.members.end(), peer) != conv->info.members.end()
// After (O(log n)):
conv->info.members.count(peer) > 0
// or equivalently:
conv->info.members.find(peer) != conv->info.members.end()
Apply the same fix at all three sites.
Complexity
| Before | After | |
|---|---|---|
| Per membership test | O(M) | O(log M) |
| needsSyncingWith() over N convs, M members | O(N × M) | O(N × log M) |