The database sort module has the file name dbengsrt.c. This low level module provides database sort facilities for the Bbuuzzb database engine. Any mention of QNX in this document refers to the QNX 4.x OS. This API can be compiled for all stated platforms. This database sort API is part of single user database access as well as the database server.
This sort module has the ability to sort a table of any size. The sort order is given as a series of sort specifications. There may be any number of sort specifications given with each specification being in either ascending or descending order.
The list of sort specifications must contain a list (with each single sort specification being delimited by DBENG_LIST_DELIM) of sort specifications. A single sort specification is in the form:
field_num[,A|D]
The sort specification starts with the field number followed by an optional order (A for ascending, D for descending, not case sensitive). A comma must separate the field number from the sort order. If no order is given, an ascending sort is assumed for that field and the comma is not specified.
Database sorting works by loading each input table record into memory until a memory threshold is reached. The record contents in memory are then sorted and written to an intermediate (temporary) table called a bin table. When all input records have been read and sorted all the bin tables are then merged.
The record contents in memory, the sort specifications and all the bin tables are managed by three dynamically allocated link lists. The record contents link list structure is called dbeng_sort_node. The sort specification link list structure is called dbeng_sort_spec and the bin table link list structure is called dbeng_sort_bin. This module uses the following function prefixes to denote functions which manipulate one of the three link lists:
Each database table has two dbeng_table members that are exclusively used for sorting. The member sort_max_mem controls how much memory should be allocated for input records before sorting and flushing the contents. The member sort_max_open_bin specifies how many bin tables may be open at any one time. These dbeng_table members are set to default values (supplied in dbengsrt.h) when the table is opened. These thresholds can easily be changed prior to the actual sort (see below).
The sorted table contents always replace the unsorted contents.
The actual sort is accomplished by a link list insertion sort. It is quite slow. The sort speed could be increased by re-coding the sort using a different method.
Here is a list of functions in this module:
This module is part of single user database access and needs to be linked with the following modules:
In the Linux/Unix/QNX platforms, this module is compiled along with the other database modules as part of the script cdbeng.
This module depends on the following header files:
Prototype : int dbeng_sort(struct dbeng_table *ot, char *specs)
Parameters :
Name : ot
Description : pointer to dbeng_table structure
Name : specs
Description : list of sort specifications
Returns : dbeng code
High Level : db_sort
This function will sort a table. The list of sort specifications must contain a list (delimited by DBENG_LIST_DELIM) of sort specifications.
The sorted table contents will always replace the unsorted contents.
Prototype : int dbeng_sort_get_max_mem(struct dbeng_table *ot,
long *mem)
Parameters :
Name : ot
Description : pointer to dbeng_table structure
Name : mem
Description : returned max memory
Returns : dbeng code
High Level : db_get_sort_max_mem
This function will obtain the current value of the dbeng_table member sort_max_mem. Function returns the current allowable maximum allocated sort memory in the returned max memory upon success.
Prototype : int dbeng_sort_set_max_mem(struct dbeng_table *ot,
long mem)
Parameters :
Name : ot
Description : pointer to dbeng_table structure
Name : mem
Description : max memory
Returns : dbeng code
High Level : db_set_sort_max_mem
This function will set the current value of the dbeng_table member sort_max_mem.
Prototype : int dbeng_sort_get_max_open_bin(struct dbeng_table *ot,
int *open_bin)
Parameters :
Name : ot
Description : pointer to dbeng_table structure
Name : open_bin
Description : returned max open bin tables
Returns : dbeng code
High Level : db_get_sort_max_open_bin
This function will obtain the current value of the dbeng_table member sort_max_open_bin. Function returns the current allowable maximum number of open bin tables in returned max open bin tables upon success.
Prototype : int dbeng_sort_set_max_open_bin(struct dbeng_table *ot,
int open_bin)
Parameters :
Name : ot
Description : pointer to dbeng_table structure
Name : open_bin
Description : max open bin tables
Returns : dbeng code
High Level : db_set_sort_max_open_bin
This function will set the current value of the dbeng_table member sort_max_open_bin.
Prototype : static int dbeng_sort_flush_rec(void) Returns : dbeng code
This private function will sort and write out the record contents in memory to a bin table.
Prototype : static int dbeng_sort_ll(void) Returns : dbeng code
This private function will sort the record contents. The record contents link list (dbeng_sort_node) must have already been loaded.
Prototype : static int dbeng_sort_compare(char *l, char *r, int *cval)
Parameters :
Name : l
Description : first record
Name : r
Description : second record
Name : cval
Description : returned comparison value
Returns : dbeng code
This private function will compare two strings according to the sort specifications.
Prototype : static int dbeng_sort_set_cval(struct dbeng_sort_spec *rov,
int *cval)
Parameters :
Name : rov
Description : pointer to sort specification
Name : cval
Description : input/output comparison value
Returns : dbeng code
This private function will set the comparison result based on the sort spec order and the initial value of the input/output comparison value. Function returns the comparison result in the input/output comparison value.
Prototype : static int dbeng_sort_write_sort_data(int tid)
Parameters :
Name : tid
Description : bin table tid
Returns : dbeng code
This private function will write the contents of the sorted record link list (dbeng_sort_node) to a temporary system table(bin table). The table is assumed to be open. The output table will be closed (with the dbeng_table structure retained) once all records have been written.
Prototype : static int dbeng_sort_set_final(struct dbeng_table *source)
Parameters :
Name : source
Description : pointer to original input table
Returns : dbeng code
This private function will take a single bin table and make it the source table.
Prototype : static int dbeng_sort_match_bin(void) Returns : dbeng code
This private function will perform a merge (according to the current sort specifications) of all the bin tables in use (whether they are open or not) and create a single table from all the bin tables.
Prototype : static int dbeng_sort_match_tables(int out_tid)
Parameters :
Name : out_tid
Description : output table tid
Returns : dbeng code
This private function will consolidate all open bin tables (according to the current sort specifications) into a single table (the output table tid).
Prototype : static int dbeng_sort_read_bin(struct dbeng_sort_bin *rov,
int out_tid)
Parameters :
Name : rov
Description : bin table to read
Name : out_tid
Description : output table tid
Returns : dbeng code
This private function will read the next record from the bin table to read. If EOF is encountered, the table will be closed and deleted.
Prototype : static int dbeng_sort_is_active_input_bin(struct dbeng_sort_bin *rov,
int tid)
Parameters :
Name : rov
Description : bin table to test
Name : tid
Description : output table tid
Returns : dbeng code
This private function will determine whether the bin table to test is open and is not an output bin table.
Prototype : static int dbeng_sort_alloc_bin(int *bintid)
Parameters :
Name : bintid
Description : returned tid
Returns : dbeng code
This private function will allocate a bin member and open a temporary system table for it. A new structure member will be added to the end of the bin list. Upon success, the tid of the temp sys table will be returned in the returned tid.
Prototype : static int dbeng_sort_sll_load(char *specs)
Parameters :
Name : specs
Description : list of sort specifications
Returns : dbeng code
This private function will load the list of sort specifications into the link list. Each sort specification in the list of sort specifications is expected to be delimited by DBENG_LIST_DELIM.
Prototype : static int dbeng_sort_rll_add(struct dbeng_table *ot)
Parameters :
Name : ot
Description : input table
Returns : dbeng code
This private function will add the contents of the current record in the input table to the link list.
Prototype : static void dbeng_sort_rll_delete(void)
This private function will delete the entire dbeng_sort_node link list and all of it's current nodes.
Prototype : static int dbeng_sort_sll_add(char *spec)
Parameters :
Name : spec
Description : a single sort specification
Returns : dbeng code
This private function will add a sort specification node to the link list.
Prototype : static void dbeng_sort_sll_delete(void)
This private function will delete the entire dbeng_sort_spec link list and all of it's current nodes.
Prototype : static int dbeng_sort_bll_delete_all(void) Returns : dbeng code
This private function will delete all members of the bin table link list and also delete all physical bin files.
Prototype : static int dbeng_sort_bll_delete(struct dbeng_sort_bin *lbin,
int delete_flag)
Parameters :
Name : lbin
Description : bin table
Name : delete_flag
Description : delete physical table flag
Returns : dbeng code
This private function will delete the bin table link list entry with or without deleting the physical bin file.
Prototype : static void dbeng_sort_sll_dump(void)
This private function will output the contents of the sort specification link list to the current log destination using the logging manager.
Prototype : static void dbeng_sort_rll_dump(void)
This private function will output the contents of the sort node link list to the current log destination using the logging manager.
Prototype : static void dbeng_sort_term(void)
This private function will deallocate all memory used by the sort module.