7#if defined(__GNUC__) && (__GNUC__<9) && !defined(__clang__)
19#if __cplusplus >= 201100
20#define HAVE_CPP_THREADS
23#undef HAVE_CPP_THREADS
102#ifdef HAVE_CPP_THREADS
103 std::atomic_flag _lock;
104 short _owner, _head, _tail;
109#ifdef HAVE_CPP_THREADS
117#ifdef HAVE_CPP_THREADS
122 _owner = other._owner;
127 FastLock &operator=(
const FastLock &other) {
128 _owner = other._owner;
142 struct flock &lock_info,
size_t offset,
size_t len,
bool lock);
160struct ProcessChannel;
172#ifdef HAVE_CPP_THREADS
194struct ProcessChannel {
213 return (
prev & 3) != 1;
217 return (
int)
data[0];
238 return (Block *) (
base + addr);
242 return block->is_free();
245 return (
void *) (
base + addr);
296 Status
init(
const char *path);
308#ifdef HAVE_CPP_THREADS
310 std::atomic<ptrdiff_t>
rc;
315 return (ptrdiff_t)
rc;
319 return (ptrdiff_t)
rc;
358 return addr ^ (1 <<
level);
365 char *addr = (
char *) ptr -
sizeof(Block);
369 size_t offset = (
unsigned char *) ptr - segstart;
429 return vaddr == other.vaddr;
432 return vaddr != other.vaddr;
434 operator bool()
const {
465 template <
typename U>
469 static VRef<T>
alloc(
size_t n = 1) {
495 operator bool()
const {
499 return vaddr == other.vaddr;
502 return vaddr != other.vaddr;
516 VRef<void> &
operator=(VRef<void> other) {
520 template <
typename U>
524 static VRef<void>
alloc(
size_t n = 1) {
555 for (
size_t i = 0;
i < n;
i++) {
567template <
typename T,
typename Arg>
568VRef<T>
vnew(Arg arg) {
574template <
typename T,
typename Arg1,
typename Arg2>
575VRef<T>
vnew(Arg1 arg1, Arg2 arg2) {
577 new (
result.to_ptr())
T(arg1, arg2);
581template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3>
582VRef<T>
vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
584 new (
result.to_ptr())
T(arg1, arg2, arg3);
588template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3,
590VRef<T>
vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4) {
592 new (
result.to_ptr())
T(arg1, arg2, arg3, arg4);
596template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3,
597 typename Arg4,
typename Arg5>
598VRef<T>
vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5) {
600 new (
result.to_ptr())
T(arg1, arg2, arg3, arg4, arg5);
608 internals::refcount_t
rc;
609#if __cplusplus >= 201100
612 char data[
sizeof(
T)];
653 template <
typename U>
654 ZRef<U>
cast()
const {
655 return ZRef<U>(
vaddr);
698 for (
size_t i = 0;
i < n;
i++) {
710template <
typename T,
typename Arg>
711ZRef<T>
znew(Arg arg) {
717template <
typename T,
typename Arg1,
typename Arg2>
718ZRef<T>
znew(Arg1 arg1, Arg2 arg2) {
720 new (
result.to_ptr())
T(arg1, arg2);
724template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3>
725ZRef<T>
znew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
727 new (
result.to_ptr())
T(arg1, arg2, arg3);
739 _buffer = vnew_uninitialized_array<char>(
_len + 1);
744 _buffer = vnew_uninitialized_array<char>(
len + 1);
746 memcpy(buffer,
s,
len);
751 _buffer = vnew_uninitialized_array<char>(
len + 1);
760 VRef<VString>
clone()
const {
763 const char *
str()
const {
768static inline VRef<VString>
vstring(
const char *
s) {
769 return vnew<VString>(
s);
772static inline VRef<VString>
vstring(
const char *
s,
size_t len) {
773 return vnew<VString>(
s, len);
776static inline VRef<VString>
vstring(
size_t len) {
777 return vnew<VString>(len);
781template <
typename Spec>
784 typedef typename Spec::Key
K;
785 typedef typename Spec::Value
V;
793 VRef<internals::FastLock>
_locks;
806 bool add(VRef<K> key, VRef<V> value, VRef<K> &oldkey, VRef<V> &oldvalue,
807 bool replace =
true);
808 bool add(VRef<K> key, VRef<V> value,
bool replace =
true) {
811 return add(key, value, oldkey, oldvalue, replace);
813 bool remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue);
814 bool remove(VRef<K> key) {
817 return remove(key, oldkey, oldvalue);
819 bool find(VRef<K> key, VRef<V> &value);
820 VRef<V>
find(VRef<K> key) {
822 if (
find(key, value))
829template <
typename Spec>
831 using namespace internals;
833 while (_nbuckets <
size)
835 _buckets = vnew_array<VRef<Node> >(_nbuckets);
836 _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
837 for (
size_t i = 0;
i < _nbuckets;
i++)
842template <
typename Spec>
844 for (
size_t b = 0;
b < _nbuckets;
b++) {
846 VRef<Node> node = _buckets[
b];
848 Node *node_ptr = node.as_ptr();
849 VRef<Node>
next = node_ptr->next;
850 Spec::free_key(node_ptr->key);
851 Spec::free_value(node_ptr->value);
861template <
typename Spec>
863 VRef<V> &oldvalue,
bool replace) {
864 size_t hash = Spec::hash(key.as_ptr());
865 size_t b = hash & (_nbuckets - 1);
867 VRef<Node> node = _buckets[
b];
868 VRef<Node>
last = vnull<Node>();
869 while (!node.is_null()) {
870 Node *node_ptr = node.as_ptr();
871 if (hash == node_ptr->hash
872 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
873 value = node_ptr->value;
874 if (!
last.is_null()) {
876 last->next = node_ptr->next;
877 node_ptr->next = _buckets[
b];
880 oldkey = node_ptr->key;
881 oldvalue = node_ptr->value;
884 node_ptr->value = value;
893 Node *node_ptr = node.as_ptr();
894 node_ptr->hash = hash;
896 node_ptr->value = value;
897 node_ptr->next = _buckets[
b];
905template <
typename Spec>
907 size_t hash = Spec::hash(key.as_ptr());
908 size_t b = hash & (_nbuckets - 1);
910 VRef<Node> node = _buckets[
b];
911 VRef<Node>
last = vnull<Node>();
912 while (!node.is_null()) {
913 Node *node_ptr = node.as_ptr();
914 if (hash == node_ptr->hash
915 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
916 oldkey = node_ptr->key;
917 oldvalue = node_ptr->value;
919 if (
last.is_null()) {
920 _buckets[
b] = node_ptr->next;
922 last->next = node_ptr->next;
934template <
typename Spec>
936 size_t hash = Spec::hash(key.as_ptr());
937 size_t b = hash & (_nbuckets - 1);
939 VRef<Node> node = _buckets[
b];
940 VRef<Node>
last = vnull<Node>();
941 while (!node.is_null()) {
942 Node *node_ptr = node.as_ptr();
943 if (hash == node_ptr->hash
944 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
945 value = node_ptr->value;
947 if (!
last.is_null()) {
948 last->next = node_ptr->next;
949 node_ptr->next = _buckets[
b];
964 typedef VString
Value;
965 static size_t hash(
const VString *
s) {
967 size_t len =
s->len();
968 const char *
str =
s->str();
970 for (
size_t i = 0;
i < len;
i++) {
975 static bool equal(
const VString *s1,
const VString *s2) {
976 if (s1->len() != s2->len())
978 size_t len = s1->len();
979 const char *str1 = s1->str(), *str2 = s2->str();
980 for (
size_t i = 0;
i < len;
i++) {
981 if (str1[
i] != str2[
i])
992 static void free_key(VRef<Key> key) {
1000typedef VMap<DictSpec>
VDict;
1004#ifdef HAVE_CPP_THREADS
1005typedef internals::FastLock
FastLock;
1010typedef internals::Mutex
Mutex;
1029 template <
typename T>
1046template <
typename T>
1060 if (
_head->next.is_null()) {
1067 void push(VRef<Node> node) {
1068 node->next = vnull<Node>();
1069 if (
_tail.is_null()) {
1076 template <
typename U>
1078 template <
typename U>
1083 VRef<Node> node = vnew<Node>();
1091 VRef<Node> node =
pop();
1135template <
typename T>
1139 VRef<Semaphore>
_sem;
1142 template <
typename U>
1156template <
typename T>
1164 if (_sem.is_null()) {
1165 _sem = vnew<Semaphore>();
1167 bool result = _sem->start_wait(sig);
1172template <
typename T>
1175 if (!_sem.is_null()) {
1183template <
typename T>
1190 if (_sem.is_null()) {
1191 _sem = vnew<Semaphore>();
1200 _sem->start_wait(0);
1208 _sem = vnull<Semaphore>();
1214template <
typename T>
1217 Result<T>
result = _set ? Result<T>(_value) : Result<
T>();
1222template <
typename T>
1253 void add(Event *event);
1254 void add(Event &event) {
1268class WaitSemaphoreEvent :
public Event {
1270 VRef<Semaphore>
_sem;
1276 return _sem->start_wait(sig);
1285template <
typename T>
1286class EnqueueEvent :
public Event {
1294 return _queue->_outgoing.start_wait(sig);
1297 _queue->_outgoing.stop_wait();
1300 _queue->enqueue_nowait(item);
1304template <
typename T>
1305class DequeueEvent :
public Event {
1313 return _queue->_incoming.start_wait(sig);
1316 _queue->_incoming.stop_wait();
1319 return _queue->dequeue_nowait();
1323template <
typename T>
1324class SyncReadEvent :
public Event {
1350#if __cplusplus >= 201100
1351#define HAVE_CPP_THREADS
1354#undef HAVE_CPP_THREADS
1383template <
typename T>
1410namespace internals {
1433#ifdef HAVE_CPP_THREADS
1434 std::atomic_flag _lock;
1435 short _owner, _head, _tail;
1440#ifdef HAVE_CPP_THREADS
1448#ifdef HAVE_CPP_THREADS
1453 _owner = other._owner;
1454 _head = other._head;
1455 _tail = other._tail;
1460 _head = other._head;
1461 _tail = other._tail;
1473 struct flock &lock_info,
size_t offset,
size_t len,
bool lock);
1503#ifdef HAVE_CPP_THREADS
1544 return (
prev & 3) != 1;
1548 return (
int)
data[0];
1576 return block->is_free();
1579 return (
void *) (
base + addr);
1641#ifdef HAVE_CPP_THREADS
1643 std::atomic<std::ptrdiff_t>
rc;
1644 refcount_t(std::ptrdiff_t init) :
rc(init) {
1648 return (std::ptrdiff_t)
rc;
1652 return (std::ptrdiff_t)
rc;
1691 return addr ^ (1 <<
level);
1698 char *addr = (
char *) ptr -
sizeof(
Block);
1702 size_t offset = (
unsigned char *) ptr - segstart;
1746template <
typename T>
1762 return vaddr == other.vaddr;
1765 return vaddr != other.vaddr;
1767 operator bool()
const {
1792 vaddr = other.vaddr;
1798 template <
typename U>
1828 operator bool()
const {
1832 return vaddr == other.vaddr;
1835 return vaddr != other.vaddr;
1847 return (
void *)
to_ptr();
1850 vaddr = other.vaddr;
1853 template <
typename U>
1866template <
typename T>
1871template <
typename T>
1878template <
typename T>
1884template <
typename T>
1888 for (
size_t i = 0;
i < n;
i++) {
1894template <
typename T>
1900template <
typename T,
typename Arg>
1907template <
typename T,
typename Arg1,
typename Arg2>
1910 new (
result.to_ptr())
T(arg1, arg2);
1914template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3>
1917 new (
result.to_ptr())
T(arg1, arg2, arg3);
1921template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3,
1925 new (
result.to_ptr())
T(arg1, arg2, arg3, arg4);
1929template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3,
1930 typename Arg4,
typename Arg5>
1933 new (
result.to_ptr())
T(arg1, arg2, arg3, arg4, arg5);
1937template <
typename T>
1942#if __cplusplus >= 201100
1984 vaddr = other.vaddr;
1986 template <
typename U>
2009template <
typename T>
2014template <
typename T>
2021template <
typename T>
2027template <
typename T>
2031 for (
size_t i = 0;
i < n;
i++) {
2037template <
typename T>
2043template <
typename T,
typename Arg>
2050template <
typename T,
typename Arg1,
typename Arg2>
2053 new (
result.to_ptr())
T(arg1, arg2);
2057template <
typename T,
typename Arg1,
typename Arg2,
typename Arg3>
2060 new (
result.to_ptr())
T(arg1, arg2, arg3);
2071 _len = std::strlen(
s);
2072 _buffer = vnew_uninitialized_array<char>(
_len + 1);
2077 _buffer = vnew_uninitialized_array<char>(
len + 1);
2079 std::memcpy(buffer,
s,
len);
2084 _buffer = vnew_uninitialized_array<char>(
len + 1);
2102 return vnew<VString>(
s);
2106 return vnew<VString>(
s, len);
2110 return vnew<VString>(len);
2114template <
typename Spec>
2117 typedef typename Spec::Key
K;
2118 typedef typename Spec::Value
V;
2140 bool replace =
true);
2144 return add(key, value, oldkey, oldvalue, replace);
2150 return remove(key, oldkey, oldvalue);
2155 if (
find(key, value))
2162template <
typename Spec>
2164 using namespace internals;
2166 while (_nbuckets <
size)
2168 _buckets = vnew_array<VRef<Node> >(_nbuckets);
2169 _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
2170 for (
size_t i = 0;
i < _nbuckets;
i++)
2175template <
typename Spec>
2177 for (
size_t b = 0;
b < _nbuckets;
b++) {
2181 Node *node_ptr = node.as_ptr();
2183 Spec::free_key(node_ptr->key);
2184 Spec::free_value(node_ptr->value);
2194template <
typename Spec>
2196 VRef<V> &oldvalue,
bool replace) {
2197 size_t hash = Spec::hash(key.as_ptr());
2198 size_t b = hash & (_nbuckets - 1);
2202 while (!node.is_null()) {
2203 Node *node_ptr = node.as_ptr();
2204 if (hash == node_ptr->hash
2205 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2206 value = node_ptr->
value;
2207 if (!
last.is_null()) {
2209 last->next = node_ptr->next;
2210 node_ptr->next = _buckets[
b];
2213 oldkey = node_ptr->key;
2214 oldvalue = node_ptr->value;
2216 node_ptr->key = key;
2217 node_ptr->value = value;
2225 node = vnew<Node>();
2226 Node *node_ptr = node.as_ptr();
2227 node_ptr->
hash = hash;
2228 node_ptr->key = key;
2229 node_ptr->value = value;
2230 node_ptr->next = _buckets[
b];
2238template <
typename Spec>
2240 size_t hash = Spec::hash(key.as_ptr());
2241 size_t b = hash & (_nbuckets - 1);
2245 while (!node.is_null()) {
2246 Node *node_ptr = node.as_ptr();
2247 if (hash == node_ptr->hash
2248 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2249 oldkey = node_ptr->
key;
2250 oldvalue = node_ptr->value;
2252 if (
last.is_null()) {
2253 _buckets[
b] = node_ptr->next;
2255 last->next = node_ptr->next;
2267template <
typename Spec>
2269 size_t hash = Spec::hash(key.as_ptr());
2270 size_t b = hash & (_nbuckets - 1);
2274 while (!node.is_null()) {
2275 Node *node_ptr = node.as_ptr();
2276 if (hash == node_ptr->hash
2277 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2278 value = node_ptr->
value;
2280 if (!
last.is_null()) {
2281 last->next = node_ptr->next;
2282 node_ptr->next = _buckets[
b];
2300 size_t len =
s->len();
2301 const char *str =
s->str();
2303 for (
size_t i = 0;
i < len;
i++) {
2309 if (s1->len() != s2->len())
2311 size_t len = s1->len();
2312 const char *str1 = s1->str(), *str2 = s2->str();
2313 for (
size_t i = 0;
i < len;
i++) {
2314 if (str1[
i] != str2[
i])
2337#ifdef HAVE_CPP_THREADS
2362 template <
typename T>
2379template <
typename T>
2393 if (
_head->next.is_null()) {
2401 node->next = vnull<Node>();
2402 if (
_tail.is_null()) {
2409 template <
typename U>
2411 template <
typename U>
2468template <
typename T>
2475 template <
typename U>
2489template <
typename T>
2497 if (_sem.is_null()) {
2498 _sem = vnew<Semaphore>();
2500 bool result = _sem->start_wait(sig);
2505template <
typename T>
2508 if (!_sem.is_null()) {
2516template <
typename T>
2523 if (_sem.is_null()) {
2524 _sem = vnew<Semaphore>();
2533 _sem->start_wait(0);
2541 _sem = vnull<Semaphore>();
2547template <
typename T>
2555template <
typename T>
2609 return _sem->start_wait(sig);
2618template <
typename T>
2627 return _queue->_outgoing.start_wait(sig);
2630 _queue->_outgoing.stop_wait();
2633 _queue->enqueue_nowait(item);
2637template <
typename T>
2646 return _queue->_incoming.start_wait(sig);
2649 _queue->_incoming.stop_wait();
2652 return _queue->dequeue_nowait();
2656template <
typename T>
static CanonicalForm bound(const CFMatrix &M)
DequeueEvent(VRef< Queue< T > > queue)
VRef< Queue< T > > _queue
virtual void stop_listen()
virtual bool start_listen(internals::ipc_signal_t sig)
virtual void stop_listen()
VRef< Queue< T > > _queue
virtual bool start_listen(internals::ipc_signal_t sig)
EnqueueEvent(VRef< Queue< T > > queue)
EventSet & operator<<(Event &event)
EventSet & operator<<(Event *event)
virtual void stop_listen()=0
virtual bool start_listen(internals::ipc_signal_t sig)=0
Result< T > try_dequeue()
void push(VRef< Node > node)
friend class EnqueueEvent
friend class DequeueEvent
void enqueue_nowait(T item)
int _waiting[internals::MAX_PROCESS+1]
bool start_wait(internals::ipc_signal_t sig=0)
internals::ipc_signal_t _signals[internals::MAX_PROCESS+1]
Semaphore(size_t value=0)
virtual bool start_listen(internals::ipc_signal_t sig)
SyncReadEvent(VRef< SyncVar< T > > syncvar)
virtual void stop_listen()
VRef< SyncVar< T > > _syncvar
friend class SyncReadEvent
bool start_wait(internals::ipc_signal_t sig)
bool remove(VRef< K > key, VRef< K > &oldkey, VRef< V > &oldvalue)
bool find(VRef< K > key, VRef< V > &value)
void _lock_bucket(size_t b)
VRef< V > find(VRef< K > key)
bool remove(VRef< K > key)
VRef< VRef< Node > > _buckets
bool add(VRef< K > key, VRef< V > value, bool replace=true)
bool add(VRef< K > key, VRef< V > value, VRef< K > &oldkey, VRef< V > &oldvalue, bool replace=true)
void _unlock_bucket(size_t b)
VRef< internals::FastLock > _locks
VString(const char *s, size_t len)
VRef< VString > clone() const
WaitSemaphoreEvent(VRef< Semaphore > sem)
virtual bool start_listen(internals::ipc_signal_t sig)
virtual void stop_listen()
FastLock(vaddr_t offset=0)
const CanonicalForm int s
STATIC_VAR unsigned add[]
void drop_pending_signals()
void init_flock_struct(struct flock &lock_info, size_t offset, size_t len, bool lock)
void lock_file(int fd, size_t offset, size_t len)
void vmem_free(vaddr_t vaddr)
Block * block_ptr(vaddr_t vaddr)
vaddr_t vmem_alloc(size_t size)
static vaddr_t allocated_ptr_to_vaddr(void *ptr)
static const size_t MAX_SEGMENTS
vaddr_t freelist[LOG2_SEGMENT_SIZE+1]
static const size_t SEGMENT_SIZE
static const size_t METABLOCK_SIZE
static const int LOG2_SEGMENT_SIZE
ipc_signal_t wait_signal(bool lock)
static const int LOG2_MAX_SEGMENTS
static const int MAX_PROCESS
ProcessInfo process_info[MAX_PROCESS]
static segaddr_t find_buddy(segaddr_t addr, int level)
ipc_signal_t check_signal(bool resume, bool lock)
void init_metapage(bool create)
void unlock_file(int fd, size_t offset, size_t len)
static const size_t SEGMENT_MASK
bool send_signal(int processno, ipc_signal_t sig, bool lock)
static int find_level(size_t size)
const segaddr_t SEGADDR_NULL
VRef< T > vnew_uninitialized_array(size_t n)
ZRef< T > znew_array(size_t n)
static void vmem_deinit()
ZRef< T > znew_uninitialized()
VRef< T > vnew_array(size_t n)
ZRef< T > znew_uninitialized_array(size_t n)
VRef< T > vnew_uninitialized()
static Status vmem_init()
static VRef< VString > vstring(const char *s)
internals::Mutex FastLock
static int index(p_Length length, p_Ord ord)
int status int void size_t count write
static void free_value(VRef< Value > value)
static bool equal(const VString *s1, const VString *s2)
static size_t hash(const VString *s)
static void free_key(VRef< Key > key)
bool operator!=(VRef< void > other)
VRef< void > & operator=(VRef< void > other)
bool operator==(VRef< void > other)
static VRef< void > from_vaddr(internals::vaddr_t vaddr)
VRef(internals::vaddr_t vaddr)
static VRef< void > alloc(size_t n=1)
VRef< T > & operator=(VRef< T > other)
static VRef< T > alloc(size_t n=1)
VRef(internals::vaddr_t vaddr)
bool operator!=(VRef< T > other)
static VRef< T > from_vaddr(internals::vaddr_t vaddr)
T & operator[](size_t index)
bool operator==(VRef< T > other)
internals::refcount_t & refcount()
ZRef(internals::vaddr_t vaddr)
ZRef< T > & operator=(ZRef< T > other)
static internals::vaddr_t alloc()
void mark_as_free(int level)
void mark_as_allocated(vaddr_t vaddr, int level)
void ensure_is_mapped(vaddr_t vaddr)
Block * block_ptr(vaddr_t vaddr)
size_t segment_no(vaddr_t vaddr)
void * mmap_segment(int seg)
VSeg segment(vaddr_t vaddr)
void * to_ptr(vaddr_t vaddr)
VSeg segments[MAX_SEGMENTS]
vaddr_t vaddr(size_t segno, segaddr_t addr)
segaddr_t segaddr(vaddr_t vaddr)
ProcessChannel channels[MAX_PROCESS]
Block * block_ptr(segaddr_t addr)
void * ptr(segaddr_t addr)
bool is_free(segaddr_t addr)
static void lock(vaddr_t vaddr)
std::ptrdiff_t dec(vaddr_t vaddr)
refcount_t(std::ptrdiff_t init)
std::ptrdiff_t inc(vaddr_t vaddr)
static void unlock(vaddr_t vaddr)