The History Module currently consists of the History Model and the Direct History. The History Model (formerly known as Global History) represents the browsing history and not the session history. It is used (on desktop) for the history panel/page, auto completion in the URL field, Top Ten and more. Direct History is typed history, and is displayed on desktop when pressing the down arrow on the URL field without having typed anything.
The policies of these histories differ in that Direct History stores what was user typed, with no regard to whether the typed string resolved to a URL and the History Model should only store valid URLs, that is a string should only be inserted after it is known to resolve.
These policies are only partially enforced by the histories themselves. Mostly a string is supplied and will be inserted, no check is made that it actually does resolve (though this required by the History Model policy). However, the History Model does enforce one policy that will be discussed below.
The History Model will be referred to as the Core History Model and History Model interchangeably, though it should not be confused with the History Model that resides in adjunct (a model built on top of the Core History Model).
The Core History Models main purpose is to store URLs and the last time they were accessed. This is stored in items called Core History Model Pages. Note that it only stores one copy of each URL and the last time it was accessed. To maintain a popularity needed for something like Top Ten an additional field is also maintained - average interval. This field is calculated based on its former value and the time passed since last access. For more information on the Core History Model Items see their section below.
There is also a set of folders to support different views of history. Currently there are four kinds of folders - Prefix Folder, Site Folder, Sub Site Folder and Time Folder. These are described further below.
The Core History Model Items are referenced from two different structures to maintain the two supported views of history - time and site.
The time view is supported by a vector where the items are maintained in chronological order based on the last time they were accessed. This is also the order maintained in the global.dat file (although there the order is reversed for legacy reasons).
The second structure is a Lexiographic Splay Tree. This tree was designed to store URLS and to provide a convenient structure for auto completion. The Lex Splay Tree will be further described below. What is important to note is that this structure was chosen to provide searches in time proportional to the length of the URL and not the number of items in history, and secondly that the URLs are stored in alphabetical order.
| Define | Prefix | Suffix | Prefix length | Suffix length | Protocol | Show_all |
| "" | "" | 0 | 0 | NONE | FALSE | |
| "opera:" | "" | 6 | 0 | OPERA | TRUE | |
| _LOCALHOST_SUPPORT_ | "file:/" | "" | 6 | 0 | FILE | FALSE |
| _LOCALHOST_SUPPORT_ | "file://" | "" | 7 | 0 | FILE | FALSE |
| _LOCALHOST_SUPPORT_ | "file://localhost" | "localhost" | 16 | 9 | FILE | FALSE |
| !NO_FTP_SUPPORT | "ftp://" | "" | 6 | 0 | FTP | FALSE |
| !NO_FTP_SUPPORT | "ftp://ftp." | "ftp." | 10 | 4 | FTP | FALSE |
| !NO_FTP_SUPPORT | "ftp://www." | "www." | 10 | 4 | FTP | FALSE |
| "http://" | "" | 7 | 0 | HTTP | FALSE | |
| "http://home." | "home." | 12 | 5 | HTTP | FALSE | |
| "http://wap." | "wap." | 11 | 4 | HTTP | FALSE | |
| "http://web." | "web." | 11 | 4 | HTTP | FALSE | |
| "http://www." | "www." | 11 | 4 | HTTP | FALSE | |
| "http://www2." | "www2." | 12 | 5 | HTTP | FALSE | |
| "https://" | "" | 8 | 0 | HTTPS | FALSE | |
| "https://home." | "home." | 13 | 5 | HTTPS | FALSE | |
| "https://wap." | "wap." | 12 | 4 | HTTPS | FALSE | |
| "https://web." | "web." | 12 | 4 | HTTPS | FALSE | |
| "https://www." | "www." | 12 | 4 | HTTPS | FALSE | |
| "https://www2." | "www2." | 13 | 5 | HTTPS | FALSE |
Below is the current set of selftests in the module. In edda_2_alpha_2 the result
is currently:
Coverage 75.31 %.
122 of 162 functions called.
The diagram bellow shows the general structure of this module. See doxygen generated documentation.
The Core History Model supports a listener mechanism that currently only supports one listener, though should in the future support more. This mechanism is the recommended interface to any external client code that intends to display a view of the Core History Model. This listener layer provides the upcalls necessary to broadcast changes in the model.
"opera:history", however, uses a different (not recommended) mechanism. This mechanism is supported but will hopefully disappear in the future, and should be considered depricated.
Core History Model Item is the base class for all pages and folders in the model.
Objects of this class represent the basic element in the Core History Model. They store the URL, title, last access and average interval of a specific URL. These items are the only items present in the time sorted vector.
Core History Model Folder is the base class for all folders in the model.
Folder representing a Site. Stored in the "stripped tree".
Folder representing a Site in a specific time period. There are five such folders contained in each site folder (actually the number of folders is NUM_TIME_PERIODS which currently is five - see history_enums.h).
Folder representing a specific time period. There are NUM_TIME_PERIODS number of time folders.
Folder representing a specific prefix. There are as many such folders as there are supported prefixes - see history_prefixes.cpp.
See "Self-adjusting binary search trees" for more information about Lexiographic Splay trees.
The History Model currently uses the templated version of the LexSplayTree called OpSplayTree. The tree is tail compressed and use keys that are assumed to be memoryvise managed outside of the tree and they are also assumed to be shared. Meaning the tree will assume that two items inserted with identical keys are actually inserted with the _same_ key.
See description of the file formats used by Core History Model.
All methods in the external API which can cause an error will return an OP_STATUS which should be checked for ERR_NO_MEMORY and ERR. A few internal methods use TRAP/LEAVE, but this should be invisible to the external API.
The History Model passes the OOM error to the caller.
The general flow in the module is simple: An item is inserted and can can be retrieved individually or in an autocompletion call.
All History Model Items are allocated in heap memory. The number of such items is limited by the product pref PrefsCollectionCore::MaxGlobalHistory which indicates the maximum number of elements. The urls of the items are indexed in the Lexiographic Splay Tree called stripped. This tree is also heap allocated. The tree is tail compressed and and all common prefixes are shared so the overhead is limited.
The url strings themselves are shared since they are Core History Model Keys combined with Prefixes. Meaning that http://www.opera.com and ftp://ftp.opera.com share the key "opera.com" and have two different prefixes. These keys are also used in the tail compressed tree - so the overhead of the tree is limited to the unique prefixes.
The total approximate size of a HistoryPage item on a 32-bit unix is 44 bytes. It has pointers to a HistorySiteFolder, a HistoryPrefixFolder and a HistoryKey which are also allocated by the module but are shared across items. The titles are item specific and can be up to MAX_URL_LEN (4096 bytes). The same length restraint applies to the url though here the prefix of the url is indicated by the prefix folder and the rest of the url is given by the key which is shared among items with the same "stripped" url. "http://www.opera.com" has "http://www." as it's prefix and "opera.com" as its "stripped" url.
There is very limited stack use except for some recursive traversing of the Lexiographic Splay Tree, since the tree is tail compressed the depth is typically not that high (between 8 and 30) but worst case it can be 4096.
There is only one global variable for the HistoryModel : g_globalHistory
There are no caches. Most of the memory used will be freed if DeleteAllItems() is called - this will however also empty the global.dat file.
All the memory is freed when the History Model is deleted.
The module does not use the tempbuffers from the memory manager.
Currently there is no way to tune the memory usage other than to reduce the number of items allowed in history - this can be done runtime by calling the Size function with the new maximum number of items.
There are no specific memory tests for this module.
Creating the History Model and reading in a global.dat file will test most memory allocations.
In the current design the items are referred to by either/both a vector (which may have a sorting) and the lexiogaphic splay tree. The tree facilitates fast searching, alphabetical sorting and gouping of pages on a site.
Currently the pages are reffered to in accessed time order in the vector. This means that when an items is accessed it is reinserted at the top. This is very wasteful, and it would be better if this was implemented differently.
Currently the tree is tail compressed, but it would be good to look into whether internal nodes could also be compressed.
It would be interesting to look into whether titles could also be shared strings in a similar manner to the urls.
See description of the file formats used by Direct History.
Direct History has no real OOM Policy. It allocates the array at startup and will leave if this fails. Otherwise it copies the strings it inserts but no test is done to check that the copy succeeded.
There are hardly any tests to check for OOM and noone is notified if they are encountered outside of the allocation of the array.
There is no real flow to speak of, an item is inserted and the list of items can be retrieved.
Direct history allocates an array with length equal to PrefsCollectionCore::MaxDirectHistory which indicates the maximum number of elements and will copy all strings added to it.
There is no stack memory usage in Direct History.
There is only one global variable for the Direct History : g_directHistory
There are no caches. All the strings stored will be deleted if DeleteAllItems() is called - this will however also empty the opera.dir file.
All the memory is freed when the Direct History is deleted.
The module does not use the tempbuffers from the memory manager.
Currently there is no way to tune the memory usage other than to reduce the number of items allowed in direct history - this can be done runtime by calling the Size function with the new maximum number of items.
There are no specific memory tests for this module.
There are no selftests for direct history yet.
The design is simple : it is a list of strings.
There are currently no real plans of improvements other than to move over to using an OpVector rather than the array.