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_element_take(struct atomic_queue_element * e)
00030 {
00031     if (!e) { return ATOMIC_QUEUE_NULL_ELEMENT;}
00032     // Duplicate element check using lock
00033     uintptr_t lock; // This is initialized in the do/while loop.
00034     // Check/obtain a lock on the element.
00035     do {
00036         lock = e->lock;
00037         if (lock) {
00038             return ATOMIC_QUEUE_DUPLICATE_ELEMENT;
00039         }
00040     } while (!aq_atomic_cas_uintptr(&e->lock, lock, 1));
00041     return ATOMIC_QUEUE_SUCCESS;
00042 }
00043 
00044 int aq_element_release(struct atomic_queue_element * e)
00045 {
00046     if (!e) { return ATOMIC_QUEUE_NULL_ELEMENT;}
00047     e->lock = 0;
00048     return ATOMIC_QUEUE_SUCCESS;
00049 }
00050 
00051 int aq_push_tail(struct atomic_queue * q, struct atomic_queue_element * e)
00052 {
00053     CORE_UTIL_ASSERT_MSG(q != NULL, "null queue used");
00054     if (!e) { return ATOMIC_QUEUE_NULL_ELEMENT;}
00055     if (q == NULL) {
00056         return ATOMIC_QUEUE_NULL_QUEUE;
00057     }
00058 
00059     do {
00060         e->next = q->tail;
00061     } while (!aq_atomic_cas_uintptr((uintptr_t *)&q->tail, (uintptr_t)e->next, (uintptr_t)e));
00062 
00063     return ATOMIC_QUEUE_SUCCESS;
00064 }
00065 
00066 struct atomic_queue_element * aq_pop_head(struct atomic_queue * q)
00067 {
00068     CORE_UTIL_ASSERT_MSG(q != NULL, "null queue used");
00069     if (q == NULL) {
00070         return NULL;
00071     }
00072     struct atomic_queue_element * current;
00073     int fail = AQ_ATOMIC_CAS_DEREF_VALUE;
00074     while (fail != AQ_ATOMIC_CAS_DEREF_SUCCESS) {
00075         // Set the element reference pointer to the tail pointer
00076         struct atomic_queue_element * volatile * px = &q->tail;
00077         if (*px == NULL) {
00078             return NULL;
00079         }
00080         fail = AQ_ATOMIC_CAS_DEREF_VALUE;
00081         while (fail == AQ_ATOMIC_CAS_DEREF_VALUE) {
00082             fail = aq_atomic_cas_deref_uintptr((uintptr_t * volatile *)px,
00083                             (uintptr_t **)&current,
00084                             (uintptr_t) NULL,
00085                             NULL,
00086                             offsetof(struct atomic_queue_element, next));
00087             if (fail == AQ_ATOMIC_CAS_DEREF_VALUE) {
00088                 // Detect a loop to the tail of the queue
00089                 if (current->next == q->tail) {
00090                     return NULL;
00091                 }
00092                 px = &current->next;
00093             }
00094         }
00095     }
00096 
00097     return current;
00098 }
00099 
00100 
00101 int aq_empty(struct atomic_queue * q)
00102 {
00103     return q->tail == NULL;
00104 }
00105 
00106 unsigned aq_count(struct atomic_queue *q)
00107 {
00108     unsigned x;
00109     struct atomic_queue_element * volatile e;
00110     if (aq_empty(q)) {
00111         return 0;
00112     }
00113     e = q->tail;
00114     for (x = 1; e->next != NULL; x++, e = e->next) {
00115         if (e->next == q->tail){
00116             return (unsigned)-1;
00117         }
00118     }
00119     return x;
00120 }
00121 
00122 void aq_initialize_element(struct atomic_queue_element* e)
00123 {
00124     if (!e) { return;}
00125     e->lock = 0;
00126     e->next = NULL;
00127 }