diff options
Diffstat (limited to 'bitbake/lib/bb/__init__.py')
-rw-r--r-- | bitbake/lib/bb/__init__.py | 179 |
1 files changed, 0 insertions, 179 deletions
diff --git a/bitbake/lib/bb/__init__.py b/bitbake/lib/bb/__init__.py index a126c17693..c452d529c1 100644 --- a/bitbake/lib/bb/__init__.py +++ b/bitbake/lib/bb/__init__.py | |||
@@ -46,7 +46,6 @@ __all__ = [ | |||
46 | "pkgcmp", | 46 | "pkgcmp", |
47 | "dep_parenreduce", | 47 | "dep_parenreduce", |
48 | "dep_opconvert", | 48 | "dep_opconvert", |
49 | "digraph", | ||
50 | 49 | ||
51 | # fetch | 50 | # fetch |
52 | "decodeurl", | 51 | "decodeurl", |
@@ -1128,184 +1127,6 @@ def dep_opconvert(mysplit, myuse): | |||
1128 | mypos += 1 | 1127 | mypos += 1 |
1129 | return newsplit | 1128 | return newsplit |
1130 | 1129 | ||
1131 | class digraph: | ||
1132 | """beautiful directed graph object""" | ||
1133 | |||
1134 | def __init__(self): | ||
1135 | self.dict={} | ||
1136 | #okeys = keys, in order they were added (to optimize firstzero() ordering) | ||
1137 | self.okeys=[] | ||
1138 | self.__callback_cache=[] | ||
1139 | |||
1140 | def __str__(self): | ||
1141 | str = "" | ||
1142 | for key in self.okeys: | ||
1143 | str += "%s:\t%s\n" % (key, self.dict[key][1]) | ||
1144 | return str | ||
1145 | |||
1146 | def addnode(self,mykey,myparent): | ||
1147 | if not mykey in self.dict: | ||
1148 | self.okeys.append(mykey) | ||
1149 | if myparent==None: | ||
1150 | self.dict[mykey]=[0,[]] | ||
1151 | else: | ||
1152 | self.dict[mykey]=[0,[myparent]] | ||
1153 | self.dict[myparent][0]=self.dict[myparent][0]+1 | ||
1154 | return | ||
1155 | if myparent and (not myparent in self.dict[mykey][1]): | ||
1156 | self.dict[mykey][1].append(myparent) | ||
1157 | self.dict[myparent][0]=self.dict[myparent][0]+1 | ||
1158 | |||
1159 | def delnode(self,mykey, ref = 1): | ||
1160 | """Delete a node | ||
1161 | |||
1162 | If ref is 1, remove references to this node from other nodes. | ||
1163 | If ref is 2, remove nodes that reference this node.""" | ||
1164 | if not mykey in self.dict: | ||
1165 | return | ||
1166 | for x in self.dict[mykey][1]: | ||
1167 | self.dict[x][0]=self.dict[x][0]-1 | ||
1168 | del self.dict[mykey] | ||
1169 | while 1: | ||
1170 | try: | ||
1171 | self.okeys.remove(mykey) | ||
1172 | except ValueError: | ||
1173 | break | ||
1174 | if ref: | ||
1175 | __kill = [] | ||
1176 | for k in self.okeys: | ||
1177 | if mykey in self.dict[k][1]: | ||
1178 | if ref == 1 or ref == 2: | ||
1179 | self.dict[k][1].remove(mykey) | ||
1180 | if ref == 2: | ||
1181 | __kill.append(k) | ||
1182 | for l in __kill: | ||
1183 | self.delnode(l, ref) | ||
1184 | |||
1185 | def allnodes(self): | ||
1186 | "returns all nodes in the dictionary" | ||
1187 | keys = self.dict.keys() | ||
1188 | ret = [] | ||
1189 | for key in keys: | ||
1190 | ret.append(key) | ||
1191 | ret.sort() | ||
1192 | return ret | ||
1193 | |||
1194 | def firstzero(self): | ||
1195 | "returns first node with zero references, or NULL if no such node exists" | ||
1196 | for x in self.okeys: | ||
1197 | if self.dict[x][0]==0: | ||
1198 | return x | ||
1199 | return None | ||
1200 | |||
1201 | def firstnonzero(self): | ||
1202 | "returns first node with nonzero references, or NULL if no such node exists" | ||
1203 | for x in self.okeys: | ||
1204 | if self.dict[x][0]!=0: | ||
1205 | return x | ||
1206 | return None | ||
1207 | |||
1208 | |||
1209 | def allzeros(self): | ||
1210 | "returns all nodes with zero references, or NULL if no such node exists" | ||
1211 | zerolist = [] | ||
1212 | for x in self.dict.keys(): | ||
1213 | if self.dict[x][0]==0: | ||
1214 | zerolist.append(x) | ||
1215 | return zerolist | ||
1216 | |||
1217 | def hasallzeros(self): | ||
1218 | "returns 0/1, Are all nodes zeros? 1 : 0" | ||
1219 | zerolist = [] | ||
1220 | for x in self.dict.keys(): | ||
1221 | if self.dict[x][0]!=0: | ||
1222 | return 0 | ||
1223 | return 1 | ||
1224 | |||
1225 | def empty(self): | ||
1226 | if len(self.dict)==0: | ||
1227 | return 1 | ||
1228 | return 0 | ||
1229 | |||
1230 | def hasnode(self,mynode): | ||
1231 | return mynode in self.dict | ||
1232 | |||
1233 | def getparents(self, item): | ||
1234 | if not self.hasnode(item): | ||
1235 | return [] | ||
1236 | parents = self.dict[item][1] | ||
1237 | ret = [] | ||
1238 | for parent in parents: | ||
1239 | ret.append(parent) | ||
1240 | ret.sort() | ||
1241 | return ret | ||
1242 | |||
1243 | def getchildren(self, item): | ||
1244 | if not self.hasnode(item): | ||
1245 | return [] | ||
1246 | children = [i for i in self.okeys if item in self.getparents(i)] | ||
1247 | return children | ||
1248 | |||
1249 | def walkdown(self, item, callback, debug = None, usecache = False): | ||
1250 | if not self.hasnode(item): | ||
1251 | return 0 | ||
1252 | |||
1253 | if usecache: | ||
1254 | if self.__callback_cache.count(item): | ||
1255 | if debug: | ||
1256 | print "hit cache for item: %s" % item | ||
1257 | return 1 | ||
1258 | |||
1259 | parents = self.getparents(item) | ||
1260 | children = self.getchildren(item) | ||
1261 | for p in parents: | ||
1262 | if p in children: | ||
1263 | # print "%s is both parent and child of %s" % (p, item) | ||
1264 | if usecache: | ||
1265 | self.__callback_cache.append(p) | ||
1266 | ret = callback(self, p) | ||
1267 | if ret == 0: | ||
1268 | return 0 | ||
1269 | continue | ||
1270 | if item == p: | ||
1271 | print "eek, i'm my own parent!" | ||
1272 | return 0 | ||
1273 | if debug: | ||
1274 | print "item: %s, p: %s" % (item, p) | ||
1275 | ret = self.walkdown(p, callback, debug, usecache) | ||
1276 | if ret == 0: | ||
1277 | return 0 | ||
1278 | if usecache: | ||
1279 | self.__callback_cache.append(item) | ||
1280 | return callback(self, item) | ||
1281 | |||
1282 | def walkup(self, item, callback): | ||
1283 | if not self.hasnode(item): | ||
1284 | return 0 | ||
1285 | |||
1286 | parents = self.getparents(item) | ||
1287 | children = self.getchildren(item) | ||
1288 | for c in children: | ||
1289 | if c in parents: | ||
1290 | ret = callback(self, item) | ||
1291 | if ret == 0: | ||
1292 | return 0 | ||
1293 | continue | ||
1294 | if item == c: | ||
1295 | print "eek, i'm my own child!" | ||
1296 | return 0 | ||
1297 | ret = self.walkup(c, callback) | ||
1298 | if ret == 0: | ||
1299 | return 0 | ||
1300 | return callback(self, item) | ||
1301 | |||
1302 | def copy(self): | ||
1303 | mygraph=digraph() | ||
1304 | for x in self.dict.keys(): | ||
1305 | mygraph.dict[x]=self.dict[x][:] | ||
1306 | mygraph.okeys=self.okeys[:] | ||
1307 | return mygraph | ||
1308 | |||
1309 | if __name__ == "__main__": | 1130 | if __name__ == "__main__": |
1310 | import doctest, bb | 1131 | import doctest, bb |
1311 | doctest.testmod(bb) | 1132 | doctest.testmod(bb) |