dirent.go

Documentation: github.com/sassoftware/relic/lib/comdoc

     1  //
     2  // Copyright (c) SAS Institute Inc.
     3  //
     4  // Licensed under the Apache License, Version 2.0 (the "License");
     5  // you may not use this file except in compliance with the License.
     6  // You may obtain a copy of the License at
     7  //
     8  //     http://www.apache.org/licenses/LICENSE-2.0
     9  //
    10  // Unless required by applicable law or agreed to in writing, software
    11  // distributed under the License is distributed on an "AS IS" BASIS,
    12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  // See the License for the specific language governing permissions and
    14  // limitations under the License.
    15  //
    16  
    17  package comdoc
    18  
    19  import (
    20  	"bytes"
    21  	"encoding/binary"
    22  	"errors"
    23  	"unicode/utf16"
    24  
    25  	"github.com/sassoftware/relic/lib/redblack"
    26  )
    27  
    28  // Parse the directory stream
    29  func (r *ComDoc) readDir() error {
    30  	var files []DirEnt
    31  	count := r.SectorSize / 128
    32  	raw := make([]RawDirEnt, count)
    33  	cooked := make([]DirEnt, count)
    34  	rootIndex := -1
    35  	for sector := r.Header.DirNextSector; sector >= 0; sector = r.SAT[sector] {
    36  		if err := r.readSectorStruct(sector, raw); err != nil {
    37  			return err
    38  		}
    39  		for i, raw := range raw {
    40  			cooked[i] = DirEnt{
    41  				RawDirEnt: raw,
    42  				Index:     len(files) + i,
    43  				name:      raw.Name(),
    44  			}
    45  			if raw.Type == DirRoot {
    46  				rootIndex = len(files) + i
    47  			}
    48  		}
    49  		files = append(files, cooked...)
    50  	}
    51  	if rootIndex < 0 {
    52  		return errors.New("missing root storage")
    53  	}
    54  	r.Files = files
    55  	r.rootStorage = rootIndex
    56  	rootFiles, err := r.ListDir(nil)
    57  	if err != nil {
    58  		return err
    59  	}
    60  	r.rootFiles = make([]int, 0, len(r.Files))
    61  	for _, f := range rootFiles {
    62  		r.rootFiles = append(r.rootFiles, f.Index)
    63  	}
    64  	return nil
    65  }
    66  
    67  // Return a pointer to the root storage.
    68  func (r *ComDoc) RootStorage() *DirEnt {
    69  	return &r.Files[r.rootStorage]
    70  }
    71  
    72  // List the items in a storage. If parent is nil, the root storage is used.
    73  func (r *ComDoc) ListDir(parent *DirEnt) ([]*DirEnt, error) {
    74  	if parent == nil {
    75  		parent = r.RootStorage()
    76  	}
    77  	if parent.Type != DirRoot && parent.Type != DirStorage {
    78  		return nil, errors.New("ListDir() on a non-directory object")
    79  	}
    80  	top := &r.Files[parent.StorageRoot]
    81  	stack := []*DirEnt{top}
    82  	var files []*DirEnt
    83  	for len(stack) > 0 {
    84  		i := len(stack) - 1
    85  		item := stack[i]
    86  		stack = stack[:i]
    87  		files = append(files, item)
    88  		if item.LeftChild != -1 {
    89  			stack = append(stack, &r.Files[item.LeftChild])
    90  		}
    91  		if item.RightChild != -1 {
    92  			stack = append(stack, &r.Files[item.RightChild])
    93  		}
    94  	}
    95  	return files, nil
    96  }
    97  
    98  // Create a new stream and add it to the directory stream.
    99  func (r *ComDoc) newDirEnt(name string, size uint32, sector SecID) (*DirEnt, error) {
   100  	runes := utf16.Encode([]rune(name))
   101  	runes = append(runes, 0)
   102  	if len(runes) > 32 {
   103  		return nil, errors.New("name is too long")
   104  	}
   105  	dirent := &DirEnt{
   106  		RawDirEnt: RawDirEnt{
   107  			NameLength:  uint16(2 * len(runes)),
   108  			Type:        DirStream,
   109  			LeftChild:   -1,
   110  			RightChild:  -1,
   111  			StorageRoot: -1,
   112  			StreamSize:  size,
   113  			NextSector:  sector,
   114  		},
   115  		Index: -1,
   116  		name:  name,
   117  	}
   118  	copy(dirent.NameRunes[:], runes)
   119  	dirent = r.appendDirEnt(dirent)
   120  	return dirent, nil
   121  }
   122  
   123  // Add a DirEnt to the directory stream, extending it if necessary
   124  func (r *ComDoc) appendDirEnt(dirent *DirEnt) *DirEnt {
   125  	// look for a free slot
   126  	index := -1
   127  	for i, j := range r.Files {
   128  		if j.Type == DirEmpty {
   129  			index = i
   130  			break
   131  		}
   132  	}
   133  	if index < 0 {
   134  		// extend the dir stream
   135  		index = len(r.Files)
   136  		newDirs := make([]DirEnt, r.SectorSize/128)
   137  		r.Files = append(r.Files, newDirs...)
   138  	}
   139  	r.Files[index] = *dirent
   140  	r.Files[index].Index = index
   141  	return &r.Files[index]
   142  }
   143  
   144  // Rewrite the red-black tree on the root storage and write the directory
   145  // stream to disk.
   146  func (r *ComDoc) writeDirStream() error {
   147  	// Presently there's no way to modify any storage other than the root one
   148  	// so it's only needed to relabance that.
   149  	r.rebuildTree(r.rootStorage, r.rootFiles)
   150  	freeSectors(r.SAT, r.Header.DirNextSector)
   151  	perSector := r.SectorSize / 128
   152  	if len(r.Files)%perSector != 0 {
   153  		panic("irregularly sized directory stream")
   154  	}
   155  	freeList := r.makeFreeSectors(len(r.Files)/perSector, false)
   156  	chunk := make([]RawDirEnt, perSector)
   157  	buf := bytes.NewBuffer(r.sectorBuf)
   158  	first := SecIDEndOfChain
   159  	previous := first
   160  	for i, sector := range freeList {
   161  		j := i * perSector
   162  		for k, f := range r.Files[j : j+perSector] {
   163  			if f.Type != DirEmpty {
   164  				chunk[k] = f.RawDirEnt
   165  			} else {
   166  				chunk[k] = RawDirEnt{LeftChild: -1, RightChild: -1, StorageRoot: -1}
   167  			}
   168  		}
   169  		buf.Reset()
   170  		binary.Write(buf, binary.LittleEndian, chunk)
   171  		if err := r.writeSector(sector, buf.Bytes()); err != nil {
   172  			return err
   173  		}
   174  		if previous == SecIDEndOfChain {
   175  			first = sector
   176  		} else {
   177  			r.SAT[previous] = sector
   178  		}
   179  		previous = sector
   180  	}
   181  	r.SAT[previous] = SecIDEndOfChain
   182  	r.Header.DirNextSector = first
   183  	r.Header.DirSectorCount = uint32(len(freeList))
   184  	return nil
   185  }
   186  
   187  // Rebuild the red-black directory tree of the root storage after files have
   188  // been added or removed
   189  func (r *ComDoc) rebuildTree(parent int, files []int) {
   190  	tree := redblack.New(lessDirEnt)
   191  	for _, i := range files {
   192  		tree.Insert(&r.Files[i])
   193  	}
   194  	nodes := tree.Nodes()
   195  	for _, n := range nodes {
   196  		e := n.Item.(*DirEnt)
   197  		if n == tree.Root {
   198  			r.Files[parent].StorageRoot = int32(e.Index)
   199  		}
   200  		if n.Red {
   201  			e.Color = Red
   202  		} else {
   203  			e.Color = Black
   204  		}
   205  		if n.Children[0] != nil {
   206  			left := n.Children[0].Item.(*DirEnt)
   207  			e.LeftChild = int32(left.Index)
   208  		} else {
   209  			e.LeftChild = -1
   210  		}
   211  		if n.Children[1] != nil {
   212  			right := n.Children[1].Item.(*DirEnt)
   213  			e.RightChild = int32(right.Index)
   214  		} else {
   215  			e.RightChild = -1
   216  		}
   217  	}
   218  }
   219  
   220  func lessDirEnt(i, j interface{}) bool {
   221  	e, f := i.(*DirEnt), j.(*DirEnt)
   222  	if e.NameLength != f.NameLength {
   223  		return e.NameLength < f.NameLength
   224  	}
   225  	return e.name < f.name
   226  }
   227
View as plain text