You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cxf.apache.org by re...@apache.org on 2022/10/04 18:34:47 UTC
[cxf] branch main updated: Fix SortedArraySet remove, containsAll (#1003)
This is an automated email from the ASF dual-hosted git repository.
reta pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/cxf.git
The following commit(s) were added to refs/heads/main by this push:
new 96d6b41cc9 Fix SortedArraySet remove, containsAll (#1003)
96d6b41cc9 is described below
commit 96d6b41cc9d5cbcccc2cc822b678de65b0953565
Author: Knut Forkalsrud <kn...@impact.com>
AuthorDate: Tue Oct 4 11:34:39 2022 -0700
Fix SortedArraySet remove, containsAll (#1003)
* Fix remove, containsAll. Tweak add.
* test
* optimize containsAll
---
.../org/apache/cxf/common/util/SortedArraySet.java | 72 +++++++++++----------
.../apache/cxf/common/util/SortedArraySetTest.java | 74 ++++++++++++++++++++++
2 files changed, 113 insertions(+), 33 deletions(-)
diff --git a/core/src/main/java/org/apache/cxf/common/util/SortedArraySet.java b/core/src/main/java/org/apache/cxf/common/util/SortedArraySet.java
index 9c2b1394ad..9891fa9908 100644
--- a/core/src/main/java/org/apache/cxf/common/util/SortedArraySet.java
+++ b/core/src/main/java/org/apache/cxf/common/util/SortedArraySet.java
@@ -39,7 +39,7 @@ import java.util.concurrent.atomic.AtomicReference;
* If no data is stored in the Set, it uses very little memory. The backing
* array is created on demand.
*
- * This class is primarly useful for stuff that will be setup at startup, but
+ * This class is primarily useful for stuff that will be setup at startup, but
* then iterated over MANY times during runtime.
*
* @param <T>
@@ -71,25 +71,29 @@ public final class SortedArraySet<T> implements SortedSet<T> {
}
public boolean add(T o) {
- if (!contains(o)) {
- T[] tmp = data.get();
- T[] tmp2;
- if (tmp == null) {
- tmp2 = newArray(1);
- tmp2[0] = o;
- } else {
- tmp2 = newArray(tmp.length + 1);
- System.arraycopy(tmp, 0, tmp2, 0, tmp.length);
- tmp2[tmp2.length - 1] = o;
- Arrays.sort(tmp2);
- }
- if (!data.compareAndSet(tmp, tmp2)) {
- return add(o);
+ T[] tmp2;
+ T[] tmp = data.get();
+
+ if (tmp == null) {
+ tmp2 = newArray(1);
+ tmp2[0] = o;
+ } else {
+ int idx = Arrays.binarySearch(tmp, o);
+ if (idx >= 0) {
+ return false;
}
- return true;
+ // insertion point
+ idx = -idx - 1;
+ tmp2 = newArray(tmp.length + 1);
+ System.arraycopy(tmp, 0, tmp2, 0, idx);
+ tmp2[idx] = o;
+ System.arraycopy(tmp, idx, tmp2, idx + 1, tmp.length - idx);
+ }
+ if (!data.compareAndSet(tmp, tmp2)) {
+ return add(o);
}
- return false;
+ return true;
}
public boolean addAll(Collection<? extends T> c) {
boolean val = false;
@@ -99,11 +103,12 @@ public final class SortedArraySet<T> implements SortedSet<T> {
return val;
}
public boolean containsAll(Collection<?> c) {
- boolean val = false;
for (Object t : c) {
- val |= contains(t);
+ if (!contains(t)) {
+ return false;
+ }
}
- return val;
+ return true;
}
public boolean contains(Object o) {
@@ -138,20 +143,21 @@ public final class SortedArraySet<T> implements SortedSet<T> {
return false;
}
int idx = Arrays.binarySearch(tmp, o);
- if (idx != -1) {
- if (tmp.length == 1
- && !data.compareAndSet(tmp, null)) {
- return remove(o);
- }
- T[] tmp2 = newArray(tmp.length - 1);
+ if (idx < 0) {
+ return false;
+ }
+ T[] tmp2;
+ if (tmp.length == 1) { // last one
+ tmp2 = null;
+ } else {
+ tmp2 = newArray(tmp.length - 1);
System.arraycopy(tmp, 0, tmp2, 0, idx);
- System.arraycopy(tmp, idx + 1, tmp2, idx, tmp.length - 1 - idx);
- if (!data.compareAndSet(tmp, tmp2)) {
- return remove(o);
- }
- return true;
+ System.arraycopy(tmp, idx + 1, tmp2, idx, tmp2.length - idx);
+ }
+ if (!data.compareAndSet(tmp, tmp2)) {
+ return remove(o);
}
- return false;
+ return true;
}
@@ -225,7 +231,7 @@ public final class SortedArraySet<T> implements SortedSet<T> {
@Override
public void remove() {
if (idx > 0) {
- SortedArraySet.this.remove((Object)data[idx - 1]);
+ SortedArraySet.this.remove(data[idx - 1]);
}
}
}
diff --git a/core/src/test/java/org/apache/cxf/common/util/SortedArraySetTest.java b/core/src/test/java/org/apache/cxf/common/util/SortedArraySetTest.java
new file mode 100644
index 0000000000..6569a17a05
--- /dev/null
+++ b/core/src/test/java/org/apache/cxf/common/util/SortedArraySetTest.java
@@ -0,0 +1,74 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.cxf.common.util;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+
+public class SortedArraySetTest {
+
+ @Test
+ public void testRemove() {
+ SortedArraySet<Integer> set = new SortedArraySet<>();
+
+ assertTrue(set.add(17238));
+ assertEquals(1, set.size());
+
+ assertFalse(set.remove(17270));
+ assertEquals(1, set.size());
+
+ assertTrue(set.remove(17238));
+ assertEquals(0, set.size());
+ }
+
+
+ @Test
+ public void testAdd() {
+
+ Random rnd = new Random(1234567);
+ SortedArraySet<Integer> set = new SortedArraySet<>();
+ List<Integer> inputs = IntStream.generate(rnd::nextInt)
+ .limit(100).boxed().collect(Collectors.toList());
+ set.addAll(inputs);
+ Collections.sort(inputs);
+ assertEquals(inputs, Arrays.asList(set.toArray()));
+ }
+
+
+ @Test
+ public void testContainsAll() {
+ SortedArraySet<Integer> set = new SortedArraySet<>();
+ set.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8));
+ assertTrue(set.containsAll(Arrays.asList(2, 4, 6)));
+ assertFalse(set.containsAll(Arrays.asList(1, 2, 99)));
+ }
+
+}