Motr  M0
tlist.h
Go to the documentation of this file.
1 /* -*- C -*- */
2 /*
3  * Copyright (c) 2012-2020 Seagate Technology LLC and/or its Affiliates
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  * For any questions about this software or licensing,
18  * please email opensource@seagate.com or cortx-questions@seagate.com.
19  *
20  */
21 
22 
23 #pragma once
24 
25 #ifndef __MOTR_LIB_TLIST_H__
26 #define __MOTR_LIB_TLIST_H__
27 
28 #include "lib/list.h"
29 #include "lib/list_xc.h"
30 #include "lib/types.h" /* uint64_t */
31 
171 struct m0_tl_descr;
172 struct m0_tl;
173 struct m0_tlink;
174 
204 struct m0_tl_descr {
206  const char *td_name;
208  int td_link_offset;
215  int td_link_magic_offset;
221  uint64_t td_link_magic;
226  uint64_t td_head_magic;
228  size_t td_container_size;
229 } M0_XCA_RECORD M0_XCA_DOMAIN(be);
230 
231 #define M0_TL_DESCR(name, ambient_type, link_field, link_magic_field, \
232  link_magic, head_magic) \
233 { \
234  .td_name = name, \
235  .td_link_offset = offsetof(ambient_type, link_field), \
236  .td_link_magic_offset = offsetof(ambient_type, link_magic_field), \
237  .td_link_magic = link_magic, \
238  .td_head_magic = head_magic, \
239  .td_container_size = sizeof(ambient_type) \
240 }; \
241  \
242 M0_BASSERT(M0_HAS_TYPE(M0_FIELD_VALUE(ambient_type, link_field), \
243  struct m0_tlink)); \
244 M0_BASSERT(M0_HAS_TYPE(M0_FIELD_VALUE(ambient_type, link_magic_field), \
245  uint64_t))
246 
247 
251 struct m0_tl {
256  uint64_t t_magic;
258  struct m0_list t_head;
259 } M0_XCA_RECORD M0_XCA_DOMAIN(be);
260 
264 struct m0_tlink {
266  struct m0_list_link t_link;
267 } M0_XCA_RECORD M0_XCA_DOMAIN(be);
268 
269 M0_INTERNAL void m0_tlist_init(const struct m0_tl_descr *d, struct m0_tl *list);
270 M0_INTERNAL void m0_tlist_fini(const struct m0_tl_descr *d, struct m0_tl *list);
271 
272 M0_INTERNAL void m0_tlink_init(const struct m0_tl_descr *d, void *obj);
273 M0_INTERNAL void m0_tlink_fini(const struct m0_tl_descr *d, void *obj);
274 M0_INTERNAL void m0_tlink_init_at(const struct m0_tl_descr *d,
275  void *obj, struct m0_tl *list);
276 M0_INTERNAL void m0_tlink_init_at_tail(const struct m0_tl_descr *d,
277  void *obj, struct m0_tl *list);
278 M0_INTERNAL void m0_tlink_del_fini(const struct m0_tl_descr *d, void *obj);
279 
280 M0_INTERNAL bool m0_tlist_invariant(const struct m0_tl_descr *d,
281  const struct m0_tl *list);
282 M0_INTERNAL bool m0_tlist_invariant_ext(const struct m0_tl_descr *d,
283  const struct m0_tl *list,
284  bool (*check)(const void *, void *),
285  void *datum);
286 M0_INTERNAL bool m0_tlink_invariant(const struct m0_tl_descr *d,
287  const void *obj);
288 
289 M0_INTERNAL bool m0_tlist_is_empty(const struct m0_tl_descr *d,
290  const struct m0_tl *list);
291 M0_INTERNAL bool m0_tlink_is_in(const struct m0_tl_descr *d, const void *obj);
292 
293 M0_INTERNAL bool m0_tlist_contains(const struct m0_tl_descr *d,
294  const struct m0_tl *list, const void *obj);
295 M0_INTERNAL size_t m0_tlist_length(const struct m0_tl_descr *d,
296  const struct m0_tl *list);
297 
304 M0_INTERNAL void m0_tlist_add(const struct m0_tl_descr *d, struct m0_tl *list,
305  void *obj);
306 
313 M0_INTERNAL void m0_tlist_add_tail(const struct m0_tl_descr *d,
314  struct m0_tl *list, void *obj);
315 
322 M0_INTERNAL void m0_tlist_add_after(const struct m0_tl_descr *d, void *obj,
323  void *next);
324 
331 M0_INTERNAL void m0_tlist_add_before(const struct m0_tl_descr *d, void *obj,
332  void *next);
333 
340 M0_INTERNAL void m0_tlist_del(const struct m0_tl_descr *d, void *obj);
341 
347 M0_INTERNAL void m0_tlist_remove(const struct m0_tl_descr *d, void *obj);
348 
355 M0_INTERNAL void m0_tlist_move(const struct m0_tl_descr *d, struct m0_tl *list,
356  void *obj);
357 
364 M0_INTERNAL void m0_tlist_move_tail(const struct m0_tl_descr *d,
365  struct m0_tl *list, void *obj);
369 void *m0_tlist_head(const struct m0_tl_descr *d, const struct m0_tl *list);
370 
374 M0_INTERNAL void *m0_tlist_pop(const struct m0_tl_descr *d,
375  const struct m0_tl *list);
376 
380 M0_INTERNAL void *m0_tlist_tail(const struct m0_tl_descr *d,
381  const struct m0_tl *list);
382 
388 void *m0_tlist_next(const struct m0_tl_descr *d,
389  const struct m0_tl *list, const void *obj);
390 
396 M0_INTERNAL void *m0_tlist_prev(const struct m0_tl_descr *d,
397  const struct m0_tl *list, const void *obj);
398 
435 #define m0_tlist_for(descr, head, obj) \
436 do { \
437  void *__tl; \
438  const struct m0_tl *__head = (head); \
439  \
440  for (obj = m0_tlist_head(descr, __head); \
441  obj != NULL && \
442  ((void)(__tl = m0_tlist_next(descr, __head, obj)), true); \
443  obj = __tl)
444 
448 #define m0_tlist_endfor ;(void)__tl; } while (0)
449 
458 #define m0_tlist_forall(descr, var, head, ...) \
459 ({ \
460  void *var; \
461  \
462  m0_tlist_for(descr, head, var) { \
463  if (!({ __VA_ARGS__ ; })) \
464  break; \
465  } m0_tlist_endfor; \
466  var == NULL; \
467 })
468 
469 #define M0_TL_DESCR_DECLARE(name, scope) \
470 scope const struct m0_tl_descr name ## _tl
471 
495 #define M0_TL_DECLARE(name, scope, amb_type) \
496  \
497 scope void name ## _tlist_init(struct m0_tl *head); \
498 scope void name ## _tlist_fini(struct m0_tl *head); \
499 scope void name ## _tlink_init(amb_type *amb); \
500 scope bool name ## _tlist_invariant(const struct m0_tl *head); \
501 scope bool name ## _tlist_invariant_ext(const struct m0_tl *head, \
502  bool (*check)(const amb_type *, \
503  void *), void *); \
504 scope bool name ## _tlist_is_empty(const struct m0_tl *list); \
505  scope void name ## _tlink_init_at(amb_type *amb, struct m0_tl *head); \
506  scope void name ## _tlink_init_at_tail(amb_type *amb, struct m0_tl *head);\
507 scope void name ## _tlink_fini(amb_type *amb); \
508 scope void name ## _tlink_del_fini(amb_type *amb); \
509 scope bool name ## _tlist_is_empty(const struct m0_tl *list); \
510 scope bool name ## _tlink_is_in (const amb_type *amb); \
511 scope bool name ## _tlist_contains(const struct m0_tl *list, \
512  const amb_type *amb); \
513 scope size_t name ## _tlist_length(const struct m0_tl *list); \
514 scope void name ## _tlist_add(struct m0_tl *list, amb_type *amb); \
515 scope void name ## _tlist_add_tail(struct m0_tl *list, amb_type *amb); \
516 scope void name ## _tlist_add_after(amb_type *amb, amb_type *next); \
517 scope void name ## _tlist_add_before(amb_type *amb, amb_type *next); \
518 scope void name ## _tlist_del(amb_type *amb); \
519 scope void name ## _tlist_remove(amb_type *amb); \
520 scope void name ## _tlist_move(struct m0_tl *list, amb_type *amb); \
521 scope void name ## _tlist_move_tail(struct m0_tl *list, amb_type *amb); \
522 scope amb_type *name ## _tlist_head(const struct m0_tl *list); \
523 scope amb_type *name ## _tlist_pop(const struct m0_tl *list); \
524 scope amb_type *name ## _tlist_tail(const struct m0_tl *list); \
525 scope amb_type *name ## _tlist_next(const struct m0_tl *list, \
526  const amb_type *amb); \
527 scope amb_type *name ## _tlist_prev(const struct m0_tl *list, \
528  const amb_type *amb)
529 
530 #define __AUN __attribute__((unused))
531 
535 #define M0_TL_DESCR_DEFINE(name, hname, scope, amb_type, amb_link_field, \
536  amb_magic_field, amb_magic, head_magic) \
537 scope const struct m0_tl_descr name ## _tl = M0_TL_DESCR(hname, \
538  amb_type, \
539  amb_link_field, \
540  amb_magic_field, \
541  amb_magic, \
542  head_magic)
543 
550 #define M0_TL_DEFINE(name, scope, amb_type) \
551  \
552 scope __AUN void name ## _tlist_init(struct m0_tl *head) \
553 { \
554  m0_tlist_init(&name ## _tl, head); \
555 } \
556  \
557 scope __AUN void name ## _tlist_fini(struct m0_tl *head) \
558 { \
559  m0_tlist_fini(&name ## _tl, head); \
560 } \
561  \
562 scope __AUN void name ## _tlink_init(amb_type *amb) \
563 { \
564  m0_tlink_init(&name ## _tl, amb); \
565 } \
566  \
567 scope __AUN void name ## _tlink_init_at(amb_type *amb, struct m0_tl *head) \
568 { \
569  m0_tlink_init_at(&name ## _tl, amb, head); \
570 } \
571  \
572 scope __AUN void name ## _tlink_init_at_tail(amb_type *amb, struct m0_tl *head) \
573 { \
574  m0_tlink_init_at_tail(&name ## _tl, amb, head); \
575 } \
576  \
577 scope __AUN void name ## _tlink_fini(amb_type *amb) \
578 { \
579  m0_tlink_fini(&name ## _tl, amb); \
580 } \
581  \
582 scope __AUN void name ## _tlink_del_fini(amb_type *amb) \
583 { \
584  m0_tlink_del_fini(&name ## _tl, amb); \
585 } \
586  \
587 scope __AUN bool name ## _tlist_invariant(const struct m0_tl *list) \
588 { \
589  return m0_tlist_invariant(&name ## _tl, list); \
590 } \
591  \
592 scope __AUN bool name ## _tlist_invariant_ext(const struct m0_tl *list, \
593  bool (*check)(const amb_type *,\
594  void *), void *datum) \
595 { \
596  return m0_tlist_invariant_ext(&name ## _tl, list, \
597  (bool (*)(const void *, void *))check, datum); \
598 } \
599  \
600 scope __AUN bool name ## _tlist_is_empty(const struct m0_tl *list) \
601 { \
602  return m0_tlist_is_empty(&name ## _tl, list); \
603 } \
604  \
605 scope __AUN bool name ## _tlink_is_in (const amb_type *amb) \
606 { \
607  return m0_tlink_is_in(&name ## _tl, amb); \
608 } \
609  \
610 scope __AUN bool name ## _tlist_contains(const struct m0_tl *list, \
611  const amb_type *amb) \
612 { \
613  return m0_tlist_contains(&name ## _tl, list, amb); \
614 } \
615  \
616 scope __AUN size_t name ## _tlist_length(const struct m0_tl *list) \
617 { \
618  return m0_tlist_length(&name ## _tl, list); \
619 } \
620  \
621 scope __AUN void name ## _tlist_add(struct m0_tl *list, amb_type *amb) \
622 { \
623  m0_tlist_add(&name ## _tl, list, amb); \
624 } \
625  \
626 scope __AUN void name ## _tlist_add_tail(struct m0_tl *list, amb_type *amb) \
627 { \
628  m0_tlist_add_tail(&name ## _tl, list, amb); \
629 } \
630  \
631 scope __AUN void name ## _tlist_add_after(amb_type *amb, amb_type *next) \
632 { \
633  m0_tlist_add_after(&name ## _tl, amb, next); \
634 } \
635  \
636 scope __AUN void name ## _tlist_add_before(amb_type *amb, amb_type *next) \
637 { \
638  m0_tlist_add_before(&name ## _tl, amb, next); \
639 } \
640  \
641 scope __AUN void name ## _tlist_del(amb_type *amb) \
642 { \
643  m0_tlist_del(&name ## _tl, amb); \
644 } \
645  \
646 scope __AUN void name ## _tlist_remove(amb_type *amb) \
647 { \
648  m0_tlist_remove(&name ## _tl, amb); \
649 } \
650  \
651 scope __AUN void name ## _tlist_move(struct m0_tl *list, amb_type *amb) \
652 { \
653  m0_tlist_move(&name ## _tl, list, amb); \
654 } \
655  \
656 scope __AUN void name ## _tlist_move_tail(struct m0_tl *list, amb_type *amb) \
657 { \
658  m0_tlist_move_tail(&name ## _tl, list, amb); \
659 } \
660  \
661 scope __AUN amb_type *name ## _tlist_head(const struct m0_tl *list) \
662 { \
663  return (amb_type *)m0_tlist_head(&name ## _tl, list); \
664 } \
665  \
666 scope __AUN amb_type *name ## _tlist_pop(const struct m0_tl *list) \
667 { \
668  return (amb_type *)m0_tlist_pop(&name ## _tl, list); \
669 } \
670  \
671 scope __AUN amb_type *name ## _tlist_tail(const struct m0_tl *list) \
672 { \
673  return (amb_type *)m0_tlist_tail(&name ## _tl, list); \
674 } \
675  \
676 scope __AUN amb_type *name ## _tlist_next(const struct m0_tl *list, \
677  const amb_type *amb) \
678 { \
679  return (amb_type *)m0_tlist_next(&name ## _tl, list, amb); \
680 } \
681  \
682 scope __AUN amb_type *name ## _tlist_prev(const struct m0_tl *list, \
683  const amb_type *amb) \
684 { \
685  return (amb_type *)m0_tlist_prev(&name ## _tl, list, amb); \
686 } \
687  \
688 struct __ ## name ## _terminate_me_with_a_semicolon { ; }
689 
695 #define m0_tl_for(name, head, obj) m0_tlist_for(& name ## _tl, head, obj)
696 
700 #define m0_tl_endfor m0_tlist_endfor
701 
708 #define m0_tl_teardown(name, head, obj) \
709  while (((obj) = name ## _tlist_pop(head)) != NULL)
710 
711 
735 #define m0_tl_forall(name, var, head, ...) \
736 ({ \
737  typeof (name ## _tlist_head(NULL)) var; \
738  \
739  m0_tl_for(name, head, var) { \
740  if (!({ __VA_ARGS__ ; })) \
741  break; \
742  } m0_tlist_endfor; \
743  var == NULL; \
744 })
745 
757 #define m0_tl_find(name, var, head, ...) \
758 ({ \
759  typeof (name ## _tlist_head(NULL)) var; \
760  \
761  m0_tl_for(name, head, var) { \
762  if (({ __VA_ARGS__ ; })) \
763  break; \
764  } m0_tlist_endfor; \
765  var; \
766 })
767 
774 #define m0_tl_exists(name, var, head, ...) \
775  (!m0_tl_forall(name, var, head, !({ __VA_ARGS__ ; })))
776 
791 #define m0_tl_reduce(name, var, head, init, exp) \
792 ({ \
793  typeof (name ## _tlist_head(NULL)) var; \
794  typeof(init) __accum = (init); \
795  \
796  m0_tl_for(name, head, var) { \
797  __accum = __accum exp; \
798  } m0_tlist_endfor; \
799  __accum; \
800 })
801 
818 #define m0_tl_fold(name, var, accum, head, init, exp) \
819 ({ \
820  typeof (name ## _tlist_head(NULL)) var; \
821  typeof(init) accum = (init); \
822  \
823  m0_tl_for(name, head, var) { \
824  accum = exp; \
825  } m0_tlist_endfor; \
826  accum; \
827 })
828 
831 /* __MOTR_LIB_TLIST_H__ */
832 #endif
833 
834 /*
835  * Local variables:
836  * c-indentation-style: "K&R"
837  * c-basic-offset: 8
838  * tab-width: 8
839  * fill-column: 80
840  * scroll-step: 1
841  * End:
842  */
m0_tl_descr::td_link_magic_offset
int td_link_magic_offset
Definition: tlist.h:215
list
static struct m0_list list
Definition: list.c:144
m0_tlist_head
void * m0_tlist_head(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:187
m0_tlist_add_before
M0_INTERNAL void m0_tlist_add_before(const struct m0_tl_descr *d, void *obj, void *new)
Definition: tlist.c:149
m0_tlist_add
M0_INTERNAL void m0_tlist_add(const struct m0_tl_descr *d, struct m0_tl *list, void *obj)
Definition: tlist.c:125
m0_tlist_init
M0_INTERNAL void m0_tlist_init(const struct m0_tl_descr *d, struct m0_tl *list)
Definition: tlist.c:46
m0_tl::t_magic
uint64_t t_magic
Definition: tlist.h:256
m0_tlist_fini
M0_INTERNAL void m0_tlist_fini(const struct m0_tl_descr *d, struct m0_tl *list)
Definition: tlist.c:53
obj
static struct foo * obj
Definition: tlist.c:302
m0_tlist_is_empty
M0_INTERNAL bool m0_tlist_is_empty(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:96
m0_tlist_del
M0_INTERNAL void m0_tlist_del(const struct m0_tl_descr *d, void *obj)
Definition: tlist.c:157
m0_tl::t_head
struct m0_list t_head
Definition: tlist.h:258
m0_list_link
Definition: list.h:39
m0_tlist_prev
M0_INTERNAL void * m0_tlist_prev(const struct m0_tl_descr *d, const struct m0_tl *list, const void *obj)
Definition: tlist.c:227
m0_tl
Definition: tlist.h:251
next
static int next[]
Definition: cp.c:248
m0_tlink_fini
M0_INTERNAL void m0_tlink_fini(const struct m0_tl_descr *d, void *obj)
Definition: tlist.c:85
m0_tlist_next
void * m0_tlist_next(const struct m0_tl_descr *d, const struct m0_tl *list, const void *obj)
Definition: tlist.c:218
m0_tlist_remove
M0_INTERNAL void m0_tlist_remove(const struct m0_tl_descr *d, void *obj)
Definition: tlist.c:163
m0_tlist_move_tail
M0_INTERNAL void m0_tlist_move_tail(const struct m0_tl_descr *d, struct m0_tl *list, void *obj)
Definition: tlist.c:179
m0_tlist_length
M0_INTERNAL size_t m0_tlist_length(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:117
m0_tl_descr::td_link_magic
uint64_t td_link_magic
Definition: tlist.h:221
m0_tl_descr::td_container_size
size_t td_container_size
Definition: tlist.h:228
m0_tl_descr
Definition: tlist.h:204
m0_tlink_init
M0_INTERNAL void m0_tlink_init(const struct m0_tl_descr *d, void *obj)
Definition: tlist.c:63
m0_tl_descr::td_head_magic
uint64_t td_head_magic
Definition: tlist.h:226
m0_tlink
Definition: tlist.h:264
m0_list
Definition: list.h:72
m0_tlink_is_in
M0_INTERNAL bool m0_tlink_is_in(const struct m0_tl_descr *d, const void *obj)
Definition: tlist.c:103
m0_tl_descr::td_link_offset
int td_link_offset
Definition: tlist.h:208
m0_tlink_init_at_tail
M0_INTERNAL void m0_tlink_init_at_tail(const struct m0_tl_descr *d, void *obj, struct m0_tl *list)
Definition: tlist.c:78
m0_tlist_invariant
M0_INTERNAL bool m0_tlist_invariant(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:236
m0_tlink::t_link
struct m0_list_link t_link
Definition: tlist.h:266
m0_tlink_init_at
M0_INTERNAL void m0_tlink_init_at(const struct m0_tl_descr *d, void *obj, struct m0_tl *list)
Definition: tlist.c:71
check
void check(struct workload *w)
Definition: crate_client_utils.c:171
m0_tlist_pop
M0_INTERNAL void * m0_tlist_pop(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:197
M0_XCA_DOMAIN
struct m0_tl_descr M0_XCA_DOMAIN(be)
m0_tlist_move
M0_INTERNAL void m0_tlist_move(const struct m0_tl_descr *d, struct m0_tl *list, void *obj)
Definition: tlist.c:170
m0_tlist_add_after
M0_INTERNAL void m0_tlist_add_after(const struct m0_tl_descr *d, void *obj, void *new)
Definition: tlist.c:141
m0_tlist_tail
M0_INTERNAL void * m0_tlist_tail(const struct m0_tl_descr *d, const struct m0_tl *list)
Definition: tlist.c:207
m0_tlist_contains
M0_INTERNAL bool m0_tlist_contains(const struct m0_tl_descr *d, const struct m0_tl *list, const void *obj)
Definition: tlist.c:109
m0_tlink_invariant
M0_INTERNAL bool m0_tlink_invariant(const struct m0_tl_descr *d, const void *obj)
Definition: tlist.c:275
m0_tlist_add_tail
M0_INTERNAL void m0_tlist_add_tail(const struct m0_tl_descr *d, struct m0_tl *list, void *obj)
Definition: tlist.c:133
be
static struct m0_be_ut_backend be
Definition: service_ut.c:59
m0_tl_descr::td_name
const char * td_name
Definition: tlist.h:206
m0_tlist_invariant_ext
M0_INTERNAL bool m0_tlist_invariant_ext(const struct m0_tl_descr *d, const struct m0_tl *list, bool(*check)(const void *, void *), void *datum)
Definition: tlist.c:259
m0_tlink_del_fini
M0_INTERNAL void m0_tlink_del_fini(const struct m0_tl_descr *d, void *obj)
Definition: tlist.c:90