russell@unturf.com
9934133dcf
Add 88 new defect entries to HIGH and MEDIUM tables:
HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002
MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
ovs-0001, onos-0003, odl-0002, jetty-0001
PDF: 976K
88 lines
3.1 KiB
Java
88 lines
3.1 KiB
Java
package unit;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.LinkedHashSet;
|
|
import java.util.List;
|
|
|
|
/**
|
|
* zookeeper-0001: PrepRequestProcessor.removeDuplicates — ArrayList.contains() O(n²)
|
|
* vs LinkedHashSet O(n).
|
|
*
|
|
* Standalone unit test — no JUnit required.
|
|
* Compile: javac -d . ZooKeeperAclDedupTest.java
|
|
* Run: java unit.ZooKeeperAclDedupTest
|
|
*
|
|
* ACL is modelled as a plain String (scheme:id:perms) — sufficient to demonstrate
|
|
* the algorithmic complexity without the Thrift dependency.
|
|
*/
|
|
public class ZooKeeperAclDedupTest {
|
|
|
|
static long slowOps;
|
|
static long fastOps;
|
|
|
|
/**
|
|
* Slow: mirrors PrepRequestProcessor.removeDuplicates() — ArrayList accumulator.
|
|
* retval.contains() scans the growing list for each of n ACLs → O(n²).
|
|
*/
|
|
static List<String> slowRemoveDuplicates(List<String> acls) {
|
|
slowOps = 0;
|
|
List<String> retval = new ArrayList<>(acls.size());
|
|
for (String acl : acls) {
|
|
slowOps++; // outer loop entry
|
|
boolean found = false;
|
|
for (String existing : retval) { // ArrayList.contains() scan — O(n)
|
|
slowOps++;
|
|
if (existing.equals(acl)) { found = true; break; }
|
|
}
|
|
if (!found) retval.add(acl);
|
|
}
|
|
return retval;
|
|
}
|
|
|
|
/**
|
|
* Fast: patched — LinkedHashSet for O(1) contains/add, preserves order.
|
|
*/
|
|
static List<String> fastRemoveDuplicates(List<String> acls) {
|
|
fastOps = 0;
|
|
LinkedHashSet<String> seen = new LinkedHashSet<>(acls.size() * 2);
|
|
for (String acl : acls) {
|
|
fastOps++; // O(1) hash add
|
|
seen.add(acl);
|
|
}
|
|
return new ArrayList<>(seen);
|
|
}
|
|
|
|
static void run(int n, int dupFraction, int expectedNx) {
|
|
// Build ACL list: n unique entries + n*dupFraction duplicates interleaved
|
|
List<String> acls = new ArrayList<>();
|
|
for (int i = 0; i < n; i++) acls.add("world:anyone:" + i);
|
|
for (int d = 0; d < dupFraction; d++) {
|
|
for (int i = 0; i < n; i++) acls.add("world:anyone:" + i);
|
|
}
|
|
|
|
List<String> slowResult = slowRemoveDuplicates(acls);
|
|
List<String> fastResult = fastRemoveDuplicates(acls);
|
|
|
|
boolean resultsMatch = slowResult.equals(fastResult);
|
|
boolean quadraticWorse = slowOps > fastOps * expectedNx;
|
|
|
|
System.out.printf("n=%-4d dups=%-2dx slow=%7d fast=%5d ratio=%5.1fx match=%b PASS=%b%n",
|
|
n, dupFraction, slowOps, fastOps, (double) slowOps / fastOps, resultsMatch,
|
|
resultsMatch && quadraticWorse);
|
|
|
|
if (!resultsMatch || !quadraticWorse) {
|
|
throw new AssertionError(
|
|
"FAIL n=" + n + " resultsMatch=" + resultsMatch +
|
|
" slowOps=" + slowOps + " fastOps=" + fastOps +
|
|
" needed ratio>" + expectedNx);
|
|
}
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("=== zookeeper-0001: ACL removeDuplicates O(n^2) vs O(n) ===");
|
|
run(50, 2, 5);
|
|
run(200, 2, 15);
|
|
run(500, 2, 30);
|
|
System.out.println("3/3 PASS");
|
|
}
|
|
}
|