Fast access priority queue for managing multiple messages at a communications node or managing multiple programs in a multiprogrammed data processor

Claim 1

In a communication node of a local area network comprising at least a processing means and a memory means a method for maintaining a priority queue for messages to be transmitted, comprising using said processing means for the steps of: reading during a network contention interval, the contents of a holding register having a data portion related to a first message to be transmitted and a priority portion related to the priority of said first message, in response to a request for a highest priority message; reading a top element from the top of an unsorted stack of elements stored in said memory means, each element of said stack containing a data portion related to a message to be transmitted and a priority portion related to the priority of the message, said top element being pointed to by a top of stack pointer, and writing the contents of said top element related to a second message to be transmitted, including a priority portion related to the priority of said second message, to said holding register; searching during a period following said network contention interval, said plurality of elements in said unsorted stack by sequentially locating consecutively adjacent elements therein which are sequentially pointed to by a stack search pointer which is initially set equal to said top of stack pointer, and comparing the priority portion of an element pointed to by said stack search pointer, related to a third message to be transmitted, with said priority portion of the contents of said holding register; swapping the contents of said element in said stack pointed to by said stack search pointer with the contents of said holding register, when the priority portion of said contents of said element related to said third message is greater than the priority portion of the contents of said holding register; determining during said period following said network contention interval, if a new element is to be written into said stack, having a data portion related to a fourth message to be transmitted and a priority portion related to the priority of said fourth message; comparing said new element to be written to said stack with the contents of said holding register to determine if the priority portion of said new element is greater than the priority portion of the contents of said holding register; incrementing by unity the contents of said top of stack pointer and writing the contents of said holding register to a location is said stack now pointed to by said top of stack pointer when said priority portion of said new element is greater than the priority portion of the contents of said holding register, and further writing said new element to said holding register; writing said new element to said stack when said priority portion of said new element is not greater than the priority portion of said contents of said holding register; repeating said comparing of each element in said stack with the contents of said holding register until all said elements in said stack have been so compared; whereby stored date related to a message with the highest priority at said communication node, is accessible in said holding register.