mtglist
changeset 0:0a45dfe93e66
initial commit
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sun, 02 Nov 2014 11:07:45 +0200 |
| parents | |
| children | 7211fa8db425 |
| files | .hgignore Makefile cardlist editions.cfg src/mtg.c src/mtg.h src/mtglist.c src/rbtree.c src/rbtree.h |
| diffstat | 9 files changed, 1452 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/.hgignore Sun Nov 02 11:07:45 2014 +0200 1.3 @@ -0,0 +1,4 @@ 1.4 +\.o$ 1.5 +\.swp$ 1.6 +\.d$ 1.7 +^mtglist$
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/Makefile Sun Nov 02 11:07:45 2014 +0200 2.3 @@ -0,0 +1,12 @@ 2.4 +src = $(wildcard src/*.c) 2.5 +obj = $(src:.c=.o) 2.6 +bin = mtglist 2.7 + 2.8 +CFLAGS = -pedantic -Wall -g 2.9 + 2.10 +$(bin): $(obj) 2.11 + $(CC) -o $@ $(obj) $(LDFLAGS) 2.12 + 2.13 +.PHONE: clean 2.14 +clean: 2.15 + rm -f $(obj) $(bin)
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/cardlist Sun Nov 02 11:07:45 2014 +0200 3.3 @@ -0,0 +1,374 @@ 3.4 +-|Crystal Vein|Land|2|6ed| 3.5 +-|Geothermal Crevice|Land|1|inv| 3.6 +-|High Market|Land|1|mmq|foil 3.7 +-|Mystic Monastery|Land|1|ktk| 3.8 +-|Sulfur Vent|Land|1|inv| 3.9 +*|Armadillo Cloak|Enchantment|2|inv|Green/White 3.10 +*|Aura Mutation|Instant|1|inv|Green/White 3.11 +*|Battlefield Forge|Land|1|apc|Red/White 3.12 +*|Captain's Maneuver|Instant|1|apc|Red/White 3.13 +*|Chief of the Scale|Creature|1|ktk|White/Black 3.14 +*|Cinder Shade|Creature|1|inv|Black/Red 3.15 +*|Gaea's Skyfolk|Creature|1|apc|Green/Blue 3.16 +*|Galina's Knight|Creature|1|inv|White/Blue 3.17 +*|Hanna, Ship's Navigator|Creature|1|inv|White/Blue 3.18 +*|Heroes' Reunion|Instant|1|inv|Green/White 3.19 +*|Jungle Barrier|Creature|1|apc|Green/Blue 3.20 +*|Jungle Hollow|Land|1|ktk|Black/Green 3.21 +*|Llanowar Dead|Creature|1|apc|Black/Green 3.22 +*|Ordered Migration|Sorcery|1|inv|White/Blue 3.23 +*|Putrid Warrior|Creature|1|apc|White/Black 3.24 +*|Shivan Zombie|Creature|1|inv|Black/Red 3.25 +*|Sorin, Solemn Visitor|Planeswalker|1|ktk|White/Black 3.26 +*|Tainted Field|Land|1|tor|White/Black 3.27 +*|Temporal Spring|Sorcery|1|apc|Green/Blue 3.28 +*|Yavimaya Kavu|Creature|1|inv|Red/Green 3.29 +Artifact|Amulet of Kroog|Artifact|1|5ed| 3.30 +Artifact|Ashnod's Transmogrant|Artifact|1|5ed| 3.31 +Artifact|Coiled Tinviper|Creature|1|tmp| 3.32 +Artifact|Crooked Scales|Artifact|1|mmq| 3.33 +Artifact|Dancing Scimitar|Creature|1|9ed| 3.34 +Artifact|Dodecapod|Creature|1|apc| 3.35 +Artifact|Glasses of Urza|Artifact|1|5ed| 3.36 +Artifact|Iron Lance|Artifact|1|mmq| 3.37 +Artifact|Iron Star|Artifact|1|5ed| 3.38 +Artifact|Ivory Cup|Artifact|1|6ed| 3.39 +Artifact|Juggernaut|Artifact|1|m15| 3.40 +Artifact|Patagia Golem|Creature|1|6ed| 3.41 +Artifact|Rod of Ruin|Artifact|1|9ed| 3.42 +Artifact|Rusting Golem|Creature|1|nms| 3.43 +Artifact|Skull Catapult|Artifact|1|5ed| 3.44 +Artifact|Throne of Bone|Artifact|1|5ed| 3.45 +Artifact|Tigereye Cameo|Artifact|1|apc| 3.46 +Artifact|Tyrant's Machine|Artifact|1|m15|foil 3.47 +Artifact|Urza's Blueprints|Artifact|1|ulg| 3.48 +Artifact|Wall of Spears|Creature|1|5ed| 3.49 +Black|Agonizing Demise|Instant|1|inv| 3.50 +Black|Black Cat|Creature|1|m15| 3.51 +Black|Blight|Enchantment|1|6ed| 3.52 +Black|Blood Pet|Creature|1|6ed| 3.53 +Black|Bog Wraith|Creature|1|5ed| 3.54 +Black|Bog Wraith|Creature|1|6ed| 3.55 +Black|Cabal Ritual|Instant|1|tor| 3.56 +Black|Cackling Witch|Creature|1|mmq| 3.57 +Black|Carrion Crow|Creature|1|m15| 3.58 +Black|Cateran Persuader|Creature|1|mmq| 3.59 +Black|Coercion|Sorcery|1|5ed| 3.60 +Black|Covenant of Blood|Sorcery|1|m15| 3.61 +Black|Crypt Sliver|Creature|1|lgn| 3.62 +Black|Cursed Land|Enchantment|1|5ed| 3.63 +Black|Dark Banishing|Instant|1|tmp| 3.64 +Black|Dark Ritual|Instant|1|5ed| 3.65 +Black|Dark Triumph|Instant|1|nms| 3.66 +Black|Dauthi Horror|Creature|1|tmp| 3.67 +Black|Dead Ringers|Sorcery|1|apc| 3.68 +Black|Despondency|Enchantment|1|usg| 3.69 +Black|Drain Life|Sorcery|1|5ed| 3.70 +Black|Fallen Angel|Creature|1|5ed| 3.71 +Black|Firescreamer|Creature|1|inv| 3.72 +Black|Frozen Shade|Creature|1|5ed| 3.73 +Black|Grave Defiler|Creature|1|apc| 3.74 +Black|Gravebane Zombie|Creature|2|6ed| 3.75 +Black|Gravedigger|Creature|1|6ed| 3.76 +Black|Haunted Crossroads|Enchantment|1|mmq| 3.77 +Black|Krovikan Fetish|Enchantment|1|5ed| 3.78 +Black|Lost Soul|Creature|1|5ed| 3.79 +Black|Maggot Therapy|Enchantment|1|mmq| 3.80 +Black|Mind Extraction|Sorcery|1|apc| 3.81 +Black|Mind Swords|Sorcery|1|nms| 3.82 +Black|Necra Disciple|Creature|1|apc| 3.83 +Black|Nightscape Apprentice|Creature|1|inv| 3.84 +Black|Phyrexian Slayer|Creature|1|inv| 3.85 +Black|Putrid Imp|Creature|1|tor| 3.86 +Black|Python|Creature|2|6ed| 3.87 +Black|Quagmire Druid|Creature|1|apc| 3.88 +Black|Razortooth Rats|Creature|1|6ed| 3.89 +Black|Reckless Spite|Instant|2|inv| 3.90 +Black|Rouse|Instant|1|mmq| 3.91 +Black|Scathe Zombies|Creature|1|6ed| 3.92 +Black|Sever Soul|Sorcery|1|mmq| 3.93 +Black|Shambling Attendants|Creature|1|ktk| 3.94 +Black|Skulking Fugitive|Creature|1|mmq|foil 3.95 +Black|Snuff Out|Instant|1|mmq| 3.96 +Black|Swamp|Land|18|*|9x5ed,1x6ed,6xinv,2xm15 3.97 +Black|Syphon Soul|Sorcery|2|6ed| 3.98 +Black|Terror|Instant|1|5ed| 3.99 +Black|Undertaker|Creature|1|mmq| 3.100 +Black|Unmake the Graves|Instant|1|m15| 3.101 +Black|Vampiric Tutor|Instant|1|6ed| 3.102 +Black|Vicious Hunger|Sorcery|1|nms| 3.103 +Black|Vile Deacon|Creature|1|lgn| 3.104 +Black|Waste Away|Instant|1|tor| 3.105 +Black|Weakness|Enchantment|1|5ed| 3.106 +Black|Zombie Master|Creature|1|6ed| 3.107 +Blue|Barrin's Unmaking|Instant|1|inv| 3.108 +Blue|Boomerang|Instant|1|5ed| 3.109 +Blue|Boomerang|Instant|1|6ed| 3.110 +Blue|Brainstorm|Instant|1|5ed| 3.111 +Blue|Brainstorm|Instant|1|mmq| 3.112 +Blue|Buoyancy|Enchantment|1|mmq| 3.113 +Blue|Cephalid Aristocrat|Creature|1|tor| 3.114 +Blue|Cephalid Sage|Creature|1|tor| 3.115 +Blue|Cephalid Snitch|Creature|1|tor| 3.116 +Blue|Cloud Sprite|Creature|2|mmq| 3.117 +Blue|Coastal Drake|Creature|1|apc| 3.118 +Blue|Coral Eel|Creature|2|9ed| 3.119 +Blue|Counterspell|Instant|1|5ed| 3.120 +Blue|Dark Maze|Creature|1|5ed| 3.121 +Blue|Daze|Instant|1|nms| 3.122 +Blue|Deep Analysis|Sorcery|1|tor| 3.123 +Blue|Diffusion Sliver|Creature|1|m15| 3.124 +Blue|Diplomatic Escort|Creature|2|mmq| 3.125 +Blue|Diplomatic Immunity|Enchantment|1|mmq| 3.126 +Blue|Dream Thrush|Creature|1|inv| 3.127 +Blue|Faerie Squadron|Creature|1|inv| 3.128 +Blue|Flight|Enchantment|1|5ed| 3.129 +Blue|Fugitive Wizard|Creature|1|9ed| 3.130 +Blue|Gaseous Form|Enchantment|1|5ed| 3.131 +Blue|Giant Crab|Creature|1|tmp| 3.132 +Blue|Giant Octopus|Creature|3|9ed| 3.133 +Blue|Glacial Crasher|Creature|1|m15| 3.134 +Blue|Harmattan Efreet|Creature|1|6ed| 3.135 +Blue|Horned Turtle|Creature|1|6ed| 3.136 +Blue|Index|Sorcery|1|9ed| 3.137 +Blue|Inspiration|Instant|2|6ed| 3.138 +Blue|Invisibility|Enchantment|1|m15| 3.139 +Blue|Island|Land|22|*|8x5ed,6xinv,8x9ed 3.140 +Blue|Jeskai Windscout|Creature|1|ktk| 3.141 +Blue|Jilt|Instant|1|apc| 3.142 +Blue|Juxtapose|Sorcery|1|5ed| 3.143 +Blue|Living Airship|Creature|1|apc| 3.144 +Blue|Manipulate Fate|Sorcery|2|inv| 3.145 +Blue|Memory Lapse|Instant|1|5ed| 3.146 +Blue|Mind Bomb|Sorcery|1|5ed| 3.147 +Blue|Mistform Sliver|Creature|1|lgn| 3.148 +Blue|Oraxid|Creature|1|nms| 3.149 +Blue|Phantasmal Terrain|Enchantment|1|5ed| 3.150 +Blue|Phantasmal Terrain|Enchantment|1|inv| 3.151 +Blue|Port Inspector|Creature|2|mmq| 3.152 +Blue|Power Sink|Instant|1|5ed| 3.153 +Blue|Prodigal Sorcerer|Creature|1|5ed| 3.154 +Blue|Prohibit|Instant|2|inv| 3.155 +Blue|Psychic Venom|Enchantment|1|5ed| 3.156 +Blue|Psychic Venom|Enchantment|2|6ed| 3.157 +Blue|Sapphire Leech|Creature|1|inv| 3.158 +Blue|Saprazzan Outrigger|Creature|1|mmq| 3.159 +Blue|Sea Monster|Creature|1|tmp| 3.160 +Blue|Segovian Leviathan|Creature|1|5ed| 3.161 +Blue|Segovian Leviathan|Creature|1|6ed| 3.162 +Blue|Shadow Rift|Instant|1|tor| 3.163 +Blue|Sneaky Homunculus|Creature|1|nms| 3.164 +Blue|Spell Blast|Instant|1|tmp| 3.165 +Blue|Storm Crow|Creature|1|6ed| 3.166 +Blue|Stringing Licid|Creature|1|tmp| 3.167 +Blue|Synapse Sliver|Creature|1|lgn| 3.168 +Blue|Talas Air Ship|Creature|1|po2| 3.169 +Blue|Telepathy|Enchantment|1|9ed| 3.170 +Blue|Tower Drake|Creature|1|inv| 3.171 +Blue|Updraft|Instant|1|5ed| 3.172 +Blue|Vizzerdrix|Creature|2|9ed| 3.173 +Blue|Vodalian Merchant|Creature|1|inv| 3.174 +Blue|Vodalian Serpent|Creature|1|inv| 3.175 +Blue|Voidmage Apprentice|Creature|1|lgn| 3.176 +Blue|Warped Researcher|Creature|1|lgn| 3.177 +Blue|Welkin Tern|Creature|1|m15| 3.178 +Blue|Whirlpool Warrior|Creature|1|apc| 3.179 +Blue|Wind Drake|Creature|1|9ed| 3.180 +Blue|Worldly Counsel|Instant|1|inv| 3.181 +Green|Aggressive Urge|Instant|1|inv| 3.182 +Green|Aurochs|Creature|1|5ed| 3.183 +Green|Berserk Murlodont|Creature|1|lgn| 3.184 +Green|Birds of Paradise|Creature|1|6ed| 3.185 +Green|Blanchwood Armor|Enchantment|1|9ed| 3.186 +Green|Cat Warriors|Creature|1|6ed| 3.187 +Green|Cockatrice|Creature|1|5ed| 3.188 +Green|Craw Wurm|Creature|1|9ed| 3.189 +Green|Eladamri, Lord of Leaves|Creature|1|tmp| 3.190 +Green|Elven Cache|Sorcery|1|6ed| 3.191 +Green|Enormous Baloth|Creature|2|9ed| 3.192 +Green|Femeref Archers|Creature|1|6ed| 3.193 +Green|Ferocity|Enchantment|1|mmq| 3.194 +Green|Forest|Land|29|*|9x5ed,6x6ed,6xinv,8x9ed 3.195 +Green|Gaea's Balance|Sorcery|1|apc| 3.196 +Green|Gather Courage|Instant|1|m15| 3.197 +Green|Giant Growth|Instant|2|6ed| 3.198 +Green|Glade Gnarr|Creature|2|apc| 3.199 +Green|Gorilla Chieftain|Creature|1|6ed| 3.200 +Green|Grizzly Bears|Creature|1|5ed| 3.201 +Green|Grizzly Bears|Creature|2|9ed| 3.202 +Green|Gurzigost|Creature|1|tor| 3.203 +Green|Hickory Woodlot|Land|1|mmq| 3.204 +Green|Horned Sliver|Creature|1|tmp| 3.205 +Green|Hungry Mist|Creature|1|5ed| 3.206 +Green|Kavu Climber|Creature|1|inv| 3.207 +Green|Krosan Constrictor|Creature|1|tor| 3.208 +Green|Living Totem|Creature|1|m15| 3.209 +Green|Llanowar Elite|Creature|1|inv| 3.210 +Green|Llanowar Vanguard|Creature|1|inv| 3.211 +Green|Longshot Squad|Creature|1|ktk| 3.212 +Green|Meandering Towershell|Creature|1|ktk|foil 3.213 +Green|Naturalize|Instant|1|9ed| 3.214 +Green|Norwood Ranger|Creature|2|9ed| 3.215 +Green|Penumbra Bobcat|Creature|1|apc| 3.216 +Green|Pincer Spider|Creature|1|inv| 3.217 +Green|Pulse of Llanowar|Enchantment|1|inv| 3.218 +Green|Quick Sliver|Creature|1|lgn| 3.219 +Green|Rampant Growth|Sorcery|1|9ed| 3.220 +Green|Reclamation Sage|Creature|1|m15| 3.221 +Green|Regeneration|Enchantment|1|5ed| 3.222 +Green|Regeneration|Enchantment|2|6ed| 3.223 +Green|Rootbreaker Wurm|Creature|1|tmp| 3.224 +Green|Runeclaw Bear|Creature|1|m15| 3.225 +Green|Rushwood Dryad|Creature|1|mmq| 3.226 +Green|Rushwood Grove|Land|1|mmq| 3.227 +Green|Rushwood Herbalist|Creature|2|mmq| 3.228 +Green|Saproling Burst|Enchantment|1|nms| 3.229 +Green|Satyr Wayfinder|Creature|1|m15| 3.230 +Green|Savage Punch|Sorcery|1|ktk| 3.231 +Green|Scaled Wurm|Creature|2|5ed| 3.232 +Green|Scryb Sprites|Creature|1|5ed| 3.233 +Green|Shrink|Instant|1|5ed| 3.234 +Green|Skyshroud Ridgeback|Creature|1|nms| 3.235 +Green|Skyshroud Sentinel|Creature|1|nms| 3.236 +Green|Snorting Gahr|Creature|1|mmq| 3.237 +Green|Spined Wurm|Creature|1|9ed| 3.238 +Green|Spontaneous Generation|Sorcery|1|mmq| 3.239 +Green|Stream of Life|Sorcery|1|6ed| 3.240 +Green|Sylvan Library|Enchantment|1|5ed| 3.241 +Green|Thicket Basilisk|Creature|1|6ed| 3.242 +Green|Tiger Claws|Enchantment|1|mmq| 3.243 +Green|Tranquil Path|Sorcery|1|apc| 3.244 +Green|Treefolk Healer|Creature|1|inv| 3.245 +Green|Untamed Wilds|Sorcery|1|6ed| 3.246 +Green|Verdant Haven|Enchantment|1|m15| 3.247 +Green|Vigorous Charge|Instant|1|inv| 3.248 +Green|Wandering Stream|Sorcery|1|inv| 3.249 +Green|Wanderlust|Enchantment|1|5ed| 3.250 +Green|Wild Growth|Enchantment|1|5ed| 3.251 +Green|Winter Blast|Sorcery|1|5ed| 3.252 +Green|Woodripper|Creature|1|nms| 3.253 +Green|Yavimaya Wurm|Creature|1|ulg| 3.254 +Green/Black|Life/Death|Sorcery|1|apc| 3.255 +Red|Act on Impulse|Sorcery|1|m15| 3.256 +Red|Aether Flash|Enchantment|1|6ed| 3.257 +Red|Anaba Shaman|Creature|1|6ed| 3.258 +Red|Anaba Shaman|Creature|1|9ed| 3.259 +Red|Battle Rampart|Creature|1|mmq| 3.260 +Red|Blood Frenzy|Instant|1|tmp| 3.261 +Red|Bloodfire Dwarf|Creature|2|apc| 3.262 +Red|Bloodstoke Howler|Creature|1|lgn| 3.263 +Red|Bring Low|Instant|1|ktk| 3.264 +Red|Burning Anger|Enchantment|1|m15| 3.265 +Red|Cave Sense|Enchantment|1|mmq| 3.266 +Red|Collapsing Borders|Enchantment|1|inv| 3.267 +Red|Crackling Club|Enchantment|1|tor| 3.268 +Red|Detonate|Sorcery|1|5ed| 3.269 +Red|Dwarven Landslide|Sorcery|1|apc| 3.270 +Red|Dwarven Soldier|Creature|1|5ed| 3.271 +Red|Dwarven Warriors|Creature|1|5ed| 3.272 +Red|Enslaved Dwarf|Creature|1|tor| 3.273 +Red|Firebrand Ranger|Creature|1|inv| 3.274 +Red|Flame Spirit|Creature|2|6ed| 3.275 +Red|Flamewave Invoker|Creature|1|lgn| 3.276 +Red|Flaming Sword|Enchantment|1|mmq| 3.277 +Red|Generator Servant|Creature|1|m15| 3.278 +Red|Goblin Dynamo|Creature|1|lgn| 3.279 +Red|Goblin Elite Infantry|Creature|1|6ed| 3.280 +Red|Goblin Hero|Creature|1|6ed| 3.281 +Red|Goblin Raider|Creature|2|9ed| 3.282 +Red|Goblin Roughrider|Creature|1|m15| 3.283 +Red|Goblin War Drums|Enchantment|1|5ed| 3.284 +Red|Goblin Warrens|Enchantment|1|6ed| 3.285 +Red|Heart Sliver|Creature|1|tmp| 3.286 +Red|Hill Giant|Creature|2|9ed| 3.287 +Red|Hill Giant|Creature|1|5ed| 3.288 +Red|Hooded Kavu|Creature|1|inv| 3.289 +Red|Hulking Cyclops|Creature|1|6ed| 3.290 +Red|Ironclaw Orcs|Creature|1|5ed| 3.291 +Red|Kavu Scout|Creature|1|inv| 3.292 +Red|Laccolith Grunt|Creature|1|nms| 3.293 +Red|Laccolith Rig|Enchantment|1|nms| 3.294 +Red|Lava Axe|Sorcery|2|9ed| 3.295 +Red|Lightning Blast|Instant|1|6ed| 3.296 +Red|Maniacal Rage|Enchantment|2|inv| 3.297 +Red|Mountain|Land|27|*|10x5ed,1x6ed,6xinv,9x9ed,1xktk 3.298 +Red|Ogre Taskmaster|Creature|1|9ed| 3.299 +Red|Orcish Oriflamme|Enchantment|1|5ed| 3.300 +Red|Orgg|Creature|1|5ed| 3.301 +Red|Petravark|Creature|1|tor| 3.302 +Red|Pyrotechnics|Sorcery|2|6ed| 3.303 +Red|Sandstone Needle|Land|1|mmq| 3.304 +Red|Scarred Puma|Creature|1|inv| 3.305 +Red|Scorching Lava|Instant|2|inv| 3.306 +Red|Shadowstorm|Sorcery|1|tmp| 3.307 +Red|Shatter|Instant|1|6ed| 3.308 +Red|Shatter|Instant|1|ktk| 3.309 +Red|Skirk Marauder|Creature|1|lgn| 3.310 +Red|Slimy Kavu|Creature|1|inv| 3.311 +Red|Spitting Earth|Sorcery|1|6ed| 3.312 +Red|Stone Rain|Sorcery|1|9ed| 3.313 +Red|Tahngarth's Glare|Sorcery|1|apc| 3.314 +Red|Thundering Giant|Creature|1|m15| 3.315 +Red|Viashino Warrior|Creature|1|6ed| 3.316 +Red|Volcanic Hammer|Sorcery|2|9ed| 3.317 +Red|Wall of Fire|Creature|1|m15| 3.318 +Red|Zap|Instant|1|apc| 3.319 +White|Abzan Falconer|Creature|1|ktk| 3.320 +White|Armageddon|Sorcery|1|5ed| 3.321 +White|Armored Pegasus|Creature|1|6ed| 3.322 +White|Avacyn, Guardian Angel|Creature|1|m15| 3.323 +White|Blessed Wine|Instant|1|5ed| 3.324 +White|Charm Peddler|Creature|2|mmq| 3.325 +White|Circle of Protection: Artifacts|Enchantment|1|5ed| 3.326 +White|Circle of Protection: Black|Enchantment|1|5ed| 3.327 +White|Circle of Protection: Blue|Enchantment|1|6ed| 3.328 +White|Circle of Protection: Green|Enchantment|1|6ed| 3.329 +White|Circle of Protection: White|Enchantment|1|5ed| 3.330 +White|Congregate|Instant|1|m15| 3.331 +White|D'Avenant Archer|Creature|2|6ed| 3.332 +White|Daru Mender|Creature|1|lgn| 3.333 +White|Daru Sanctifier|Creature|1|lgn| 3.334 +White|Daru Stinger|Creature|1|lgn| 3.335 +White|Death Ward|Instant|1|5ed| 3.336 +White|Devout Witness|Creature|1|mmq| 3.337 +White|Disenchant|Instant|1|5ed| 3.338 +White|Dismantling Blow|Instant|1|inv| 3.339 +White|Eager Cadet|Creature|1|9ed| 3.340 +White|Erase|Instant|1|ktk| 3.341 +White|Fanatical Devotion|Enchantment|1|nms| 3.342 +White|Glimmering Angel|Creature|1|inv| 3.343 +White|Glory Seeker|Creature|4|9ed| 3.344 +White|Holy Day|Instant|1|9ed| 3.345 +White|Honor Guard|Creature|1|9ed| 3.346 +White|Icatian Town|Sorcery|1|5ed| 3.347 +White|Infantry Veteran|Creature|1|6ed| 3.348 +White|Last Breath|Instant|1|mmq| 3.349 +White|Liberate|Instant|1|inv| 3.350 +White|Light of Day|Enchantment|1|6ed| 3.351 +White|Manacles of Decay|Enchantment|1|apc| 3.352 +White|Meditation Puzzle|Instant|1|m15| 3.353 +White|Moment of Silence|Instant|1|mmq| 3.354 +White|Mystic Familiar|Creature|1|tor| 3.355 +White|Nightwind Glider|Creature|1|mmq| 3.356 +White|Off Balance|Instant|1|nms| 3.357 +White|Oppressive Rays|Enchantment|1|m15| 3.358 +White|Order of the White Shield|Creature|1|5ed| 3.359 +White|Orim's Touch|Instant|1|inv| 3.360 +White|Pearled Unicorn|Creature|1|5ed| 3.361 +White|Pikemen|Creature|1|5ed| 3.362 +White|Plains|Land|23|*|8x5ed,6xinv,9x9ed 3.363 +White|Prison Barricade|Creature|1|inv| 3.364 +White|Sacred Nectar|Sorcery|2|9ed| 3.365 +White|Samite Healer|Creature|1|5ed| 3.366 +White|Samite Healer|Creature|1|6ed| 3.367 +White|Serra Angel|Creature|1|9ed|foil 3.368 +White|Shield of Duty and Reason|Enchantment|2|apc| 3.369 +White|Siegecraft|Enchantment|1|ktk| 3.370 +White|Strenght of Isolation|Enchantment|1|tor| 3.371 +White|Strength of Unity|Enchantment|1|inv| 3.372 +White|Thermal Glider|Creature|1|mmq| 3.373 +White|Tireless Missionaries|Creature|1|m15| 3.374 +White|Trap Runner|Creature|2|mmq| 3.375 +White|Triplicate Spirits|Sorcery|1|m15| 3.376 +White|Tundra Wolves|Creature|2|5ed| 3.377 +White|Vengeance|Sorcery|2|9ed|
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 4.2 +++ b/editions.cfg Sun Nov 02 11:07:45 2014 +0200 4.3 @@ -0,0 +1,101 @@ 4.4 +LEA|Limited Edition Alpha 4.5 +LEB|Limited Edition Beta 4.6 +2ED|Unlimited 4.7 +ARN|Arabian Nights 4.8 +ATQ|Antiquities 4.9 +3ED|Revised 4.10 +LEG|Legends 4.11 +DRK|The Dark 4.12 +FEM|Fallen Empires 4.13 +4ED|4th Edition 4.14 +ICE|Ice Age 4.15 +CHR|Chronicles 4.16 +HML|Homelands 4.17 +ALL|Alliances 4.18 +MIR|Mirage 4.19 +VIS|Visions 4.20 +5ED|5th Edition 4.21 +POR|Portal 4.22 +WTH|Weatherlight 4.23 +TMP|Tempest 4.24 +STH|Stronghold 4.25 +PO2|Portal The Second Age 4.26 +EXO|Exodus 4.27 +USG|Urza's Saga 4.28 +ULG|Urza's Legacy 4.29 +6ED|6th Edition 4.30 +UDS|Urza's Destiny 4.31 +S99|Starter 1999 4.32 +MMQ|Mercadian Masques 4.33 +NMS|Nemesis 4.34 +PCY|Prophecy 4.35 +INV|Invasion 4.36 +BTD|Beatdown 4.37 +PLS|Planeshift 4.38 +7ED|7th Edition 4.39 +APC|Apocalypse 4.40 +ODY|Odyssey 4.41 +DKM|Deckmasters 2001 4.42 +TOR|Torment 4.43 +JUD|Judgment 4.44 +ONS|Onslaught 4.45 +LGN|Legions 4.46 +SCG|Scourge 4.47 +8ED|8th Edition 4.48 +MRD|Mirrodin 4.49 +DST|Darksteel 4.50 +5DN|Fifth Dawn 4.51 +CHK|Champions of Kamigawa 4.52 +BOK|Betrayers of Kamigawa 4.53 +SOK|Saviors of Kamigawa 4.54 +9ED|9th Edition 4.55 +RAV|Ravnica: City of Guilds 4.56 +GPT|Guildpact 4.57 +DIS|Dissension 4.58 +CLD|Coldsnap 4.59 +TSP|Time Spiral 4.60 +PLC|Planar Chaos 4.61 +FST|Future Sight 4.62 +10E|10th Edition 4.63 +LRW|Lorwyn 4.64 +MOR|Morningtide 4.65 +SHM|Shadowmoor 4.66 +EVE|Eventide 4.67 +ALA|Shards of Alara 4.68 +CON|Conflux 4.69 +DDC|Duel Decks: Divine vs. Demonic 4.70 +ARB|Alara Reborn 4.71 +M10|Magic 2010 4.72 +ZEN|Zendikar 4.73 +H09|Premium Deck Series: Slivers 4.74 +WWK|Worldwake 4.75 +DDE|Duel Decks: Phyrexia vs. the Coalition 4.76 +ROE|Rise of the Eldrazi 4.77 +M11|Magic 2011 4.78 +DDF|Duel Decks: Elspeth vs. Tezzeret 4.79 +SOM|Scars of Mirrodin 4.80 +MBS|Mirrodin Besieged 4.81 +DDG|Duel Decks: Knights vs. Dragons 4.82 +NPH|New Phyrexia 4.83 +CMD|Commander 4.84 +M12|Magic 2012 4.85 +DDH|Duel Decks: Ajani vs. Nicol Bolas 4.86 +ISD|Innistrad 4.87 +DKA|Dark Ascension 4.88 +DDI|Duel Decks: Venser vs. Koth 4.89 +AVR|Avacyn Restored 4.90 +M13|Magic 2013 4.91 +DDJ|Duel Decks: Izzet Vs. Golgari 4.92 +RTR|Return to Ravnica 4.93 +GTC|Gatecrash 4.94 +DDK|Duel Decks: Sorin vs. Tibalt 4.95 +DGM|Dragon's Maze 4.96 +MMA|Modern Masters 4.97 +M14|Magic 2014 4.98 +THS|Theros 4.99 +C13|Commander 2013 4.100 +BNG|Born of the Gods 4.101 +JOU|Journey into Nyx 4.102 +CNS|Conspiracy 4.103 +M15|Magic 2015 4.104 +KTK|Khans of Tarkir
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/src/mtg.c Sun Nov 02 11:07:45 2014 +0200 5.3 @@ -0,0 +1,290 @@ 5.4 +#include <stdio.h> 5.5 +#include <stdlib.h> 5.6 +#include <string.h> 5.7 +#include <ctype.h> 5.8 +#include <errno.h> 5.9 +#include "rbtree.h" 5.10 +#include "mtg.h" 5.11 + 5.12 +#define ED_FNAME "editions.cfg" 5.13 + 5.14 +static int load_editions(void); 5.15 +static unsigned int parse_color(const char *colstr, const char *notes); 5.16 +static int strcmp_lower(const char *a, const char *b); 5.17 +static void rbdel(struct rbnode *node, void *cls); 5.18 + 5.19 +static struct { 5.20 + enum mtg_card_type type; 5.21 + const char *name; 5.22 +} type_names[] = { 5.23 + {MTG_TYPE_LAND, "Land"}, 5.24 + {MTG_TYPE_CREATURE, "Creature"}, 5.25 + {MTG_TYPE_SORCERY, "Sorcery"}, 5.26 + {MTG_TYPE_INSTANT, "Instant"}, 5.27 + {MTG_TYPE_ENCHANTMENT, "Enchantment"}, 5.28 + {MTG_TYPE_ARTIFACT, "Artifact"}, 5.29 + {MTG_TYPE_PLANESWALKER, "Planeswalker"}, 5.30 + {MTG_TYPE_UNKNOWN, 0} 5.31 +}; 5.32 + 5.33 +static struct rbtree *cards; 5.34 +static struct rbtree *editions; 5.35 + 5.36 + 5.37 +int mtg_init(void) 5.38 +{ 5.39 + if(cards || editions) { 5.40 + fprintf(stderr, "mtg already initialized\n"); 5.41 + return -1; 5.42 + } 5.43 + 5.44 + if(!(cards = rb_create((rb_cmp_func_t)strcmp_lower))) { 5.45 + goto err; 5.46 + } 5.47 + rb_set_delete_func(cards, rbdel, 0); 5.48 + 5.49 + if(!(editions = rb_create((rb_cmp_func_t)strcmp_lower))) { 5.50 + goto err; 5.51 + } 5.52 + rb_set_delete_func(editions, rbdel, 0); 5.53 + 5.54 + if(load_editions() == -1) { 5.55 + goto err; 5.56 + } 5.57 + return 0; 5.58 + 5.59 +err: 5.60 + if(cards) rb_destroy(cards); 5.61 + if(editions) rb_destroy(editions); 5.62 + return -1; 5.63 +} 5.64 + 5.65 +void mtg_destroy(void) 5.66 +{ 5.67 + rb_free(cards); 5.68 + rb_free(editions); 5.69 + cards = editions = 0; 5.70 +} 5.71 + 5.72 +int mtg_load_cards(const char *fname) 5.73 +{ 5.74 + int i; 5.75 + FILE *fp; 5.76 + char buf[512]; 5.77 + 5.78 + if(!(fp = fopen(fname, "r"))) { 5.79 + fprintf(stderr, "failed to open magic list: %s: %s\n", fname, strerror(errno)); 5.80 + return -1; 5.81 + } 5.82 + 5.83 + while(fgets(buf, sizeof buf, fp)) { 5.84 + struct mtg_card *card; 5.85 + char *field[6]; 5.86 + 5.87 + for(i=0; i<6; i++) { 5.88 + field[i] = strtok(i ? 0 : buf, "|\n\r\t\v;"); 5.89 + } 5.90 + 5.91 + if(!(card = malloc(sizeof *card))) { 5.92 + continue; 5.93 + } 5.94 + if(!field[1] || !(card->name = strdup(field[1]))) { 5.95 + free(card); 5.96 + continue; 5.97 + } 5.98 + card->color = parse_color(field[0], field[5]); 5.99 + card->type = mtg_str_type(field[2]); 5.100 + card->edition = mtg_edition(field[4]); 5.101 + card->count = atoi(field[3]); 5.102 + 5.103 + rb_insert(cards, card->name, card); 5.104 + } 5.105 + 5.106 + fclose(fp); 5.107 + return 0; 5.108 +} 5.109 + 5.110 +void mtg_iter_begin(void) 5.111 +{ 5.112 + rb_begin(cards); 5.113 +} 5.114 + 5.115 +const struct mtg_card *mtg_iter_next(void) 5.116 +{ 5.117 + struct rbnode *node = rb_next(cards); 5.118 + return node ? rb_node_data(node) : 0; 5.119 +} 5.120 + 5.121 +#define ADDCOL(x) \ 5.122 + do { \ 5.123 + if(*str) { \ 5.124 + strcat(str, "/"); \ 5.125 + } \ 5.126 + strcat(str, x); \ 5.127 + } while(0) 5.128 + 5.129 +const char *mtg_color_str(unsigned int color) 5.130 +{ 5.131 + static char str[128]; 5.132 + str[0] = 0; 5.133 + 5.134 + if(color == MTG_COL_MULTI) { 5.135 + return "multicolor"; 5.136 + } 5.137 + 5.138 + if(color & MTG_COL_RED) { 5.139 + ADDCOL("red"); 5.140 + } 5.141 + if(color & MTG_COL_GREEN) { 5.142 + ADDCOL("green"); 5.143 + } 5.144 + if(color & MTG_COL_BLUE) { 5.145 + ADDCOL("blue"); 5.146 + } 5.147 + if(color & MTG_COL_BLACK) { 5.148 + ADDCOL("black"); 5.149 + } 5.150 + if(color & MTG_COL_WHITE) { 5.151 + ADDCOL("white"); 5.152 + } 5.153 + if(color & MTG_COL_ARTIFACT) { 5.154 + ADDCOL("artifact"); 5.155 + } 5.156 + return str[0] ? str : "colorless"; 5.157 +} 5.158 + 5.159 +const char *mtg_type_str(enum mtg_card_type type) 5.160 +{ 5.161 + int i; 5.162 + for(i=0; type_names[i].name; i++) { 5.163 + if(type_names[i].type == type) { 5.164 + return type_names[i].name; 5.165 + } 5.166 + } 5.167 + return MTG_TYPE_UNKNOWN; 5.168 +} 5.169 + 5.170 +enum mtg_card_type mtg_str_type(const char *s) 5.171 +{ 5.172 + int i; 5.173 + for(i=0; type_names[i].name; i++) { 5.174 + if(strcmp_lower(type_names[i].name, s) == 0) { 5.175 + return type_names[i].type; 5.176 + } 5.177 + } 5.178 + return MTG_TYPE_UNKNOWN; 5.179 +} 5.180 + 5.181 +const char *mtg_edition(const char *edcode) 5.182 +{ 5.183 + struct rbnode *node = rb_find(editions, (void*)edcode); 5.184 + if(!node) { 5.185 + return "unknown"; 5.186 + } 5.187 + return rb_node_data(node); 5.188 +} 5.189 + 5.190 +int mtg_is_multicolor(unsigned int color) 5.191 +{ 5.192 + int i, bits = 0; 5.193 + 5.194 + for(i=0; i<16; i++) { 5.195 + if(color & 1) ++bits; 5.196 + color >>= 1; 5.197 + } 5.198 + return bits > 1; 5.199 +} 5.200 + 5.201 +static void dbgprint(struct rbnode *node, void *cls) 5.202 +{ 5.203 + fprintf(stderr, "%s\n", (char*)rb_node_key(node)); 5.204 +} 5.205 + 5.206 +static int load_editions(void) 5.207 +{ 5.208 + FILE *fp; 5.209 + char buf[128]; 5.210 + 5.211 + if(!(fp = fopen(ED_FNAME, "r"))) { 5.212 + perror("failed to open editions config file: " ED_FNAME); 5.213 + return -1; 5.214 + } 5.215 + 5.216 + while(fgets(buf, sizeof buf, fp)) { 5.217 + char *code, *name; 5.218 + 5.219 + code = strtok(buf, "|\n\r"); 5.220 + if(!code) continue; 5.221 + 5.222 + name = strtok(0, "|\n\r"); 5.223 + if(!name) continue; 5.224 + 5.225 + rb_insert(editions, strdup(code), strdup(name)); 5.226 + } 5.227 + 5.228 + rb_foreach(editions, dbgprint, 0); 5.229 + 5.230 + fclose(fp); 5.231 + return 0; 5.232 +} 5.233 + 5.234 +static unsigned int parse_multicolor(const char *str) 5.235 +{ 5.236 + int i; 5.237 + unsigned int mask = 0; 5.238 + 5.239 + char *cstr = alloca(strlen(str) + 1); 5.240 + for(i=0; str[i]; i++) { 5.241 + cstr[i] = tolower(str[i]); 5.242 + } 5.243 + cstr[i] = 0; 5.244 + 5.245 + if(strstr(cstr, "red")) mask |= MTG_COL_RED; 5.246 + if(strstr(cstr, "green")) mask |= MTG_COL_GREEN; 5.247 + if(strstr(cstr, "blue")) mask |= MTG_COL_BLUE; 5.248 + if(strstr(cstr, "black")) mask |= MTG_COL_BLACK; 5.249 + if(strstr(cstr, "white")) mask |= MTG_COL_WHITE; 5.250 + if(strstr(cstr, "artifact")) mask |= MTG_COL_ARTIFACT; 5.251 + 5.252 + return mask; 5.253 +} 5.254 + 5.255 +static unsigned int parse_color(const char *colstr, const char *notes) 5.256 +{ 5.257 + int i; 5.258 + unsigned int res = 0; 5.259 + char *cstr = alloca(strlen(colstr) + 1); 5.260 + for(i=0; colstr[i]; i++) { 5.261 + cstr[i] = tolower(colstr[i]); 5.262 + } 5.263 + cstr[i] = 0; 5.264 + 5.265 + if((res = parse_multicolor(colstr))) { 5.266 + return res; 5.267 + } 5.268 + 5.269 + if(strcmp(cstr, "*") == 0) { 5.270 + if((res = parse_multicolor(notes))) { 5.271 + return res; 5.272 + } 5.273 + return MTG_COL_MULTI; 5.274 + } 5.275 + 5.276 + return MTG_COL_NONE; 5.277 +} 5.278 + 5.279 +static int strcmp_lower(const char *a, const char *b) 5.280 +{ 5.281 + return strcasecmp(a, b); 5.282 + while(*a && tolower(*a) == tolower(*b)) { 5.283 + ++a; 5.284 + ++b; 5.285 + } 5.286 + return tolower(*a) - tolower(*b); 5.287 +} 5.288 + 5.289 +static void rbdel(struct rbnode *node, void *cls) 5.290 +{ 5.291 + free(rb_node_key(node)); 5.292 + free(rb_node_data(node)); 5.293 +}
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 6.2 +++ b/src/mtg.h Sun Nov 02 11:07:45 2014 +0200 6.3 @@ -0,0 +1,52 @@ 6.4 +#ifndef MTG_H_ 6.5 +#define MTG_H_ 6.6 + 6.7 +#define MTG_COL_NONE 0 6.8 +#define MTG_COL_RED 1 6.9 +#define MTG_COL_GREEN 2 6.10 +#define MTG_COL_BLUE 4 6.11 +#define MTG_COL_BLACK 8 6.12 +#define MTG_COL_WHITE 16 6.13 +#define MTG_COL_ARTIFACT 32 6.14 +#define MTG_COL_MULTI 0xff 6.15 + 6.16 +enum mtg_card_type { 6.17 + MTG_TYPE_UNKNOWN, 6.18 + 6.19 + MTG_TYPE_LAND, 6.20 + MTG_TYPE_CREATURE, 6.21 + MTG_TYPE_SORCERY, 6.22 + MTG_TYPE_INSTANT, 6.23 + MTG_TYPE_ENCHANTMENT, 6.24 + MTG_TYPE_ARTIFACT, 6.25 + MTG_TYPE_PLANESWALKER 6.26 +}; 6.27 + 6.28 + 6.29 +struct mtg_card { 6.30 + char *name; 6.31 + unsigned int color; 6.32 + enum mtg_card_type type; 6.33 + const char *edition; 6.34 + int count; 6.35 +}; 6.36 + 6.37 +int mtg_init(void); 6.38 +void mtg_destroy(void); 6.39 + 6.40 +int mtg_load_cards(const char *fname); 6.41 + 6.42 +void mtg_iter_begin(void); 6.43 +const struct mtg_card *mtg_iter_next(void); 6.44 + 6.45 +const char *mtg_color_str(unsigned int color); 6.46 + 6.47 +const char *mtg_type_str(enum mtg_card_type type); 6.48 +enum mtg_card_type mtg_str_type(const char *s); 6.49 + 6.50 +const char *mtg_edition(const char *edcode); 6.51 + 6.52 +int mtg_is_multicolor(unsigned int color); 6.53 + 6.54 + 6.55 +#endif /* MTG_H_ */
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/src/mtglist.c Sun Nov 02 11:07:45 2014 +0200 7.3 @@ -0,0 +1,40 @@ 7.4 +#include <stdio.h> 7.5 +#include <stdlib.h> 7.6 +#include <string.h> 7.7 +#include "mtg.h" 7.8 + 7.9 +int main(int argc, char **argv) 7.10 +{ 7.11 + const struct mtg_card *card; 7.12 + const char *fname = "cardlist"; 7.13 + int ncards; 7.14 + 7.15 + if(argv[1]) fname = argv[1]; 7.16 + 7.17 + if(mtg_init() == -1) { 7.18 + return 1; 7.19 + } 7.20 + 7.21 + if(mtg_load_cards(fname) == -1) { 7.22 + mtg_destroy(); 7.23 + return 1; 7.24 + } 7.25 + 7.26 + ncards = 0; 7.27 + 7.28 + mtg_iter_begin(); 7.29 + while((card = mtg_iter_next())) { 7.30 + printf("%3d ", card->count); 7.31 + printf("%-11s ", mtg_color_str(card->color)); 7.32 + printf("%-32s ", card->name); 7.33 + printf("%-12s ", mtg_type_str(card->type)); 7.34 + printf("%s\n", card->edition); 7.35 + 7.36 + ncards += card->count; 7.37 + } 7.38 + 7.39 + printf("Total cards: %d\n", ncards); 7.40 + 7.41 + mtg_destroy(); 7.42 + return 0; 7.43 +}
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 8.2 +++ b/src/rbtree.c Sun Nov 02 11:07:45 2014 +0200 8.3 @@ -0,0 +1,501 @@ 8.4 +/* 8.5 +rbtree - simple balanced binary search tree (red-black tree) library. 8.6 +Copyright (C) 2011-2014 John Tsiombikas <nuclear@member.fsf.org> 8.7 + 8.8 +rbtree is free software, feel free to use, modify, and redistribute it, under 8.9 +the terms of the 3-clause BSD license. See COPYING for details. 8.10 + */ 8.11 +#include <stdio.h> 8.12 +#include <stdlib.h> 8.13 +#include <stdint.h> 8.14 +#include <string.h> 8.15 +#include "rbtree.h" 8.16 + 8.17 +#define INT2PTR(x) ((void*)(intptr_t)(x)) 8.18 +#define PTR2INT(x) ((int)(intptr_t)(x)) 8.19 + 8.20 +struct rbtree { 8.21 + struct rbnode *root; 8.22 + 8.23 + rb_alloc_func_t alloc; 8.24 + rb_free_func_t free; 8.25 + 8.26 + rb_cmp_func_t cmp; 8.27 + rb_del_func_t del; 8.28 + void *del_cls; 8.29 + 8.30 + struct rbnode *rstack, *iter; 8.31 +}; 8.32 + 8.33 +static int cmpaddr(const void *ap, const void *bp); 8.34 +static int cmpint(const void *ap, const void *bp); 8.35 + 8.36 +static int count_nodes(struct rbnode *node); 8.37 +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); 8.38 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); 8.39 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); 8.40 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ 8.41 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); 8.42 + 8.43 +struct rbtree *rb_create(rb_cmp_func_t cmp_func) 8.44 +{ 8.45 + struct rbtree *rb; 8.46 + 8.47 + if(!(rb = malloc(sizeof *rb))) { 8.48 + return 0; 8.49 + } 8.50 + if(rb_init(rb, cmp_func) == -1) { 8.51 + free(rb); 8.52 + return 0; 8.53 + } 8.54 + return rb; 8.55 +} 8.56 + 8.57 +void rb_free(struct rbtree *rb) 8.58 +{ 8.59 + rb_destroy(rb); 8.60 + free(rb); 8.61 +} 8.62 + 8.63 + 8.64 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) 8.65 +{ 8.66 + memset(rb, 0, sizeof *rb); 8.67 + 8.68 + if(!cmp_func) { 8.69 + rb->cmp = cmpaddr; 8.70 + } else if(cmp_func == RB_KEY_INT) { 8.71 + rb->cmp = cmpint; 8.72 + } else if(cmp_func == RB_KEY_STRING) { 8.73 + rb->cmp = (rb_cmp_func_t)strcmp; 8.74 + } else { 8.75 + rb->cmp = cmp_func; 8.76 + } 8.77 + 8.78 + rb->alloc = malloc; 8.79 + rb->free = free; 8.80 + return 0; 8.81 +} 8.82 + 8.83 +void rb_destroy(struct rbtree *rb) 8.84 +{ 8.85 + del_tree(rb->root, rb->del, rb->del_cls); 8.86 +} 8.87 + 8.88 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) 8.89 +{ 8.90 + rb->alloc = alloc; 8.91 + rb->free = free; 8.92 +} 8.93 + 8.94 + 8.95 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) 8.96 +{ 8.97 + rb->cmp = func; 8.98 +} 8.99 + 8.100 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) 8.101 +{ 8.102 + rb->del = func; 8.103 + rb->del_cls = cls; 8.104 +} 8.105 + 8.106 + 8.107 +void rb_clear(struct rbtree *rb) 8.108 +{ 8.109 + del_tree(rb->root, rb->del, rb->del_cls); 8.110 + rb->root = 0; 8.111 +} 8.112 + 8.113 +int rb_copy(struct rbtree *dest, struct rbtree *src) 8.114 +{ 8.115 + struct rbnode *node; 8.116 + 8.117 + rb_clear(dest); 8.118 + rb_begin(src); 8.119 + while((node = rb_next(src))) { 8.120 + if(rb_insert(dest, node->key, node->data) == -1) { 8.121 + return -1; 8.122 + } 8.123 + } 8.124 + return 0; 8.125 +} 8.126 + 8.127 +int rb_size(struct rbtree *rb) 8.128 +{ 8.129 + return count_nodes(rb->root); 8.130 +} 8.131 + 8.132 +int rb_insert(struct rbtree *rb, void *key, void *data) 8.133 +{ 8.134 + rb->root = insert(rb, rb->root, key, data); 8.135 + rb->root->red = 0; 8.136 + return 0; 8.137 +} 8.138 + 8.139 +int rb_inserti(struct rbtree *rb, int key, void *data) 8.140 +{ 8.141 + rb->root = insert(rb, rb->root, INT2PTR(key), data); 8.142 + rb->root->red = 0; 8.143 + return 0; 8.144 +} 8.145 + 8.146 + 8.147 +int rb_delete(struct rbtree *rb, void *key) 8.148 +{ 8.149 + rb->root = delete(rb, rb->root, key); 8.150 + rb->root->red = 0; 8.151 + return 0; 8.152 +} 8.153 + 8.154 +int rb_deletei(struct rbtree *rb, int key) 8.155 +{ 8.156 + rb->root = delete(rb, rb->root, INT2PTR(key)); 8.157 + rb->root->red = 0; 8.158 + return 0; 8.159 +} 8.160 + 8.161 + 8.162 +struct rbnode *rb_find(struct rbtree *rb, void *key) 8.163 +{ 8.164 + struct rbnode *node = rb->root; 8.165 + 8.166 + while(node) { 8.167 + int cmp = rb->cmp(key, node->key); 8.168 + if(cmp == 0) { 8.169 + return node; 8.170 + } 8.171 + node = cmp < 0 ? node->left : node->right; 8.172 + } 8.173 + return 0; 8.174 +} 8.175 + 8.176 +struct rbnode *rb_findi(struct rbtree *rb, int key) 8.177 +{ 8.178 + return rb_find(rb, INT2PTR(key)); 8.179 +} 8.180 + 8.181 + 8.182 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) 8.183 +{ 8.184 + traverse(rb->root, func, cls); 8.185 +} 8.186 + 8.187 + 8.188 +struct rbnode *rb_root(struct rbtree *rb) 8.189 +{ 8.190 + return rb->root; 8.191 +} 8.192 + 8.193 +void rb_begin(struct rbtree *rb) 8.194 +{ 8.195 + rb->rstack = 0; 8.196 + rb->iter = rb->root; 8.197 +} 8.198 + 8.199 +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) 8.200 +#define pop(sp) ((sp) = (sp)->next) 8.201 +#define top(sp) (sp) 8.202 + 8.203 +struct rbnode *rb_next(struct rbtree *rb) 8.204 +{ 8.205 + struct rbnode *res = 0; 8.206 + 8.207 + while(rb->rstack || rb->iter) { 8.208 + if(rb->iter) { 8.209 + push(rb->rstack, rb->iter); 8.210 + rb->iter = rb->iter->left; 8.211 + } else { 8.212 + rb->iter = top(rb->rstack); 8.213 + pop(rb->rstack); 8.214 + res = rb->iter; 8.215 + rb->iter = rb->iter->right; 8.216 + break; 8.217 + } 8.218 + } 8.219 + return res; 8.220 +} 8.221 + 8.222 +void *rb_node_key(struct rbnode *node) 8.223 +{ 8.224 + return node ? node->key : 0; 8.225 +} 8.226 + 8.227 +int rb_node_keyi(struct rbnode *node) 8.228 +{ 8.229 + return node ? PTR2INT(node->key) : 0; 8.230 +} 8.231 + 8.232 +void *rb_node_data(struct rbnode *node) 8.233 +{ 8.234 + return node ? node->data : 0; 8.235 +} 8.236 + 8.237 +static int cmpaddr(const void *ap, const void *bp) 8.238 +{ 8.239 + return ap < bp ? -1 : (ap > bp ? 1 : 0); 8.240 +} 8.241 + 8.242 +static int cmpint(const void *ap, const void *bp) 8.243 +{ 8.244 + return PTR2INT(ap) - PTR2INT(bp); 8.245 +} 8.246 + 8.247 + 8.248 +/* ---- left-leaning 2-3 red-black implementation ---- */ 8.249 + 8.250 +/* helper prototypes */ 8.251 +static int is_red(struct rbnode *tree); 8.252 +static void color_flip(struct rbnode *tree); 8.253 +static struct rbnode *rot_left(struct rbnode *a); 8.254 +static struct rbnode *rot_right(struct rbnode *a); 8.255 +static struct rbnode *find_min(struct rbnode *tree); 8.256 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); 8.257 +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ 8.258 +static struct rbnode *move_red_left(struct rbnode *tree); 8.259 +static struct rbnode *fix_up(struct rbnode *tree); 8.260 + 8.261 +static int count_nodes(struct rbnode *node) 8.262 +{ 8.263 + if(!node) 8.264 + return 0; 8.265 + 8.266 + return 1 + count_nodes(node->left) + count_nodes(node->right); 8.267 +} 8.268 + 8.269 +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) 8.270 +{ 8.271 + if(!node) 8.272 + return; 8.273 + 8.274 + del_tree(node->left, delfunc, cls); 8.275 + del_tree(node->right, delfunc, cls); 8.276 + 8.277 + if(delfunc) { 8.278 + delfunc(node, cls); 8.279 + } 8.280 + free(node); 8.281 +} 8.282 + 8.283 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) 8.284 +{ 8.285 + int cmp; 8.286 + 8.287 + if(!tree) { 8.288 + struct rbnode *node = rb->alloc(sizeof *node); 8.289 + node->red = 1; 8.290 + node->key = key; 8.291 + node->data = data; 8.292 + node->left = node->right = 0; 8.293 + return node; 8.294 + } 8.295 + 8.296 + cmp = rb->cmp(key, tree->key); 8.297 + 8.298 + if(cmp < 0) { 8.299 + tree->left = insert(rb, tree->left, key, data); 8.300 + } else if(cmp > 0) { 8.301 + tree->right = insert(rb, tree->right, key, data); 8.302 + } else { 8.303 + tree->data = data; 8.304 + } 8.305 + 8.306 + /* fix right-leaning reds */ 8.307 + if(is_red(tree->right)) { 8.308 + tree = rot_left(tree); 8.309 + } 8.310 + /* fix two reds in a row */ 8.311 + if(is_red(tree->left) && is_red(tree->left->left)) { 8.312 + tree = rot_right(tree); 8.313 + } 8.314 + 8.315 + /* if 4-node, split it by color inversion */ 8.316 + if(is_red(tree->left) && is_red(tree->right)) { 8.317 + color_flip(tree); 8.318 + } 8.319 + 8.320 + return tree; 8.321 +} 8.322 + 8.323 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) 8.324 +{ 8.325 + int cmp; 8.326 + 8.327 + if(!tree) { 8.328 + return 0; 8.329 + } 8.330 + 8.331 + cmp = rb->cmp(key, tree->key); 8.332 + 8.333 + if(cmp < 0) { 8.334 + if(!is_red(tree->left) && !is_red(tree->left->left)) { 8.335 + tree = move_red_left(tree); 8.336 + } 8.337 + tree->left = delete(rb, tree->left, key); 8.338 + } else { 8.339 + /* need reds on the right */ 8.340 + if(is_red(tree->left)) { 8.341 + tree = rot_right(tree); 8.342 + } 8.343 + 8.344 + /* found it at the bottom (XXX what certifies left is null?) */ 8.345 + if(cmp == 0 && !tree->right) { 8.346 + if(rb->del) { 8.347 + rb->del(tree, rb->del_cls); 8.348 + } 8.349 + rb->free(tree); 8.350 + return 0; 8.351 + } 8.352 + 8.353 + if(!is_red(tree->right) && !is_red(tree->right->left)) { 8.354 + tree = move_red_left(tree); 8.355 + } 8.356 + 8.357 + if(key == tree->key) { 8.358 + struct rbnode *rmin = find_min(tree->right); 8.359 + tree->key = rmin->key; 8.360 + tree->data = rmin->data; 8.361 + tree->right = del_min(rb, tree->right); 8.362 + } else { 8.363 + tree->right = delete(rb, tree->right, key); 8.364 + } 8.365 + } 8.366 + 8.367 + return fix_up(tree); 8.368 +} 8.369 + 8.370 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) 8.371 +{ 8.372 + int cmp; 8.373 + 8.374 + if(!node) 8.375 + return 0; 8.376 + 8.377 + if((cmp = rb->cmp(key, node->key)) == 0) { 8.378 + return node; 8.379 + } 8.380 + return find(rb, cmp < 0 ? node->left : node->right, key); 8.381 +}*/ 8.382 + 8.383 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) 8.384 +{ 8.385 + if(!node) 8.386 + return; 8.387 + 8.388 + traverse(node->left, func, cls); 8.389 + func(node, cls); 8.390 + traverse(node->right, func, cls); 8.391 +} 8.392 + 8.393 +/* helpers */ 8.394 + 8.395 +static int is_red(struct rbnode *tree) 8.396 +{ 8.397 + return tree && tree->red; 8.398 +} 8.399 + 8.400 +static void color_flip(struct rbnode *tree) 8.401 +{ 8.402 + tree->red = !tree->red; 8.403 + tree->left->red = !tree->left->red; 8.404 + tree->right->red = !tree->right->red; 8.405 +} 8.406 + 8.407 +static struct rbnode *rot_left(struct rbnode *a) 8.408 +{ 8.409 + struct rbnode *b = a->right; 8.410 + a->right = b->left; 8.411 + b->left = a; 8.412 + b->red = a->red; 8.413 + a->red = 1; 8.414 + return b; 8.415 +} 8.416 + 8.417 +static struct rbnode *rot_right(struct rbnode *a) 8.418 +{ 8.419 + struct rbnode *b = a->left; 8.420 + a->left = b->right; 8.421 + b->right = a; 8.422 + b->red = a->red; 8.423 + a->red = 1; 8.424 + return b; 8.425 +} 8.426 + 8.427 +static struct rbnode *find_min(struct rbnode *tree) 8.428 +{ 8.429 + if(!tree) 8.430 + return 0; 8.431 + 8.432 + while(tree->left) { 8.433 + tree = tree->left; 8.434 + } 8.435 + return tree; 8.436 +} 8.437 + 8.438 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) 8.439 +{ 8.440 + if(!tree->left) { 8.441 + if(rb->del) { 8.442 + rb->del(tree->left, rb->del_cls); 8.443 + } 8.444 + rb->free(tree->left); 8.445 + return 0; 8.446 + } 8.447 + 8.448 + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ 8.449 + if(!is_red(tree->left) && !is_red(tree->left->left)) { 8.450 + tree = move_red_left(tree); 8.451 + } 8.452 + tree->left = del_min(rb, tree->left); 8.453 + 8.454 + /* fix right-reds, red-reds, and split 4-nodes on the way up */ 8.455 + return fix_up(tree); 8.456 +} 8.457 + 8.458 +#if 0 8.459 +/* push a red link on this node to the right */ 8.460 +static struct rbnode *move_red_right(struct rbnode *tree) 8.461 +{ 8.462 + /* flipping it makes both children go red, so we have a red to the right */ 8.463 + color_flip(tree); 8.464 + 8.465 + /* if after the flip we've got a red-red situation to the left, fix it */ 8.466 + if(is_red(tree->left->left)) { 8.467 + tree = rot_right(tree); 8.468 + color_flip(tree); 8.469 + } 8.470 + return tree; 8.471 +} 8.472 +#endif 8.473 + 8.474 +/* push a red link on this node to the left */ 8.475 +static struct rbnode *move_red_left(struct rbnode *tree) 8.476 +{ 8.477 + /* flipping it makes both children go red, so we have a red to the left */ 8.478 + color_flip(tree); 8.479 + 8.480 + /* if after the flip we've got a red-red on the right-left, fix it */ 8.481 + if(is_red(tree->right->left)) { 8.482 + tree->right = rot_right(tree->right); 8.483 + tree = rot_left(tree); 8.484 + color_flip(tree); 8.485 + } 8.486 + return tree; 8.487 +} 8.488 + 8.489 +static struct rbnode *fix_up(struct rbnode *tree) 8.490 +{ 8.491 + /* fix right-leaning */ 8.492 + if(is_red(tree->right)) { 8.493 + tree = rot_left(tree); 8.494 + } 8.495 + /* change invalid red-red pairs into a proper 4-node */ 8.496 + if(is_red(tree->left) && is_red(tree->left->left)) { 8.497 + tree = rot_right(tree); 8.498 + } 8.499 + /* split 4-nodes */ 8.500 + if(is_red(tree->left) && is_red(tree->right)) { 8.501 + color_flip(tree); 8.502 + } 8.503 + return tree; 8.504 +}
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 9.2 +++ b/src/rbtree.h Sun Nov 02 11:07:45 2014 +0200 9.3 @@ -0,0 +1,78 @@ 9.4 +/* 9.5 +rbtree - simple balanced binary search tree (red-black tree) library. 9.6 +Copyright (C) 2011-2014 John Tsiombikas <nuclear@member.fsf.org> 9.7 + 9.8 +rbtree is free software, feel free to use, modify, and redistribute it, under 9.9 +the terms of the 3-clause BSD license. See COPYING for details. 9.10 + */ 9.11 +#ifndef RBTREE_H_ 9.12 +#define RBTREE_H_ 9.13 + 9.14 +struct rbtree; 9.15 + 9.16 + 9.17 +struct rbnode { 9.18 + void *key, *data; 9.19 + int red; 9.20 + struct rbnode *left, *right; 9.21 + struct rbnode *next; /* for iterator stack */ 9.22 +}; 9.23 + 9.24 + 9.25 +typedef void *(*rb_alloc_func_t)(size_t); 9.26 +typedef void (*rb_free_func_t)(void*); 9.27 + 9.28 +typedef int (*rb_cmp_func_t)(const void*, const void*); 9.29 +typedef void (*rb_del_func_t)(struct rbnode*, void*); 9.30 + 9.31 +#define RB_KEY_ADDR (rb_cmp_func_t)(0) 9.32 +#define RB_KEY_INT (rb_cmp_func_t)(1) 9.33 +#define RB_KEY_STRING (rb_cmp_func_t)(3) 9.34 + 9.35 + 9.36 +#ifdef __cplusplus 9.37 +extern "C" { 9.38 +#endif 9.39 + 9.40 +struct rbtree *rb_create(rb_cmp_func_t cmp_func); 9.41 +void rb_free(struct rbtree *rb); 9.42 + 9.43 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); 9.44 +void rb_destroy(struct rbtree *rb); 9.45 + 9.46 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); 9.47 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); 9.48 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); 9.49 +/* TODO add user deep copy function */ 9.50 + 9.51 +void rb_clear(struct rbtree *rb); 9.52 +int rb_copy(struct rbtree *dest, struct rbtree *src); 9.53 + 9.54 +int rb_size(struct rbtree *rb); 9.55 + 9.56 +int rb_insert(struct rbtree *rb, void *key, void *data); 9.57 +int rb_inserti(struct rbtree *rb, int key, void *data); 9.58 + 9.59 +int rb_delete(struct rbtree *rb, void *key); 9.60 +int rb_deletei(struct rbtree *rb, int key); 9.61 + 9.62 +struct rbnode *rb_find(struct rbtree *rb, void *key); 9.63 +struct rbnode *rb_findi(struct rbtree *rb, int key); 9.64 + 9.65 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); 9.66 + 9.67 +struct rbnode *rb_root(struct rbtree *rb); 9.68 + 9.69 +void rb_begin(struct rbtree *rb); 9.70 +struct rbnode *rb_next(struct rbtree *rb); 9.71 + 9.72 +void *rb_node_key(struct rbnode *node); 9.73 +int rb_node_keyi(struct rbnode *node); 9.74 +void *rb_node_data(struct rbnode *node); 9.75 + 9.76 +#ifdef __cplusplus 9.77 +} 9.78 +#endif 9.79 + 9.80 + 9.81 +#endif /* RBTREE_H_ */