SearchableFile.phpclass

<?php
/**************************************************************************************************************

    NAME
	SearchableFile.phpclass

    DESCRIPTION
	A class to perform string search operations on big files that do not fit into memory.

    AUTHOR
        Christian Vigh, 03/2016.

    HISTORY
    [Version : 1.0]	[Date : 2016/03/29]     [Author : CV]
        Initial version.

    [Version : 1.1]	[Date : 2016/04/24]     [Author : CV]
	. Implemented some kind of naive buffer cache to avoid unnecessary disk IO.

    [Version : 1.1.1]	[Date : 2016/09/04]     [Author : CV]
	. Added the get_contents() method.

    [Version : 1.1.2]	[Date : 2016/09/20]     [Author : CV]
	. The substr() method was returning an empty string when the 3rd parameter ($length) was not specified.

    [Version : 1.1.3]	[Date : 2016/09/20]     [Author : CV]
	. Fixed an inconsistency in method do_strpos() which caused warnings to be issued when searching for a
	  string in cached data.

 **************************************************************************************************************/

/*==============================================================================================================

    SearchableFile class -
        Allows to perform string search operations on big files that do not fit into memory.

  ==============================================================================================================*/
class  SearchableFile			implements 	\ArrayAccess, \Countable, \Iterator
   {
	// Name of the file whose contents are to be searched
	public 		$Filename ;
	// File size
	public		$Filesize ;
	// Buffer cache and cache size
	public 		$Cache ;
	private		$CacheSize ;
	// Input record size
	public 		$RecordSize ;
	// File descriptor
	public 		$fp ;
	// Number of cache hits/misses
	public 		$CacheHits ;
	public		$CacheMisses ;


	/*--------------------------------------------------------------------------------------------------------------

	    CONSTRUCTOR
	        Instantiates a SearchableFile object.

	    PROTOTYPE
	        $sf 	=  new SearchableFile ( $record_size = 16384, $cache_size = 8 ) ;

	    PARAMETERS
		$record_size (integer) -
			Size of a read buffer, in bytes.

		$cache_size (integer) -
			Buffer cache size. A cache of $cache_size items, each having a record size of $record_size, will
			be allocated into memory.

	    NOTES
		Both record size and cache size can be changed after instatiation but they will only be applied during
		the next call to Open().

	 *-------------------------------------------------------------------------------------------------------------*/
	 public function  __construct  ( $record_size = 16384, $cache_size = 8 )
	   {
		 $this -> RecordSize	=  $record_size ;
		 $this -> CacheSize	=  $cache_size ;

		 $this -> __initialize ( ) ;
	    }


	private function  __initialize ( )
	   {
		$this -> Filename	=  false ;
		$this -> Filesize	=  false ;
		$this -> Cache		=  false ;
		$this -> fp		=  false ;
		$this -> CacheMisses 	=  0 ;
		$this -> CacheHits 	=  0 ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    DESTRUCTOR
	        Closes the searched file, if opened.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  __destruct ( )
	   { $this -> Close ( ) ; }


	/**************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 ******                                         PUBLIC FUNCTIONS                                         ******
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 **************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************/

	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		Open - Opens a file for searching.

	    PROTOTYPE
	        $sf -> Open ( $filename ) ;

	    DESCRIPTION
		Opens the specified file for searching.

	    PARAMETERS
		$filename (string) -
			File to be opened.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Open ( $filename )
	   {
		$this -> Close ( ) ;

		if  ( ! ( $this -> fp  =  @fopen ( $filename, "r" ) ) )
			throw ( new \RuntimeException ( "Cannot open file \"$filename\"." ) ) ;

		$info 			=  fstat ( $this -> fp ) ;

		$this -> Filename	=  $filename ;
		$this -> Filesize 	=  $info [ 'size' ] ;
		$this -> Cache		=  new SearchableFileCache ( $this, $this -> CacheSize ) ;
		$this -> CacheMisses 	=  0 ;
		$this -> CacheHits 	=  0 ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		Close - Closes the searchable file.

	    PROTOTYPE
	        $sf -> Close ( ) ;

	    DESCRIPTION
	        Closes the searchable file, if already opened.

	    NOTES
		Nothing happens if the file is already closed.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Close ( )
	   {
		if  ( $this -> fp )
		   {
			fclose ( $this -> fp ) ;
			$this -> __initialize ( ) ;
		    }
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		Write - write file data between two offsets.

	    PROTOTYPE
	        $sf -> Write ( $output, $start, $end = false ) ;

	    DESCRIPTION
	        Writes all file data comprised between offsets $start and $end.

	    PARAMETERS
	    	$output -
	    		Either a file or stream resource, or a callback which has the following prototype, the $data
	    		parameter containing the next block of data :

	    			function callback ( $data ) ;

	    	$start (integer) -
	    		Start offset.

	    	$end (integer) -
	    		End offset. If this parameter is not specified or set to false, the whole contents of the file
	    		will be written, starting at offset $start.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Write ( $output, $start, $end = false )
	   {
		if  ( is_callable ( $output ) )
			$callable 	=  true ;
		else if  ( is_resource ( $output ) )
			$callable 	=  false ;
		else
			throw ( new \InvalidArgumentException ( "The '\$ouput' parameter of the Write() method must either be a valid file resource or a callback." ) ) ;

		if  ( $end  !==  false  &&  $end  <  $start )
			throw ( new \InvalidArgumentException ( "The '\$end' parameter of the Write() method must be greater than or equal to " .
								"the '\$start' parameter." ) ) ;


		if  ( $end  ===  false )
			$end 	=  $this -> Filesize - 1 ;


		if  ( ! ( $buffer = $this -> Cache -> Get ( $start ) ) )
			return ;

		$rel_offset 	=  $start % $this -> RecordSize ;
		$count		=  $end - $start + 1 ;
		$length 	=  min ( $count, $this -> RecordSize - $rel_offset ) ;
		$data 		=  substr ( $buffer, $rel_offset, $length ) ;
		$count 	       -=  strlen ( $data ) ;

		if  ( $callable )
			$output ( $data ) ;
		else
			fwrite ( $output, $data ) ;

		while  ( $count  >  0 )
		   {
			if  ( ! ( $buffer = $this -> Cache -> Next ( ) ) )
				return ;

			$data 	 =  substr ( $buffer -> Data, 0, $count ) ;

			if  ( $callable )
				$output ( $data ) ;
			else
				fwrite ( $output, $data ) ;

			$count  -=  strlen ( $data ) ;
		   }
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
	        get_contents - Returns file contents as a string.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  get_contents ( )
	   {
		return ( file_get_contents ( $this -> Filename ) ) ;
	    }


	/**************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 ******                                         SEARCH FUNCTIONS                                         ******
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 **************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************/

	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		strpos, stripos - Searches for a string.

	    PROTOTYPE
	        $pos 	=  $sf -> strpos  ( $searched_string, $offset = 0 ) ;
	        $pos 	=  $sf -> stripos ( $searched_string, $offset = 0 ) ;

	    DESCRIPTION
	        Behave like the PHP standard strpos() and stripos() functions.

	    PARAMETERS
		$searched_string (string) -
			The string to be searched.

		$offset (integer) -
			Byte offset where the search should start.

	    RETURN VALUE
		Returns either the byte offset of a found occurrence of $searched_string, or false if the string was not
		found in the file.

	 *-------------------------------------------------------------------------------------------------------------*/
	public function   strpos ( $searched_string, $offset = 0 )
	   { return ( $this -> do_strpos ( $searched_string, $offset, 'strpos' ) ) ; }


	public function   stripos ( $searched_string, $offset = 0 )
	   { return ( $this -> do_strpos ( $searched_string, $offset, 'stripos' ) ) ; }


	private function   do_strpos ( $searched_string, $offset = 0, $func )
	   {
		$searched_length 	=  strlen ( $searched_string ) ;

		// Read the data block that contains the specified offset
		$buffer 		=  $this -> Cache -> Get ( $offset ) ;

		if  ( ! $buffer )
			return ( false ) ;

		// Compute the relative offset within this data block
		$relative_offset 	=  $offset - $buffer -> Offset ;

		// Search the string ; if found, we're done
		$pos 			=  $func ( $buffer -> Data, $searched_string, $relative_offset ) ;

		if  ( $pos  !==  false )
			return ( $buffer -> Offset + $pos ) ;

		// Otherwise, continue reading blocks until we find something or EOF
		while  ( $buffer )
		   {
			// Don't forget that the searched string could span two data blocks, so we will do a search on the
			// last $searched_length-1 characters of the current buffer plus the next data block
			$tail 		=  substr ( $buffer -> Data, $buffer -> Size - $searched_length + 1 ) ;
			$old_size 	=  $buffer -> Size ;
			$old_offset	=  $buffer -> Offset ;
			$buffer 	=  $this -> Cache -> Next ( ) ;

			// There is a next block
			if  ( $buffer )
			   {
				$data 	=  $tail . $buffer -> Data ;			// Catenate the tail of the previous block with the current one
				$pos 	=  $func ( $data, $searched_string, 0 ) ;	// Do a search on this

				// Of cours, since we did a search on a whole block plus some characters from the previous one, we will
				// have to perform some adjustments to the value return by the strpos/stripos function.
				if  ( $pos  !==  false )
					return ( $old_offset + $old_size - $searched_length + 1 + $pos ) ;
			    }
		    }

		// Everything has been read, the searched string was not found
		return ( false ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		strchr - Searches for a character within a set.

	    PROTOTYPE
	        $pos 	=  $sf -> strchr ( $cset, $offset = 0 ) ;

	    DESCRIPTION
		Finds the offset of the first character belonging to $cset.

	    PARAMETERS
		$cset (string) -
			The set of characters to be searched.

		$offset (integer) -
			Byte offset where the search should start.

	    RETURN VALUE
		Returns either the byte offset of the first character found belonging to $cset, or false if no more
		characters from $cset are present in the file.

	    NOTES
		Unlike the useless PHP strchr() function, which returns a substring starting with the searched
		character or string, but much more like the C strchr() function, which returns a pointer to the found
		character, strchr() returns the offset in the file of the searched character(s).

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  strchr ( $cset, $offset = 0 )
	   {
		// Read the data block that contains the specified offset
		$buffer 		=  $this -> Cache -> Get ( $offset ) ;

		if  ( ! $buffer )
			return ( false ) ;

		// Compute the relative offset within this data block
		$relative_offset 	=  $offset - $buffer -> Offset ;

		// Search for the first character in the specified cset
		$length 		=  strcspn ( $buffer -> Data, $cset, $relative_offset ) ;

		if  ( $length + $relative_offset  <  $buffer -> Size  &&
				strpos ( $cset, $buffer -> Data [ $relative_offset + $length ] )  !==  false )
			return ( $buffer -> Offset + $relative_offset + $length ) ;

		// Otherwise, continue reading blocks until we find something or EOF
		while  ( $buffer )
		   {
			$buffer 	=  $this -> Cache -> Next ( ) ;

			if  ( $buffer )
			   {
				$length 	=  strcspn ( $buffer -> Data, $cset, 0 ) ;

				if  ( $length  <  $buffer -> Size  &&
						strpos ( $cset, $buffer -> Data [ $length ] ) !==  false )
					return ( $buffer -> Offset + $length ) ;
			    }
		    }

		// Everything has been read, no character within the cset was found
		return ( false ) ;
	    }



	/*--------------------------------------------------------------------------------------------------------------

	    NAME
		multistrpos, multistripos - Searches for a string within a set of strings.

	    PROTOTYPE
	        $pos 	=  $sf -> multistrpos  ( $searched_strings, $offset = 0, &$found_index = null, &$found_string = null ) ;
	        $pos 	=  $sf -> multistripos ( $searched_strings, $offset = 0, &$found_index = null, &$found_string = null ) ;

	    DESCRIPTION
	        Behaves like the PHP standard strpos() and stripos() functions, but can be used to find the first occurrence
	        of a string within a set of searched strings.

	    PARAMETERS
		$searched_strings (array of strings) -
			Strings to be searched.

		$offset (integer) -
			Byte offset where the search should start.

		&$found_index (integer) -
			Will receive the index, in the $searched_string array, of the found string.

		&$found_string (string) -
			Will receive the string contents that have been found in the input file, which may differ from
			the searched strings when the case-insensitive version is used.

	    RETURN VALUE
		Returns either the byte offset of a found occurrence in $searched_strings, or false if the string was not
		found in the file.

	 *-------------------------------------------------------------------------------------------------------------*/
	 public function  multistrpos ( $searched_strings, $offset = 0, & $found_index = null, & $found_string = null )
	   {
		return ( $this -> domultistrpos ( false, $searched_strings, $offset, $found_index, $found_string ) ) ;
	    }


	public function  multistripos ( $searched_strings, $offset = 0, & $found_index = null, & $found_string = null )
	   {
		return ( $this -> domultistrpos ( true, $searched_strings, $offset, $found_index, $found_string ) ) ;
	    }


	protected function  domultistrpos ( $case_insensitive, $searched_strings, $offset = 0, & $found_index = null, & $found_string = null )
	   {
		// Let's assume that the $searched_strings array will be the same from one call to another.
		// This is why we will store this static data and reuse it until a different $searched_strings
		// array is passed
		static 		$previous_searched_strings 	=  [] ;		// Serves to compare $searched_strings with the previous one
		static 		$searched_lengths ;				// Store string lengths (they will be computed only once)
		static 		$cset ;						// A charset built from the first letter of every search string
										// (we will be using the strchr() method to locate the first
										// potential candidate for a match)
		static  	$search_count ;					// Number of searched strings
		static 		$min_string_length ;				// When strchr() succeeded but the string is not the desired one,
										// we will go forward of that number of characters


		// 1st time call or parameters changed, rebuild our static data
		if  ( $searched_strings  !==  $previous_searched_strings )
		   {
			$previous_searched_strings 	=  $searched_strings ;
			$searched_lengths 		=  [] ;
			$cset 				=  '' ;
			$search_count 			=  count ( $searched_strings ) ;
			$min_string_length 		=  PHP_INT_MAX ;

			// For each string, add its first character to $cset (if not already here), compute string length
			// and adjust min string length.
			for  ( $i = 0 ; $i  <  $search_count ; $i ++ )
			   {
			   	$string 		=  $searched_strings [$i] ;
			   	$length 		=  strlen ( $string ) ;

			   	if  ( ! $length )
			   		throw ( new \RuntimeException ( "Empty search string found at index #$i." ) ) ;

				$searched_lengths [] 	=  $length ;
				$ch 			=  $string [0] ;

				if  ( strpos ( $cset, $ch )  ===  false )
					$cset 	.=  $ch ;

					if  ( $min_string_length  >  $length )
						$min_string_length 	=  $length ;
			    }
		    }

		// Loop through file contents until a match is found
		$pos 		=  $offset ;

		while  ( ( $pos = $this -> strchr ( $cset, $pos ) )  !==  false )
		   {
		   	$relpos		=  $pos - $this -> BufferOffset ;	// Relative position in the current buffer
			$ch 		=  $this -> Buffer [ $relpos ] ;

			// Loop through searched strings to find a match
			for  ( $i = 0 ; $i  <  $search_count ; $i ++ )
			   {
			   	$string 	=  $searched_strings [$i] ;

			   	// Match found
			   	if  ( $string [0]  ==  $ch  &&
			   			! substr_compare ( $this -> Buffer, $string, $relpos, $searched_lengths [$i], $case_insensitive ) )
			   	   {
			   	   	$found_index 	=  $i ;
			   	   	$found_string 	=  substr ( $this -> Buffer, $relpos, $searched_lengths [$i] ) ;

			   		return ( $pos ) ;
			   	    }
			    }

			// Match not found : skip by then length of the shortest searched string
			$pos +=  $min_string_length ;
		    }

		return ( false ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
	    	substr - Extracts a substring from the file

	    PROTOTYPE
		$result 	=  $sf -> substr ( $start, $length ) ;

	    DESCRIPTION
		Returns a substring from the searchable file. The $start and $length parameters have the same meaning
		that for the php substr() function.

	    PARAMETERS
	    	The explanation of the following parameters is taken from PHP5.6 documentation ; the word "string",
	    	when designating the 1st parameter of the PHP substr() function, should be read here as "file" :

		$start (integer) -
			If start is non-negative, the returned string will start at the start'th position in string,
			counting from zero. For instance, in the string 'abcdef', the character at position 0 is 'a',
			the character at position 2 is 'c', and so forth.

			If start is negative, the returned string will start at the start'th character from the end of
			string.

			If string is less than start characters long, FALSE will be returned.

		$length (integer) -
			If length is given and is positive, the string returned will contain at most length characters
			beginning from start (depending on the length of string).

			If length is given and is negative, then that many characters will be omitted from the end of
			string (after the start position has been calculated when a start is negative).
			If start denotes the position of this truncation or beyond, FALSE will be returned.

			If length is given and is 0, FALSE or NULL, an empty string will be returned.

			If length is omitted, the substring starting from start until the end of the string will be
			returned.

	    RETURN VALUE
	    	Returns the specified substring or false if one of the following conditions occur :
	    	- The file is less than $start bytes
	    	- $length is negative, and goes past $start backwards
	    	An empty string is returned if $length has been specified and is zero (ie, 0, false or null)

	 *-------------------------------------------------------------------------------------------------------------*/
	public function  substr ( /* $start, $length */ )
	   {
		$argv 		=  func_get_args ( ) ;
		$argc 		=  count ( $argv ) ;
		$start 		=  0 ;
		$length		=  $this -> Filesize ;

		// Compute the real start offset and the real length, according to the specifications above
		switch  ( $argc )
		   {
		   	case 	0 :
				throw ( new \RuntimeException ( "substr() expects at least 1 parameter." ) ) ;

		   	case 	2 :
		   		$length2 =  $argv [1] ;

		   		if  ( ! $length2 )
		   			return ( false ) ;

		   		if  ( $length2  <  0 )
		   			$length	+=  $length2 ;
		   		else
		   			$length  =  $length2 ;

			case 	1 :
		   		$start 	=  $argv [0] ;

		   		if  ( $start  >=  $this -> Filesize )
		   			return ( FALSE ) ;

		   		if  ( $start  <  0 )
		   			$start 	=  $this -> Filesize + $start ;

		   		break ;

		   	default :
		   		throw ( new \RuntimeException ( "substr() expects at most 2 parameters." ) ) ;
		    }

		if  ( $length  <= 0 )
			return ( false ) ;

		// Read the first block that contains the start character
		$buffer 	=  $this -> Cache -> Get ( $start ) ;

		if  ( ! $buffer )
			return ( false ) ;

		$relpos 	=  $start - $buffer -> Offset ;		// Compute relative position in current buffer
		$substring 	=  '' ;					// Value to be returned

		// Loop until $length characters have been extracted
		while ( $length  >  0 )
		   {
		   	// Compute the number of bytes we can extract from the current buffer
			$remaining 	 =  min ( $buffer -> Size - $relpos, $length ) ;

			// Get the substring
			$substring 	.=  substr ( $buffer -> Data, $relpos, $remaining ) ;

			// Subtract the number of characters extracted from the remaining number of
			// characters to process
			$length 	-=  $remaining ;
			$relpos 	 =  0 ;

			// If we have still more characters to be extracted, read the next block
			if  ( $length )
			   {
				$buffer 	=  $this -> Cache -> Next ( ) ;

				if  ( ! $buffer )
					break ;
			    }
		    }

	   	// All done, return
		return ( $substring ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
	        pcre_match - Searches for a pattern.

	    PROTOTYPE
	        $status 	=  pcre_match ( $pattern, &$matches = null, $flags = 0, $start_offset = 0 ) ;

	    DESCRIPTION
	        pcre_match() tries to behave like preg_match(), but operates on a file rather than in memory.
		For achieving that, it uses the pcregrep linux command to extract match offset using the --file-offsets
		parameter.

	    PARAMETERS
		$pattern (string) -
			Pcre pattern to be matched.

		$matches (array) -
			Array that will receive the match values.

		$flags (integer) -
			Any PREG_* flags recognized by the PHP preg_match() builtin function.

		$start_offset (integer) -
			Offset in the file where the search is to be started.

	    RETURN VALUE
		Returns false if some error occurred (the starting offset is beyond the end of the file, or the search
		pattern is incorrect) ; otherwise the number of matches is returned (0 or 1).

	    PERFORMANCES
		The performances have been tested on a quad-core system running at 1.8GHz, with 8Gb of memory and a
		sample data file of 380Mb, enough to be considered as a "big file", but not too big to allow the
		file_get_contents() function to load it into memory.

		The file contains Rtf data, and the string '\pict' has been searched all over it. The test has been
		performed on a Windows platform.

		A single string search gives the following :
		- Using the SearchableFile class : 2.08s
		- Using file_get_contents() + preg_match() : 0.448s
		The overhead between both methods is due to the execution of the pcregrep command, which takes around
		1.5s.

		Finding all the occurrences of the same pattern gives the following :
		- Using the SearchableFile class : 2.155s
		- Using file_get_contents() + preg_match() : 0.886s

		Running the same test with a 780Mb (which still fits in memory on my system) file gives the following :
		- Using the SearchableFile class : 4.36s
		- Using file_get_contents() + preg_match() : 1.83s

		As a conclusion, pcre_match() will always take longer than preg_match() ; however, it allows to handle
		files whose size does not fit into memory.
		However, performance delta between both methods should significantly decrease on Linux systems, since
		file IO is faster.

	    NOTES
		. pcre_match() first uses the pcregrep command to find the strings matching the specified pattern ; then
		  it uses the SearchableFile::substr() method to extract that data ; and finally it applies the
		  preg_match() function to generate an appropriate $matches array. For these reasons, anchor characters
		  ("^" and "$") should be avoided : if you have to cope with huge files, you have to make some
		  concessions.
		. pcregrep command results are cached ; so a next call to the pcre_match() function with the same
		  pattern will extract the results from the cache, instead of running the pcregrep command again.

	 *-------------------------------------------------------------------------------------------------------------*/
	function  pcre_match ( $pattern, &$matches = null, $flags = 0, $start_offset = 0 )
	   {
		static 	$match_data 	=  [] ;

		// Handle extreme cases immediately
		if  ( $start_offset  >=  $this -> Filesize )
			return ( false ) ;

		// Cache the match results if we have a new pattern
		if  ( ! isset  ( $match_data [ $pattern ] ) )
		   {
			$pcre 		=  $this -> transform_regex ( $pattern ) ;
			$re 		=  $pcre [0] ;
			$re_flags	=  $pcre [1] ;
			$command 	=  "pcregrep --file-offsets $re_flags -e $re {$this -> Filename}" ;

			exec ( $command, $output, $status ) ;

			if  ( $status )
				throw ( new \RuntimeException ( "An error occurred during the execution of the pcregrep command :\n" .
						implode ( "\n", $output ) ) ) ;

			$match_data [ $pattern ] 	=  [] ;

			foreach  ( $output  as  $line )
			   {
				list ( $offset, $length )	=  explode ( ',', $line ) ;
				$match_data [ $pattern ] []	=  [ $offset, $length ] ;
			    }
		    }

		$ranges 	=  $match_data [ $pattern ] ;

		// Instead of sequentially searching within the array of matches the first entry that has an offset
		// strictly greater than zero, we will first perform some kind of dichotomic search.
		// In most cases, the found entry will not be equal to the searched offset, so we will have to
		// perform some adjustments after.
		// For an array of x matches, it will require log2(x)+a comparisons, where a is the number of
		// adjustments needed (between 0 and 2)
		$min 		=  0 ;
		$max 		=  count ( $ranges ) - 1 ;
		$index 	=  ( integer ) ( ( $max - $min ) / 2 ) ;

		while  ( $min  <=  $max )
		   {
		   	$offset 	=  $ranges [ $index ] [0] ;

		   	if  ( $offset  <  $start_offset )
		   		$min 	=  $index + 1 ;
		   	else if  ( $offset  >  $start_offset )
		   	   	$max 	=  $index + 1 ;
		   	else
		   		break ;

		   	$old_index 	=  $index ;
		   	$index 	=  $min + ( integer ) ( ( $max - $min ) / 2 ) ;

		   	if  ( $old_index  ==  $index )
		   		break ;
		    }

		$adjusted	=  0 ;

		while  ( $index  >=  0  &&  $ranges [ $index ] [0]  >  $start_offset )
		   {
			$index -- ;
			$adjusted ++ ;
		    }

		if  ( $adjusted )
			$index ++ ;

		// Get the matched substring from the searchable file
		$match_offset 	=  $ranges [ $index ] [0] ;
		$match_length 	=  $ranges [ $index ] [1] ;
		$data 		=  $this -> substr ( $match_offset, $match_length ) ;

		// Now execute preg_match to get our match array
		$status 	=  preg_match ( $pattern, $data, $matches, $flags ) ;

		if  ( $status  &&  ( $flags  &  PREG_OFFSET_CAPTURE ) )
		   {
			foreach  ( $matches  as  &$match )
				$match [1] 	+=  $match_offset ;
	 	    }

		// All done, return
		return ( $status ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------

	    NAME
	        pcre_match_all - Searches for all occurrences of a pattern.

	    PROTOTYPE
	        $status 	=  pcre_match_all ( $pattern, &$matches = null, $flags = 0, $start_offset = 0 ) ;

	    DESCRIPTION
	        pcre_match_all() tries to behave like preg_match_all(), but operates on a file rather than in memory.
		For achieving that, it uses the pcregrep linux command to extract match offset using the --file-offsets
		parameter.

	    PARAMETERS
		$pattern (string) -
			Pcre pattern to be matched.

		$matches (array) -
			Array that will receive the match values.

		$flags (integer) -
			Any PREG_* flags recognized by the PHP preg_match() builtin function.

		$start_offset (integer) -
			Offset in the file where the search is to be started.

	    RETURN VALUE
		Returns false if some error occurred (the starting offset is beyond the end of the file, or the search
		pattern is incorrect, or an individual preg_match() on one of the sub-results failed for some reason) ;
		otherwise the number of matches is returned.

	    PERFORMANCES
		The performances have been tested with the same conditions as for the pcre_match() method ; operating
		on a 780Mb file gave the following results :

		- Using the SearchableFile class : 4.2s
		- Using file_get_contents() + preg_match() : 0.811s

	 *-------------------------------------------------------------------------------------------------------------*/
	function  pcre_match_all ( $pattern, &$matches = null, $flags = 0, $start_offset = 0 )
	   {
		// Handle extreme cases immediately
		if  ( $start_offset  >=  $this -> Filesize )
			return ( false ) ;

		// Execute the pcregrep command
		$pcre 		=  $this -> transform_regex ( $pattern ) ;
		$re 		=  $pcre [0] ;
		$re_flags	=  $pcre [1] ;
		$command 	=  "pcregrep --file-offsets $re_flags -e $re {$this -> Filename}" ;

		exec ( $command, $output, $status ) ;

		if  ( $status )
			throw ( new \RuntimeException ( "An error occurred during the execution of the pcregrep command :\n" .
					implode ( "\n", $output ) ) ) ;

		// Collect the results
		$matches 	=  [] ;

		foreach  ( $output  as  $line )
		   {
			list ( $offset, $length )	=  explode ( ',', $line ) ;
			$data 				=  $this -> substr ( $offset, $length ) ;
			$status 			=  preg_match ( $pattern, $data, $data_matches, $flags ) ;

			if  ( $status  &&  ( $flags  &  PREG_OFFSET_CAPTURE ) )
			   {
				foreach  ( $data_matches  as  &$match )
					$match [1] 	+=  $offset ;

				$matches [] 	=  $data_matches ;
			    }
			else
				return ( $status ) ;
		    }

		// All done, return
		return ( count ( $matches ) ) ;
	    }


	/**************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 ******                                         PRIVATE METHODS                                          ******
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 **************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************/

	// transform_regex -
	//	Transforms a regular expression into a form suitable to the pcregrep command, including command-line
	//	options determined by the regex modifiers.
	private function  transform_regex ( $re )
	   {
		static 		$modifiers 	=  'imsxeADSUXJu' ;	// Allowed modifiers

		$length 	=  strlen ( $re ) ;

		// A regex must contain at list two delimiters and a character within - hence the 3-characters minimal expression
		if  ( $length  <  3 )
			throw ( new \RuntimeException ( "Invalid regular expression \"$re\"." ) ) ;

		// First character is the opening delimiter
		$start 		=  $re [0] ;

		// And we must match the ending delimiter ; <>, [], {} and () are authorized as beginning and ending delimiters !
		switch  ( $start )
		   {
		   	case 	'<' :  $end = '>' ; break ;
		   	case 	'[' :  $end = ']' ; break ;
		   	case 	'(' :  $end = ')' ; break ;
		   	case 	'{' :  $end = '}' ; break ;
		   	default     :  $end = $start ;
		    }

		// Scan starting from the last character until we find a closing delimiter
		$length -- ;
		$found			=  false ;
		$pcregrep_options 	=  [] ;
		$extended 		=  false ;

		while  ( $length  >  1 )
		   {
			$ch	=  $re [ $length ] ;

			// Closing delimiter found : we're done
			if  ( $ch  ==  $end )
			   {
				$found	=  true ;
				break ;
			    }
			// Check that the specified modifiers are authorized
			else if  ( strpos ( $modifiers, $ch )  ===  false )
				throw ( new \RuntimeException ( "Invalid modifier '$ch' in regular expression." ) ) ;
			// If yes, try to emulate what we can
			else
			   {
				switch  ( $ch )
				   {
					// 'm' modifier :
					//	Matches multiline patterns.
					case 	'm' :
						$pcregrep_options [] 	=  '-M' ;
						break ;

					// 'i' modifier :
					//	Case-insensitive match.
					case 	'i' :
						$pcregrep_options [] 	=  '-i' ;
						break ;

					// 'x' modifiers :
					//	Spaces are not significant in a regular expression.
					case 	'x' :
						$extended 		=  true ;

					// Other modifiers have no counterpart - silently ignore them
					default :
				    }
			    }

			$length -- ;
		    }

		// Check that a closing delimiter has been found
		if  ( ! $found )
			throw ( new \RuntimeException ( "Missing ending delimiter in regular expression." ) ) ;

		// Extract the regular expression, without delimiters and modifiers
		$re 	=  substr ( $re, 1, $length - 1 ) ;

		// If the 'x' modifier has been specified, we have to suppress spaces from the regular expression,
		// because the pcregrep command does not allow for that
		if  ( $extended )
		   {
			$extended_re 	=  $re ;
			$re 		=  '' ;
			$re_length 	=  strlen ( $extended_re ) ;
			$in_brackets 	=  false ;

			for  ( $i = 0 ; $i  <  $re_length ; $i ++ )
			   {
				$ch 	=  $extended_re [$i] ;

				switch ( $ch )
				   {
					// Backslash :
					//	Copy this character and the one following it (we don't handle unicode escape sequences here)
					case 	'\\' :
						if  ( isset ( $extended_re [ $i + 1 ] ) )
							$re 	.=  '\\' . $extended_re [ ++ $i ] ;
						else
							$re 	.=  '\\' ;

						break ;

					// Closing bracket :
					//	Spaces outside brackets will be ignored.
					case 	']' :
						if  ( $in_brackets )
							$in_brackets 	=  false ;

						$re 	.=  $ch ;
						break ;

					// Opening brackets :
					//	We have to say that we don't ignore spaces within brackets (character sets).
					case 	'[' :
						$in_brackets 	 =  true ;
						$re 		.=  $ch ;
						break ;

					// Spaces :
					//	Ignore them if we're not inside brackets.
					case  	' ' :
					case 	'\t' :
					case 	'\r' :
					case 	'\n' :
						if  ( $in_brackets )
							$re 	.=  $ch ;
						break ;

					// Other :
					//	Just copy the character to the output string.
					default :
						$re 	.=  $ch ;
				    }
			    }
		    }

		// All done, return
		return ( [ $re, implode ( ' ', $pcregrep_options ) ] ) ;
	    }


	/**************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 ******                                    INTERFACES IMPLEMENTATION                                     ******
	 ******                                                                                                  ******
	 ******                                                                                                  ******
	 **************************************************************************************************************
	 **************************************************************************************************************
	 **************************************************************************************************************/

	// Countable interface
	public function  Count ( )
	   { return ( $this -> Filesize ) ; }


	// ArrayAccess interface - note that it is illegal to set/unset a byte, since the file is opened in read-only mode
	public function   offsetExists ( $offset )
	   { return ( $offset  >=  0  &&  $offset  <  $this -> Filesize ) ; }


	public function   offsetGet ( $offset )
	   {
		if  ( $offset  >=  0  &&  $offset  <  $this -> Filesize )
		   {
			$buffer		=  $this -> Cache -> Get ( $offset ) ;

			return ( $buffer -> Data [ $offset - $buffer -> Offset ] ) ;
		    }
		else
			throw ( new \RuntimeException ( "Undefined offset $offset." ) ) ;

	    }

	public function  offsetSet ( $offset, $member )
	   { throw ( new \RuntimeException ( "Unsupported operation." ) ) ; }


	public function  offsetUnset ( $offset )
	   { throw ( new \RuntimeException ( "Unsupported operation." ) ) ; }


	// Iterator interface
	private 	$iterator_index ;

	public function  key ( )
	    { return ( $this -> iterator_index ) ; }


	public function  rewind ( )
	    { $this -> iterator_index = 0 ; }


	public function  next ( )
	    { $this -> iterator_index ++ ; }


	public function  valid ( )
	    { return ( $this -> iterator_index  >=  0  &&  $this -> iterator_index  <  $this -> Filesize ) ; }


	public function  current ( )
	   { return ( $this -> offsetGet ( $this -> iterator_index ) ) ; }
    }


/*==============================================================================================================

    SearchableFileCache class -
        Implements a buffer cache.

  ==============================================================================================================*/
 class  SearchableFileCache	// extends object
   {
	// Pool of buffer data
	public		$BufferPool		=  [] ;
	// Cache size (number of buffers in the pool)
	private		$CacheSize ;
	// Current buffer (last accessed)
	private		$LastBuffer		=  false ;
	// Parent SearchableFile object
	private		$Parent ;


	/*--------------------------------------------------------------------------------------------------------------
	
	    CONSTRUCTOR
	        Builds a buffer pool for a searchable file.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  __construct ( $parent, $cache_size )
	   {
		$this -> Parent		=  $parent ;
		$this -> CacheSize	=  $cache_size ;
	    }


	/*--------------------------------------------------------------------------------------------------------------
	
	    NAME
	        Get - Retrieves record data based on its offset.
	
	    PROTOTYPE
	        $buffer		=  $cache -> Get ( $offset ) ;
	
	    DESCRIPTION
	        Retrieves record data based on its offset.
	
	    PARAMETERS
	        $offset (integer) -
	                Record containing the offset to be loaded into memory.
	
	    RETURN VALUE
	        A SearchableFileBuffer object, or false if $offset is out of bounds.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Get ( $offset )
	   {
		// Ignore offset outside the current file size
		if  ( $offset  <  0  ||  $offset  >=  $this -> Parent -> Filesize )
			return ( false ) ;

		// The last read buffer contains the requested offset : return it
		if  ( $this -> LastBuffer  &&  $this -> LastBuffer -> Contains ( $offset ) )
			return ( $this -> LastBuffer ) ;

		// Compute absolute record start offset
		$record_offset	=  $offset - ( $offset % $this -> Parent -> RecordSize ) ;

		$pool_size	=  count ( $this -> BufferPool ) ;

		// Last read record already contains whaat we need...
		if  ( isset ( $this -> BufferPool [ $record_offset ] ) ) 
		   {
			$this -> LastBuffer			=  $this -> BufferPool [ $record_offset ] ;
			$this -> Parent -> CacheHits ++ ;
		    }
		// Requested offset is not in the last read record so we may have to add another one in the pool, if not full
		else if  ( $pool_size  <  $this -> CacheSize )
		   {
			$this -> BufferPool [ $record_offset ]	=
			$this -> LastBuffer			=  new SearchableFileBuffer ( $this -> Parent, $offset ) ;
		    }
		// Buffer pool is full : replace the oldest record with the one we need
		else
		   {
			$oldest_time	=  INF ;
			$oldest_entry	=  PHP_INT_MAX ;

			foreach ( $this -> BufferPool  as  $pool_offset => $buffer )
			    {
				if  ( $buffer -> Timestamp  <  $oldest_time )
				   {
					$oldest_time	=  $buffer -> Timestamp ;
					$oldest_entry	=  $pool_offset ;
				    }
			     }

			unset ( $this -> BufferPool [ $oldest_entry ] ) ;

			$this -> BufferPool [ $record_offset ]	=
			$this -> LastBuffer			=  new SearchableFileBuffer ( $this -> Parent, $offset ) ;
		    }

		return ( $this -> LastBuffer ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------
	
	    NAME
	        Next - Retrieves next record
	
	    PROTOTYPE
	        $buffer		=  $cache -> Next ( ) ;
	
	    DESCRIPTION
	        Retrieves the next record from the cached file.
		If no record has been read so far, retrieves the first record at offset 0.
	
	    RETURN VALUE
	        Returns a SearchableFileBuffer object, or false if no more records are available.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Next ( )
	   {
		if  ( $this -> LastBuffer )
			$offset		=  $this -> LastBuffer -> Offset + $this -> Parent -> RecordSize ;
		else
			$offset		=  0 ;

		return ( $this -> Get ( $offset ) ) ;
	    }


	/*--------------------------------------------------------------------------------------------------------------
	
	    NAME
	        Previous - Retrieves previous record
	
	    PROTOTYPE
	        $buffer		=  $cache -> Previous ( ) ;
	
	    DESCRIPTION
	        Retrieves the previous record from the cached file.
		If no record has been read so far, returns false.
	
	    RETURN VALUE
	        Returns a SearchableFileBuffer object, or false if no more records are available.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Previous ( )
	   {
		if  ( $this -> LastBuffer )
			$offset		=  $this -> LastBuffer -> Offset + $this -> Parent -> RecordSize ;
		else
			$offset		=  -1 ;

		return ( $this -> Get ( $offset ) ) ;
	    }
    }


/*==============================================================================================================

    SearchableFileBuffer class -
        Implements a buffer in the buffer cache.

  ==============================================================================================================*/
 class  SearchableFileBuffer	// extends object
   {
	// Record data
	public 		$Data ;
	// Record offset in file
	public		$Offset ;
	// Record size (may differ from that of the parent, if we reached the last record)
	public		$Size ;
	// Record age
	public 		$Timestamp ;
	// Parent SearchableFile object
	public		$Parent ;


	/*--------------------------------------------------------------------------------------------------------------
	
	    NAME
	        Constructor - Builds a SearchableFileBuffer object.
	
	    PROTOTYPE
	        $buffer		=  new SearchableFileBuffer ( $parent, $offset ) ;
	
	    DESCRIPTION
	        Builds a SearchableFileBuffer object, by loading the contents of the record containing the specified 
		offset.
	
	    PARAMETERS
	        $parent (SearchableFile object) -
	                Parent object for this buffer.

		$offset (integer) -
			Offset of the record to be loaded. The loaded buffer will start at a $parent -> RecordSize 
			boundary and is guaranteed to contain the specified offset.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  __construct ( $parent, $offset )
	   {
		if  ( ! $offset )
			$offset		=  0 ;

		$this -> Parent		=  $parent ;
		$record 		=  ( integer ) ( $offset / $parent -> RecordSize ) ;
		$new_offset 		=  $record * $parent -> RecordSize ;

		fseek ( $parent -> fp, $new_offset, SEEK_SET ) ;

		$this -> Data	 	=  fread ( $parent -> fp, $parent -> RecordSize ) ;
		$this -> Size 		=  strlen ( $this -> Data ) ;
		$this -> Offset 	=  $new_offset ;
		$this -> Timestamp	=  microtime ( true ) ;

		$this -> Parent -> CacheMisses ++ ;
	    }


	/*--------------------------------------------------------------------------------------------------------------
	
	    NAME
	        Contains - Checks if this buffer contains the specified offset.
	
	    PROTOTYPE
	        $status		=  $buffer -> Contains ( $offset ) ;
	
	    DESCRIPTION
	        Checks if this buffer contains the specified offset.
	
	    PARAMETERS
	        $offset (integer) -
	                File offset to be checked.
	
	    RETURN VALUE
	        True if the specified buffer contains $offset, false otherwise.
	
	 *-------------------------------------------------------------------------------------------------------------*/
	public function  Contains ( $offset )
	   {
		return ( $offset  >=  $this -> Offset  &&  $offset  <  $this -> Offset + $this -> Size ) ;
	    }
    }