atomic-queue.c

00001 // ----------------------------------------------------------------------------
00002 // Copyright 2015-2017 ARM Ltd.
00003 //
00004 // SPDX-License-Identifier: Apache-2.0
00005 //
00006 // Licensed under the Apache License, Version 2.0 (the "License");
00007 // you may not use this file except in compliance with the License.
00008 // You may obtain a copy of the License at
00009 //
00010 //     http://www.apache.org/licenses/LICENSE-2.0
00011 //
00012 // Unless required by applicable law or agreed to in writing, software
00013 // distributed under the License is distributed on an "AS IS" BASIS,
00014 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015 // See the License for the specific language governing permissions and
00016 // limitations under the License.
00017 // ----------------------------------------------------------------------------
00018 
00019 #include "atomic-queue/atomic-queue.h"
00020 #include "atomic.h"
00021 
00022 #include <stddef.h>
00023 #include <stdint.h>
00024 #include <stdio.h>
00025 
00026 #define CORE_UTIL_ASSERT_MSG(test, msg)
00027 
00028 
00029 int aq_push_tail(struct atomic_queue * q, struct atomic_queue_element * e)
00030 {
00031     CORE_UTIL_ASSERT_MSG(q != NULL, "null queue used");
00032     if (q == NULL) {
00033         return ATOMIC_QUEUE_NULL_QUEUE;
00034     }
00035 
00036 /* duplicate element check using lock */
00037 #ifdef ATOMIC_QUEUE_CONFIG_ELEMENT_LOCK
00038     uintptr_t lock;
00039     // Check/obtain a lock on the element.
00040     do {
00041         lock = e->lock;
00042         if (lock) {
00043             return ATOMIC_QUEUE_DUPLICATE_ELEMENT;
00044         }
00045     } while (!aq_atomic_cas_uintptr(&e->lock, lock, 1));
00046 #endif
00047 
00048     do {
00049 /* duplicate element check by searching */
00050 #ifndef ATOMIC_QUEUE_CONFIG_ELEMENT_LOCK
00051         // Make sure the new element does not exist in the current queue
00052         struct atomic_queue_element* te = q->tail;
00053         while (te != NULL)
00054         {
00055             CORE_UTIL_ASSERT_MSG(te != e, "duplicate queue element");
00056             if (te == e) {
00057                 return ATOMIC_QUEUE_DUPLICATE_ELEMENT;
00058             }
00059             te = te->next;
00060         }
00061 #endif
00062         e->next = q->tail;
00063     } while (!aq_atomic_cas_uintptr((uintptr_t *)&q->tail, (uintptr_t)e->next, (uintptr_t)e));
00064 
00065     return ATOMIC_QUEUE_SUCCESS;
00066 }
00067 
00068 struct atomic_queue_element * aq_pop_head(struct atomic_queue * q)
00069 {
00070     CORE_UTIL_ASSERT_MSG(q != NULL, "null queue used");
00071     if (q == NULL) {
00072         return NULL;
00073     }
00074     struct atomic_queue_element * current;
00075     int fail = AQ_ATOMIC_CAS_DEREF_VALUE;
00076     while (fail != AQ_ATOMIC_CAS_DEREF_SUCCESS) {
00077         // Set the element reference pointer to the tail pointer
00078         struct atomic_queue_element * volatile * px = &q->tail;
00079         if (*px == NULL) {
00080             return NULL;
00081         }
00082         fail = AQ_ATOMIC_CAS_DEREF_VALUE;
00083         while (fail == AQ_ATOMIC_CAS_DEREF_VALUE) {
00084             fail = aq_atomic_cas_deref_uintptr((uintptr_t * volatile *)px,
00085                             (uintptr_t **)&current,
00086                             (uintptr_t) NULL,
00087                             NULL,
00088                             offsetof(struct atomic_queue_element, next));
00089             if (fail == AQ_ATOMIC_CAS_DEREF_VALUE) {
00090                 if (current->next == q->tail) {
00091                     return NULL;
00092                 }
00093                 px = &current->next;
00094             }
00095         }
00096     }
00097 
00098 #ifdef ATOMIC_QUEUE_CONFIG_ELEMENT_LOCK
00099     // Release element lock
00100     current->lock = 0;
00101 #endif
00102 
00103     return current;
00104 }
00105 
00106 
00107 int aq_empty(struct atomic_queue * q)
00108 {
00109     return q->tail == NULL;
00110 }
00111 
00112 unsigned aq_count(struct atomic_queue *q)
00113 {
00114     unsigned x;
00115     struct atomic_queue_element * volatile e;
00116     if (aq_empty(q)) {
00117         return 0;
00118     }
00119     e = q->tail;
00120     for (x = 1; e->next != NULL; x++, e = e->next) {
00121         if (e->next == q->tail){
00122             return (unsigned)-1;
00123         }
00124     }
00125     return x;
00126 }
00127 
00128 void aq_initialize_element(struct atomic_queue_element* e)
00129 {
00130 #ifdef ATOMIC_QUEUE_CONFIG_ELEMENT_LOCK
00131     e->lock = 0;
00132 #endif
00133 }