[mynewt-newt] 01/02: resolve: Maintain reverse dependency list per-pkg

[cc...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

ccollins pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mynewt-newt.git

commit a1d3d2722a36e76779a929fb9c3074dfd9ea26f1
Author: Christopher Collins <cc...@apache.org>
AuthorDate: Wed Nov 7 09:46:18 2018 -0800

    resolve: Maintain reverse dependency list per-pkg
    
    Replace `ResolvePackage`'s reference count with a reverse dependency
    list (implemented as map).  This is less error prone, and it allows for
    package removal to be more efficient.
---
 newt/resolve/resolve.go | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/newt/resolve/resolve.go b/newt/resolve/resolve.go
index a85c97e..02d69f9 100644
--- a/newt/resolve/resolve.go
+++ b/newt/resolve/resolve.go
@@ -89,9 +89,9 @@ type ResolvePackage struct {
 
 	depsResolved bool
 
-	// Tracks this package's number of dependents.  If this number reaches 0,
-	// this package can be deleted from the resolver.
-	refCount int
+	// Tracks this package's dependents (things that depend on us).  If this
+	// map becomes empty, this package can be deleted from the resolver.
+	revDeps map[*ResolvePackage]struct{}
 }
 
 type ResolveSet struct {
@@ -169,6 +169,7 @@ func NewResolvePkg(lpkg *pkg.LocalPackage) *ResolvePackage {
 		Lpkg:      lpkg,
 		reqApiMap: map[string]resolveReqApi{},
 		Deps:      map[*ResolvePackage]*ResolveDep{},
+		revDeps:   map[*ResolvePackage]struct{}{},
 	}
 }
 
@@ -187,17 +188,17 @@ func (r *Resolver) resolveDep(dep *pkg.Dependency, depender string) (*pkg.LocalP
 // @return                      true if the package's dependency list was
 //                                  modified.
 func (rpkg *ResolvePackage) AddDep(
-	apiPkg *ResolvePackage, api string, expr string) bool {
+	depPkg *ResolvePackage, api string, expr string) bool {
 
-	if dep := rpkg.Deps[apiPkg]; dep != nil {
+	if dep := rpkg.Deps[depPkg]; dep != nil {
 		if dep.Api != "" && api == "" {
 			dep.Api = api
 		} else {
 			return false
 		}
 	} else {
-		rpkg.Deps[apiPkg] = &ResolveDep{
-			Rpkg: apiPkg,
+		rpkg.Deps[depPkg] = &ResolveDep{
+			Rpkg: depPkg,
 			Api:  api,
 			Expr: expr,
 		}
@@ -212,7 +213,8 @@ func (rpkg *ResolvePackage) AddDep(
 		rpkg.reqApiMap[api] = apiReq
 	}
 
-	apiPkg.refCount++
+	depPkg.revDeps[rpkg] = struct{}{}
+
 	return true
 }
 
@@ -339,16 +341,16 @@ func (r *Resolver) deletePkg(rpkg *ResolvePackage) error {
 	r.cfg.DeletePkg(rpkg.Lpkg)
 
 	// If the deleted package is the only depender for any other packages
-	// (i.e., if any of its dependencies have a reference count of one), delete
-	// them as well.
+	// (i.e., if any of its dependencies have only one reverse dependency),
+	// delete them as well.
 	for rdep, _ := range rpkg.Deps {
-		if rdep.refCount <= 0 {
+		if len(rdep.revDeps) == 0 {
 			return util.FmtNewtError(
-				"package %s unexpectedly has refcount <= 0",
+				"package %s unexpectedly has 0 reverse dependencies",
 				rdep.Lpkg.FullName())
 		}
-		rdep.refCount--
-		if rdep.refCount == 0 {
+		delete(rdep.revDeps, rpkg)
+		if len(rdep.revDeps) == 0 {
 			if err := r.deletePkg(rdep); err != nil {
 				return nil
 			}
@@ -406,12 +408,12 @@ func (r *Resolver) loadDepsForPkg(rpkg *ResolvePackage) (bool, error) {
 	for rdep, _ := range rpkg.Deps {
 		if _, ok := seen[rdep]; !ok {
 			delete(rpkg.Deps, rdep)
-			rdep.refCount--
+			delete(rdep.revDeps, rpkg)
 			changed = true
 
 			// If we just deleted the last reference to a package, remove the
 			// package entirely from the resolver and syscfg.
-			if rdep.refCount == 0 {
+			if len(rdep.revDeps) == 0 {
 				if err := r.deletePkg(rdep); err != nil {
 					return true, err
 				}