DEB_DD (1158343), страница 2
Текст из файла (страница 2)
Index –an array that contains indexes of the cut (selected) dimensions. If an element of this array is not equal to –1, the range appropriate to the given array element is used. Otherwise, the whole dimension of the array is used.
The function marks remote access buffer creation for dynamic control system. This call is necessary for correct monitoring of access to the elements of a DVM-array through the remote access buffer. The call should be used after creation of the buffer and initialization of its elements.
long dskpbl_(void)
The function marks the possible skip of statement group in a sequential branch of the program after checking the membership of the array element to the current processor. The function should be called after execution of the statement group and independently of the checking results.
2.Base modules
2.1.Table
The table is intended to keep large volume of data. A peculiarity of the implementation is that the memory is allocated not for each element but by large blocks of fixed size. The size of the allocated block is defined by parameters of table initialization. The table is expanded automatically, when the current allocated memory block is exhausted.
Types: DYNCNTRL.TYP
Prototypes: DYNCNTRL.DEC
Implementation: TABLE.C
Macros definition: DYNCNTRL.MAC
The following structure is defined for the table:
typedef struct tag_TABLE
{
byte IsInit;
s_COLLECTION cTable;
size_t TableSize;
size_t CurSize;
size_t ElemSize;
PFN_TABLE_ELEMDESTRUCTOR Destruct;
}
TABLE;
IsInit – flag of the table initialization. It is used for postponed initialization improve performance.
cTable – a set of pointers to allocated memory blocks.
TableSize – number of elements to allocate when the table is expanded.
CurSize – number of used elements in the current table block.
ElemSize – size in bytes of one element.
Destruct – pointer to the function with prototype void (*PFN_TABLE_ELEMDESTRUCTOR)(void *Elem). This function is called for each table element when it is removed from the table.
The following calls are intended for work with the table:
void table__Init( TABLE *tb, size_t TableSize, size_t ElemSize, PFN_TABLE_ELEMDESTRUCTOR Destruct );
tb – pointer to the initialized TABLE structure.
TableSize – number of the elements to allocate when expanding the table.
ElemSize – size in bytes of one table element.
Destuct – pointer to table element destructor function. It can be NULL.
Table initialization. This function should be called before using the table.
void table_Done( TABLE *tb );
tb – pointer to the TABLE structure.
Table destructor. This function should be called upon usage of the table to free allocated memory. It calls element destructor for each element of the table.
long table_Count( TABLE *tb );
tb – pointer to the TABLE structure.
The number of used table elements is returned.
void *table__At( TABLE *tb, long No );
tb – pointer to the TABLE structure.
No – zero based element number. The program will aborted if the No does not fall to number of elements range.
The pointer to the specified table element is returned.
long table__Put( TABLE *tb, void *Struct );
tb – pointer to the TABLE structure.
Struct – pointer to the inserted element. Only ElemSize bytes will be copied into the table.
The function inserts a new element into the table.
void *table__GetNew( TABLE *tb );
tb – pointer to the TABLE structure.
The function inserts a new element into the table and returns a pointer to this element. The function is more effective then table_Put() as it saves coping of memory block.
void table_RemoveFrom( TABLE *tb, long Index );
tb – pointer to the TABLE structure.
Index – element number from which elements will be removed.
The function removes elements of the table starting from number Index. The element with the number Index itself remains in the table.
void table_RemoveAll( TABLE *tb );
tb – pointer to the TABLE structure.
All the elements of the table are removed, and the allocated memory is freed.
void table__Iterator( TABLE *tb, PFN_TABLEITERATION Proc, void *Param1, void *Param2 );
tb – pointer to the TABLE structure.
Proc – iteration function with the following prototype: void (*PFN_TABLEITERATION)( void *Elem, void *Param1, void *Param2 ). This function will be called for each element of the table.
Param1 – the parameter passed as Param1 into the Proc function.
Param2 – the parameter passed as Param2 into the Proc function.
The function applies the same operation to each element of the table.
The following macros are defined for the table:
table_Init(tb,TableSize,ElemSize,Destruct)
It calls table__Init() with the Destruct parameter cast to type PFN_TABLE_ELEMDESTRUCTOR.
table_At( type, table, no )
It returns the pointer to the table element with type cast to (type *).
table_Put( tb, str )
It calls table__Put() with the str argument cast to type (void *).
table_Iterator(tb,Proc,Param1,Param2)
It calls table__Iterator() with Proc argument cast to type PFN_TABLEITERATION and Param1 and Param2 arguments cast to (void *).
table_GetNew(type,tb)
It returns pointer to new table element with type cast to (type *).
2.2.Hash-table
The hash-table is intended to store elements of long type accessed by a key. The hash-table is organized as a table of fixed size. All elements with the same hash-value are put to a chain that is associated with the hash-value. When an element is searched, the hash-value is calculated using the key, and then each element of the corresponding chain is examined.
The hash-table consists of two parts: a hash-index and a hash-array keeping keys and associated values. The following steps are performed to find the specified value using a key. The hash-value is calculated using the key. The element of the hash-index determined by the hash-value is extracted. The element contains an element number in the hash-array. This hash-array element starts the chain of elements with the same hash-value. Each element of the hash-array has NextElem field that refers to the next chain element. The zero value of this field means the end of the chain. While elements are searched, the key field of the elements is compared with the specified key. If the keys are matched, the value of the Assign field is returned as result of the search.
The following algorithms can be used to calculate hash-values:
-
StandartHashCalc. The following function is used: HASH-VALUE = (long)Key % HashIndexSize, where Key is the element's key, HashIndexSize is the size of the hash-index, % is operator to take the reminder of integral division.
-
OffsetHashCalc. The following function is used: HASH-VALUE = ((long)Key >> Offset)% HashIndexSize, where Key is the element's key, HashIndexSize is the size of the hash-index, Offset is an offset specified as parameter, % is operator to take the reminder of integral division, and >> is shift right operator. If Offset = 0, this algorithm is identical to StandartHashCalc.
The most optimal hash-value distribution is achieved by using the OffsetHashCalc algorithm with the following parameters: Offset = 3 and HashIndexSize = 2n+1.
Data types: DYNCNTRL.TYP
Prototypes: DYNCNTRL.DEC
Implementation: HASH.C
Macros: DYNCNTRL.MAC
The following types are defined for the hash-table:
typedef size_t HASH_VALUE;
Hash-value.
typedef unsigned long STORE_VALUE;
Key value.
Structure of the hash-table element:
typedef struct tag_HashList
{
long NextElem;
STORE_VALUE Value;
long Assign;
}
HashList;
NextElem – the number of the next chain element. It is equal to zero for the last chain element.
Value – the element key. This key is used to access to the element.
Assign – associated value.
Structure of the hash-table:
typedef struct tag_HASH_TABLE
{
TABLE hTable;
long *pIndex;
size_t IndexSize;
PFN_CALC_HASH_FUNC HashFunc;
unsigned long *pElements;
unsigned long statCompare, statPut, statFind;
}
HASH_TABLE;
hTable – the hash-array of hash-table elements. The hash-array is organized as a table structure.
pIndex – the hash-index, an array containing starting indexes of the chains. The hash-value gives an index in the hash-index.
IndexSize – size of the pIndex array.
HashFunc – pointer to the function that calculates a hash-value by a key.
pElements – array that keeps chain sizes of corresponding pIndex elements. It is used to store statistics of using hash-table elements.
statCompare, statPut, statFind – statistics fields. These fields contain count of ‘compare’, ‘put’ and ‘find’ actions performed with the hash-table.
Figure 1 Hash-table representation
The following functions are intended for working with hash-table.
void hash_Init( HASH_TABLE *HT, size_t IndexSize, int TableSize, PFN_CALC_HASH_FUNC Func );
HT – pointer to the initialized HASH_TABLE structure.
IndexSize – the size of the hash-index.
TableSize – hash-array increment value for hash-array expansion.
Func – pointer to the function that calculates hash-value. If Func is, equal to NULL then the standard function StandartHashCalc will be applied. The function StandartHashCalc calculates hash-value using the following formula: <hash-value> = <key> % IndexSize.
Initialization of the hash-table. The function performs all required initialization operations.
void hash_Done( HASH_TABLE *HT );
HT – pointer to the HASH_TABLE structure.
The function uninitializes the hash-table. The function frees all allocated memory for hash-table elements.
long hash__Find( HASH_TABLE *HT, STORE_VALUE Val );
HT – pointer to the HASH_TABLE structure.
Val – the key of the element.
Searching element by the specified key. The function returns the value that is associated with this key.
void hash__Insert( HASH_TABLE *HT, STORE_VALUE Val, long Assign );
HT – pointer to the HASH_TABLE structure.
Val – the key of the inserted element.
Assign – the value associated with the key.
Inserting a new element into the hash-table.
void hash__Change( HASH_TABLE *HT, STORE_VALUE Val, long Assign );
HT – pointer to the HASH_TABLE structure.
Val – the key of the updated element.
Assign – the new value associated with the key.
Updating associated value for the specified key.
void hash__Remove( HASH_TABLE *HT, STORE_VALUE Val );
HT – pointer to the HASH_TABLE structure.
Val – the key of the removed element.
Removing the element with the specified key.
void hash__Iterator( HASH_TABLE *HT, PFN_HASHITERATION Proc, void *Param );
HT – pointer to the HASH_TABLE structure.
Proc – iteration function with the following prototype: void (*PFN_HASHITERATION)(long Elem, void *Param), where Elem is associated value of a hash-table element and Param is additional parameter. This function will be called for each hash-table element.
Param – parameter passed as Param into the Proc function.
Performing the same operation for the hash-table elements.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
