PM7324 S/UNI-ATLAS
S/UNI-ATLAS
DATASHEET
PMC-1971154
ISSUE 7
S/UNI-ATM LAYER SOLUTION
8.3
Search Table Data Structure
The Primary and Secondary Search Key table fields reside in the Ingress VC Table.
The Primary Table Record entry is located in the least significant 16-bits of ingress
(LP + LA)
VC Table locations with ISA[19:16]=0000, and requires 2
words of memory.
The Secondary Search Key entry is located at locations with ISA[19:16]=0001 and
its size is bounded by the number of virtual connections supported.
The figure below illustrates the relationship between the Primary Search Table Key,
Secondary Search Table Key and the Ingress VC Table.
Figure 5 Atlas Search Table Structure
0
P rim ary S earch T ab le
2 (L P + L A ) -1
S econ d ary
S earch
T ab le
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
Ing ress
VC
T ab le
E ntry
The following gives the immutable coding rules for the search data structures. The
coding supports numerous possible algorithms, but the Operations Section presents
an algorithm that is optimized for most applications.
8.3.1
Primary Search Table
The Primary Search Table contains an array of pointers that point to the roots of
binary trees. The table is directly indexed by the contents of the Primary Search
Key, as defined above.
The entire Primary Search Table must be initialized to all zeros. A table value of
zero represents a null pointer; therefore, the initial state means no provisioned
connections are defined. If a connection is added which results in a new binary
search tree (i.e. it is the only connection associated with a particular Primary Search
Key), the appropriate Primary Search Table location must point to the newly created
binary search tree root. If the last connection with a particular Primary Search Key
is removed, the associated Primary Search Table location must be set to all zeros.
PROPRIETARY AND CONFIDENTIAL TO PMC-SIERRA, INC AND FOR ITS CUSTOMERS’ INTERNAL USE
52