The Tor Browser / file revision

 // Copyright 2013 Google Inc. All Rights Reserved.

 //

 // Licensed under the Apache License, Version 2.0 (the "License");

 // you may not use this file except in compliance with the License.

 // You may obtain a copy of the License at

 //

 //     http://www.apache.org/licenses/LICENSE-2.0

 //

 // Unless required by applicable law or agreed to in writing, software

 // distributed under the License is distributed on an "AS IS" BASIS,

 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 // See the License for the specific language governing permissions and

 // limitations under the License.

 //

 // Author: dsites@google.com (Dick Sites)

 //

 #ifndef UTIL_UTF8_OFFSETMAP_H_

 #define UTIL_UTF8_OFFSETMAP_H_

 #include <string>                       // for string

 #include "integral_types.h"             // for uint32

 // ***************************** OffsetMap **************************

 //

 // An OffsetMap object is a container for a mapping from offsets in one text

 // buffer A' to offsets in another text buffer A. It is most useful when A' is

 // built from A via substitutions that occasionally do not preserve byte length.

 //

 // A series of operators are used to build the correspondence map, then

 // calls can be made to map an offset in A' to an offset in A, or vice versa.

 // The map starts with offset 0 in A corresponding to offset 0 in A'.

 // The mapping is then built sequentially, adding on byte ranges that are

 // identical in A and A', byte ranges that are inserted in A', and byte ranges

 // that are deleted from A. All bytes beyond those specified when building the

 // map are assumed to correspond, i.e. a Copy(infinity) is assumed at the

 // end of the map.

 //

 // The internal data structure records positions at which bytes are added or

 // deleted. Using the map is O(1) when increasing the A' or A offset

 // monotonically, and O(n) when accessing random offsets, where n is the

 // number of differences.

 //

 namespace CLD2 {

 class OffsetMap {

  public:

   // Constructor, destructor

   OffsetMap();

   ~OffsetMap();

   // Clear the map

   void Clear();

   // Add to  mapping from A to A', specifying how many next bytes correspond

   // in A and A'

   void Copy(int bytes);

   // Add to mapping from A to A', specifying how many next bytes are

   // inserted in A' while not advancing in A at all

   void Insert(int bytes);

   // Add to mapping from A to A', specifying how many next bytes are

   // deleted from A while not advancing in A' at all

   void Delete(int bytes);

   // Print map to file, for debugging

   void Printmap(const char* filename);

   // [Finish building map,] Re-position to offset 0

   // This call is optional; MapForward and MapBack finish building the map

   // if necessary

   void Reset();

   // Map an offset in A' to the corresponding offset in A

   int MapBack(int aprimeoffset);

   // Map an offset in A to the corresponding offset in A'

   int MapForward(int aoffset);

   // h = ComposeOffsetMap(g, f), where f is a map from A to A', g is

   // from A' to A'' and h is from A to A''.

   //

   // Note that g->MoveForward(f->MoveForward(aoffset)) always equals

   // to h->MoveForward(aoffset), while

   // f->MoveBack(g->MoveBack(aprimeprimeoffset)) doesn't always equals

   // to h->MoveBack(aprimeprimeoffset). This happens when deletion in

   // f and insertion in g are at the same place.  For example,

   //

   // A    1   2   3   4

   //      ^   |  ^    ^

   //      |   | /     |  f

   //      v   vv      v

   // A'   1'  2'      3'

   //      ^   ^^      ^

   //      |   | \     |  g

   //      v   |  v    v

   // A''  1'' 2'' 3'' 4''

   //

   // results in:

   //

   // A    1   2   3   4

   //      ^   ^\  ^   ^

   //      |   | \ |   |  h

   //      v   |  vv   v

   // A''  1'' 2'' 3'' 4''

   //

   // 2'' is mapped 3 in the former figure, while 2'' is mapped to 2 in

   // the latter figure.

   static void ComposeOffsetMap(OffsetMap* g, OffsetMap* f, OffsetMap* h);

   // For debugging only; writes to stderr

   void DumpWindow();

   // For testing only -- force a mapping

   void StuffIt(const std::string& diffs, int max_aoffset, int max_aprimeoffset);

  private:

   enum MapOp {PREFIX_OP, COPY_OP, INSERT_OP, DELETE_OP};

   void Flush();

   void FlushAll();

   void MaybeFlushAll();

   void Emit(MapOp op, int len);

   void SetLeft();

   void SetRight();

   // Back up over previous range, 1..5 bytes

   // Return subscript at the beginning of that. Pins at 0

   int Backup(int sub);

   // Parse next range, 1..5 bytes

   // Return subscript just off the end of that

   int ParseNext(int sub, MapOp* op, int* length);

   // Parse previous range, 1..5 bytes

   // Return current subscript

   int ParsePrevious(int sub, MapOp* op, int* length);

   void PrintPosition(const char* str);

   bool MoveRight();     // Returns true if OK

   bool MoveLeft();      // Returns true if OK

   void DumpString();

   // Copies insert operations from source to dest. Returns true if no

   // other operations are found.

   static bool CopyInserts(OffsetMap* source, OffsetMap* dest);

   // Copies delete operations from source to dest. Returns true if no other

   // operations are found.

   static bool CopyDeletes(OffsetMap* source, OffsetMap* dest);

   std::string diffs_;

   MapOp pending_op_;

   uint32 pending_length_;

   // Offsets in the ranges below correspond to each other, with A' = A + diff

   int next_diff_sub_;

   int current_lo_aoffset_;

   int current_hi_aoffset_;

   int current_lo_aprimeoffset_;

   int current_hi_aprimeoffset_;

   int current_diff_;

   int max_aoffset_;

   int max_aprimeoffset_;

 };

 }  // namespace CLD2

 #endif  // UTIL_UTF8_OFFSETMAP_H_