Adding comparision function

[Jim Mellander <jmellander@...>]

Hi everyone:

For a custom application (parsing netflow data into input records for a 
custom IDS called Bro), I embarked on a search for the proverbial 
"language that didn't suck", which would combine performance with simple 
syntax and ease of use and understanding....

So I found lua....  In a week and a half, from a standing start, I've 
written a prototype application that uses the socket library, parses 
input records, pastes the (possible) two sides of netflow data into a 
connection record with a timeout, along with heuristics for determining 
source/destination of the traffic.  The only real stumbling block has 
been (aside from learning lua - not a steep learning curve at all!) the 
lack of built-in libraries for common tasks - although I soon found the 
libraries I needed, and added them in.

I've attached a simple binary-heap priority queue implementation I wrote 
for the timeouts, but would like to generalize it, ala lua sort, by 
allowing an optional comparison function -- Can anyone help??

BTW - I spent a fair amount of time optimizing the code, and I eschewed 
the use of table.getn after looking at the C code for the lua 
interpreter, since table.getn appears to be using a binary search 
function to find the size of the table - so, I just store the size as a 
specific key whic is incremented/decremented as needed - any comments on 
that?

===========================================

--
-- pqueue.lua - implementation of a binary heap
--
-- References:
--   http://en.wikipedia.org/wiki/Binary_heap
--   http://www.sbhatnagar.com/SourceCode/pqueue.html
--
-- The operations:
--
--  pqinsert(q,k) - insert to queue q, key k
--  pqremove(q) - returns top item of queue, and removes it from the queue
--
-- q should be initialized as an empty table
--
-- the top item in the queue is q[1], unless the queue is empty, so the
--  queue can be inspected easily.
--
--  The size of the queue dynamically changes, due to lua's table
--    implementation.  We use a key "_size" to keep the table size
--    in preference to using the table.getn() function, since the 
table.getn()
--    function does a binary search in the key space each time to find
--    the length of the table.  (I imagine the performance of table.getn 
could
--    be improved with metamethods)
--
--

function pqinsert(q,k)
        if type(q) ~= "table" then
                return nil
        end

        local i = (q._size or 0) + 1
        q._size = i

        while i > 1 do
                local i2 = math.floor(i/2)
                local qi2 = q[i2]
                if qi2 >= k then
                        break
                end
                q[i] = qi2
                i = i2
        end

        q[i]=k

        return k

end


function pqremove(q)
        if type(q) ~= "table" then
                return nil
        end
        local n = q._size or 0
        if n == 0 then
                q._size = nil
                return nil
        end

        local i=1
        local d=q[1]
        local tmp = q[n]

        q[n]=nil

        n=n-1
        q._size=n

        if n > 0 then
                local t1=math.floor(n/2)

                while i <= t1 do
                        local j=2*i
                        local j1=j+1
                        if j < n and q[j] < q[j1] then
                                j = j1
                        end

                        local qj=q[j]
                        if qj <= tmp then
                                break
                        end

                        q[i] = qj
                        i = j
                end
                q[i] = tmp
        end
        return d
end



-- test main program

a=os.time()
local q={}
local i
for i=1,1000000 do
        local x=i
        -- print("adding "..x)
        pqinsert(q,x)
end
b=os.time()

for i=1,1000000 do
        local x=pqremove(q)
        -- print("removing "..x)
end
c=os.time()

print("Insert took "..b-a)
print("Remove took "..c-b)
print("Size of table: "..table.getn(q))



--
Jim Mellander
Incident Response Manager
Computer Protection Program
Lawrence Berkeley National Laboratory
(510) 486-7204

Your fortune for today is:

If God had intended Man to program, we'd be born with serial I/O ports.