source: tests/zombies/linked-list-perf/mike-proto-list.hfa @ 9319a23

ADTast-experimental
Last change on this file since 9319a23 was 3c2c2f0, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

The cheap and chearful linked-list performance test

  • Property mode set to 100644
File size: 2.1 KB
Line 
1#include <assert.h>
2
3forall( tE & ) {
4
5    struct dlink{
6        tE *next;
7        tE *prev;
8    };
9
10    static inline void ?{}( dlink(tE) & this ) {
11        this.next = 0p;
12        this.prev = 0p;
13    }
14
15    forall( tLinks & = dlink(tE) ) {
16        struct dlist{
17            tE *first;
18            tE *last;
19        };
20
21        static inline void ?{}( dlist(tE, tLinks) & this ) {
22            this.first = 0p;
23            this.last = 0p;
24        }
25    }
26}
27
28trait embedded( tOuter &, tInner & ) {
29    tInner & ?`inner( tOuter & );
30};
31
32// embedded is reflexive
33forall( tX & )
34static inline tX & ?`inner( tX & this ) { return this; }
35
36// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
37#define P9_EMBEDDED( tOuter, tInner ) \
38    static inline tInner & ?`inner( tOuter & this ) { return this; }
39
40
41forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
42    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
43        if (lst.last) {
44            verify(lst.first);
45            dlink(tE) & oldLastLinks = (*lst.last)`inner`inner;
46            verify(oldLastLinks.next == 0p);
47            oldLastLinks.next = & e;
48        } else {
49            verify(!lst.first);
50            lst.first = &e;
51        }
52        dlink(tE) & newLastLinks = e`inner`inner;
53        verify(newLastLinks.prev == 0p);
54        verify(newLastLinks.next == 0p);
55        newLastLinks.prev = lst.last;
56        lst.last = &e;
57    }
58    static inline void remove_first( dlist(tE, tLinks) &lst ) {
59        verify(lst.first && lst.last);
60        dlink(tE) & oldFirstLinks = (*lst.first)`inner`inner;
61        verify(oldFirstLinks.prev == 0p);
62        if( lst.last != lst.first) {
63            verify(oldFirstLinks.next != 0p);
64            tE & newFirst = * oldFirstLinks.next;
65            dlink(tE) & newFirstLinks = (newFirst)`inner`inner;
66            oldFirstLinks.next = 0p;
67            newFirstLinks.prev = 0p;
68            lst.first = & newFirst;
69        } else {
70            verify(oldFirstLinks.next == 0p);
71            lst.last = 0p;
72            lst.first = 0p;
73        }
74    }
75}
Note: See TracBrowser for help on using the repository browser.