source: project/release/4/sfht/trunk/sfht-eggdoc.scm @ 14491

Last change on this file since 14491 was 14491, checked in by Ivan Raikov, 11 years ago

sfht ported to Chicken 4

File size: 6.3 KB
Line 
1
2(use eggdoc)
3
4(define doc
5  `((eggdoc:begin
6     (name "sfht")
7     (description "A dictionary data structure based on counting Bloom filters.")
8     (author (url "http://chicken.wiki.br/users/ivan-raikov" "Ivan Raikov"))
9
10     (history 
11      (version "2.3" "Ported to Chicken 4")
12      (version "2.1" "Build script updated for better cross-platform compatibility")
13      (version "2.0" "Introduced an API that is independent of the RNG used")
14      (version "1.3" "Documentation updates")
15      (version "1.2" "License upgrade to GPL v3")
16      (version "1.1" "Added random-swb to the list of dependencies")
17      (version "1.0" "Initial release"))
18
19     (requires (url "sparse-vectors.html" "sparse-vectors"))
20
21     (usage "(require-extension sfht)")
22
23     (download "sfht.egg")
24
25     (documentation
26     
27      (p "The sfht library is an implementation of the Shared-node "
28         "Fast Hash Table (SFHT) data structure described by Song, et al., in " 
29         (pre "_Fast Hash Table Lookup Using Extended Bloom Filter: "
30              "An Aid to Network Processing_. (SIGCOMM'05)") ". ")
31
32      (p "This code defines an " (tt "sfht") " object that implements a "
33         "dictionary mapping of keys to values. The object responds to "
34         "messages for querying, insertion of new elements, and deletion "
35         "of existing elements. The interface of the " (tt "sfht") " object "
36         "is particularly suitable for situations where the keys are "
37         "represented by bit vectors or vectors of fixnum values. ")
38
39      (p "A counting Bloom filter is a Bloom filter that has been extended so "
40         "that each bit of the filter has a counter associated with it. Upon "
41         "insertion or deletion of an element, the counter is incremented or "
42         "decremented, respectively. In order to find an element efficiently, "
43         "we need to compute the " (tt "k") " hash values, read the counters "
44         "at the " (tt "k") " locations, determine the smallest bucket size, "
45         "and perform a linear search of that bucket for the element. ")
46
47
48      (subsection "SFHT procedures"
49
50          (p "The sfht object is created by a make-sfht function, "
51             "the only user-visible function defined in this egg: ")
52
53          (procedure "make-sfht:: N P MAKE-RNG-STATE RANDOM! KEY->VECTOR KEY-VECTOR-REF KEY-VECTOR-LENGTH [KEY-EQUAL?] -> SELECTOR"
54                        (p "where  "
55                           (symbol-table
56                            (describe "MAKE-RNG-STATE"
57                                      ("is a user-supplied function that takes in an integer argument and "
58                                       "returns an RNG state value. " ))
59                            (describe "RANDOM!"
60                                      ("is a user-supplied function that generates a random positive integer, "
61                                       "given a state value, which is expected to be mutated. " ))
62                            (describe "KEY->VECTOR"
63                                      ("is a user-supplied function that takes a key value " 
64                                       "and returns a vector."))
65                            (describe "KEY-VECTOR-REF"
66                                      ("is a user-supplied function that retrieves an element from " 
67                                       "the vector returned by " (tt "KEY-VECTOR") ". "))
68                            (describe "KEY-VECTOR-LENGTH"
69                                      ("is a user-supplied function that returns the length " 
70                                       "of the key vector."))
71                            (describe "KEY->EQUAL?"
72                                      ("is a user-supplied predicate that takes two keys and returns " 
73                                       (tt "#t") " if they are equal. The default function used is " 
74                                       (tt "equal?")))))
75                       
76                        (p "The returned selector procedure can take one of the following arguments: "
77                           (symbol-table 
78                            (describe "'get" 
79                                      ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE") 
80                                         " which searches the hash table for an association with a given "
81                                         (tt "KEY") ", and returns a (key . value) pair of the found association. "
82                                         "If an association with " (tt "KEY") " cannot be located in the hash table, "
83                                         "the PROC returns the result of evaluating the " (tt "DEFAULT-CLAUSE") ". "
84                                         "If the default clause is omitted, an error is signaled. "
85                                         (tt "KEY") " must be comparable to the keys in the hash table "
86                                         "by the " (tt "KEY-EQUAL?") " predicate specified "
87                                         "when the hash table was created)"))
88                           
89                            (describe "'empty?"
90                                      ("returns " (tt "#t") " if the hash table is empty"))
91                           
92                            (describe "'size"
93                                      ("returns the size (the number of associations) in the hash table"))
94                           
95                            (describe "'clear!"
96                                      ("removes all associations from the hash table (thus making it empty)"))
97                           
98                            (describe "'put!"
99                                      ("returns a procedure " (tt "LAMBDA KEY VALUE") 
100                                         " which, given a " (tt "KEY") " and a " (tt "VALUE") 
101                                         ", adds the corresponding association to the hash table. "
102                                         "If an association with the same " (tt "KEY") 
103                                         " already exists, its value is replaced with the "
104                                         (tt "VALUE") ". The return value is " (tt "#f") "."))
105                           
106                            (describe "'delete!"
107                                      ("returns a procedure " (tt "LAMBDA KEY . DEFAULT-CLAUSE")
108                                         " which searches the hash table for an association with a given "
109                                         (tt "KEY") ", deletes it, and returns a (key . value) pair of the found "
110                                         "and deleted association. If an association with the KEY cannot be located "
111                                         "in the hash table, the " (tt "PROC") " returns the result of evaluating "
112                                         (tt "DEFAULT-CLAUSE") ". " 
113                                         "If the default clause is omitted, an error is signaled. "))
114                           
115                            (describe "'debugprint"
116                                      ("prints out all the contents the Bloom filter, for debug purposes")))))))
117
118
119     (examples (pre #<<EOF
120(require-extension iset)
121(require-extension sfht)
122(require-extension random-swb)
123
124(define sfht (make-sfht 100000 0.0001 
125                        (lambda (i) (make-swb-random-state i (fx+ i 17)))
126                        swb:random!
127                        integer->bit-vector 
128                        (compose (lambda (x) (if x 1 0)) bit-vector-ref)
129                        bit-vector-length))
130
131((sfht 'put!) 1 'one)
132((sfht 'get))
133EOF
134))
135
136     (license
137      "Copyright 2007-2009 Ivan Raikov.
138
139This program is free software: you can redistribute it and/or modify
140it under the terms of the GNU General Public License as published by
141the Free Software Foundation, either version 3 of the License, or
142at your option any later version.
143
144This program is distributed in the hope that it will be useful, but
145WITHOUT ANY WARRANTY; without even the implied warranty of
146MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
147General Public License for more details.
148
149A full copy of the GPL license can be found at
150<http://www.gnu.org/licenses/>."))))
151
152(if (eggdoc->html doc) (void))
Note: See TracBrowser for help on using the repository browser.