1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
list type
=========
we want to be able to handle several different scenarios:
- list in read only memory (this should perhaps be a separate type, or?)
- list in arena
- list in heap
- list in fragmented heap
type List<T> = (
enum .... # for type (List, Set, etc)? or just have one Set and one List type, and then a Collection wrapper which has the enum?
size length
size capacity
ref [capacity]T data
)
# we would like to have index types also (both for lists and arrays)
# Based type for both lists and collections?
# FIXME "kwb" needs only a byte but the following size/refs needs 32 or 64 bit alignment
# - for 32 bit we have 2 bits in the address that could be used, for 4 types
# - for 64 bit we have 3 bits, for 8 types
type Collection<E> =
case (
.EmptyList ( )
.EmptySet ( )
.MergedList ( size length, [length]E elems )
.KnownLengthList ( [length]E elems )
# Should we also have versions with relative pointers?
.ReadOnlyView (
size length
ref [length]E elems
)
.OneChunkList (
size length
size capacity
ownrwref [length]E elems
)
.MultiChunkList (
size length
size num_chunks
#ownrwref ChunkNode<E> root
ownrwref List<E> root_node
#ownrwref [num_chunks]ListChunk<E>
)
.ChunkNode (
size lowindex
[4](
ownrwref List<E> node
size highindex
) sub_nodes
)
#.JaggedList (
# when T is []U # XXX complex!
# size length
# [length]relative(data) ref offsets # XXX forward reference!
# []U
#)
# .JaggedByteList ( # XXX probably not needed?
# when type E == [*]byte # or char, if we should have a char type
# size length
# size total_length
# #[length]relative(data) ref offsets # XXX forward reference!
# [length]size[< total_length] offsets
# [total_length]byte data
# )
.JaggedList (
size length
#[length]size offsets
#
jaggedlist[length] E elems # generates elems_offsets and elems_data
)
.UnordedSet # TODO hashset
.OrderedSet # TODO linkedhashset or treeset
.JaggedSet # TODO how to initialize this at compile time?
.CustomList (
...vtable here...
)
.CustomSet (
...vtable here...
)
)
type List<T> = Collection<T> where case in
[.EmptyList, .MergedList, .KnownLengthList, .ReadOnlyView, .OneChunkList, .MultiChunkList, .JaggedList, .CustomList]
type Set<T> = Collection<T> where case in
[.EmptySet, .UnorderedSet, .OrderedSet, .JaggedSet, .CustomSet]
# Should it have a hashcode? and encoding (to support non-UTF-8/ASCII)?
type String = List<byte>
#type String = (uint32 hashcode, List<Byte>) # Alignment waste on 64-bit!
# So the following becomes a jagged array (List<String.Merged>.JaggedList)
const List<String> = ["Hello", "world", "!"]
|
