## Algorithms » History » Version 33

Greg Burri, 03/04/2011 02:52 PM

1 2 3 1 Greg Burri `h1. Algorithms` 20 Greg Burri `h2. Word indexing` 1 Greg Burri 33 Greg Burri `Each shared file and directory is indexed by its name which are splitting in words. A search will be based on this index.` 24 Greg Burri `See the associated prototype here for some performance measures : [[Word index prototype]].` `h3. Word splitting` 20 Greg Burri `Theses steps are valid independently of the language.` 1 Greg Burri `# Some character are replaced by a another, for example : ['é', 'ë',..] => 'e'. The goal is to remove all accent.` `# All characters are converted to lower case.` 29 Greg Burri `# Each file is split in word, there is a set of characters which will use as delimiter between the word like [' ', '#', '.', '?',..].` 1 Greg Burri 26 Greg Burri `This process is also valid for the user input when searching.` 20 Greg Burri 24 Greg Burri `h3. Structure ` 1 Greg Burri 24 Greg Burri `A simple tree structure is used like this :` `
`
`struct Node {`
`   QChar letter;`
`   QList children;`
`   QList itemList;`
`};`
`
` 25 Greg Burri `h3. Searching into the tree` 1 Greg Burri 25 Greg Burri `The match of a word can be partial from the beginning, for example _train_ will match _training_.` 1 Greg Burri 25 Greg Burri `# Match each character of the searched word against the letter of the children of the root node recursively` `## If the match failed the result is empty` 27 Greg Burri `## Else, the result contains all items from the sub tree` 1 Greg Burri 25 Greg Burri `In the worst case the number of iteration is _N*36_ for a latin alphabet (a-z, 0-9). Where _N_ is the number of character of the searched word.` `h3. Searching among other peers` `For a functional description see here : [[Functional definition#The-search-window]]` 1 Greg Burri 24 Greg Burri `# The words are sent to each peers (see the message _Find_ here : [[Protocol core-core]])` `# Each peer will do a search for each word into its index` `# The results for each search will be merged according the schema below` 1 Greg Burri `!aybabtu_search.png!` `_This schema depicts how the results are sorted from one peer. Each peer result are then merged._` 24 Greg Burri 5 Greg Burri `h2. Peer ID` 7 Greg Burri `Each peer owns a peer id which is unique and generated during the first start. This ID is used to identify a peer, it's better than the previous usage of peer IP, considering this situation :` 5 Greg Burri `* _A_ put in queue a file entry _f_ from _B_, _B_ doesn't know the hashes of this file entry.` 1 Greg Burri `* _B_ change his IP address.` `* _A_ want to download _f_, it can ask _B_ for the hashes even _B_'s IP changed.` 24 Greg Burri 5 Greg Burri 8 Greg Burri `h2. Core threads` 9 Greg Burri `There are three kind of threads in the core in addition to the main thread :` `* [[Protocol_core-core#Downloading-thread|Downloading thread]] : @DownloadManager::ChunkDownloader@` 8 Greg Burri `* Uploading thread : @UploadManager::Uploader@` 11 Greg Burri `* [[Algorithms#Updating-the-file-cache|Updating file cache thread]] : @FileManager::FileUpdater@` 5 Greg Burri 32 Greg Burri `These threads exist only for treating IO in a parallel manner. The goal is not the computation nor robustness.` 30 Greg Burri 22 Greg Burri `h2. Updating the file cache` 10 Greg Burri `Here is the algorithm for the thread (@FileManager::FileUpdater@) which will periodically update the file cache and persist it.` 28 Greg Burri `There is a prototype for the watcher here : [[Watcher prototype]]` 23 Greg Burri 10 Greg Burri `
`
1    Greg Burri  `D : The set of shared directories`
22   Greg Burri  `T : Time during which the hashes are computed (for example 30s)`
`F : A set containing file with unknown hashes, initially empty`
`W : the directory watcher`
13   Greg Burri
`// First synchronize (at start)`
`For each d in D (recursively) :`
22   Greg Burri  `   - Add d to W`
14   Greg Burri  `   - Synchronize physical folders and files with d content`
22   Greg Burri  `   - Add in F the files which don't have hashes`
13   Greg Burri
10   Greg Burri  `Loop :   `
1    Greg Burri  `   t : Time.now`
13   Greg Burri  `   For each f in F :`
1    Greg Burri  `      - Compute the unknown hash of files f`
10   Greg Burri  `      - Remove f from F`
`      If (Time.now - t) > T : break`
22   Greg Burri  `   - Wait for changes for a period of (if F is empty then INFINITE else 0)`
`      - When a modification occurs synchronize the file/folder`
13   Greg Burri  `      - Add each new file in F`
12   Greg Burri  `   - Persist the entire cache in a file (only every ~30min)`
10   Greg Burri  `
` 5 Greg Burri 4 Greg Burri `h2. Downloading` `See here : [[Protocol_core-core#Downloading-threads]]`