# History Module

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.

# History Model

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.

## Supported Prefixes

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

## Selftests

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.

#### addtest.ot

Tests the adding of items.

#### autocompletiontest.ot

Tests the general autocompletion capability based on alphabetical sorting.

#### filetest.ot

Tests the autocompletion treatment of file urls.

#### ftptest.ot

Tests the autocompletion treatment of ftp urls.

#### hometest.ot

Tests the autocompletion treatment of url with a home subdomain.

#### iterationtest.ot

Tests the iteration options in the module by testing the GetFirst-GetNext option (which is depricated) and the GetItemAtPosition which is the preferred method.

#### popularitytest.ot

Tests the popularity sorted autocompletion.

#### readwritetest.ot

Tests the reading and writing of the global.dat file.

## API

The diagram bellow shows the general structure of this module. See doxygen generated documentation.

### class HistoryModel

The Core History Model is implemented as a singleton. This means that there is only one Core History Model at any given time. This model is pointed to by the global variable g_globalHistory (also called globalHistory).

#### class Listener

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.

### class HistoryItem

Core History Model Item is the base class for all pages and folders in the model.

### class HistoryPage

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.

### class HistoryFolder

Core History Model Folder is the base class for all folders in the model.

#### class HistorySiteFolder

Folder representing a Site. Stored in the "stripped tree".

#### class HistorySiteSubFolder

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).

#### class HistoryTimeFolder

Folder representing a specific time period. There are NUM_TIME_PERIODS number of time folders.

#### HistoryPrefixFolder

Folder representing a specific prefix. There are as many such folders as there are supported prefixes - see history_prefixes.cpp.

### class LexSplayTree

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.

## File formats

See description of the file formats used by Core History Model.

## Memory usage

### Used OOM policies

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.

### Who is handling OOM?

The History Model passes the OOM error to the caller.

### Description of flow

The general flow in the module is simple: An item is inserted and can can be retrieved individually or in an autocompletion call.

### Heap memory usage

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.

### Stack memory usage

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.

### Static memory usage

There is only one global variable for the HistoryModel : g_globalHistory

### Caching and freeing memory

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.

### Freeing memory on exit

All the memory is freed when the History Model is deleted.

### Temp buffers

The module does not use the tempbuffers from the memory manager.

### Memory tuning

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.

### Tests

There are no specific memory tests for this module.

### Coverage

Creating the History Model and reading in a global.dat file will test most memory allocations.

### Design choices

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.

### Suggestions of improvements

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.

# Direct History

## API

### class DirectHistory

Currently DirectHistory is simply an array of uni_char strings.

## File formats

See description of the file formats used by Direct History.

## Memory usage

### Used OOM policies

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.

### Who is handling OOM?

There are hardly any tests to check for OOM and noone is notified if they are encountered outside of the allocation of the array.

### Description of flow

There is no real flow to speak of, an item is inserted and the list of items can be retrieved.

### Heap memory usage

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.

### Stack memory usage

There is no stack memory usage in Direct History.

### Static memory usage

There is only one global variable for the Direct History : g_directHistory

### Caching and freeing memory

There are no caches. All the strings stored will be deleted if DeleteAllItems() is called - this will however also empty the opera.dir file.

### Freeing memory on exit

All the memory is freed when the Direct History is deleted.

### Temp buffers

The module does not use the tempbuffers from the memory manager.

### Memory tuning

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.

### Tests

There are no specific memory tests for this module.

### Coverage

There are no selftests for direct history yet.

### Design choices

The design is simple : it is a list of strings.

### Suggestions of improvements

There are currently no real plans of improvements other than to move over to using an OpVector rather than the array.