136 lines
3.9 KiB
Python
136 lines
3.9 KiB
Python
"""
|
|
pidgin-0001: add_all_buddies_to_permit_list O(B^2) GSList scan
|
|
|
|
libpurple/privacy.c: add_all_buddies_to_permit_list() iterates all B buddies
|
|
and for each calls g_slist_find_custom(account->permit, ...) which scans our
|
|
growing permit GSList linearly. As buddies are added the list grows to B,
|
|
making total comparisons O(B^2/2).
|
|
|
|
Fix: snapshot account->permit into a GHashTable before our loop so each
|
|
membership test is O(1), reducing total work to O(B).
|
|
|
|
CWE-407: Algorithmic Complexity
|
|
UNDF: UNDF-2026-000001141
|
|
"""
|
|
|
|
import time
|
|
import sys
|
|
|
|
PYTHONUNBUFFERED = 1 # ensure unbuffered output
|
|
|
|
|
|
def add_buddies_defective(buddies: list[str]) -> int:
|
|
"""
|
|
Models the defective C code:
|
|
for each buddy in find_buddies(account):
|
|
if not g_slist_find_custom(account->permit, name, g_utf8_collate):
|
|
purple_privacy_permit_add(account, name, local)
|
|
|
|
g_slist_find_custom scans account->permit linearly.
|
|
As our permit list grows, each scan takes longer: O(B^2) total.
|
|
Returns operation count.
|
|
"""
|
|
permit = [] # GSList analog
|
|
ops = 0
|
|
for buddy in buddies:
|
|
# linear scan of permit list
|
|
found = False
|
|
for p in permit:
|
|
ops += 1
|
|
if p == buddy:
|
|
found = True
|
|
break
|
|
if not found:
|
|
permit.append(buddy)
|
|
return ops
|
|
|
|
|
|
def add_buddies_fixed(buddies: list[str]) -> int:
|
|
"""
|
|
Models our fix:
|
|
permit_set = g_hash_table_new(g_str_hash, g_str_equal)
|
|
for p in account->permit:
|
|
g_hash_table_add(permit_set, p)
|
|
for each buddy in find_buddies(account):
|
|
if not g_hash_table_lookup(permit_set, name):
|
|
purple_privacy_permit_add(account, name, local)
|
|
g_hash_table_destroy(permit_set)
|
|
|
|
Each lookup is O(1): total work is O(B).
|
|
Returns operation count.
|
|
"""
|
|
permit_set = set()
|
|
ops = 0
|
|
for buddy in buddies:
|
|
ops += 1 # O(1) hash lookup
|
|
if buddy not in permit_set:
|
|
permit_set.add(buddy)
|
|
return ops
|
|
|
|
|
|
def make_buddies(n: int) -> list[str]:
|
|
return [f"buddy{i}@example.com" for i in range(n)]
|
|
|
|
|
|
def bench(n: int) -> tuple[float, float, float]:
|
|
buddies = make_buddies(n)
|
|
|
|
t0 = time.perf_counter()
|
|
ops_def = add_buddies_defective(list(buddies))
|
|
t1 = time.perf_counter()
|
|
ops_fix = add_buddies_fixed(list(buddies))
|
|
t2 = time.perf_counter()
|
|
|
|
ratio = ops_def / ops_fix
|
|
return ops_def, ops_fix, ratio
|
|
|
|
|
|
def test_correctness():
|
|
"""Both paths produce same deduplication result."""
|
|
buddies = ["alice@x.com", "bob@x.com", "alice@x.com", "carol@x.com"]
|
|
|
|
# defective: simulate permit list construction
|
|
permit_def = []
|
|
for b in buddies:
|
|
if b not in permit_def:
|
|
permit_def.append(b)
|
|
|
|
# fixed: hash set
|
|
permit_fix = list(dict.fromkeys(buddies))
|
|
|
|
assert permit_def == permit_fix, f"Mismatch: {permit_def} vs {permit_fix}"
|
|
print("correctness: PASS")
|
|
|
|
|
|
def test_speedup_100():
|
|
ops_def, ops_fix, ratio = bench(100)
|
|
print(f"B=100: defective={ops_def} ops, fixed={ops_fix} ops, ratio={ratio:.1f}x")
|
|
assert ratio > 20, f"Expected >20x speedup at B=100, got {ratio:.1f}x"
|
|
print("speedup B=100: PASS")
|
|
|
|
|
|
def test_speedup_1000():
|
|
ops_def, ops_fix, ratio = bench(1000)
|
|
print(f"B=1000: defective={ops_def} ops, fixed={ops_fix} ops, ratio={ratio:.1f}x")
|
|
assert ratio > 200, f"Expected >200x speedup at B=1000, got {ratio:.1f}x"
|
|
print("speedup B=1000: PASS")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import os
|
|
os.environ["PYTHONUNBUFFERED"] = "1"
|
|
|
|
print("pidgin-0001: add_all_buddies_to_permit_list O(B^2) -> O(B)")
|
|
print("=" * 60)
|
|
|
|
sizes = [50, 100, 200, 500, 1000, 2000]
|
|
for n in sizes:
|
|
ops_def, ops_fix, ratio = bench(n)
|
|
print(f"B={n:4d}: defective={ops_def:8d} ops | fixed={ops_fix:6d} ops | ratio={ratio:.1f}x")
|
|
|
|
print()
|
|
test_correctness()
|
|
test_speedup_100()
|
|
test_speedup_1000()
|
|
print()
|
|
print("ALL TESTS PASS")
|