xref: /unit/src/nxt_nncq.h (revision 2155:f1b4e7b942c4)
11554Smax.romanov@nginx.com 
21554Smax.romanov@nginx.com /*
31554Smax.romanov@nginx.com  * Copyright (C) NGINX, Inc.
41554Smax.romanov@nginx.com  */
51554Smax.romanov@nginx.com 
61554Smax.romanov@nginx.com #ifndef _NXT_NNCQ_H_INCLUDED_
71554Smax.romanov@nginx.com #define _NXT_NNCQ_H_INCLUDED_
81554Smax.romanov@nginx.com 
91554Smax.romanov@nginx.com 
101554Smax.romanov@nginx.com /* Numeric Naive Circular Queue */
111554Smax.romanov@nginx.com 
121554Smax.romanov@nginx.com #define NXT_NNCQ_SIZE  16384
131554Smax.romanov@nginx.com 
141554Smax.romanov@nginx.com typedef uint32_t nxt_nncq_atomic_t;
151554Smax.romanov@nginx.com typedef uint16_t nxt_nncq_cycle_t;
161554Smax.romanov@nginx.com 
171554Smax.romanov@nginx.com typedef struct {
181554Smax.romanov@nginx.com     nxt_nncq_atomic_t  head;
191554Smax.romanov@nginx.com     nxt_nncq_atomic_t  entries[NXT_NNCQ_SIZE];
201554Smax.romanov@nginx.com     nxt_nncq_atomic_t  tail;
211554Smax.romanov@nginx.com } nxt_nncq_t;
221554Smax.romanov@nginx.com 
231554Smax.romanov@nginx.com 
241554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_head(nxt_nncq_t const volatile * q)251554Smax.romanov@nginx.com nxt_nncq_head(nxt_nncq_t const volatile *q)
261554Smax.romanov@nginx.com {
271554Smax.romanov@nginx.com     return q->head;
281554Smax.romanov@nginx.com }
291554Smax.romanov@nginx.com 
301554Smax.romanov@nginx.com 
311554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_tail(nxt_nncq_t const volatile * q)321554Smax.romanov@nginx.com nxt_nncq_tail(nxt_nncq_t const volatile *q)
331554Smax.romanov@nginx.com {
341554Smax.romanov@nginx.com     return q->tail;
351554Smax.romanov@nginx.com }
361554Smax.romanov@nginx.com 
371554Smax.romanov@nginx.com 
381554Smax.romanov@nginx.com static inline void
nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile * q,nxt_nncq_atomic_t t)391554Smax.romanov@nginx.com nxt_nncq_tail_cmp_inc(nxt_nncq_t volatile *q, nxt_nncq_atomic_t t)
401554Smax.romanov@nginx.com {
411554Smax.romanov@nginx.com     nxt_atomic_cmp_set(&q->tail, t, t + 1);
421554Smax.romanov@nginx.com }
431554Smax.romanov@nginx.com 
441554Smax.romanov@nginx.com 
451554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_index(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)461554Smax.romanov@nginx.com nxt_nncq_index(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
471554Smax.romanov@nginx.com {
481554Smax.romanov@nginx.com     return i % NXT_NNCQ_SIZE;
491554Smax.romanov@nginx.com }
501554Smax.romanov@nginx.com 
511554Smax.romanov@nginx.com 
521554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_map(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)531554Smax.romanov@nginx.com nxt_nncq_map(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
541554Smax.romanov@nginx.com {
551554Smax.romanov@nginx.com     return i % NXT_NNCQ_SIZE;
561554Smax.romanov@nginx.com }
571554Smax.romanov@nginx.com 
581554Smax.romanov@nginx.com 
591554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_cycle(nxt_nncq_t const volatile * q,nxt_nncq_atomic_t i)601554Smax.romanov@nginx.com nxt_nncq_cycle(nxt_nncq_t const volatile *q, nxt_nncq_atomic_t i)
611554Smax.romanov@nginx.com {
621554Smax.romanov@nginx.com     return i / NXT_NNCQ_SIZE;
631554Smax.romanov@nginx.com }
641554Smax.romanov@nginx.com 
651554Smax.romanov@nginx.com 
661554Smax.romanov@nginx.com static inline nxt_nncq_cycle_t
nxt_nncq_next_cycle(nxt_nncq_t const volatile * q,nxt_nncq_cycle_t i)671554Smax.romanov@nginx.com nxt_nncq_next_cycle(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t i)
681554Smax.romanov@nginx.com {
691554Smax.romanov@nginx.com     return i + 1;
701554Smax.romanov@nginx.com }
711554Smax.romanov@nginx.com 
721554Smax.romanov@nginx.com 
731554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_new_entry(nxt_nncq_t const volatile * q,nxt_nncq_cycle_t cycle,nxt_nncq_atomic_t i)741554Smax.romanov@nginx.com nxt_nncq_new_entry(nxt_nncq_t const volatile *q, nxt_nncq_cycle_t cycle,
751554Smax.romanov@nginx.com     nxt_nncq_atomic_t i)
761554Smax.romanov@nginx.com {
771554Smax.romanov@nginx.com     return cycle * NXT_NNCQ_SIZE + (i % NXT_NNCQ_SIZE);
781554Smax.romanov@nginx.com }
791554Smax.romanov@nginx.com 
801554Smax.romanov@nginx.com 
811554Smax.romanov@nginx.com static inline nxt_nncq_atomic_t
nxt_nncq_empty(nxt_nncq_t const volatile * q)821554Smax.romanov@nginx.com nxt_nncq_empty(nxt_nncq_t const volatile *q)
831554Smax.romanov@nginx.com {
841554Smax.romanov@nginx.com     return NXT_NNCQ_SIZE;
851554Smax.romanov@nginx.com }
861554Smax.romanov@nginx.com 
871554Smax.romanov@nginx.com 
88*2155Salx.manpages@gmail.com static inline void
nxt_nncq_init(nxt_nncq_t volatile * q)891554Smax.romanov@nginx.com nxt_nncq_init(nxt_nncq_t volatile *q)
901554Smax.romanov@nginx.com {
911554Smax.romanov@nginx.com     q->head = NXT_NNCQ_SIZE;
921554Smax.romanov@nginx.com     nxt_memzero((void *) q->entries, NXT_NNCQ_SIZE * sizeof(nxt_nncq_atomic_t));
931554Smax.romanov@nginx.com     q->tail = NXT_NNCQ_SIZE;
941554Smax.romanov@nginx.com }
951554Smax.romanov@nginx.com 
961554Smax.romanov@nginx.com 
97*2155Salx.manpages@gmail.com static inline void
nxt_nncq_enqueue(nxt_nncq_t volatile * q,nxt_nncq_atomic_t val)981554Smax.romanov@nginx.com nxt_nncq_enqueue(nxt_nncq_t volatile *q, nxt_nncq_atomic_t val)
991554Smax.romanov@nginx.com {
1001554Smax.romanov@nginx.com     nxt_nncq_cycle_t   e_cycle, t_cycle;
1011554Smax.romanov@nginx.com     nxt_nncq_atomic_t  n, t, e, j;
1021554Smax.romanov@nginx.com 
1031554Smax.romanov@nginx.com     for ( ;; ) {
1041554Smax.romanov@nginx.com         t = nxt_nncq_tail(q);
1051554Smax.romanov@nginx.com         j = nxt_nncq_map(q, t);
1061554Smax.romanov@nginx.com         e = q->entries[j];
1071554Smax.romanov@nginx.com 
1081554Smax.romanov@nginx.com         e_cycle = nxt_nncq_cycle(q, e);
1091554Smax.romanov@nginx.com         t_cycle = nxt_nncq_cycle(q, t);
1101554Smax.romanov@nginx.com 
1111554Smax.romanov@nginx.com         if (e_cycle == t_cycle) {
1121554Smax.romanov@nginx.com             nxt_nncq_tail_cmp_inc(q, t);
1131554Smax.romanov@nginx.com             continue;
1141554Smax.romanov@nginx.com         }
1151554Smax.romanov@nginx.com 
1161554Smax.romanov@nginx.com         if (nxt_nncq_next_cycle(q, e_cycle) != t_cycle) {
1171554Smax.romanov@nginx.com             continue;
1181554Smax.romanov@nginx.com         }
1191554Smax.romanov@nginx.com 
1201554Smax.romanov@nginx.com         n = nxt_nncq_new_entry(q, t_cycle, val);
1211554Smax.romanov@nginx.com 
1221554Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->entries[j], e, n)) {
1231554Smax.romanov@nginx.com             break;
1241554Smax.romanov@nginx.com         }
1251554Smax.romanov@nginx.com     }
1261554Smax.romanov@nginx.com 
1271554Smax.romanov@nginx.com     nxt_nncq_tail_cmp_inc(q, t);
1281554Smax.romanov@nginx.com }
1291554Smax.romanov@nginx.com 
1301554Smax.romanov@nginx.com 
131*2155Salx.manpages@gmail.com static inline nxt_nncq_atomic_t
nxt_nncq_dequeue(nxt_nncq_t volatile * q)1321554Smax.romanov@nginx.com nxt_nncq_dequeue(nxt_nncq_t volatile *q)
1331554Smax.romanov@nginx.com {
1341554Smax.romanov@nginx.com     nxt_nncq_cycle_t   e_cycle, h_cycle;
1351554Smax.romanov@nginx.com     nxt_nncq_atomic_t  h, j, e;
1361554Smax.romanov@nginx.com 
1371554Smax.romanov@nginx.com     for ( ;; ) {
1381554Smax.romanov@nginx.com         h = nxt_nncq_head(q);
1391554Smax.romanov@nginx.com         j = nxt_nncq_map(q, h);
1401554Smax.romanov@nginx.com         e = q->entries[j];
1411554Smax.romanov@nginx.com 
1421554Smax.romanov@nginx.com         e_cycle = nxt_nncq_cycle(q, e);
1431554Smax.romanov@nginx.com         h_cycle = nxt_nncq_cycle(q, h);
1441554Smax.romanov@nginx.com 
1451554Smax.romanov@nginx.com         if (e_cycle != h_cycle) {
1461554Smax.romanov@nginx.com             if (nxt_nncq_next_cycle(q, e_cycle) == h_cycle) {
1471554Smax.romanov@nginx.com                 return nxt_nncq_empty(q);
1481554Smax.romanov@nginx.com             }
1491554Smax.romanov@nginx.com 
1501554Smax.romanov@nginx.com             continue;
1511554Smax.romanov@nginx.com         }
1521554Smax.romanov@nginx.com 
1531554Smax.romanov@nginx.com         if (nxt_atomic_cmp_set(&q->head, h, h + 1)) {
1541554Smax.romanov@nginx.com             break;
1551554Smax.romanov@nginx.com         }
1561554Smax.romanov@nginx.com     }
1571554Smax.romanov@nginx.com 
1581554Smax.romanov@nginx.com     return nxt_nncq_index(q, e);
1591554Smax.romanov@nginx.com }
1601554Smax.romanov@nginx.com 
1611554Smax.romanov@nginx.com 
1621554Smax.romanov@nginx.com #endif /* _NXT_NNCQ_H_INCLUDED_ */
163