8. Bigloo
A practical Scheme compiler
User manual for version 4.2a
September 2015 -- Fast search
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 patternbigloo procedure
This function creates a kmp-table used for fast search.

kmp-mmap kmp-table mmap offsetbigloo procedure
kmp-string kmp-table string offsetbigloo 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)
      ((null? (cdr args))
       (fprintf (current-error-port) "Usage: grep STRING [FILE]...")
       (exit 0))
       (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 Thu Sep 3 08:07:38 2015.