golang源码分析：cayley(5)

func NewQuadStore(name string, dbpath string, opts Options) (QuadStore, error) {
    r, registered := storeRegistry[name]
    return r.NewFunc(dbpath, opts)

var storeRegistry = make(map[string]QuadStoreRegistration)

type QuadStoreRegistration struct {
  NewFunc      NewStoreFunc
  UpgradeFunc  UpgradeStoreFunc
  InitFunc     InitStoreFunc
  IsPersistent bool
}

type NewStoreFunc func(string, Options) (QuadStore, error)
type InitStoreFunc func(string, Options) error
type UpgradeStoreFunc func(string, Options) error

func RegisterQuadStore(name string, register QuadStoreRegistration) {
        if _, found := storeRegistry[name]; found {
    panic(fmt.Sprintf("Already registered QuadStore %q.", name))
  }
  storeRegistry[name] = register

func init() {
  graph.RegisterQuadStore("gaedatastore", graph.QuadStoreRegistration{
    NewFunc:      newQuadStore,
    UpgradeFunc:  nil,
    InitFunc:     initQuadStore,
    IsPersistent: true,
  })
}

func newQuadStore(_ string, options graph.Options) (graph.QuadStore, error) {
  return &QuadStore{}, nil
}

func initQuadStore(_ string, _ graph.Options) error {
  // TODO (panamafrancis) check appengine datastore for consistency
  return nil
}

type QuadStore struct {
  context context.Context
}

func Register(name string, r Registration) {
  graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
    InitFunc: func(addr string, opt graph.Options) error {
      kv, err := r.InitFunc(addr, opt)
      if err = Init(kv, opt); err != nil {
        NewFunc: func(addr string, opt graph.Options) (graph.QuadStore, error) {
      kv, err := r.NewFunc(addr, opt)
        if err = Init(kv, opt); err != nil {
      return New(kv, opt)

func init() {
  graph.RegisterQuadStore(QuadStoreType, graph.QuadStoreRegistration{
    NewFunc: func(string, graph.Options) (graph.QuadStore, error) {
      return newQuadStore(), nil
    },

const QuadStoreType = "memstore"

func newQuadStore() *QuadStore {
  return &QuadStore{
    vals:  make(map[string]int64),
    quads: make(map[internalQuad]int64),
    prim:  make(map[int64]*primitive),
    index: NewQuadDirectionIndex(),
  }
}

func Register(name string, r Registration) {
  graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
    InitFunc: func(addr string, opt graph.Options) error {

func registerQuadStore(name, typ string) {
  graph.RegisterQuadStore(name, graph.QuadStoreRegistration{
    NewFunc: func(addr string, options graph.Options) (graph.QuadStore, error) {
      return New(typ, addr, options)

type QuadStore interface {
  Namer
  QuadIndexer


  // The only way in is through building a transaction, which
  // is done by a replication strategy.
  ApplyDeltas(in []Delta, opts IgnoreOpts) error


  // NewQuadWriter starts a batch quad import process.
  // The order of changes is not guaranteed, neither is the order and result of concurrent ApplyDeltas.
  NewQuadWriter() (quad.WriteCloser, error)


  // Returns an iterator enumerating all nodes in the graph.
  NodesAllIterator() Iterator


  // Returns an iterator enumerating all links in the graph.
  QuadsAllIterator() Iterator


  // Stats returns the number of nodes and quads currently stored.
  // Exact flag controls the correctness of the value. It can be an estimation, or a precise calculation.
  // The quadstore may have a fast way of retrieving the precise stats, in this case it may ignore 'exact'
  // flag and always return correct stats (with an appropriate flags set in the output).
  Stats(ctx context.Context, exact bool) (Stats, error)


  // Close the quad store and clean up. (Flush to disk, cleanly
  // sever connections, etc)
  Close() error
}

type Namer interface {
  // Given a node ID, return the opaque token used by the QuadStore
  // to represent that id.
  ValueOf(quad.Value) Ref
  // Given an opaque token, return the node that it represents.
  NameOf(Ref) quad.Value
}

type QuadIndexer interface {
  // Given an opaque token, returns the quad for that token from the store.
  Quad(Ref) quad.Quad


  // Given a direction and a token, creates an iterator of links which have
  // that node token in that directional field.
  QuadIterator(quad.Direction, Ref) Iterator


  // QuadIteratorSize returns an estimated size of an iterator.
  QuadIteratorSize(ctx context.Context, d quad.Direction, v Ref) (Size, error)


  // Convenience function for speed. Given a quad token and a direction
  // return the node token for that direction. Sometimes, a QuadStore
  // can do this without going all the way to the backing store, and
  // gives the QuadStore the opportunity to make this optimization.
  //
  // Iterators will call this. At worst, a valid implementation is
  //
  //  qs.ValueOf(qs.Quad(id).Get(dir))
  //
  QuadDirection(id Ref, d quad.Direction) Ref
}

type internalQuad struct {
  S, P, O, L int64
}

type primitive struct {
  ID    int64
  Quad  internalQuad
  Value quad.Value
  refs  int
}

func NewQuadDirectionIndex() QuadDirectionIndex {
  return QuadDirectionIndex{[...]map[int64]*Tree{
    quad.Subject - 1:   make(map[int64]*Tree),
    quad.Predicate - 1: make(map[int64]*Tree),
    quad.Object - 1:    make(map[int64]*Tree),
    quad.Label - 1:     make(map[int64]*Tree),
  }}
}

type QuadDirectionIndex struct {
  index [4]map[int64]*Tree
}

func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool) {
  p, _ := qs.resolveQuad(q, false)
  if id := qs.quads[p]; id != 0 {
    return id, false
  p, _ = qs.resolveQuad(q, true)
  pr := &primitive{Quad: p}
  id := qs.addPrimitive(pr)
  qs.quads[p] = id
  for _, t := range qs.indexesForQuad(p) {
    t.Set(id, pr)
  }

func (qs *QuadStore) resolveQuad(q quad.Quad, add bool) (internalQuad, bool) {
    for dir := quad.Subject; dir <= quad.Label; dir++ {
    v := q.Get(dir)
    if vid, _ := qs.resolveVal(v, add); vid != 0 {
      p.SetDir(dir, vid)
    } else if !add {
      return internalQuad{}, false
    }

func (qs *QuadStore) resolveVal(v quad.Value, add bool) (int64, bool) {
      if n, ok := v.(quad.BNode); ok && strings.HasPrefix(string(n), internalBNodePrefix) {
            if p, ok := qs.prim[id]; ok || !add {
        if add {
          p.refs++
        }
        return id, ok
      qs.appendPrimitive(&primitive{ID: id, refs: 1})

type primitive struct {
  ID    int64
  Quad  internalQuad
  Value quad.Value
  refs  int
}

func (qs *QuadStore) appendPrimitive(p *primitive) {
  qs.prim[p.ID] = p
  if !qs.reading {
    qs.all = append(qs.all, p)

type QuadStore struct {
  last int64
  // TODO: string -> quad.Value once Raw -> typed resolution is unnecessary
  vals    map[string]int64
  quads   map[internalQuad]int64
  prim    map[int64]*primitive
  all     []*primitive // might not be sorted by id
  reading bool         // someone else might be reading "all" slice - next insert/delete should clone it
  index   QuadDirectionIndex
  horizon int64 // used only to assign ids to tx
  // vip_index map[string]map[int64]map[string]map[int64]*b.Tree
}

type QuadDirectionIndex struct {
  index [4]map[int64]*Tree
}

func (qs *QuadStore) indexesForQuad(q internalQuad) []*Tree {
  trees := make([]*Tree, 0, 4)
  for dir := quad.Subject; dir <= quad.Label; dir++ {
    v := q.Dir(dir)
    if v == 0 {
      continue
    }
    trees = append(trees, qs.index.Tree(dir, v))

func (qdi QuadDirectionIndex) Tree(d quad.Direction, id int64) *Tree {
      tree, ok := qdi.index[d-1][id]

// Our quad struct, used throughout.
type Quad struct {
  Subject   Value `json:"subject"`
  Predicate Value `json:"predicate"`
  Object    Value `json:"object"`
  Label     Value `json:"label,omitempty"`
}

// List of the valid directions of a quad.
const (
  Any Direction = iota
  Subject
  Predicate
  Object
  Label
)

// Per-field accessor for quads.
func (q Quad) Get(d Direction) Value {
  switch d {
  case Subject:
    return q.Subject
  case Predicate:
    return q.Predicate
  case Label:
    return q.Label
  case Object:
    return q.Object
  default:
    panic(d.String())
  }
}

type String string

// Tree is a B+tree.
  Tree struct {
    c     int
    cmp   Cmp
    first *d
    last  *d
    r     interface{}
    ver   int64
  }

Cmp func(a, b int64) int

d struct { // data page
    c int
    d [2*kd + 1]de
    n *d
    p *d
  }

func (t *Tree) Set(k int64, v *primitive) {
  z := t.insert(btDPool.Get().(*d), 0, k, v)
    for {
    i, ok := t.find(q, k)
    if ok {
      switch x := q.(type) {
      case *x:
        if x.c > 2*kx {

// Make creates a quad with provided values.
func Make(subject, predicate, object, label interface{}) (q Quad) {
  var ok bool
  if q.Subject, ok = AsValue(subject); !ok {
    q.Subject = String(fmt.Sprint(subject))
  }
  if q.Predicate, ok = AsValue(predicate); !ok {
    q.Predicate = String(fmt.Sprint(predicate))
  }
  if q.Object, ok = AsValue(object); !ok {
    q.Object = String(fmt.Sprint(object))
  }
  if q.Label, ok = AsValue(label); !ok {
    q.Label = String(fmt.Sprint(label))
  }
  return
}

func NativeOf(v Value) interface{} {
  if v == nil {
    return nil
  }
  return v.Native()
}

// AsValue converts native type into closest Value representation.
// It returns false if type was not recognized.
func AsValue(v interface{}) (out Value, ok bool) {
  if v == nil {
    return nil, true
  }
  switch v := v.(type) {
  case Value:
    out = v
  case string:
    out = String(v)
  case int:
    out = Int(v)
  case int8:
    out = Int(v)
  case int16:
    out = Int(v)
  case int32:
    out = Int(v)
  case int64:
    out = Int(v)
  case uint:
    out = Int(v)
  case uint8:
    out = Int(v)
  case uint16:
    out = Int(v)
  case uint32:
    out = Int(v)
  case uint64:
    out = Int(v)
  case float64:
    out = Float(v)
  case float32:
    out = Float(v)
  case bool:
    out = Bool(v)
  case time.Time:
    out = Time(v)
  default:
    return nil, false
  }
  return out, true
}