Patent ID: 6247108
Filing Date: 2001-06-12
Classification: G06F,Y10S

Abstract:
A method of searching for a specific node of a binary decision diagram (BDD) in a memory of a computer system comprising:performing a hash function on said specific node to obtain a hash key, said specific node including pointers to a parent node and two child nodes, said two child nodes having memory addresses that indicate an order of creation;indexing into a hash table using said hash key and obtaining a collision chain memory address that points to a collision chain in said memory, said collision chain includes a plurality of chronologically ordered linked BDD entry nodes, said BDD entry nodes including a BDD specific node and a collision chain link;comparing said collision chain memory address with said specific node's said two child nodes memory addresses;if said collision chain memory address is not chronologically newer than said specific node's said two child nodes' memory addresses, then terminating said method;if said collision chain memory address is chronologically newer than said specific node's said two child nodes' memory addresses, then sequentially retrieving said plurality of chronologically ordered linked BDD entry nodes associated with said collision chain; andterminating said sequential retrieval upon determining that said BDD specific node matches said specific node, said BDD entry node's collision chain link is not linked to another BDD entry node or if said BDD child nodes' memory addresses are chronologically older than said specific node's said child nodes' memory addresses.