diff options
Diffstat (limited to 'hicn-light/src/content_store')
| -rwxr-xr-x | hicn-light/src/content_store/CMakeLists.txt | 33 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreEntry.c | 136 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreEntry.h | 146 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreInterface.c | 57 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreInterface.h | 211 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreLRU.c | 455 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/contentStoreLRU.h | 39 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/listLRU.c | 133 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/listLRU.h | 94 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/listTimeOrdered.c | 94 | ||||
| -rwxr-xr-x | hicn-light/src/content_store/listTimeOrdered.h | 103 |
11 files changed, 1501 insertions, 0 deletions
diff --git a/hicn-light/src/content_store/CMakeLists.txt b/hicn-light/src/content_store/CMakeLists.txt new file mode 100755 index 000000000..85643cf5e --- /dev/null +++ b/hicn-light/src/content_store/CMakeLists.txt @@ -0,0 +1,33 @@ +# 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. + +cmake_minimum_required(VERSION 3.5 FATAL_ERROR) + +list(APPEND HEADER_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreEntry.h + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreInterface.h + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreLRU.h + ${CMAKE_CURRENT_SOURCE_DIR}/listTimeOrdered.h + ${CMAKE_CURRENT_SOURCE_DIR}/listLRU.h +) + +list(APPEND SOURCE_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreInterface.c + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreLRU.c + ${CMAKE_CURRENT_SOURCE_DIR}/listLRU.c + ${CMAKE_CURRENT_SOURCE_DIR}/listTimeOrdered.c + ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreEntry.c +) + +set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) +set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE)
\ No newline at end of file diff --git a/hicn-light/src/content_store/contentStoreEntry.c b/hicn-light/src/content_store/contentStoreEntry.c new file mode 100755 index 000000000..d36ed61a0 --- /dev/null +++ b/hicn-light/src/content_store/contentStoreEntry.c @@ -0,0 +1,136 @@ +/* + * 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 <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_Memory.h> +#include <src/content_store/contentStoreEntry.h> + +#include <parc/assert/parc_Assert.h> + +const uint64_t contentStoreEntry_MaxExpiryTime = UINT64_MAX; + +struct contentstore_entry { + Message *message; + ListLruEntry *lruEntry; + unsigned refcount; + bool hasExpiryTimeTicks; + uint64_t expiryTimeTicks; +}; + +ContentStoreEntry *contentStoreEntry_Create(Message *contentMessage, + ListLru *listLRU) { + parcAssertNotNull(contentMessage, "Parameter objectMessage must be non-null"); + + ContentStoreEntry *entry = + parcMemory_AllocateAndClear(sizeof(ContentStoreEntry)); + parcAssertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(ContentStoreEntry)); + entry->message = message_Acquire(contentMessage); + entry->refcount = 1; + + if (listLRU != NULL) { + entry->lruEntry = listLRU_NewHeadEntry(listLRU, entry); + } + + entry->hasExpiryTimeTicks = message_HasContentExpiryTime(contentMessage); + + if (entry->hasExpiryTimeTicks) { + entry->expiryTimeTicks = message_GetContentExpiryTimeTicks(contentMessage); + } + + return entry; +} + +ContentStoreEntry *contentStoreEntry_Acquire( + const ContentStoreEntry *original) { + parcAssertNotNull(original, "Parameter must be non-null"); + ((ContentStoreEntry *)original)->refcount++; + return (ContentStoreEntry *)original; +} + +void contentStoreEntry_Release(ContentStoreEntry **entryPtr) { + parcAssertNotNull(entryPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*entryPtr, + "Parameter must dereference to non-null pointer"); + + ContentStoreEntry *entry = *entryPtr; + parcAssertTrue(entry->refcount > 0, "Illegal state: has refcount of 0"); + + entry->refcount--; + if (entry->refcount == 0) { + if (entry->lruEntry) { + listLRU_EntryDestroy(&entry->lruEntry); + } + message_Release(&entry->message); + parcMemory_Deallocate((void **)&entry); + } + *entryPtr = NULL; +} + +Message *contentStoreEntry_GetMessage(const ContentStoreEntry *storeEntry) { + parcAssertNotNull(storeEntry, "Parameter must be non-null"); + return storeEntry->message; +} + +bool contentStoreEntry_HasExpiryTimeTicks(const ContentStoreEntry *storeEntry) { + parcAssertNotNull(storeEntry, "Parameter must be non-null"); + return storeEntry->hasExpiryTimeTicks; +} + +uint64_t contentStoreEntry_GetExpiryTimeTicks( + const ContentStoreEntry *storeEntry) { + parcAssertNotNull(storeEntry, "Parameter must be non-null"); + parcAssertTrue(storeEntry->hasExpiryTimeTicks, + "storeEntry has no ExpiryTimeTicks. Did you call " + "contentStoreEntry_HasExpiryTimeTicks() first?"); + return storeEntry->expiryTimeTicks; +} + +int contentStoreEntry_CompareExpiryTime(const ContentStoreEntry *value1, + const ContentStoreEntry *value2) { + // A signum comparison. negative if key 1 is smaller, 0 if key1 == key2, + // greater than 0 if key1 is bigger. + + ContentStoreEntry *v1 = (ContentStoreEntry *)value1; + ContentStoreEntry *v2 = (ContentStoreEntry *)value2; + + if (v1->expiryTimeTicks < v2->expiryTimeTicks) { + return -1; + } else if (v1->expiryTimeTicks > v2->expiryTimeTicks) { + return +1; + } else { + // At this point, the times are the same. Use the address of the message as + // the decider. This allows us to store multiple messages with the same + // expiry/cache time. + if (v1->message < v2->message) { + return -1; + } else if (v1->message > v2->message) { + return +1; + } + } + + return 0; // The same message has been encountered. +} + +void contentStoreEntry_MoveToHead(ContentStoreEntry *storeEntry) { + parcAssertNotNull(storeEntry, "Parameter must be non-null"); + parcAssertNotNull(storeEntry->lruEntry, + "ContentStoreEntry is not attached to an ListLru"); + if (storeEntry->lruEntry) { + listLRU_EntryMoveToHead(storeEntry->lruEntry); + } +} diff --git a/hicn-light/src/content_store/contentStoreEntry.h b/hicn-light/src/content_store/contentStoreEntry.h new file mode 100755 index 000000000..766cc15e4 --- /dev/null +++ b/hicn-light/src/content_store/contentStoreEntry.h @@ -0,0 +1,146 @@ +/* + * 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. + */ + +#ifndef contentStoreEntry_h +#define contentStoreEntry_h + +#include <src/content_store/listLRU.h> +#include <src/core/message.h> + +struct contentstore_entry; +typedef struct contentstore_entry ContentStoreEntry; + +/** + * The max time allowed for an ExpiryTime. Will never be exceeded. + */ +extern const uint64_t contentStoreEntry_MaxExpiryTime; + +/** + * Creates a new `ContentStoreEntry` instance, acquiring a reference to the + * supplied `Message`. + * + * @param message the message to store + * @param listLRU the LRU list that this entry will be stored in. + * @return A newly created `ContentStoreEntry` instance that must eventually be + * released by calling + * {@link contentStoreEntry_Release}. + * + * @see contentStoreEntry_Release + */ +ContentStoreEntry *contentStoreEntry_Create(Message *objectMessage, + ListLru *listLRU); + +/** + * Returns a reference counted copy of the supplied `ContentStoreEntry`. + * + * @param original the ContentStoreEntry to return a reference to. + * @return Reference counted copy, must call + * <code>contentStoreEntry_Destroy()</code> on it. + */ +ContentStoreEntry *contentStoreEntry_Acquire(const ContentStoreEntry *original); + +/** + * Releases one reference count and destroys object when reaches zero + * + * @param [in,out] entryPtr A pointer to an allocated ContentStoreEntry + * + */ +void contentStoreEntry_Release(ContentStoreEntry **entryPtr); + +/** + * Returns a pointer to the contained {@link Message}. + * The caller must called {@link message_Acquire()} if they want to keep a + * reference to the returned message. + * + * @param storeEntry the ContentStoreEntry from which to retrieve the `Message` + * pointer. + * @return the address of the `Message` contained in the storeEntry. + * @see message_Acquire + */ +Message *contentStoreEntry_GetMessage(const ContentStoreEntry *storeEntry); + +/** + * Return true if the message stored in this `ContentStoreEntry` has an + * ExpiryTime. + * + * @param storeEntry the ContentStoreEntry containing the message. + * @return true if the referenced message has an ExpiryTime. False, otherwise. + */ +bool contentStoreEntry_HasExpiryTimeTicks(const ContentStoreEntry *storeEntry); + +/** + * Return the ExpiryTime stored in this `ContentStoreEntry`. + * + * @param storeEntry the ContentStoreEntry from which to retrieve the `Message` + * pointer. + * @return the address of the `Message` contained in the storeEntry. + */ +uint64_t contentStoreEntry_GetExpiryTimeTicks( + const ContentStoreEntry *storeEntry); + +/** + * A signum function comparing two `ContentStoreEntry` instances, using their + * ExpiryTime and, if necessary, the addresses of the referenced Message. In + * other words, if two ContentStoreEntries have the same ExpiryTime, the + * comparison will then be made on the memory addresses of the Messages + * referenced by the ContentStoreEntrys. So, the only way two ContentStoreEntrys + * will compare equally (0) is if they both have the same ExpiryTime and + * reference the same Message. + * + * Used to determine the ordering relationship of two `ContentStoreEntry` + * instances. This is used by the {@link ListTimeOrdered} to keep a list of + * ContentStoreEntrys, sorted by ExpiryTime. + * + * @param [in] storeEntry1 A pointer to a `ContentStoreEntry` instance. + * @param [in] storeEntry2 A pointer to a `ContentStoreEntry` instance to be + * compared to `storeEntry1`. + * + * @return 0 if `storeEntry1` and `storeEntry2` are equivalent + * @return < 0 if `storeEntry1` < `storeEntry2` + * @return > 0 if `storeEntry1` > `storeEntry2` + * + * Example: + * @code + * { + * ContentStoreEntry *entry1 = contentStoreEntry_Create(...); + * ContentStoreEntry *entry2 = contentStoreEntry_Create(...); + * + * int val = contentStoreEntry_CompareExpiryTime(entry1, entry2); + * if (val < 0) { + * // entry1 has a lower ExpiryTime, or the same ExpiryTime as entry2 + * and a different message. } else if (val > 0) { + * // entry2 has a lower ExpiryTime, or the same ExpiryTime as entry1 + * and a different message. } else { + * // entry1 and entry2 have the same ExpiryTime AND the same message. + * } + * + * contentStoreEntry_Release(&entry1); + * contentStoreEntry_Release(&entry2); + * + * } + * @endcode + */ +int contentStoreEntry_CompareExpiryTime(const ContentStoreEntry *storeEntry1, + const ContentStoreEntry *storeEntry2); + +/** + * Move this entry to the head of the LRU list + * + * Moves the entry to the head of the LRU list it was created with + * + * @param [in] storeEntry An allocated ContenstoreEntry + */ +void contentStoreEntry_MoveToHead(ContentStoreEntry *storeEntry); +#endif // contentStoreEntry_h diff --git a/hicn-light/src/content_store/contentStoreInterface.c b/hicn-light/src/content_store/contentStoreInterface.c new file mode 100755 index 000000000..a42041670 --- /dev/null +++ b/hicn-light/src/content_store/contentStoreInterface.c @@ -0,0 +1,57 @@ +/* + * 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 <src/config.h> +#include <stdio.h> + +#include <src/content_store/contentStoreInterface.h> + +void contentStoreInterface_Release(ContentStoreInterface **storeImplPtr) { + (*storeImplPtr)->release(storeImplPtr); +} + +bool contentStoreInterface_PutContent(ContentStoreInterface *storeImpl, + Message *content, + uint64_t currentTimeTicks) { + return storeImpl->putContent(storeImpl, content, currentTimeTicks); +} + +bool contentStoreInterface_RemoveContent(ContentStoreInterface *storeImpl, + Message *content) { + return storeImpl->removeContent(storeImpl, content); +} + +Message *contentStoreInterface_MatchInterest(ContentStoreInterface *storeImpl, + Message *interest, + uint64_t currentTimeTicks) { + return storeImpl->matchInterest(storeImpl, interest, currentTimeTicks); +} + +size_t contentStoreInterface_GetObjectCapacity( + ContentStoreInterface *storeImpl) { + return storeImpl->getObjectCapacity(storeImpl); +} + +size_t contentStoreInterface_GetObjectCount(ContentStoreInterface *storeImpl) { + return storeImpl->getObjectCount(storeImpl); +} + +void contentStoreInterface_Log(ContentStoreInterface *storeImpl) { + storeImpl->log(storeImpl); +} + +void *contentStoreInterface_GetPrivateData(ContentStoreInterface *storeImpl) { + return storeImpl->_privateData; +} diff --git a/hicn-light/src/content_store/contentStoreInterface.h b/hicn-light/src/content_store/contentStoreInterface.h new file mode 100755 index 000000000..d73c63019 --- /dev/null +++ b/hicn-light/src/content_store/contentStoreInterface.h @@ -0,0 +1,211 @@ +/* + * 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. + */ + +#ifndef contentStoreInterface_h +#define contentStoreInterface_h + +#include <stdio.h> + +#include <src/core/message.h> + +typedef struct contentstore_config { + size_t objectCapacity; +} ContentStoreConfig; + +typedef struct contentstore_interface ContentStoreInterface; + +struct contentstore_interface { + /** + * Place a Message representing a ContentObject into the ContentStore. If + * necessary to make room, remove expired content or content that has exceeded + * the Recommended Cache Time. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param content - a pointer to a `Message` to place in the store. + * @param currentTimeTicks - the current time, in hicn-light ticks, since the + * UTC epoch. + */ + bool (*putContent)(ContentStoreInterface *storeImpl, Message *content, + uint64_t currentTimeTicks); + + /** + * The function to call to remove content from the ContentStore. + * It will Release any references that were created when the content was + * placed into the ContentStore. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param content - a pointer to a `Message` to remove from the store. + */ + bool (*removeContent)(ContentStoreInterface *storeImpl, Message *content); + + /** + * Given a Message that represents and Interest, try to find a matching + * ContentObject. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param interest - a pointer to a `Message` representing the Interest to + * match. + * + * @return a pointer to a Message containing the matching ContentObject + * @return NULL if no matching ContentObject was found + */ + Message *(*matchInterest)(ContentStoreInterface *storeImpl, Message *interest, + uint64_t currentTimeTicks); + + /** + * Return the maximum number of ContentObjects that can be stored in this + * ContentStore. This is a raw count, not based on memory size. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * + * @return the maximum number of ContentObjects that can be stored + */ + size_t (*getObjectCapacity)(ContentStoreInterface *storeImpl); + + /** + * Return the number of ContentObjects currently stored in the ContentStore. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * + * @return the current number of ContentObjects in the ContentStore + */ + size_t (*getObjectCount)(ContentStoreInterface *storeImpl); + + /** + * Log a ContentStore implementation specific version of store-related + * information. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ + void (*log)(ContentStoreInterface *storeImpl); + + /** + * Acquire a new reference to the specified ContentStore instance. This + * reference will eventually need to be released by calling {@link + * contentStoreInterface_Release}. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ + ContentStoreInterface *(*acquire)(const ContentStoreInterface *storeImpl); + + /** + * Release the ContentStore, which will also Release any references held by + * it. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ + void (*release)(ContentStoreInterface **storeImpl); + + /** + * A pointer to opaque private data used by the ContentStore instance + * represented by this instance of ContentStoreInterface. + */ + void *_privateData; +}; + +/** + * Place a Message representing a ContentObject into the ContentStore. If + * necessary to make room, remove expired content or content that has exceeded + * the Recommended Cache Time. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param content - a pointer to a `Message` to place in the store. + * + * @param currentTimeTicks - the current time, in hicn-light ticks, since the + * UTC epoch. + */ +bool contentStoreInterface_PutContent(ContentStoreInterface *storeImpl, + Message *content, + uint64_t currentTimeTicks); + +/** + * The function to call to remove content from the ContentStore. + * It will Release any references that were created when the content was placed + * into the ContentStore. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param content - a pointer to a `Message` to remove from the store. + */ +bool contentStoreInterface_RemoveContent(ContentStoreInterface *storeImpl, + Message *content); + +/** + * Given a Message that represents and Interest, try to find a matching + * ContentObject. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * @param interest - a pointer to a `Message` representing the Interest to + * match. + * + * @return a pointer to a Message containing the matching ContentObject + * @return NULL if no matching ContentObject was found + */ +Message *contentStoreInterface_MatchInterest(ContentStoreInterface *storeImpl, + Message *interest, + uint64_t currentTimeTicks); + +/** + * Return the maximum number of ContentObjects that can be stored in this + * ContentStore. This is a raw count, not based on memory size. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * + * @return the maximum number of ContentObjects that can be stored + */ +size_t contentStoreInterface_GetObjectCapacity( + ContentStoreInterface *storeImpl); + +/** + * Return the number of ContentObjects currently stored in the ContentStore. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + * + * @return the current number of ContentObjects in the ContentStore + */ +size_t contentStoreInterface_GetObjectCount(ContentStoreInterface *storeImpl); + +/** + * Loga ContentStore implementation specific version of store-related + * information. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ +void contentStoreInterface_Log(ContentStoreInterface *storeImpl); + +/** + * Acquire a new reference to the specified ContentStore instance. This + * reference will eventually need to be released by calling {@link + * contentStoreInterface_Release}. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ +ContentStoreInterface *contentStoreInterface_Aquire( + const ContentStoreInterface *storeImpl); + +/** + * Release the ContentStore, which will also Release any references held by it. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ +void contentStoreInterface_Release(ContentStoreInterface **storeImplPtr); + +/** + * Return a pointer to the data private to this implementation of the + * ContentStore interface. + * + * @param storeImpl - a pointer to this ContentStoreInterface instance. + */ +void *contentStoreInterface_GetPrivateData(ContentStoreInterface *storeImpl); +#endif // contentStoreInterface_h diff --git a/hicn-light/src/content_store/contentStoreLRU.c b/hicn-light/src/content_store/contentStoreLRU.c new file mode 100755 index 000000000..9b69d51c0 --- /dev/null +++ b/hicn-light/src/content_store/contentStoreLRU.c @@ -0,0 +1,455 @@ +/* + * 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 <src/config.h> +#include <stdio.h> +#include <sys/queue.h> + +#include <parc/algol/parc_DisplayIndented.h> +#include <parc/algol/parc_HashCodeTable.h> +#include <parc/algol/parc_Object.h> + +#include <src/core/logger.h> + +#include <src/content_store/contentStoreLRU.h> + +#include <src/content_store/contentStoreEntry.h> +#include <src/content_store/contentStoreInterface.h> +#include <src/content_store/listLRU.h> +#include <src/content_store/listTimeOrdered.h> + +#include <parc/assert/parc_Assert.h> +#include <src/processor/hashTableFunction.h> + +typedef struct contentstore_stats { + uint64_t countExpiryEvictions; + uint64_t countRCTEvictions; + uint64_t countLruEvictions; + uint64_t countAdds; + uint64_t countHits; + uint64_t countMisses; +} _ContentStoreLRUStats; + +typedef struct contentstore_lru_data { + size_t objectCapacity; + size_t objectCount; + + Logger *logger; + + // This LRU is just for keeping track of insertion and access order. + ListLru *lru; + + ListTimeOrdered *indexByExpirationTime; + + PARCHashCodeTable *storageByName; + + _ContentStoreLRUStats stats; +} _ContentStoreLRU; + +static void _destroyIndexes(_ContentStoreLRU *store) { + if (store->indexByExpirationTime != NULL) { + listTimeOrdered_Release(&(store->indexByExpirationTime)); + } + + if (store->storageByName != NULL) { + parcHashCodeTable_Destroy(&(store->storageByName)); + } + + if (store->lru != NULL) { + listLRU_Destroy(&(store->lru)); + } +} + +static void _contentStoreInterface_Destroy( + ContentStoreInterface **storeImplPtr) { + _ContentStoreLRU *store = contentStoreInterface_GetPrivateData(*storeImplPtr); + + parcObject_Release((PARCObject **)&store); +} + +static bool _contentStoreLRU_Destructor(_ContentStoreLRU **storePtr) { + _ContentStoreLRU *store = *storePtr; + + _destroyIndexes(store); + logger_Release(&store->logger); + + return true; +} + +parcObject_Override(_ContentStoreLRU, PARCObject, + .destructor = (PARCObjectDestructor *) + _contentStoreLRU_Destructor); + +parcObject_ExtendPARCObject(ContentStoreInterface, + _contentStoreInterface_Destroy, NULL, NULL, NULL, + NULL, NULL, NULL); + +static parcObject_ImplementAcquire(_contentStoreLRU, ContentStoreInterface); +static parcObject_ImplementRelease(_contentStoreLRU, ContentStoreInterface); + +static void _hashTableFunction_ContentStoreEntryDestroyer(void **dataPtr) { + contentStoreEntry_Release((ContentStoreEntry **)dataPtr); +} + +static bool _contentStoreLRU_Init(_ContentStoreLRU *store, + ContentStoreConfig *config, Logger *logger) { + bool result = false; + + store->logger = logger_Acquire(logger); + + size_t initialSize = config->objectCapacity * 2; + memset(&store->stats, 0, sizeof(_ContentStoreLRUStats)); + + store->objectCapacity = config->objectCapacity; + store->objectCount = 0; + + // initial size must be at least 1 or else the data structures break. + initialSize = (initialSize == 0) ? 1 : initialSize; + + store->indexByExpirationTime = listTimeOrdered_Create( + (TimeOrderList_KeyCompare *)contentStoreEntry_CompareExpiryTime); + + store->storageByName = parcHashCodeTable_Create_Size( + hashTableFunction_MessageNameEquals, + hashTableFunction_MessageNameHashCode, NULL, + _hashTableFunction_ContentStoreEntryDestroyer, initialSize); + + store->lru = listLRU_Create(); + + // If any of the index tables couldn't be allocated, we can't continue. + if ((store->indexByExpirationTime == NULL) || + (store->storageByName == NULL) || (store->lru == NULL)) { + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Error)) { + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Error, + __func__, + "ContentStoreLRU could not be created. Could not allocate all " + "index tables.", + (void *)store, store->objectCapacity); + } + + _destroyIndexes(store); + result = false; + } else { + result = true; + } + return result; +} + +/** + * Remove a ContentStoreEntry from all tables and indices. + */ +static void _contentStoreLRU_PurgeStoreEntry(_ContentStoreLRU *store, + ContentStoreEntry *entryToPurge) { + if (contentStoreEntry_HasExpiryTimeTicks(entryToPurge)) { + listTimeOrdered_Remove(store->indexByExpirationTime, entryToPurge); + } + + Message *content = contentStoreEntry_GetMessage(entryToPurge); + + // This _Del call will call the Release/Destroy on the ContentStoreEntry, + // which will remove it from the LRU as well. + parcHashCodeTable_Del(store->storageByName, content); + + store->objectCount--; +} + +static bool _contentStoreLRU_RemoveLeastUsed(_ContentStoreLRU *store) { + bool result = false; + + if (store->objectCount > 0) { + ListLruEntry *lruEntry = listLRU_PopTail(store->lru); + ContentStoreEntry *storeEntry = + (ContentStoreEntry *)listLRU_EntryGetData(lruEntry); + + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log( + store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "ContentStore %p evict message %p by LRU (LRU evictions %" PRIu64 ")", + (void *)store, (void *)contentStoreEntry_GetMessage(storeEntry), + store->stats.countLruEvictions); + } + + _contentStoreLRU_PurgeStoreEntry(store, storeEntry); + + result = true; + } + return result; +} + +static void _evictByStorePolicy(_ContentStoreLRU *store, + uint64_t currentTimeInTicks) { + // We need to make room. Here's the plan: + // 1) Check to see if anything has expired. If so, remove it and we're done. + // If not, 2) Remove the least recently used item. + + ContentStoreEntry *entry = + listTimeOrdered_GetOldest(store->indexByExpirationTime); + if (entry && contentStoreEntry_HasExpiryTimeTicks(entry) && + (currentTimeInTicks > contentStoreEntry_GetExpiryTimeTicks(entry))) { + // Found an expired entry. Remove it, and we're done. + + store->stats.countExpiryEvictions++; + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "ContentStore %p evict message %p by ExpiryTime (ExpiryTime " + "evictions %" PRIu64 ")", + (void *)store, (void *)contentStoreEntry_GetMessage(entry), + store->stats.countExpiryEvictions); + } + + _contentStoreLRU_PurgeStoreEntry(store, entry); + } else { + store->stats.countLruEvictions++; + _contentStoreLRU_RemoveLeastUsed(store); + } +} + +static bool _contentStoreLRU_PutContent(ContentStoreInterface *storeImpl, + Message *content, + uint64_t currentTimeTicks) + +{ + bool result = false; + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + parcAssertNotNull(store, "Parameter store must be non-null"); + parcAssertNotNull(content, "Parameter objectMessage must be non-null"); + + parcAssertTrue(message_GetType(content) == MessagePacketType_ContentObject, + "Parameter objectMessage must be a Content Object"); + + if (store->objectCapacity == 0) { + return false; + } + + uint64_t expiryTimeTicks = contentStoreEntry_MaxExpiryTime; + + if (message_HasContentExpiryTime(content)) { + expiryTimeTicks = message_GetContentExpiryTimeTicks(content); + } + // Don't add anything that's already expired or has exceeded RCT. + if (currentTimeTicks >= expiryTimeTicks) { + return false; + } + + if (store->objectCount >= store->objectCapacity) { + // Store is full. Need to make room. + _evictByStorePolicy(store, currentTimeTicks); + } + + // And now add a new entry to the head of the LRU. + + ContentStoreEntry *entry = contentStoreEntry_Create(content, store->lru); + + if (entry != NULL) { + if (parcHashCodeTable_Add(store->storageByName, content, entry)) { + if (contentStoreEntry_HasExpiryTimeTicks(entry)) { + listTimeOrdered_Add(store->indexByExpirationTime, entry); + } + + store->objectCount++; + store->stats.countAdds++; + + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "ContentStoreLRU %p saved message %p (object count %" PRIu64 + ")", + (void *)store, (void *)content, store->objectCount); + } + + result = true; + } else { + // Free what we just created, but did not add. 'entry' has ownership of + // 'copy', and so will call _Release() on it + contentStoreEntry_Release(&entry); + + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Warning)) { + logger_Log(store->logger, LoggerFacility_Processor, + PARCLogLevel_Warning, __func__, + "ContentStoreLRU %p failed to add message %p to hash table", + (void *)store, (void *)content); + } + } + } + + return result; +} + +static Message *_contentStoreLRU_MatchInterest(ContentStoreInterface *storeImpl, + Message *interest, + uint64_t currentTimeTicks) { + Message *result = NULL; + + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + + parcAssertNotNull(store, "Parameter store must be non-null"); + parcAssertNotNull(interest, "Parameter interestMessage must be non-null"); + parcAssertTrue(message_GetType(interest) == MessagePacketType_Interest, + "Parameter interestMessage must be an Interest"); + + PARCHashCodeTable *table; + table = store->storageByName; + + ContentStoreEntry *storeEntry = parcHashCodeTable_Get(table, interest); + + bool foundEntry = false; + + if (storeEntry) { + if (contentStoreEntry_HasExpiryTimeTicks(storeEntry) && + contentStoreEntry_GetExpiryTimeTicks(storeEntry) < currentTimeTicks) { + // the entry is expired, we can remove it + _contentStoreLRU_PurgeStoreEntry(store, storeEntry); + } else { + foundEntry = true; + } + } + + if (foundEntry) { + contentStoreEntry_MoveToHead(storeEntry); + result = contentStoreEntry_GetMessage(storeEntry); + + store->stats.countHits++; + + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "ContentStoreLRU %p matched interest %p (hits %" PRIu64 + ", misses %" PRIu64 ")", + (void *)store, (void *)interest, store->stats.countHits, + store->stats.countMisses); + } + } else { + store->stats.countMisses++; + + if (logger_IsLoggable(store->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "ContentStoreLRU %p missed interest %p (hits %" PRIu64 + ", misses %" PRIu64 ")", + (void *)store, (void *)interest, store->stats.countHits, + store->stats.countMisses); + } + } + + return result; +} + +static bool _contentStoreLRU_RemoveContent(ContentStoreInterface *storeImpl, + Message *content) { + bool result = false; + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + + ContentStoreEntry *storeEntry = + parcHashCodeTable_Get(store->storageByName, content); + + if (storeEntry != NULL) { + _contentStoreLRU_PurgeStoreEntry(store, storeEntry); + result = true; + } + + return result; +} + +static void _contentStoreLRU_Log(ContentStoreInterface *storeImpl) { + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + + logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_All, + __func__, + "ContentStoreLRU @%p {count = %zu, capacity = %zu {" + "stats = @%p {adds = %" PRIu64 ", hits = %" PRIu64 + ", misses = %" PRIu64 ", LRUEvictons = %" PRIu64 + ", ExpiryEvictions = %" PRIu64 ", RCTEvictions = %" PRIu64 "} }", + store, store->objectCount, store->objectCapacity, &store->stats, + store->stats.countAdds, store->stats.countHits, + store->stats.countMisses, store->stats.countLruEvictions, + store->stats.countExpiryEvictions, store->stats.countRCTEvictions); +} + +static size_t _contentStoreLRU_GetObjectCapacity( + ContentStoreInterface *storeImpl) { + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + return store->objectCapacity; +} + +static size_t _contentStoreLRU_GetObjectCount( + ContentStoreInterface *storeImpl) { + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + return store->objectCount; +} + +static size_t _contentStoreLRU_SetObjectCapacity( + ContentStoreInterface *storeImpl, size_t newCapacity) { + _ContentStoreLRU *store = + (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl); + return store->objectCapacity = newCapacity; +} + +ContentStoreInterface *contentStoreLRU_Create(ContentStoreConfig *config, + Logger *logger) { + ContentStoreInterface *storeImpl = NULL; + + parcAssertNotNull(logger, "ContentStoreLRU requires a non-NULL logger"); + + storeImpl = parcObject_CreateAndClearInstance(ContentStoreInterface); + + if (storeImpl != NULL) { + storeImpl->_privateData = + parcObject_CreateAndClearInstance(_ContentStoreLRU); + + if (_contentStoreLRU_Init(storeImpl->_privateData, config, logger)) { + storeImpl->putContent = &_contentStoreLRU_PutContent; + storeImpl->removeContent = &_contentStoreLRU_RemoveContent; + + storeImpl->matchInterest = &_contentStoreLRU_MatchInterest; + + storeImpl->getObjectCount = &_contentStoreLRU_GetObjectCount; + storeImpl->getObjectCapacity = &_contentStoreLRU_GetObjectCapacity; + + storeImpl->log = &_contentStoreLRU_Log; + + storeImpl->acquire = &_contentStoreLRU_Acquire; + storeImpl->release = &_contentStoreLRU_Release; + + // Initialize from the config passed to us. + _contentStoreLRU_SetObjectCapacity(storeImpl, config->objectCapacity); + + if (logger_IsLoggable(logger, LoggerFacility_Processor, + PARCLogLevel_Info)) { + logger_Log(logger, LoggerFacility_Processor, PARCLogLevel_Info, + __func__, "ContentStoreLRU %p created with capacity %zu", + (void *)storeImpl, + contentStoreInterface_GetObjectCapacity(storeImpl)); + } + } + } else { + parcObject_Release((void **)&storeImpl); + } + + return storeImpl; +} diff --git a/hicn-light/src/content_store/contentStoreLRU.h b/hicn-light/src/content_store/contentStoreLRU.h new file mode 100755 index 000000000..3c0815ebd --- /dev/null +++ b/hicn-light/src/content_store/contentStoreLRU.h @@ -0,0 +1,39 @@ +/* + * 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. + */ + +#ifndef contentStoreLRU_h +#define contentStoreLRU_h + +#include <src/content_store/contentStoreInterface.h> +#include <src/core/logger.h> +#include <stdio.h> + +/** + * Create and Initialize an instance of contentStoreLRU. A newly allocated + * {@link ContentStoreInterface} object is initialized and returned. It must + * eventually be released by calling {@link contentStoreInterface_Release}. + * + * + * @param config An instance of `ContentStoreConfig`, specifying options to be + * applied by the underlying contentStoreLRU instance. + * @param logger An instance of a {@link Logger} to use for logging content + * store events. + * + * @return a newly created contentStoreLRU instance. + * + */ +ContentStoreInterface *contentStoreLRU_Create(ContentStoreConfig *config, + Logger *logger); +#endif // contentStoreLRU_h diff --git a/hicn-light/src/content_store/listLRU.c b/hicn-light/src/content_store/listLRU.c new file mode 100755 index 000000000..42b491d7c --- /dev/null +++ b/hicn-light/src/content_store/listLRU.c @@ -0,0 +1,133 @@ +/* + * 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 <src/config.h> +#include <stdbool.h> +#include <stdio.h> +#include <sys/queue.h> + +#include <parc/algol/parc_Memory.h> +#include <parc/assert/parc_Assert.h> +#include <src/content_store/listLRU.h> + +struct list_lru_entry { + void *userData; + + // always set to the list + ListLru *parentList; + + // indicates if the Entry is currently in the list + bool inList; + + TAILQ_ENTRY(list_lru_entry) list; +}; + +// this defines the TAILQ structure so we can access the tail pointer +TAILQ_HEAD(lru_s, list_lru_entry); + +struct list_lru { + struct lru_s head; + size_t itemsInList; +}; + +void listLRU_EntryDestroy(ListLruEntry **entryPtr) { + parcAssertNotNull(entryPtr, + "Parameter entryPtr must be non-null double pointer"); + + ListLruEntry *entry = *entryPtr; + if (entry->inList) { + TAILQ_REMOVE(&entry->parentList->head, entry, list); + parcAssertTrue( + entry->parentList->itemsInList > 0, + "Invalid state, removed entry from list, but itemsInList is 0"); + entry->parentList->itemsInList--; + } + + parcMemory_Deallocate((void **)&entry); + *entryPtr = NULL; +} + +void listLRU_EntryMoveToHead(ListLruEntry *entry) { + parcAssertNotNull(entry, "Parameter entry must be non-null"); + + TAILQ_REMOVE(&entry->parentList->head, entry, list); + TAILQ_INSERT_HEAD(&entry->parentList->head, entry, list); +} + +void *listLRU_EntryGetData(ListLruEntry *entry) { return entry->userData; } + +ListLru *listLRU_Create() { + ListLru *list = parcMemory_AllocateAndClear(sizeof(ListLru)); + parcAssertNotNull(list, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(ListLru)); + list->itemsInList = 0; + TAILQ_INIT(&list->head); + return list; +} + +void listLRU_Destroy(ListLru **lruPtr) { + parcAssertNotNull(lruPtr, "Parameter lruPtr must be non-null double pointer"); + + ListLru *lru = *lruPtr; + + ListLruEntry *entry = TAILQ_FIRST(&lru->head); + while (entry != NULL) { + ListLruEntry *next = TAILQ_NEXT(entry, list); + listLRU_EntryDestroy(&entry); + entry = next; + } + + parcMemory_Deallocate((void **)&lru); + *lruPtr = NULL; +} + +ListLruEntry *listLRU_NewHeadEntry(ListLru *lru, void *data) { + parcAssertNotNull(lru, "Parameter lru must be non-null"); + parcAssertNotNull(data, "Parameter data must be non-null"); + + ListLruEntry *entry = parcMemory_AllocateAndClear(sizeof(ListLruEntry)); + parcAssertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(ListLruEntry)); + entry->userData = data; + entry->parentList = lru; + entry->inList = true; + + TAILQ_INSERT_HEAD(&lru->head, entry, list); + lru->itemsInList++; + + return entry; +} + +ListLruEntry *listLRU_PopTail(ListLru *lru) { + parcAssertNotNull(lru, "Parameter lru must be non-null"); + + ListLruEntry *entry = TAILQ_LAST(&lru->head, lru_s); + + if (entry) { + parcAssertTrue( + lru->itemsInList > 0, + "Invalid state, removed entry from list, but itemsInList is 0"); + lru->itemsInList--; + TAILQ_REMOVE(&lru->head, entry, list); + entry->inList = false; + } + + return entry; +} + +size_t listLRU_Length(const ListLru *lru) { + parcAssertNotNull(lru, "Parameter lru must be non-null"); + return lru->itemsInList; +} diff --git a/hicn-light/src/content_store/listLRU.h b/hicn-light/src/content_store/listLRU.h new file mode 100755 index 000000000..75f698b61 --- /dev/null +++ b/hicn-light/src/content_store/listLRU.h @@ -0,0 +1,94 @@ +/* + * 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. + */ + +/** + * @file listLRU.h + * @brief Maintains an LRU for the content store + * + * An LRU list is make up of LRU entries. The entries are bound to the list. + * The user of the list is reponsible for knowing when there's too many things + * and wants to remove one. The LRU list will grow without bound otherwise. + * + * The LRU list is meant to be used as an auxiliary data structure, not the + * primary storage of data elements. + * + */ + +#ifndef listLRU_h +#define listLRU_h + +struct list_lru_entry; +typedef struct list_lru_entry ListLruEntry; + +struct list_lru; +typedef struct list_lru ListLru; + +/** + * @function lruEntry_Destroy + * @abstract Destroys and element. This will also remove it from the list. + */ +void listLRU_EntryDestroy(ListLruEntry **entryPtr); + +/** + * @function listLRU_EntryMoveToHead + * @abstract move an element to head + */ +void listLRU_EntryMoveToHead(ListLruEntry *entry); + +/** + * @function lruEntry_GetData + * @abstract Returns the user-supplied opaque data when the entry was created + */ +void *listLRU_EntryGetData(ListLruEntry *entry); + +/** + * @function listLRU_Create + * @abstract Creates a new Least-Recently-Used list + */ +ListLru *listLRU_Create(); + +/** + * @function listLRU_Destroy + * @abstract Destroys a list and frees all the elements in it + */ +void listLRU_Destroy(ListLru **listPtr); + +/** + * Returns the number of items in the list + * + * @param [in] lru An allocated ListLru + * @retval number The number of items in the LRU list + */ +size_t listLRU_Length(const ListLru *lru); + +/** + * @function listLRU_NewHeadEntry + * @abstract Creates a new entry for the list. It is inserted at the head of + * the list. + */ +ListLruEntry *listLRU_NewHeadEntry(ListLru *lru, void *data); + +/** + * @function listLRU_PopTail + * @abstract Removes the tail element from the list and returns it to the user + * @discussion + * Pops the tail element. The user should examine its data to destroy their + * tail object, then call <code>LruEntry_Destroy()</code> to free the + * LRU entry. + * + * @return The tail element, or NULL for an empty list + */ +ListLruEntry *listLRU_PopTail(ListLru *list); +#endif // listLRU_h diff --git a/hicn-light/src/content_store/listTimeOrdered.c b/hicn-light/src/content_store/listTimeOrdered.c new file mode 100755 index 000000000..44697d202 --- /dev/null +++ b/hicn-light/src/content_store/listTimeOrdered.c @@ -0,0 +1,94 @@ +/* + * 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/assert/parc_Assert.h> +#include <src/config.h> +#include <src/content_store/listTimeOrdered.h> + +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_TreeRedBlack.h> + +/** + * A list of ContentStoreEntrys, kept in sorted order by time. The ordering is + * calculated by a key compare function (e.g. {@link TimeOrderList_KeyCompare}), + * passed in. + * + * This container does not hold references to the objects that it contains. In + * other words, it does not Acquire() the Messages that are placed in it. That + * reference count is managed by the owning ContentStore. This is purely an + * index, and provides an easy to way index Messages based on a specified time + * value. Typically, that would be the Expiration Time. + * + * It maintains a tree, sorted by the time values passed in to the Add() + * function. It does not manage capacity, and can grow uncontrollably if the + * owning ContentStore does not manage it. Items are indexed first by time, then + * address of the Message (just as a distringuishing attribute). This allows us + * to store multiple items with the same expiration time. + */ + +struct list_timeordered { + PARCTreeRedBlack *timeOrderedTree; +}; + +static void _finalRelease(ListTimeOrdered **listP) { + ListTimeOrdered *list = *listP; + parcTreeRedBlack_Destroy(&list->timeOrderedTree); +} + +parcObject_ExtendPARCObject(ListTimeOrdered, _finalRelease, NULL, NULL, NULL, + NULL, NULL, NULL); + +parcObject_ImplementAcquire(listTimeOrdered, ListTimeOrdered); + +parcObject_ImplementRelease(listTimeOrdered, ListTimeOrdered); + +ListTimeOrdered *listTimeOrdered_Create( + TimeOrderList_KeyCompare *keyCompareFunction) { + ListTimeOrdered *result = parcObject_CreateInstance(ListTimeOrdered); + if (NULL != result) { + result->timeOrderedTree = + parcTreeRedBlack_Create(keyCompareFunction, // keyCompare + NULL, // keyFree + NULL, // keyCopy + NULL, // valueEquals + NULL, // valueFree + NULL); // valueCopy + } + return result; +} + +void listTimeOrdered_Add(ListTimeOrdered *list, ContentStoreEntry *entry) { + parcTreeRedBlack_Insert(list->timeOrderedTree, entry, entry); +} + +ContentStoreEntry *listTimeOrdered_GetOldest(ListTimeOrdered *list) { + return parcTreeRedBlack_FirstKey(list->timeOrderedTree); +} + +bool listTimeOrdered_Remove(ListTimeOrdered *list, + ContentStoreEntry *storeEntry) { + bool result = false; + + ContentStoreEntry *entry = (ContentStoreEntry *)parcTreeRedBlack_Remove( + list->timeOrderedTree, storeEntry); + if (entry != NULL) { + result = true; + } + return result; +} + +size_t listTimeOrdered_Length(ListTimeOrdered *list) { + return (size_t)parcTreeRedBlack_Size(list->timeOrderedTree); +} diff --git a/hicn-light/src/content_store/listTimeOrdered.h b/hicn-light/src/content_store/listTimeOrdered.h new file mode 100755 index 000000000..b18bd16f7 --- /dev/null +++ b/hicn-light/src/content_store/listTimeOrdered.h @@ -0,0 +1,103 @@ +/* + * 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. + */ + +#ifndef listTimeOrdered_h +#define listTimeOrdered_h + +#include <parc/algol/parc_TreeRedBlack.h> +#include <src/content_store/contentStoreEntry.h> +#include <src/core/message.h> +#include <stdio.h> + +struct list_timeordered; +typedef struct list_timeordered ListTimeOrdered; + +/** + * A signum function that takes two instances of ContentStoreEntrys and + * returns a value based on their relative values. + */ +typedef PARCTreeRedBlack_KeyCompare TimeOrderList_KeyCompare; + +/** + * Create a new instance of `ListTimeOrdered` that will maintain the order of + * its list items using the supplied `keyCompareFunction`. + * + * The newly created `ListTimeOrdered` must eventually be released by calling + * {@link listTimeOrdered_Release}. + * + * @param keyCompareFunction the signum comparison function to use to sort + * stored items. + * @return a new instance of `TimeOrderList`. + * @return NULL if the new instance couldn't be created. + * + */ +ListTimeOrdered *listTimeOrdered_Create( + TimeOrderList_KeyCompare *keyCompareFunction); + +/** + * Release a previously acquired reference to the specified instance, + * decrementing the reference count for the instance. + * + * The pointer to the instance is set to NULL as a side-effect of this function. + * + * If the invocation causes the last reference to the instance to be released, + * the instance is deallocated and the instance's implementation will perform + * additional cleanup and release other privately held references. + * + */ +void listTimeOrdered_Release(ListTimeOrdered **listP); + +/** + * Add a {@link ContentStoreEntry} instance to the specified list. Note that a + * new refernece to the specified `storeEntry` is not acquired. + * + * @param list the list instance into which to add the specified storeEntry. + * @param storeEntry the storeEntry instance to add. + * + */ +void listTimeOrdered_Add(ListTimeOrdered *list, ContentStoreEntry *storeEntry); + +/** + * Remove a {@link ContentStoreEntry} instance from the specified list. + * + * @param list the list instance from which to remove the specified storeEntry. + * @param storeEntry the storeEntry instance to remove. + * @return true if the removal was succesful. + * @return false if the removal was not succesful. + * + */ +bool listTimeOrdered_Remove(ListTimeOrdered *list, + ContentStoreEntry *storeEntry); + +/** + * Return the oldest {@link ContentStoreEntry} instance in this list. That is, + * the one with the smallest time value. + * + * @param list the list instance from which to retrieve the oldest storeEntry. + * @param the oldest `ContentStoreEntry` in the list + * @param NULL if no `ContentStoreEntry` was available. + * + */ +ContentStoreEntry *listTimeOrdered_GetOldest(ListTimeOrdered *list); + +/** + * Return the number of items currently stored in the list. + * + * @param list the `ListTimeOrdered` instance from which to retrieve the count. + * @return the number of items in the list. + * + */ +size_t listTimeOrdered_Length(ListTimeOrdered *list); +#endif /* defined(listTimeOrdered_h) */ |