<commit_before>
// plan: 
// - ConcurrentHash is a lava_vec and is at the start of the memory
// - ConcurrentStore takes up the rest of the memory
// | - ConcurrentStore is made up of ConcurrentList at the start of its memory
// | - block memory is everything after ConcurrentList
// - The order ends up being ConcurentHash, ConcurrentList, then block storage

// -todo: hash key data instead of the block index of the key
//       --create function to hash arbitrary bytes 
//       --create function to put into a hashmap with a pre-hashed value
// -todo: make bitwise compare function between blocks
// -todo: make a function to compare a block to an arbitrary byte buffer
// -todo: change store_kv to use compare exchange and return previous kv ?
// -todo: make remove function for ConcurrentStore? - just use free
// -todo: remove overwritten indices from the ConcurrentStore
// -todo: figure out why "wat" and "wut" match - 3 bugs: unsigned size_t in the blockcompare function, not flipping the signs of the next index when it is negative (for length), default value of true when while loop ends from the blocks comparing as false
// -todo: figure out why second insert is putting EMPTY_KEY for key and value in the hash map - comp returns true even though strings are different?
// -todo: use match function instead of block comparison for everything? better for continguous memory anyway?
// -todo: fix not finding a key too long to fit in block - wasn't updating the current block index in the loop
// -todo: return an error on running out of blocks - done with a negative blockcount if not enough blocks are available
// -todo: free blocks if not enough block are allocated
// -todo: fix infinite loop on free - last block wasn't getting next block index set when reaching LIST_END 
// -todo: deal with memory / allocate from  shared memory
// -todo: make a membuf class that encapsulates a shared memory buffer / memory mapped file on windows or linux
// -todo: make remove function
// -todo: add const to thread safe functions
// -todo: figure out why readers is so high - uninitialized KV struct in a put function
// -todo: do KV structs need versions? can an identical KV struct ever be inserted? only if the List somehow gave up identical indices, which shouldn't happen?
// -todo: test deletion from db
// -todo: check when reading if something is marked for deletion and return 0 / EMPTY_KEY if it is
// -todo: make remove function concurrent and account for the number of readers
// -todo: make remove decremented the readers but don't actually delete, so that the last reader out would delete, maybe just make a flag as mark for deletion?
// -todo: make addReaders not add any readers below zero
// -todo: figure out how to deal with deletion when there is a concurrent write - reset the readers and hash?
// -todo: make -1 an error instead of returning a length of 0? - distinguising a key with length 0 and no key could be useful 
// -todo: is only the key being deleted? - no, but vals should be removed before keys to keep the order more consistent, all other things being equal
// -todo: need to fix ConcurrentList free? it writes to the list before the compare_swap has gone through? - no, because writing to taken indices in the list doesn't matter + only one thread should be freeing a specific index at a time - if two threads were freeing the same index on top of each other, a problem bigger than atomics would be that even if both operations went through, there would be a double free
// -todo: change public get methods to use read - took out one get and changed the other to being private getFromBlkIdx
// -todo: fix shared memory aligned allocation
// -todo: make SharedMem check if the mem file already exists
// -todo: test opening the db from multiple processes - didn't work at first, likely because the copy constructor was not deleted and the destructor was run early
// -todo: test lava_vec with external memory
// -todo: convert ConcurrenList to use lava_vec
// -todo: fix hash function hashing string() different from const char* - off by one error was hashing an extra 32 bits
// -todo: fix block memory being written but get() not working (ConcurrentList not correct yet?) - hash problem, not ConcurrentList problem
// -todo: need to make ConcurrentList a flat data structure so it can be store at the start of the memory mapped file
// -todo: make ConcurrentHash flat using lava_vec
// -todo: make Store and Hash both take bool for ownership to decide whether or not to init
// -todo: test using the db from multiple processes
// -todo: make simdb read the sizes from the the database - if the Store uses the size as the head and the hashmap is sized larger than the number of blocks, how to get the number of elements? - made 12 bytes at the start of the shared memory
// -todo: store blockSize and blockCount and flags in the starting three ui64 slots
// -todo: make flag to see if the db has been initialized yet to mitigate race conditions on creating and opening the memory mapping
// -todo: make post build run a copy command for an extra .exe that can be run while the primary exe is overwritten by the compiler
// -todo: figure out why memory is different on second run - why does "wat" get inserted again? - working as intended?
// -todo: try zeroing memory of each block on free - works, just needs two memset() calls just as there are two free() calls to the list
// -todo: move block lists to a lava_vec
// -todo: figure out why memory seem correct but get is not working - just the check of readers being below or equal to zero
// -todo: make decReaders run doFree ? 
// -todo: add readers inc and dec to matching - made memcmpBlk function
// -todo: test db.rm 
// -todo: make readers on a per block level
// -todo: make free decrement block readers
// -todo: move readers to the ConcurrentStore
// -todo: make comparison function in ConcurrentHash that increments and decrements reader
// -todo: should rm on the last put erase their memory? - yes, wasn't resetting readers
// -todo: figure out why get returns -1  -  no return statement, just empty probedKv.key; 
// -todo: figure out why get after put isn't working - was switching the order of readers and index in BlkLst struct
// -todo: figure out why put after rm doesn't show up with get - readers not being reset on allocation? - forgot to take out the free-ing in put() 
// -todo: make both free and read give back a block with last one out strategy
// -todo: test again with multiple processes after redoing rm() technique - without put deleting old elements, how to get rid of overwritten elements? - needed to put back deleting in put(), but make sure rm() swaps in EMPTY_KEY
// -todo: make rmHashed return EMPTY_KEY on MATCH_REMOVED
// -todo: take readers out of hash struct 
// -todo: move hash functions to be static instead of member functions
// -todo: look up better hash function - fnv
// -todo: clean up fnv
// -todo: try making macro with ALLOCA to create a stack based lava_vec
// -todo: load blockSize and blockLength from existing shared memory
// -todo: make function to query size - simb.len(key)
// -todo: make setting the key flag be the last thing when allocating 
// -todo: have last one out remove hash index
// -todo: add removal of blocks to CH doFree ? - no, simdb does that
// -todo: make incReaders for ConcurrentHash
// -todo: have to make hash the authority, give KV struct a reader count
// -todo: put incReaders and decReaders around match function call in ConcurrentHash functions
// -todo: make setting the key flag be the first thing when freeing - actually done in decReaders
// todo: make indexed list of keys
//       -create a bitset in the ConcurrentHash? - can't use ConcurrentHash because blocks could change after query
//       -bitset has to be atomic? - can't create bitset because the key flag, reader count, and index all have to be together?
// done  -use key flag in Block Index struct, treat the entire thing as a 64 bit atomic
// done  -iterate through BlkLst vector to find the next key - done in ConcurrenHash
// done  -after a key is found, get the length of that block index
// done    -when getting the length, check if the block is a key, if not, return an error
// done    -check if the key is not empty
// done    -check if the readers is not less than 0
//       -after getting the length, read from the block index, again checking if the block index is a key and if not, returning an error 
// -todo: can cleanup be done by checking the CH entry after read and setting a flag to delete the old version? - no, because this would only shield one overlap, if more threads were swapping CH entries, they would have to wait/spinlock

// todo: make readers for blocks only exist on the head of the list?
// todo: make sure that a block isn't read from if readers<0
// todo: do a write up on overall structure
// todo: need more data with BlkIdx so that blocks read are known to be from the correct key value pair
// todo: need to have a version with each block and store it with each non head BlkIdx as well as the key value pair of ConcurrentHash - how many bits for the version? 32 bits to start? - just needs to be enough so that a so many blocks can't be gotten while a thread is stalled that the version wraps back around
// todo: have to put version in concurrent hash so that an overwrite from a new write won't cause an ABA problem with another thread reading from it, then decrementing readers?
// todo: make ConcurrentStore.get take a length that it won't exceed
// todo: do a write up on if linear search is neccesary because a hash could land on a KV that has readers as -1 ?  - no different than any other hash map? - search stops on an empty key, but it shouldn't stop on readers<0 ? what happens if a key is inserted a few slots from where the hash lands, then the original landing place is removed? does the empty key stop the search?
// todo: work out how doFree from ConcurrentHash connects to removing blocks 
// todo: redo simdb functions to use runRead
// todo: test looking up values from the iterated keys
// todo: give put() return type a BLKIDX type
// todo: take out size_t from ConcurrentStore
// todo: organize all C++ functions separate from C functions so that they can be #ifdef out if used as a C library
// todo: implement get that takes an index into ConcurrentHash - 0 length does nothing, length must be inout, if key is empty or readers is < 0, make length 0 and do nothing 
// todo: make sure when looping through keys, that readers is not negative? all reads must be atomic? all BlkLst must have their original index embedded? ConcurrentHash does need readers after all?
// todo: make alloc give back blocks if allocation fails
// todo: flip decReaders return value
// todo: can make a bitmap for filled hash indices if the bit is set after the KV is set, and the bit is unset before unsetting the KV
// todo: combine keys and data into one block run
// todo: make len be a direct lookup somehow? - if ConcurrentHash is the authority, len can be done the same way as an  empty/full bitset ? 
// todo: change ConcurrentHash to no longer be only powers of 2

// todo: change string to pass through to c_str() and const char* overload
// todo: take out power of 2 size restriction and use modulo
// todo: use blockSize and blockCount from the already created shared mem if not the owner
// todo: store size in the ConcurrentList? list isn't atomic so it should work well? should block lists, key sizes, and val sizes all be in their own lava_vecs ? 
// todo: redo concurrent store get to store length so that buffer can be returned
// todo: test with multiple threads in a loop
// todo: store lengths and check key lengths before trying bitwise comparison as an optimization? - would only make a difference for long keys that are larger than one block? no it would make a difference on every get?
// todo: prefetch memory for next block when looping through blocks
// todo: move to using packed key value in one block list
// todo: can block sync be done with a removed flag instead of just using readers?
// todo: change lava_vec name to flat_vec?

// todo: combine key and value storage so they are packed together in the same block list?
// todo: mark free cells as negative numbers so double free is caught? - do it only in debug mode?
// todo: make erase function that 0s out bytes? - only in debug mode?
// todo: Make block size for keys different than data?
// todo: lock init with mutex?
// todo: implement locking resize?
// todo: should the readers be integrated with the list also? 
// todo: make SharedMemory take an address and destructor, or make simdb take an address and destructor to use arbitrary memory?

//Block based allocation
//-Checking if the head has been touched means either incrementing a counter every time it is written, or putting in a thread id every time it is read or written
//-Each ui32 in a vector holds the position of the next free block 
//-Alloc checks the head to read the next free position and puts it in head if head hasn't been touched. 
//-Free checks the head to read the next free position, stores the head value in the free position, then moves head to the just written new free position if head hasn't been touched

//
// Make frees happen from the last block to the first - don't remember what this means

// idea: use max_waste as a recipricol power of two giving the percentage of waste allowed for an allocation
// - 2 would be 25%, 3 would be 12.5% 
// - not allowed to be below 2
// idea: put atomic reader counter into each ConcurrentStore entry as a signed integer
// idea: figure out how to make ConcurrentHash a flat data structure so it can sit in shared memory

// q: can cleanup be done by a ring buffer of block lists? would the ring buffer only need to be as long as the number of threads if each thread helps clear out the ring buffer after every free()? Probably not, because delayed deallocation would be useful only when there is a reader/ref count, which would mean many more reads than writes could stall the ability to free? But each thread can really only hold one reference at a time so maybe it would work? 
// q: if using a ring buffer, indices might be freed in between non-freed indices, in which case the pointer to beginning and end would not be able to shift, and therefore would need space for more indices than just the number of threads
// q: if using a ring buffer for frees, could a thread freeing the index then bubble sort backwards and move the begin pointer forwards until the begin and end pointers have only non freed indices between them 
// q: does the main program even need a key value store? can't it just use the block list indices directly?

/*
 SimDB

 What it does:
 |  SimDB is a key value store that uses arbitrary byte data as both the key and the value. 
 |  It additionally uses shared memory, which allows processes to communicate with each other quickly.  
 |  It is lock free and scales well with multiple threads writing, reading, and removing concurrently.  

 How it works:<commit_msg>questions about using a ring buffer to store frees<commit_after>
// plan: 
// - ConcurrentHash is a lava_vec and is at the start of the memory
// - ConcurrentStore takes up the rest of the memory
// | - ConcurrentStore is made up of ConcurrentList at the start of its memory
// | - block memory is everything after ConcurrentList
// - The order ends up being ConcurentHash, ConcurrentList, then block storage

// -todo: hash key data instead of the block index of the key
//       --create function to hash arbitrary bytes 
//       --create function to put into a hashmap with a pre-hashed value
// -todo: make bitwise compare function between blocks
// -todo: make a function to compare a block to an arbitrary byte buffer
// -todo: change store_kv to use compare exchange and return previous kv ?
// -todo: make remove function for ConcurrentStore? - just use free
// -todo: remove overwritten indices from the ConcurrentStore
// -todo: figure out why "wat" and "wut" match - 3 bugs: unsigned size_t in the blockcompare function, not flipping the signs of the next index when it is negative (for length), default value of true when while loop ends from the blocks comparing as false
// -todo: figure out why second insert is putting EMPTY_KEY for key and value in the hash map - comp returns true even though strings are different?
// -todo: use match function instead of block comparison for everything? better for continguous memory anyway?
// -todo: fix not finding a key too long to fit in block - wasn't updating the current block index in the loop
// -todo: return an error on running out of blocks - done with a negative blockcount if not enough blocks are available
// -todo: free blocks if not enough block are allocated
// -todo: fix infinite loop on free - last block wasn't getting next block index set when reaching LIST_END 
// -todo: deal with memory / allocate from  shared memory
// -todo: make a membuf class that encapsulates a shared memory buffer / memory mapped file on windows or linux
// -todo: make remove function
// -todo: add const to thread safe functions
// -todo: figure out why readers is so high - uninitialized KV struct in a put function
// -todo: do KV structs need versions? can an identical KV struct ever be inserted? only if the List somehow gave up identical indices, which shouldn't happen?
// -todo: test deletion from db
// -todo: check when reading if something is marked for deletion and return 0 / EMPTY_KEY if it is
// -todo: make remove function concurrent and account for the number of readers
// -todo: make remove decremented the readers but don't actually delete, so that the last reader out would delete, maybe just make a flag as mark for deletion?
// -todo: make addReaders not add any readers below zero
// -todo: figure out how to deal with deletion when there is a concurrent write - reset the readers and hash?
// -todo: make -1 an error instead of returning a length of 0? - distinguising a key with length 0 and no key could be useful 
// -todo: is only the key being deleted? - no, but vals should be removed before keys to keep the order more consistent, all other things being equal
// -todo: need to fix ConcurrentList free? it writes to the list before the compare_swap has gone through? - no, because writing to taken indices in the list doesn't matter + only one thread should be freeing a specific index at a time - if two threads were freeing the same index on top of each other, a problem bigger than atomics would be that even if both operations went through, there would be a double free
// -todo: change public get methods to use read - took out one get and changed the other to being private getFromBlkIdx
// -todo: fix shared memory aligned allocation
// -todo: make SharedMem check if the mem file already exists
// -todo: test opening the db from multiple processes - didn't work at first, likely because the copy constructor was not deleted and the destructor was run early
// -todo: test lava_vec with external memory
// -todo: convert ConcurrenList to use lava_vec
// -todo: fix hash function hashing string() different from const char* - off by one error was hashing an extra 32 bits
// -todo: fix block memory being written but get() not working (ConcurrentList not correct yet?) - hash problem, not ConcurrentList problem
// -todo: need to make ConcurrentList a flat data structure so it can be store at the start of the memory mapped file
// -todo: make ConcurrentHash flat using lava_vec
// -todo: make Store and Hash both take bool for ownership to decide whether or not to init
// -todo: test using the db from multiple processes
// -todo: make simdb read the sizes from the the database - if the Store uses the size as the head and the hashmap is sized larger than the number of blocks, how to get the number of elements? - made 12 bytes at the start of the shared memory
// -todo: store blockSize and blockCount and flags in the starting three ui64 slots
// -todo: make flag to see if the db has been initialized yet to mitigate race conditions on creating and opening the memory mapping
// -todo: make post build run a copy command for an extra .exe that can be run while the primary exe is overwritten by the compiler
// -todo: figure out why memory is different on second run - why does "wat" get inserted again? - working as intended?
// -todo: try zeroing memory of each block on free - works, just needs two memset() calls just as there are two free() calls to the list
// -todo: move block lists to a lava_vec
// -todo: figure out why memory seem correct but get is not working - just the check of readers being below or equal to zero
// -todo: make decReaders run doFree ? 
// -todo: add readers inc and dec to matching - made memcmpBlk function
// -todo: test db.rm 
// -todo: make readers on a per block level
// -todo: make free decrement block readers
// -todo: move readers to the ConcurrentStore
// -todo: make comparison function in ConcurrentHash that increments and decrements reader
// -todo: should rm on the last put erase their memory? - yes, wasn't resetting readers
// -todo: figure out why get returns -1  -  no return statement, just empty probedKv.key; 
// -todo: figure out why get after put isn't working - was switching the order of readers and index in BlkLst struct
// -todo: figure out why put after rm doesn't show up with get - readers not being reset on allocation? - forgot to take out the free-ing in put() 
// -todo: make both free and read give back a block with last one out strategy
// -todo: test again with multiple processes after redoing rm() technique - without put deleting old elements, how to get rid of overwritten elements? - needed to put back deleting in put(), but make sure rm() swaps in EMPTY_KEY
// -todo: make rmHashed return EMPTY_KEY on MATCH_REMOVED
// -todo: take readers out of hash struct 
// -todo: move hash functions to be static instead of member functions
// -todo: look up better hash function - fnv
// -todo: clean up fnv
// -todo: try making macro with ALLOCA to create a stack based lava_vec
// -todo: load blockSize and blockLength from existing shared memory
// -todo: make function to query size - simb.len(key)
// -todo: make setting the key flag be the last thing when allocating 
// -todo: have last one out remove hash index
// -todo: add removal of blocks to CH doFree ? - no, simdb does that
// -todo: make incReaders for ConcurrentHash
// -todo: have to make hash the authority, give KV struct a reader count
// -todo: put incReaders and decReaders around match function call in ConcurrentHash functions
// -todo: make setting the key flag be the first thing when freeing - actually done in decReaders
// todo: make indexed list of keys
//       -create a bitset in the ConcurrentHash? - can't use ConcurrentHash because blocks could change after query
//       -bitset has to be atomic? - can't create bitset because the key flag, reader count, and index all have to be together?
// done  -use key flag in Block Index struct, treat the entire thing as a 64 bit atomic
// done  -iterate through BlkLst vector to find the next key - done in ConcurrenHash
// done  -after a key is found, get the length of that block index
// done    -when getting the length, check if the block is a key, if not, return an error
// done    -check if the key is not empty
// done    -check if the readers is not less than 0
//       -after getting the length, read from the block index, again checking if the block index is a key and if not, returning an error 
// -todo: can cleanup be done by checking the CH entry after read and setting a flag to delete the old version? - no, because this would only shield one overlap, if more threads were swapping CH entries, they would have to wait/spinlock

// todo: make readers for blocks only exist on the head of the list?
// todo: make sure that a block isn't read from if readers<0
// todo: do a write up on overall structure
// todo: need more data with BlkIdx so that blocks read are known to be from the correct key value pair
// todo: need to have a version with each block and store it with each non head BlkIdx as well as the key value pair of ConcurrentHash - how many bits for the version? 32 bits to start? - just needs to be enough so that a so many blocks can't be gotten while a thread is stalled that the version wraps back around
// todo: have to put version in concurrent hash so that an overwrite from a new write won't cause an ABA problem with another thread reading from it, then decrementing readers?
// todo: make ConcurrentStore.get take a length that it won't exceed
// todo: do a write up on if linear search is neccesary because a hash could land on a KV that has readers as -1 ?  - no different than any other hash map? - search stops on an empty key, but it shouldn't stop on readers<0 ? what happens if a key is inserted a few slots from where the hash lands, then the original landing place is removed? does the empty key stop the search?
// todo: work out how doFree from ConcurrentHash connects to removing blocks 
// todo: redo simdb functions to use runRead
// todo: test looking up values from the iterated keys
// todo: give put() return type a BLKIDX type
// todo: take out size_t from ConcurrentStore
// todo: organize all C++ functions separate from C functions so that they can be #ifdef out if used as a C library
// todo: implement get that takes an index into ConcurrentHash - 0 length does nothing, length must be inout, if key is empty or readers is < 0, make length 0 and do nothing 
// todo: make sure when looping through keys, that readers is not negative? all reads must be atomic? all BlkLst must have their original index embedded? ConcurrentHash does need readers after all?
// todo: make alloc give back blocks if allocation fails
// todo: flip decReaders return value
// todo: can make a bitmap for filled hash indices if the bit is set after the KV is set, and the bit is unset before unsetting the KV
// todo: combine keys and data into one block run
// todo: make len be a direct lookup somehow? - if ConcurrentHash is the authority, len can be done the same way as an  empty/full bitset ? 
// todo: change ConcurrentHash to no longer be only powers of 2

// todo: change string to pass through to c_str() and const char* overload
// todo: take out power of 2 size restriction and use modulo
// todo: use blockSize and blockCount from the already created shared mem if not the owner
// todo: store size in the ConcurrentList? list isn't atomic so it should work well? should block lists, key sizes, and val sizes all be in their own lava_vecs ? 
// todo: redo concurrent store get to store length so that buffer can be returned
// todo: test with multiple threads in a loop
// todo: store lengths and check key lengths before trying bitwise comparison as an optimization? - would only make a difference for long keys that are larger than one block? no it would make a difference on every get?
// todo: prefetch memory for next block when looping through blocks
// todo: move to using packed key value in one block list
// todo: can block sync be done with a removed flag instead of just using readers?
// todo: change lava_vec name to flat_vec?

// todo: combine key and value storage so they are packed together in the same block list?
// todo: mark free cells as negative numbers so double free is caught? - do it only in debug mode?
// todo: make erase function that 0s out bytes? - only in debug mode?
// todo: Make block size for keys different than data?
// todo: lock init with mutex?
// todo: implement locking resize?
// todo: should the readers be integrated with the list also? 
// todo: make SharedMemory take an address and destructor, or make simdb take an address and destructor to use arbitrary memory?

//Block based allocation
//-Checking if the head has been touched means either incrementing a counter every time it is written, or putting in a thread id every time it is read or written
//-Each ui32 in a vector holds the position of the next free block 
//-Alloc checks the head to read the next free position and puts it in head if head hasn't been touched. 
//-Free checks the head to read the next free position, stores the head value in the free position, then moves head to the just written new free position if head hasn't been touched

//
// Make frees happen from the last block to the first - don't remember what this means

// idea: use max_waste as a recipricol power of two giving the percentage of waste allowed for an allocation
// - 2 would be 25%, 3 would be 12.5% 
// - not allowed to be below 2
// idea: put atomic reader counter into each ConcurrentStore entry as a signed integer
// idea: figure out how to make ConcurrentHash a flat data structure so it can sit in shared memory

// q: can cleanup be done by a ring buffer of block lists? would the ring buffer only need to be as long as the number of threads if each thread helps clear out the ring buffer after every free()? Probably not, because delayed deallocation would be useful only when there is a reader/ref count, which would mean many more reads than writes could stall the ability to free? But each thread can really only hold one reference at a time so maybe it would work? 
// q: if using a ring buffer, indices might be freed in between non-freed indices, in which case the pointer to beginning and end would not be able to shift, and therefore would need space for more indices than just the number of threads
// q: if using a ring buffer for frees, could a thread freeing the index then bubble sort backwards and move the begin pointer forwards until the begin and end pointers have only non freed indices between them 
// q: what is the benefit of a ring buffer? does it prevent the need for a spinlock anywhere?
// q: does the main program even need a key value store? can't it just use the block list indices directly?

/*
 SimDB

 What it does:
 |  SimDB is a key value store that uses arbitrary byte data as both the key and the value. 
 |  It additionally uses shared memory, which allows processes to communicate with each other quickly.  
 |  It is lock free and scales well with multiple threads writing, reading, and removing concurrently.  

 How it works:
{'fraction_non_alphanumeric': 0.05341197403538832, 'fraction_numerical': 0.0023724010675804804, 'mean_word_length': 3.554321728691477, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '399656', 'n_tokens_mistral': 7715, 'n_tokens_neox': 7513, 'n_words': 5083}