1 files changed, 225 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/core/metis_NumberSet.c b/metis/ccnx/forwarder/metis/core/metis_NumberSet.c
new file mode 100644
index 00000000..6828014a
--- /dev/null
+++ b/metis/ccnx/forwarder/metis/core/metis_NumberSet.c
@@ -0,0 +1,225 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+
+/**
+ * Currently uses an unsorted array of numbers.
+ *
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <parc/algol/parc_Memory.h>
+#include <ccnx/forwarder/metis/core/metis_NumberSet.h>
+#include <parc/algol/parc_ArrayList.h>
+
+#include <LongBow/runtime.h>
+
+struct metis_number_set {
+    MetisNumber *arrayOfNumbers;
+    size_t length;
+    size_t limit;
+    unsigned refcount;
+};
+
+static void metisNumberSet_Expand(MetisNumberSet *set);
+
+MetisNumberSet *
+metisNumberSet_Create()
+{
+    MetisNumberSet *set = parcMemory_AllocateAndClear(sizeof(MetisNumberSet));
+    assertNotNull(set, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisNumberSet));
+    set->arrayOfNumbers = parcMemory_AllocateAndClear(sizeof(MetisNumber) * 16);
+    assertNotNull((set->arrayOfNumbers), "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisNumber) * 16);
+    set->length = 0;
+    set->limit = 16;
+    set->refcount = 1;
+    return set;
+}
+
+MetisNumberSet *
+metisNumberSet_Acquire(const MetisNumberSet *original)
+{
+    assertNotNull(original, "Parameter original must be non-null");
+    MetisNumberSet *copy = (MetisNumberSet *) original;
+    copy->refcount++;
+    return copy;
+}
+
+void
+metisNumberSet_Release(MetisNumberSet **setPtr)
+{
+    assertNotNull(setPtr, "Parameter must be non-null double pointer");
+    assertNotNull(*setPtr, "Parameter must dereference to non-null pointer");
+
+    MetisNumberSet *set = *setPtr;
+    assertTrue(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 metisNumberSet_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.
+ *
+ * @param <#param1#>
+ */
+static void
+metisNumberSet_AddNoChecks(MetisNumberSet *set, MetisNumber number)
+{
+    if (set->length == set->limit) {
+        metisNumberSet_Expand(set);
+    }
+
+    set->arrayOfNumbers[ set->length ] = number;
+    set->length++;
+}
+
+bool
+metisNumberSet_Add(MetisNumberSet *set, MetisNumber number)
+{
+    assertNotNull(set, "Parameter set must be non-null");
+    if (metisNumberSet_Contains(set, number)) {
+        return false;
+    }
+
+    metisNumberSet_AddNoChecks(set, number);
+    return true;
+}
+
+size_t
+metisNumberSet_Length(const MetisNumberSet *set)
+{
+    assertNotNull(set, "Parameter set must be non-null");
+    return set->length;
+}
+
+MetisNumber
+metisNumberSet_GetItem(const MetisNumberSet *set, size_t ordinalIndex)
+{
+    assertNotNull(set, "Parameter set must be non-null");
+    assertTrue(ordinalIndex < set->length, "Limit beyond end of set, length %zu got %zu", set->length, ordinalIndex);
+
+    return set->arrayOfNumbers[ordinalIndex];
+}
+
+bool
+metisNumberSet_Contains(const MetisNumberSet *set, MetisNumber number)
+{
+    assertNotNull(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
+metisNumberSet_AddSet(MetisNumberSet *destinationSet, const MetisNumberSet *setToAdd)
+{
+    assertNotNull(destinationSet, "Parameter destinationSet must be non-null");
+    assertNotNull(setToAdd, "Parameter setToAdd must be non-null");
+
+    for (size_t i = 0; i < setToAdd->length; i++) {
+        metisNumberSet_Add(destinationSet, setToAdd->arrayOfNumbers[i]);
+    }
+}
+
+MetisNumberSet *
+metisNumberSet_Subtract(const MetisNumberSet *minuend, const MetisNumberSet *subtrahend)
+{
+    // because the underlying ADT is not sorted, this is pretty ineffient, could be O(n^2).
+
+    MetisNumberSet *difference = metisNumberSet_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) {
+            metisNumberSet_AddNoChecks(difference, minuend->arrayOfNumbers[i]);
+        }
+    }
+    return difference;
+}
+
+bool
+metisNumberSet_Equals(const MetisNumberSet *a, const MetisNumberSet *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
+metisNumberSet_Remove(MetisNumberSet *set, MetisNumber number)
+{
+    assertNotNull(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
+metisNumberSet_Expand(MetisNumberSet *set)
+{
+    size_t newlimit = set->limit * 2;
+    size_t newbytes = newlimit * sizeof(MetisNumber);
+
+    set->arrayOfNumbers = parcMemory_Reallocate(set->arrayOfNumbers, newbytes);
+    set->limit = newlimit;
+}