aboutsummaryrefslogtreecommitdiffstats
path: root/hicn-light/src/core/numberSet.c
diff options
context:
space:
mode:
authorLuca Muscariello <lumuscar+fdio@cisco.com>2019-01-17 13:47:57 +0100
committerLuca Muscariello <lumuscar+fdio@cisco.com>2019-01-17 16:32:51 +0100
commitbac3da61644515f05663789b122554dc77549286 (patch)
tree898210bc8e70371d77de7d446a26c5dd4fd1165a /hicn-light/src/core/numberSet.c
parentd5165246787301d0f13b646fda5e8a8567aef5ac (diff)
This is the first commit of the hicn projectv19.01
Change-Id: I6f2544ad9b9f8891c88cc4bcce3cf19bd3cc863f Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>
Diffstat (limited to 'hicn-light/src/core/numberSet.c')
-rwxr-xr-xhicn-light/src/core/numberSet.c203
1 files changed, 203 insertions, 0 deletions
diff --git a/hicn-light/src/core/numberSet.c b/hicn-light/src/core/numberSet.c
new file mode 100755
index 000000000..75fec1524
--- /dev/null
+++ b/hicn-light/src/core/numberSet.c
@@ -0,0 +1,203 @@
+/*
+ * Copyright (c) 2017-2019 Cisco and/or its affiliates.
+ * Licensed 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.
+ */
+
+#include <parc/algol/parc_ArrayList.h>
+#include <parc/algol/parc_Memory.h>
+#include <src/config.h>
+#include <src/core/numberSet.h>
+#include <stdio.h>
+
+#include <parc/assert/parc_Assert.h>
+
+struct number_set {
+ Number *arrayOfNumbers;
+ size_t length;
+ size_t limit;
+ unsigned refcount;
+};
+
+static void numberSet_Expand(NumberSet *set);
+
+NumberSet *numberSet_Create() {
+ NumberSet *set = parcMemory_AllocateAndClear(sizeof(NumberSet));
+ parcAssertNotNull(set, "parcMemory_AllocateAndClear(%zu) returned NULL",
+ sizeof(NumberSet));
+ set->arrayOfNumbers = parcMemory_AllocateAndClear(sizeof(Number) * 16);
+ parcAssertNotNull((set->arrayOfNumbers),
+ "parcMemory_AllocateAndClear(%zu) returned NULL",
+ sizeof(Number) * 16);
+ set->length = 0;
+ set->limit = 16;
+ set->refcount = 1;
+ return set;
+}
+
+NumberSet *numberSet_Acquire(const NumberSet *original) {
+ parcAssertNotNull(original, "Parameter original must be non-null");
+ NumberSet *copy = (NumberSet *)original;
+ copy->refcount++;
+ return copy;
+}
+
+void numberSet_Release(NumberSet **setPtr) {
+ parcAssertNotNull(setPtr, "Parameter must be non-null double pointer");
+ parcAssertNotNull(*setPtr, "Parameter must dereference to non-null pointer");
+
+ NumberSet *set = *setPtr;
+ parcAssertTrue(
+ set->refcount > 0,
+ "Invalid state: calling destroy on an object with 0 reference count");
+ set->refcount--;
+
+ if (set->refcount == 0) {
+ parcMemory_Deallocate((void **)&(set->arrayOfNumbers));
+ parcMemory_Deallocate((void **)&set);
+ *setPtr = NULL;
+ }
+}
+
+/**
+ * @function numberSet_AddNoChecks
+ * @abstract Add a number we know is not already in the set
+ * @discussion
+ * Used by other functions that already know the number is unique in the set,
+ * Does not do the expensive Contains check.
+ */
+static void numberSet_AddNoChecks(NumberSet *set, Number number) {
+ if (set->length == set->limit) {
+ numberSet_Expand(set);
+ }
+
+ set->arrayOfNumbers[set->length] = number;
+ set->length++;
+}
+
+bool numberSet_Add(NumberSet *set, Number number) {
+ parcAssertNotNull(set, "Parameter set must be non-null");
+ if (numberSet_Contains(set, number)) {
+ return false;
+ }
+
+ numberSet_AddNoChecks(set, number);
+ return true;
+}
+
+size_t numberSet_Length(const NumberSet *set) {
+ parcAssertNotNull(set, "Parameter set must be non-null");
+ return set->length;
+}
+
+Number numberSet_GetItem(const NumberSet *set, size_t ordinalIndex) {
+ parcAssertNotNull(set, "Parameter set must be non-null");
+ parcAssertTrue(ordinalIndex < set->length,
+ "Limit beyond end of set, length %zu got %zu", set->length,
+ ordinalIndex);
+
+ return set->arrayOfNumbers[ordinalIndex];
+}
+
+bool numberSet_Contains(const NumberSet *set, Number number) {
+ parcAssertNotNull(set, "Parameter set must be non-null");
+ for (size_t i = 0; i < set->length; i++) {
+ if (set->arrayOfNumbers[i] == number) {
+ return true;
+ }
+ }
+ return false;
+}
+
+void numberSet_AddSet(NumberSet *destinationSet, const NumberSet *setToAdd) {
+ parcAssertNotNull(destinationSet,
+ "Parameter destinationSet must be non-null");
+ parcAssertNotNull(setToAdd, "Parameter setToAdd must be non-null");
+
+ for (size_t i = 0; i < setToAdd->length; i++) {
+ numberSet_Add(destinationSet, setToAdd->arrayOfNumbers[i]);
+ }
+}
+
+NumberSet *numberSet_Subtract(const NumberSet *minuend,
+ const NumberSet *subtrahend) {
+ // because the underlying ADT is not sorted, this is pretty ineffient, could
+ // be O(n^2).
+
+ NumberSet *difference = numberSet_Create();
+
+ for (size_t i = 0; i < minuend->length; i++) {
+ bool unique = true;
+ for (size_t j = 0; j < subtrahend->length && unique; j++) {
+ if (minuend->arrayOfNumbers[i] == subtrahend->arrayOfNumbers[j]) {
+ unique = false;
+ }
+ }
+
+ if (unique) {
+ numberSet_AddNoChecks(difference, minuend->arrayOfNumbers[i]);
+ }
+ }
+ return difference;
+}
+
+bool numberSet_Equals(const NumberSet *a, const NumberSet *b) {
+ if (a == NULL && b == NULL) {
+ return true;
+ }
+
+ if (a == NULL || b == NULL) {
+ return false;
+ }
+
+ if (a->length == b->length) {
+ for (size_t i = 0; i < a->length; i++) {
+ bool found = false;
+ for (size_t j = 0; j < b->length && !found; j++) {
+ if (a->arrayOfNumbers[i] == b->arrayOfNumbers[j]) {
+ found = true;
+ }
+ }
+ if (!found) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ return false;
+}
+
+void numberSet_Remove(NumberSet *set, Number number) {
+ parcAssertNotNull(set, "Parameter set must be non-null");
+ for (size_t i = 0; i < set->length; i++) {
+ if (set->arrayOfNumbers[i] == number) {
+ set->length--;
+ if (set->length > 0) {
+ // move the last element to the removed element to keep the array
+ // packed.
+ set->arrayOfNumbers[i] = set->arrayOfNumbers[set->length];
+ }
+ return;
+ }
+ }
+}
+
+// =====================================================
+
+static void numberSet_Expand(NumberSet *set) {
+ size_t newlimit = set->limit * 2;
+ size_t newbytes = newlimit * sizeof(Number);
+
+ set->arrayOfNumbers = parcMemory_Reallocate(set->arrayOfNumbers, newbytes);
+ set->limit = newlimit;
+}