8. Bigloo A ``practical Scheme compiler'' User manual for version 3.2a January 2009 -- Fast search

main page

top: | Bigloo A ``practical Scheme compiler'' User manual for version 3.2a January 2009

Fast search

Chapters

This chapters details the Bigloo's API for fast string search algorithms.

### 8.1 Knuth, Morris, and Pratt

Bigloo supports an implementation of the Knuth, Morris, and Pratt algorithm on strings and memory mapped area, See Memory mapped area.

kmp-table pattern | bigloo procedure

This function creates a kmp-table used for fast search.

kmp-mmap kmp-table mmap offset | bigloo procedure

kmp-string kmp-table string offset | bigloo procedure

This function searches the `pattern` described by `kmp-table` in the memory mapped area `mmap` (respec. in the `string`). The search starts at `offset`. If an occurrence is found, its position in the `mmap` is returned. Otherwise `-1` is returned.
For the sake of the example, here is a prototypal implementation of the Usenix command `grep`:

    (define (main args)
       (cond
          ((null? (cdr args))
           (fprintf (current-error-port) "Usage: grep STRING [FILE]...")
           (exit 0))
          (else
           (let ((t (kmp-table (cadr args))))
    	  (for-each (lambda (f) (grep-file t f)) (cddr args))))))

    (define (grep-file t file)
       (let* ((mm (open-mmap file read: #t write: #f))
    	  (ls (mmap-length mm)))
          (let loop ((o 0))
    	 (unless (>=fx o ls)
    	    (let ((n (kmp-mmap t mm o)))
    	       (when (>fx n 0)
    		  (print file ":" (mmap-line mm ls n))
    		  (loop (+fx n 1))))))
          (close-mmap mm)))

    (define (mmap-line mm ls n)
       (let ((b 0)
    	 (e (elong->fixnum ls)))
          ;; beginning
          (let loop ((i n))
    	 (when (>fx i 0)
    	    (if (char=? (mmap-ref mm i) #\Newline)
    		(set! b (+fx i 1))
    		(loop (-fx i 1)))))
          ;; end
          (let loop ((i n))
    	 (when (<fx i ls)
    	    (if (char=? (mmap-ref mm i) #\Newline)
    		(set! e i)
    		(loop (+fx i 1)))))
          (mmap-substring mm b (- e b))))

This Html page has been produced by Skribe.
Last update Tue Jan 6 18:43:50 2009.