Database Sort

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.

# Sort Specifications

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.

# Theory of Operation and Construction Techniques

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:

- dbeng_sort_rll_ - dbeng_sort_node (the r stands for record)
- dbeng_sort_sll_ - dbeng_sort_spec (the s stands for spec)
- dbeng_sort_bll_ - dbeng_sort_bin (the b stands for bin)

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:

# Module Functions

- dbeng_sort
- dbeng_sort_get_max_mem
- dbeng_sort_set_max_mem
- dbeng_sort_get_max_open_bin
- dbeng_sort_set_max_open_bin
- dbeng_sort_flush_rec
- dbeng_sort_ll
- dbeng_sort_compare
- dbeng_sort_set_cval
- dbeng_sort_write_sort_data
- dbeng_sort_set_final
- dbeng_sort_match_bin
- dbeng_sort_match_tables
- dbeng_sort_read_bin
- dbeng_sort_is_active_input_bin
- dbeng_sort_alloc_bin
- dbeng_sort_sll_load
- dbeng_sort_rll_add
- dbeng_sort_rll_delete
- dbeng_sort_sll_add
- dbeng_sort_sll_delete
- dbeng_sort_bll_delete_all
- dbeng_sort_bll_delete
- dbeng_sort_sll_dump
- dbeng_sort_rll_dump
- dbeng_sort_term

# Module Dependencies

This module is part of single user database access and needs to be linked with the following modules:

- fio.c
- parse.c
- logger.c
- ipcomm.c (database server and single user if using system logger, all platforms except QNX and DOS)
- sys_log.c (database server and single user if using system logger, all platforms except DOS)
- slogcode.c (database server and single user if using system logger, all platforms except DOS)
- sloc.c (database server and single user if using system logger, all platforms except QNX and DOS)
- slconfig.c (database server and single user if using system logger, all platforms except QNX and DOS)
- sliocode.c (database server and single user if using system logger, all platforms except QNX and DOS)
- sconnect.c (database server and single user if using system logger, all platforms except QNX and DOS)
- dbengses.c (database server only)
- dbengrep.c (database server only)
- dbiocode.c
- dblocal.c
- dbengcfg.c
- dblocfg.c
- dbeng.c
- dbengcat.c

In the Linux/Unix/QNX platforms, this module is compiled along with the other database modules as part of the script cdbeng.

# Module Header Files

This module depends on the following header files:

- stdhead.h
- dbeng.h
- dbmess.h
- dbengcfg.h
- dbengsrt.h

# Module Functions

## dbeng_sort

    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.

## dbeng_sort_get_max_mem

    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.

## dbeng_sort_set_max_mem

    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.

## dbeng_sort_get_max_open_bin

    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.

## dbeng_sort_set_max_open_bin

    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.

## dbeng_sort_flush_rec

    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.

## dbeng_sort_ll

    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.

## dbeng_sort_compare

    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.

## dbeng_sort_set_cval

    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.

## dbeng_sort_write_sort_data

    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.

## dbeng_sort_set_final

    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.

## dbeng_sort_match_bin

    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.

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

## dbeng_sort_read_bin

    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.

## dbeng_sort_is_active_input_bin

    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.

## dbeng_sort_alloc_bin

    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.

## dbeng_sort_sll_load

    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.

## dbeng_sort_rll_add

    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.

## dbeng_sort_rll_delete

    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.

## dbeng_sort_sll_add

    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.

## dbeng_sort_sll_delete

    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.

## dbeng_sort_bll_delete_all

    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.

## dbeng_sort_bll_delete

    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.

## dbeng_sort_sll_dump

    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.

## dbeng_sort_rll_dump

    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.

## dbeng_sort_term

    Prototype   : static void dbeng_sort_term(void)

This private function will deallocate all memory used by the sort module.

Goto Top | Future Lab Home | Contact Webmaster | Feedback

Copyright © 2003-2006 Future Lab, Last Updated Jun 30, 2006