From ec688b4723a041044226358bcd4dd6e2da39da49 Mon Sep 17 00:00:00 2001 From: Luca Muscariello Date: Thu, 23 Feb 2017 17:01:02 +0100 Subject: Initial commit: cframework. Longbow and Libparc Change-Id: I90378dbd30da6033b20fb1f829b3b822cf366c59 Signed-off-by: Luca Muscariello --- libparc/parc/algol/parc_Deque.h | 465 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 465 insertions(+) create mode 100755 libparc/parc/algol/parc_Deque.h (limited to 'libparc/parc/algol/parc_Deque.h') diff --git a/libparc/parc/algol/parc_Deque.h b/libparc/parc/algol/parc_Deque.h new file mode 100755 index 00000000..3e11e845 --- /dev/null +++ b/libparc/parc/algol/parc_Deque.h @@ -0,0 +1,465 @@ +/* + * 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. + */ + +/** + * @file parc_Deque.h + * @ingroup datastructures + * @brief PARC Double-ended Queue (Deque) + * + * + */ +#ifndef libparc_parc_Deque_h +#define libparc_parc_Deque_h +#include +#include + +#include +#include +#include + +struct parc_deque; +/** + * A double-ended queue. + * + * @see {@link parcDeque_Create} + * @see {@link parcDeque_CreateCustom} + */ +typedef struct parc_deque PARCDeque; + +/** + * Create a `PARCDeque` instance with the default element equality and copy functions. + * + * The queue is created with no elements. + * + * The default element equals function is used by the `{@link parcDeque_Equals} function and + * simply compares the values using the `==` operator. + * Users that need more sophisticated comparisons of the elements need to supply their own + * function via the {@link parcDeque_CreateCustom} function. + * + * @return non-NULL A pointer to a `PARCDeque` instance. + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +PARCDeque *parcDeque_Create(void); + +PARCIterator *parcDeque_Iterator(PARCDeque *deque); + +/** + * Create a PARCDeque instance that uses the {@link PARCObjectDescriptor} providing functions for element equality and copy function. + * + * The queue is created with no elements. + * + * @param [in] interface A pointer to a `PARCObjectDescriptor` instance. + * + * @return non-NULL A pointer to a `PARCDeque` instance. + * + * Example: + * @code + * <#example#> + * @endcode + */ +PARCDeque *parcDeque_CreateObjectInterface(const PARCObjectDescriptor *interface); + +/** + * Create a `PARCDeque` instance with a custom element equality and copy function. + * + * The queue is created with no elements. + * + * The supplied element equals function is used by the `parcDeque_Equals` + * function which must return `true` if the elements are equal, and `false` if unequal. + * + * @param [in] elementEquals The function to be used for equals + * @param [in] elementCopy The function to be used for copy + * + * @return non-NULL A pointer to a `PARCDeque` instance. + * + * Example: + * @code + * <#example#> + * @endcode + * + * @see {@link parcDeque_CreateObjectInterface} + */ +PARCDeque *parcDeque_CreateCustom(bool (*elementEquals)(const void *, const void *), void *(*elementCopy)(const void *)); + +/** + * Acquire a new reference to an instance of `PARCDeque`. + * + * The reference count to the instance is incremented. + * + * @param [in] deque The instance of `PARCDeque` to which to refer. + * + * @return The same value as the input parameter @p deque + * + * Example: + * @code + * <#example#> + * @endcode + */ +PARCDeque *parcDeque_Acquire(const PARCDeque *deque); + +/** + * 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 interface will perform + * additional cleanup and release other privately held references. + * + * @param [in,out] dequePtr A pointer to a pointer to the instance of `PARCDeque` to release. + * + * + * Example: + * @code + * { + * PARCDeque *buffer = parcDeque_Create(10); + * + * parcDeque_Release(&buffer); + * } + * @endcode + */ +void parcDeque_Release(PARCDeque **dequePtr); + +/** + * Copy a a `PARCDeque` to another. + * + * @param [in] deque A pointer to an instance of `PARCDeque` + * + * @return A pointer to a copy of the original instance of `PARCDeque` + * + * Example: + * @code + * { + * <#example#> + * } + * @endcode + */ +PARCDeque *parcDeque_Copy(const PARCDeque *deque); + +/** + * Append an element to the tail end of the specified `PARCDeque` + * + * @param [in,out] deque A pointer to the instance of `PARCDeque` to which the element will be appended + * @param [in] element A pointer to the element to be appended to the instance of `PARCDeque` + * + * @return non NULL A pointer to the specific instance of `PARCDeque` + * + * Example: + * @code + * <#example#> + * @endcode + */ +PARCDeque *parcDeque_Append(PARCDeque *deque, void *element); + +/** + * Prepend an element to the head end of the specified `PARCDeque` + * + * + * @param [in,out] deque A pointer to the instance of `PARCDeque` to which the element will be prepended + * @param [in] element A pointer to the element to be appended to the instance of `PARCDeque` + * + * @return non NULL A pointer to the specific instance of `PARCDeque` + * + * + * Example: + * @code + * <#example#> + * @endcode + */ +PARCDeque *parcDeque_Prepend(PARCDeque *deque, void *element); + +/** + * Return the first element of the specified `PARCDeque` and remove it from the queue + * + * @param [in,out] deque A pointer to the instance of `PARCDeque` from which the first element will be returned and removed + * + * @return non NULL A pointer to the element removed + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +void *parcDeque_RemoveFirst(PARCDeque *deque); + +/** + * Return the last element of the specified `PARCDeque` and remove it from the queue + * + * @param [in,out] deque A pointer to the instance of `PARCDeque` from which the last element will be returned and removed + * + * @return non NULL A pointer to the element removed + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +void *parcDeque_RemoveLast(PARCDeque *deque); + +/** + * Return the first element of the specified `PARCDeque` but do NOT remove it from the queue + * + * @param [in] deque A pointer to the instance of `PARCDeque` from which the first element will be returned + * + * @return non NULL A pointer to the first element + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +void *parcDeque_PeekFirst(const PARCDeque *deque); + +/** + * Return the last element of the specified `PARCDeque` but do NOT remove it from the queue + * + * @param [in] deque A pointer to the instance of `PARCDeque` from which the last element will be returned + * + * @return non NULL A pointer to the last element + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +void *parcDeque_PeekLast(const PARCDeque *deque); + +/** + * Return the size of the specified queue + * + * @param [in] deque A pointer to the instance of `PARCDeque` + * + * @return `size_t` The size of the queue + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +size_t parcDeque_Size(const PARCDeque *deque); + +/** + * Return True if the `PARCDeque` is empty or False if not. + * + * @param [in] deque A pointer to the instance of `PARCDeque` + * + * @return bool True if the `PARCDeque` is empty or False if not. + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +bool parcDeque_IsEmpty(const PARCDeque *deque); + +/** + * Get a pointer to the specified element. + * + * @param [in] deque A pointer to a `PARCDeque` instance. + * @param [in] index The index of the element to be retrieved. + * + * @throws `trapOutOfBounds` + * + * Example: + * @code + * <#example#> + * @endcode + * + */ +void *parcDeque_GetAtIndex(const PARCDeque *deque, size_t index); + +/** + * Determine if two `PARCDeque` instances are equal. + * + * This function implements the following equivalence relations on non-null `PARCDeque` instances: + * + * * It is reflexive: for any non-null reference value x, `parcDeque_Equals(x, x)` must return true. + * + * * It is symmetric: for any non-null reference values x and y, `parcDeque_Equals(x, y)` must return true if and only if + * `parcDeque_Equals(y x)` returns true. + * + * * It is transitive: for any non-null reference values x, y, and z, if + * `parcDeque_Equals(x, y)` returns true and + * `parcDeque_Equals(y, z)` returns true, + * then `parcDeque_Equals(x, z)` must return true. + * + * * It is consistent: for any non-null reference values x and y, multiple invocations of `parcDeque_Equals(x, y)` + * consistently return true or consistently return false. + * + * * For any non-null reference value x, `parcDeque_Equals(x, NULL)` must return false. + * + * Two `PARCDeque` instances with different element equality functions are always unequal. + * + * @param [in] x A pointer to a `PARCDeque` instance. + * @param [in] y A pointer to a `PARCDeque` instance. + * + * @return true `PARCDeque` x and y are equal. + * @return false `PARCDeque` x and y are not equal. + * + * Example: + * @code + * <#example#> + * @endcode + */ +bool parcDeque_Equals(const PARCDeque *x, const PARCDeque *y); + +/** + * Print a human readable representation of the given `PARCDeque`. + * + * @param [in] indentation The level of indentation to use to pretty-print the output. + * @param [in] deque A pointer to the instance to display. + * + * Example: + * @code + * { + * PARCDeque *instance = parcDeque_Create(); + * + * parcDeque_Display(instance, 0); + * + * parcDeque_Release(&instance); + * } + * @endcode + * + */ +void parcDeque_Display(const PARCDeque *deque, int indentation); + +/** + * Wakes up a single thread that is waiting on this object (see `parcDeque_Wait)`. + * If any threads are waiting on this object, one of them is chosen to be awakened. + * The choice is arbitrary and occurs at the discretion of the underlying implementation. + * + * The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. + * The awakened thread will compete in the usual manner with any other threads that might be actively + * competing to synchronize on this object; + * for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object. + * + * @param [in] object A pointer to a valid PARCDeque instance. + * + * Example: + * @code + * { + * + * parcDeque_Notify(object); + * } + * @endcode + */ +parcObject_ImplementNotify(parcDeque, PARCDeque); + +/** + * Causes the calling thread to wait until either another thread invokes the parcDeque_Notify() function on the same object. + * * + * @param [in] object A pointer to a valid `PARCDeque` instance. + * + * Example: + * @code + * { + * + * parcDeque_Wait(object); + * } + * @endcode + */ +parcObject_ImplementWait(parcDeque, PARCDeque); + +/** + * Obtain the lock on the given `PARCDeque` instance. + * + * If the lock is already held by another thread, this function will block. + * If the lock is aleady held by the current thread, this function will return `false`. + * + * Implementors must avoid deadlock by attempting to lock the object a second time within the same calling thread. + * + * @param [in] object A pointer to a valid `PARCDeque` instance. + * + * @return true The lock was obtained successfully. + * @return false The lock is already held by the current thread, or the `PARCDeque` is invalid. + * + * Example: + * @code + * { + * if (parcDeque_Lock(object)) { + * + * } + * } + * @endcode + */ +parcObject_ImplementLock(parcDeque, PARCDeque); + +/** + * Try to obtain the advisory lock on the given PARCDeque instance. + * + * Once the lock is obtained, the caller must release the lock as soon as possible. + * + * @param [in] object A pointer to a valid PARCDeque instance. + * + * @return true The PARCDeque is locked. + * @return false The PARCDeque is unlocked. + * + * Example: + * @code + * { + * parcDeque_TryLock(object); + * } + * @endcode + */ +parcObject_ImplementTryLock(parcDeque, PARCDeque); + +/** + * Try to unlock the advisory lock on the given `PARCDeque` instance. + * + * @param [in] object A pointer to a valid `PARCDeque` instance. + * + * @return true The `PARCDeque` was locked and now is unlocked. + * @return false The `PARCDeque` was not locked and remains unlocked. + * + * Example: + * @code + * { + * parcDeque_Unlock(object); + * } + * @endcode + */ +parcObject_ImplementUnlock(parcDeque, PARCDeque); + +/** + * Determine if the advisory lock on the given `PARCDeque` instance is locked. + * + * @param [in] object A pointer to a valid `PARCDeque` instance. + * + * @return true The `PARCDeque` is locked. + * @return false The `PARCDeque` is unlocked. + * Example: + * @code + * { + * if (parcDeque_IsLocked(object)) { + * ... + * } + * } + * @endcode + */ +parcObject_ImplementIsLocked(parcDeque, PARCDeque); + +#endif // libparc_parc_Deque_h -- cgit 1.2.3-korg