Re: [Chicken-users] hash table questions

[Kon Lovett]

On Nov 22, 2012, at 4:56 PM, Claude Marinier <address@hidden> wrote:

> Greetings fellow Schemers,
> 
> Having established in a previous post that using a u8vector as a key for a 
> hash table is expected to work, I have some specific questions.
> 
> I am still learning how to post questions properly. I hope this is clear and 
> contains enough information.
> 
> By the way, how can I make the included code display properly? In Mozilla 
> Firefox, it uses a proportional font.
> 
> 
> 1) Is using a hash function other than the default worth the trouble?

Maybe, depending on the datatype used as a key. But in the case of a u8vector 
nothing in the hashes egg is suitable.

The hashes suite assumes the bits to be hashed are contiguous in memory. So it 
does not handle linked data in a useful manner. (The srfi-4 vectors are 
implemented using records & blobs. The FNVAHash will only see the record bits, 
not the actual data bits in the blob.)

> 
> I define the hash table this way.
> 
> (define IPv4-table
>   (make-hash-table IPv4-addr= (make-fixnum-bounded-hash FNVAHash)))
> 
> (declare (inline IPv4-addr=))
> (define IPv4-addr=
>   (lambda (addr1 addr2)
>     (and (= (u8vector-ref addr1 0) (u8vector-ref addr2 0))
>          (= (u8vector-ref addr1 1) (u8vector-ref addr2 1))
>          (= (u8vector-ref addr1 2) (u8vector-ref addr2 2))
>          (= (u8vector-ref addr1 3) (u8vector-ref addr2 3)))))
> 
> Would it be simpler, as effective, and almost as efficient to use the default?

In this case.

> 
> P.S. Is this the correct way to specific an alternate hash function?

Yes.

> 
> 
> 2) Is this the correct way to add new records to the table and update 
> existing records?
> 
> (define update-IPv4-counters
>   (lambda (addr direction proto tokens)
>     (let ((IP-record (hash-table-ref/default IPv4-table addr #f)))
>       (cond
>         ((not (vector? IP-record))
>           ; addr is not in the table, this is a new entry
>           (hash-table-set! IPv4-table addr
>             (update-IP-record (make-IP-record) direction proto tokens)))
>         (else
>           ; addr is in the table, increment packets and add bytes
>           (hash-table-set! IPv4-table addr
>             (update-IP-record IP-record direction proto tokens)))))))
> 
> Note that an IP record is a seven elements vector (i.e. created with 
> make-vector).
> 
> If I understand SRFI-69 correctly, hash-table-set! will replace a record with 
> the same key. Is this correct?

Yes.

> There cannot be duplicate keys, right?

No.

> 
> 
> 3) This is how I dump the hash table.
> 
> (define dump-data
>   (lambda ()
> 
>     (let*  ((outport (open-output-file (make-dump-file-name)))
>             (dump-IPv4-record (lambda (address IP-record)
>                 (write-with-indent (IPv4-address->string address) 1 outport)
>                 (dump-IP-protocols IP-record 1 outport))))
> 
>       (write-with-indent "IPv4" 0 outport)
>       (hash-table-for-each IPv4-table dump-IPv4-record)
> 
>       ...
> 
> (define IPv4-address->string
>   (lambda (addr)
>     (string-append
>       (number->string (u8vector-ref addr 0)) "."
>       (number->string (u8vector-ref addr 1)) "."
>       (number->string (u8vector-ref addr 2)) "."
>       (number->string (u8vector-ref addr 3))))
> 
> This code displays two records with the same key and different data. This has 
> happened more than once. I have kept the output files.

See above.

> 
> If I call hash-table-set! with the same address as another record but in a 
> different format (say a vector instead of a u8vector), would it choke

No.

> or would it just create a new record without complaining? This would look 
> like duplicate keys but they would be different.

The builtin hash will treat a u8vector & a vector of fixnum differently.

I suggest using a vector of fixnum as your IP-addr representation. I am 
doubtful that records as keys are correctly processed. ex: (vector 192 168 1 16)

> 
> I assume that hash-table-for-each will present each key / record pair once 
> and do so in some arbitrary order.

Yes.

> 
> Can I assume that dump-IPv4-record, when it calls IPv4-address->string, will 
> choke on a key which is not a u8vector?

Yes.

> 
> 
> 
> I am looking for the mistake I made which is producing the illusion of a 
> duplicate key in the hash table. I believe that confirming my assumptions is 
> a good starting point.
> 
> I hope this sort of question is not abusing the list members.
> 
> Thank you for your patience.
> 
> -- 
> Claude Marinier
> 
> _______________________________________________
> Chicken-users mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/chicken-users