trunk/src/emu/debug/debugcpu.c
| r245618 | r245619 | |
|---|
| 1994 | 1994 | { |
| 1995 | 1995 | if (m_track_mem) |
| 1996 | 1996 | { |
| 1997 | | dasm_memory_access newAccess(space.spacenum(), address, data, history_pc(0)); |
| 1998 | | dasm_memory_access* trackedAccess = m_track_mem_set.find(newAccess); |
| 1999 | | if (trackedAccess) |
| 2000 | | trackedAccess->m_pc = newAccess.m_pc; |
| 2001 | | else |
| 2002 | | m_track_mem_set.insert(newAccess); |
| 1997 | dasm_memory_access const newAccess(space.spacenum(), address, data, history_pc(0)); |
| 1998 | std::pair<std::set<dasm_memory_access>::iterator, bool> trackedAccess = m_track_mem_set.insert(newAccess); |
| 1999 | if (!trackedAccess.second) |
| 2000 | trackedAccess.first->m_pc = newAccess.m_pc; |
| 2003 | 2001 | } |
| 2004 | 2002 | watchpoint_check(space, WATCHPOINT_WRITE, address, data, mem_mask); |
| 2005 | 2003 | } |
| r245618 | r245619 | |
|---|
| 2041 | 2039 | // make sure we get good results |
| 2042 | 2040 | assert((result & DASMFLAG_LENGTHMASK) != 0); |
| 2043 | 2041 | #ifdef MAME_DEBUG |
| 2044 | | if (m_memory != NULL && m_disasm != NULL) |
| 2045 | | { |
| 2046 | | address_space &space = m_memory->space(AS_PROGRAM); |
| 2047 | | int bytes = space.address_to_byte(result & DASMFLAG_LENGTHMASK); |
| 2048 | | assert(bytes >= m_disasm->min_opcode_bytes()); |
| 2049 | | assert(bytes <= m_disasm->max_opcode_bytes()); |
| 2050 | | (void) bytes; // appease compiler |
| 2051 | | } |
| 2042 | if (m_memory != NULL && m_disasm != NULL) |
| 2043 | { |
| 2044 | address_space &space = m_memory->space(AS_PROGRAM); |
| 2045 | int bytes = space.address_to_byte(result & DASMFLAG_LENGTHMASK); |
| 2046 | assert(bytes >= m_disasm->min_opcode_bytes()); |
| 2047 | assert(bytes <= m_disasm->max_opcode_bytes()); |
| 2048 | (void) bytes; // appease compiler |
| 2049 | } |
| 2052 | 2050 | #endif |
| 2053 | 2051 | |
| 2054 | 2052 | return result; |
| r245618 | r245619 | |
|---|
| 2589 | 2587 | if (m_track_pc_set.empty()) |
| 2590 | 2588 | return false; |
| 2591 | 2589 | const UINT32 crc = compute_opcode_crc32(pc); |
| 2592 | | return m_track_pc_set.contains(dasm_pc_tag(pc, crc)); |
| 2590 | return m_track_pc_set.find(dasm_pc_tag(pc, crc)) != m_track_pc_set.end(); |
| 2593 | 2591 | } |
| 2594 | 2592 | |
| 2595 | 2593 | |
| r245618 | r245619 | |
|---|
| 2618 | 2616 | const offs_t missing = (offs_t)(-1); |
| 2619 | 2617 | if (m_track_mem_set.empty()) |
| 2620 | 2618 | return missing; |
| 2621 | | dasm_memory_access* mem_access = m_track_mem_set.find(dasm_memory_access(space, address, data, 0)); |
| 2622 | | if (mem_access == NULL) return missing; |
| 2619 | std::set<dasm_memory_access>::iterator const mem_access = m_track_mem_set.find(dasm_memory_access(space, address, data, 0)); |
| 2620 | if (mem_access == m_track_mem_set.end()) return missing; |
| 2623 | 2621 | return mem_access->m_pc; |
| 2624 | 2622 | } |
| 2625 | 2623 | |
| r245618 | r245619 | |
|---|
| 2632 | 2630 | void device_debug::comment_add(offs_t addr, const char *comment, rgb_t color) |
| 2633 | 2631 | { |
| 2634 | 2632 | // create a new item for the list |
| 2635 | | const UINT32 crc = compute_opcode_crc32(addr); |
| 2636 | | dasm_comment newComment = dasm_comment(addr, crc, comment, color); |
| 2637 | | if (!m_comment_set.insert(newComment)) |
| 2633 | UINT32 const crc = compute_opcode_crc32(addr); |
| 2634 | dasm_comment const newComment = dasm_comment(addr, crc, comment, color); |
| 2635 | std::pair<std::set<dasm_comment>::iterator, bool> const inserted = m_comment_set.insert(newComment); |
| 2636 | if (!inserted.second) |
| 2638 | 2637 | { |
| 2639 | 2638 | // Insert returns false if comment exists |
| 2640 | | m_comment_set.remove(newComment); |
| 2639 | m_comment_set.erase(inserted.first); |
| 2641 | 2640 | m_comment_set.insert(newComment); |
| 2642 | 2641 | } |
| 2643 | 2642 | |
| r245618 | r245619 | |
|---|
| 2654 | 2653 | bool device_debug::comment_remove(offs_t addr) |
| 2655 | 2654 | { |
| 2656 | 2655 | const UINT32 crc = compute_opcode_crc32(addr); |
| 2657 | | bool success = m_comment_set.remove(dasm_comment(addr, crc, "", 0xffffffff)); |
| 2658 | | if (success) m_comment_change++; |
| 2659 | | return success; |
| 2656 | size_t const removed = m_comment_set.erase(dasm_comment(addr, crc, "", 0xffffffff)); |
| 2657 | if (removed != 0U) m_comment_change++; |
| 2658 | return removed != 0U; |
| 2660 | 2659 | } |
| 2661 | 2660 | |
| 2662 | 2661 | |
| r245618 | r245619 | |
|---|
| 2667 | 2666 | const char *device_debug::comment_text(offs_t addr) const |
| 2668 | 2667 | { |
| 2669 | 2668 | const UINT32 crc = compute_opcode_crc32(addr); |
| 2670 | | dasm_comment* comment = m_comment_set.find(dasm_comment(addr, crc, "", 0)); |
| 2671 | | if (comment == NULL) return NULL; |
| 2669 | std::set<dasm_comment>::iterator comment = m_comment_set.find(dasm_comment(addr, crc, "", 0)); |
| 2670 | if (comment == m_comment_set.end()) return NULL; |
| 2672 | 2671 | return comment->m_text; |
| 2673 | 2672 | } |
| 2674 | 2673 | |
| r245618 | r245619 | |
|---|
| 2682 | 2681 | { |
| 2683 | 2682 | // iterate through the comments |
| 2684 | 2683 | astring crc_buf; |
| 2685 | | simple_set_iterator<dasm_comment> iter(m_comment_set); |
| 2686 | | for (dasm_comment* item = iter.first(); item != iter.last(); item = iter.next()) |
| 2684 | for (std::set<dasm_comment>::iterator item = m_comment_set.begin(); item != m_comment_set.end(); ++item) |
| 2687 | 2685 | { |
| 2688 | 2686 | xml_data_node *datanode = xml_add_child(&curnode, "comment", xml_normalize_string(item->m_text)); |
| 2689 | 2687 | if (datanode == NULL) |
trunk/src/lib/util/simple_set.h
| r245618 | r245619 | |
|---|
| 1 | | /********************************************************************* |
| 2 | | |
| 3 | | simple_set.h |
| 4 | | |
| 5 | | A STL-like set class. |
| 6 | | |
| 7 | | Copyright Nicola Salmoria and the MAME Team. |
| 8 | | Visit http://mamedev.org for licensing and usage restrictions. |
| 9 | | |
| 10 | | *********************************************************************/ |
| 11 | | |
| 12 | | #pragma once |
| 13 | | |
| 14 | | #ifndef __SIMPLE_SET_H__ |
| 15 | | #define __SIMPLE_SET_H__ |
| 16 | | |
| 17 | | #ifdef SIMPLE_SET_DEBUG |
| 18 | | #include <iostream> |
| 19 | | #endif |
| 20 | | |
| 21 | | |
| 22 | | // Predeclarations |
| 23 | | template <class T> class avl_tree_node; |
| 24 | | template <class T> class simple_set_iterator; |
| 25 | | |
| 26 | | |
| 27 | | // |
| 28 | | // ======================> simple_set |
| 29 | | // A shiny stl-like set interface wrapping an AVL tree |
| 30 | | // |
| 31 | | // PUBLIC OPERATIONS: |
| 32 | | // size, empty, clear, insert, remove, find, contains, merge, & assignment. |
| 33 | | // |
| 34 | | |
| 35 | | template <class T> |
| 36 | | class simple_set |
| 37 | | { |
| 38 | | friend class simple_set_iterator<T>; |
| 39 | | typedef avl_tree_node<T> tree_node; |
| 40 | | |
| 41 | | public: |
| 42 | | // Construction |
| 43 | | simple_set() |
| 44 | | : m_root(NULL) |
| 45 | | { } |
| 46 | | |
| 47 | | simple_set(const simple_set& rhs) |
| 48 | | : m_root(NULL) |
| 49 | | { |
| 50 | | *this = rhs; |
| 51 | | } |
| 52 | | |
| 53 | | ~simple_set() |
| 54 | | { |
| 55 | | clear(); |
| 56 | | } |
| 57 | | |
| 58 | | |
| 59 | | // Returns number of elements in the tree -- O(n) |
| 60 | | int size() const |
| 61 | | { |
| 62 | | if (empty()) return 0; |
| 63 | | |
| 64 | | const tree_node* currentNode = m_root; |
| 65 | | const int nodeCount = sizeRecurse(currentNode); |
| 66 | | return nodeCount; |
| 67 | | } |
| 68 | | |
| 69 | | |
| 70 | | // Test for emptiness -- O(1). |
| 71 | | bool empty() const |
| 72 | | { |
| 73 | | return m_root == NULL; |
| 74 | | } |
| 75 | | |
| 76 | | |
| 77 | | // Empty the tree -- O(n). |
| 78 | | void clear() |
| 79 | | { |
| 80 | | clearRecurse(m_root); |
| 81 | | } |
| 82 | | |
| 83 | | |
| 84 | | // Insert x into the avl tree; duplicates are ignored -- O(log n). |
| 85 | | bool insert(const T& x) |
| 86 | | { |
| 87 | | bool retVal = insert(x, m_root); |
| 88 | | |
| 89 | | // Whether the node was successfully inserted or not (i.e. wasn't a duplicate) |
| 90 | | return retVal; |
| 91 | | } |
| 92 | | |
| 93 | | |
| 94 | | // Remove x from the tree. Nothing is done if x is not found -- O(n). |
| 95 | | bool remove(const T& x) |
| 96 | | { |
| 97 | | // First find the node in the tree |
| 98 | | tree_node* currNode = find(x, m_root); |
| 99 | | |
| 100 | | // Only do this when the current node is valid |
| 101 | | if (currNode) |
| 102 | | { |
| 103 | | // See if it's a leaf |
| 104 | | if (currNode->isLeaf()) |
| 105 | | { |
| 106 | | // Get the parent object |
| 107 | | tree_node* parentNode = currNode->parent; |
| 108 | | |
| 109 | | // If we're a leaf and we have no parent, then the tree will be emptied |
| 110 | | if (!currNode->parent) |
| 111 | | { |
| 112 | | m_root = NULL; |
| 113 | | } |
| 114 | | |
| 115 | | // If it's a leaf node, simply remove it |
| 116 | | removeNode(currNode); |
| 117 | | global_free(currNode); |
| 118 | | |
| 119 | | // Update the balance of the parent of |
| 120 | | // currentNode after having disconnected |
| 121 | | // it |
| 122 | | if (parentNode) |
| 123 | | parentNode->calcHeights(); |
| 124 | | } |
| 125 | | else |
| 126 | | { |
| 127 | | // Get the parent object |
| 128 | | tree_node* parentNode = currNode->parent; |
| 129 | | |
| 130 | | // Remove the child and reconnect the smallest node in the right sub tree |
| 131 | | // (in order successor) |
| 132 | | tree_node* replaceNode = findMin(currNode->right); |
| 133 | | |
| 134 | | // See if there's even a right-most node |
| 135 | | if (!replaceNode) |
| 136 | | { |
| 137 | | // Get the largest node on the left (because the right doesn't exist) |
| 138 | | replaceNode = findMax(currNode->left); |
| 139 | | } |
| 140 | | |
| 141 | | tree_node* parentReplaceNode = replaceNode->parent; |
| 142 | | |
| 143 | | // Disconnect the replacement node's branch |
| 144 | | removeNode(replaceNode); |
| 145 | | |
| 146 | | // Update the balance of the parent of |
| 147 | | // replaceNode after having disconnected |
| 148 | | // it |
| 149 | | if (parentReplaceNode) |
| 150 | | parentReplaceNode->calcHeights(); |
| 151 | | |
| 152 | | // Disconnect the current node |
| 153 | | removeNode(currNode); |
| 154 | | |
| 155 | | // Get the current node's left and right branches |
| 156 | | tree_node* left = currNode->left; |
| 157 | | tree_node* right = currNode->right; |
| 158 | | |
| 159 | | // We no longer need this node |
| 160 | | global_free(currNode); |
| 161 | | |
| 162 | | // Check to see if we removed the root node |
| 163 | | if (!parentNode) |
| 164 | | { |
| 165 | | // Merge the branches into the parent node of what we deleted |
| 166 | | merge(replaceNode, parentNode); |
| 167 | | merge(left, parentNode); |
| 168 | | merge(right, parentNode); |
| 169 | | |
| 170 | | // Now we're the root |
| 171 | | m_root = parentNode; |
| 172 | | } |
| 173 | | else |
| 174 | | { |
| 175 | | // Merge the branches into the parent node of what we |
| 176 | | // deleted, we let the merge algorithm decide where to |
| 177 | | // put the branches |
| 178 | | merge(replaceNode, parentNode); |
| 179 | | merge(left, parentNode); |
| 180 | | merge(right, parentNode); |
| 181 | | } |
| 182 | | } |
| 183 | | |
| 184 | | // Balance the tree |
| 185 | | balanceTree(); |
| 186 | | |
| 187 | | // The node was found and removed successfully |
| 188 | | return true; |
| 189 | | } |
| 190 | | else |
| 191 | | { |
| 192 | | // The node was not found |
| 193 | | return false; |
| 194 | | } |
| 195 | | } |
| 196 | | |
| 197 | | |
| 198 | | // Find item x in the tree. Returns a pointer to the matching item |
| 199 | | // or NULL if not found -- O(log n) |
| 200 | | T* find(const T& x) const |
| 201 | | { |
| 202 | | tree_node* found = find(x, m_root); |
| 203 | | if (found == NULL) return NULL; |
| 204 | | return &found->element; |
| 205 | | } |
| 206 | | |
| 207 | | |
| 208 | | // Is the data present in the set? -- O(log n) |
| 209 | | bool contains(const T& x) const |
| 210 | | { |
| 211 | | if (find(x) != NULL) |
| 212 | | return true; |
| 213 | | else |
| 214 | | return false; |
| 215 | | } |
| 216 | | |
| 217 | | |
| 218 | | // Merge a different tree with ours -- O(n). |
| 219 | | bool merge(const simple_set<T>& b) |
| 220 | | { |
| 221 | | tree_node* c = b->clone(); |
| 222 | | bool retVal = merge(c->m_root, m_root); |
| 223 | | |
| 224 | | // Re-balance the tree if the merge was successful |
| 225 | | if (retVal) |
| 226 | | { |
| 227 | | balanceTree(); |
| 228 | | } |
| 229 | | else |
| 230 | | { |
| 231 | | global_free(c); |
| 232 | | } |
| 233 | | |
| 234 | | return retVal; |
| 235 | | } |
| 236 | | |
| 237 | | |
| 238 | | // Replace this set with another -- O(n) |
| 239 | | const simple_set& operator=(const simple_set& rhs) |
| 240 | | { |
| 241 | | // Don't clone if it's the same pointer |
| 242 | | if (this != &rhs) |
| 243 | | { |
| 244 | | clear(); |
| 245 | | |
| 246 | | m_root = clone(rhs.m_root); |
| 247 | | } |
| 248 | | |
| 249 | | return *this; |
| 250 | | } |
| 251 | | |
| 252 | | |
| 253 | | #ifdef SIMPLE_SET_DEBUG |
| 254 | | // Debug -- O(n log n) |
| 255 | | void printTree(std::ostream& out = std::cout) const |
| 256 | | { |
| 257 | | if(empty()) |
| 258 | | { |
| 259 | | out << "Empty tree" << std::endl; |
| 260 | | } |
| 261 | | else |
| 262 | | { |
| 263 | | printTree(out, m_root); |
| 264 | | } |
| 265 | | } |
| 266 | | #endif |
| 267 | | |
| 268 | | |
| 269 | | private: |
| 270 | | // The AVL tree's root |
| 271 | | tree_node* m_root; |
| 272 | | |
| 273 | | // Find a node in the tree |
| 274 | | tree_node* findNode(const T& x) const |
| 275 | | { |
| 276 | | tree_node* node = find(x, m_root); |
| 277 | | if (node) |
| 278 | | { |
| 279 | | return node; |
| 280 | | } |
| 281 | | else |
| 282 | | { |
| 283 | | return NULL; |
| 284 | | } |
| 285 | | } |
| 286 | | |
| 287 | | |
| 288 | | // Insert item x into a subtree t (root) -- O(log n) |
| 289 | | bool insert(const T& x, tree_node*& t) |
| 290 | | { |
| 291 | | if (t == NULL) |
| 292 | | { |
| 293 | | t = global_alloc(tree_node(x, NULL, NULL, NULL)); |
| 294 | | |
| 295 | | // An empty sub-tree here, insertion successful |
| 296 | | return true; |
| 297 | | } |
| 298 | | else if (x < t->element) |
| 299 | | { |
| 300 | | // O(log n) |
| 301 | | bool retVal = insert(x, t->left); |
| 302 | | |
| 303 | | if (retVal) |
| 304 | | { |
| 305 | | t->left->setParent(t); |
| 306 | | t->calcHeights(); |
| 307 | | |
| 308 | | if(t->balanceFactor() < -1) |
| 309 | | { |
| 310 | | // See if it went left of the left |
| 311 | | if(x < t->left->element) |
| 312 | | { |
| 313 | | rotateWithLeftChild(t); |
| 314 | | } |
| 315 | | else |
| 316 | | { |
| 317 | | // The element goes on the right of the left |
| 318 | | doubleWithLeftChild(t); |
| 319 | | } |
| 320 | | } |
| 321 | | } |
| 322 | | |
| 323 | | return retVal; |
| 324 | | } |
| 325 | | else if (t->element < x) |
| 326 | | { |
| 327 | | bool retVal = insert(x, t->right); |
| 328 | | |
| 329 | | // Only do this if the insertion was successful |
| 330 | | if (retVal) |
| 331 | | { |
| 332 | | t->right->setParent(t); |
| 333 | | t->calcHeights(); |
| 334 | | |
| 335 | | if (t->balanceFactor() > 1) |
| 336 | | { |
| 337 | | // See if it went right of the right |
| 338 | | if(t->right->element < x) |
| 339 | | { |
| 340 | | rotateWithRightChild(t); |
| 341 | | } |
| 342 | | else |
| 343 | | { |
| 344 | | // The element goes on the left of the right |
| 345 | | doubleWithRightChild(t); |
| 346 | | } |
| 347 | | } |
| 348 | | } |
| 349 | | |
| 350 | | return retVal; |
| 351 | | } |
| 352 | | else |
| 353 | | { |
| 354 | | return false; // Duplicate |
| 355 | | } |
| 356 | | } |
| 357 | | |
| 358 | | |
| 359 | | // Recursively free all nodes in the tree -- O(n). |
| 360 | | void clearRecurse(tree_node*& t) const |
| 361 | | { |
| 362 | | if(t != NULL) |
| 363 | | { |
| 364 | | clearRecurse(t->left); |
| 365 | | clearRecurse(t->right); |
| 366 | | |
| 367 | | global_free(t); |
| 368 | | } |
| 369 | | t = NULL; |
| 370 | | } |
| 371 | | |
| 372 | | |
| 373 | | // Merge a tree with this one. Private because external care is required. |
| 374 | | bool merge(tree_node* b, tree_node*& t) |
| 375 | | { |
| 376 | | if (!b) |
| 377 | | { |
| 378 | | return false; |
| 379 | | } |
| 380 | | else |
| 381 | | { |
| 382 | | bool retVal = false; |
| 383 | | |
| 384 | | if (t == NULL) |
| 385 | | { |
| 386 | | // Set this element to that subtree |
| 387 | | t = b; |
| 388 | | |
| 389 | | // The parent here should be NULL anyway, but we |
| 390 | | // set it just to be sure. This pointer will be |
| 391 | | // used as a flag to indicate where in the call |
| 392 | | // stack the tree was actually set. |
| 393 | | // |
| 394 | | // The middle layers of this method's call will |
| 395 | | // all have their parent references in tact since |
| 396 | | // no operations took place there. |
| 397 | | // |
| 398 | | //t->parent = NULL; |
| 399 | | t->setParent(NULL); |
| 400 | | |
| 401 | | // We were successful in merging |
| 402 | | retVal = true; |
| 403 | | } |
| 404 | | else if (b->element < t->element) |
| 405 | | { |
| 406 | | retVal = merge(b, t->left); |
| 407 | | |
| 408 | | // Only do this if the insertion actually took place |
| 409 | | if (retVal && !t->left->parent) |
| 410 | | { |
| 411 | | t->left->setParent(t); |
| 412 | | t->calcHeights(); |
| 413 | | } |
| 414 | | } |
| 415 | | else if (t->element < b->element) |
| 416 | | { |
| 417 | | retVal = merge(b, t->right); |
| 418 | | |
| 419 | | // Only do this if the insertion was successful |
| 420 | | if (retVal && !t->right->parent) |
| 421 | | { |
| 422 | | t->right->setParent(t); |
| 423 | | t->calcHeights(); |
| 424 | | } |
| 425 | | |
| 426 | | return retVal; |
| 427 | | } |
| 428 | | |
| 429 | | return retVal; |
| 430 | | } |
| 431 | | } |
| 432 | | |
| 433 | | |
| 434 | | // Find the smallest item's node in a subtree t -- O(log n). |
| 435 | | tree_node* findMin(tree_node* t) const |
| 436 | | { |
| 437 | | if(t == NULL) |
| 438 | | { |
| 439 | | return t; |
| 440 | | } |
| 441 | | |
| 442 | | while(t->left != NULL) |
| 443 | | { |
| 444 | | t = t->left; |
| 445 | | } |
| 446 | | |
| 447 | | return t; |
| 448 | | } |
| 449 | | |
| 450 | | |
| 451 | | // Find the smallest item's node in a subtree t -- O(log n). |
| 452 | | tree_node* findMax(tree_node* t) const |
| 453 | | { |
| 454 | | if(t == NULL) |
| 455 | | { |
| 456 | | return t; |
| 457 | | } |
| 458 | | |
| 459 | | while(t->right != NULL) |
| 460 | | { |
| 461 | | t = t->right; |
| 462 | | } |
| 463 | | |
| 464 | | return t; |
| 465 | | } |
| 466 | | |
| 467 | | |
| 468 | | // Find item x's node in subtree t -- O(log n) |
| 469 | | tree_node* find(const T& x, tree_node* t) const |
| 470 | | { |
| 471 | | while(t != NULL) |
| 472 | | { |
| 473 | | if (x < t->element) |
| 474 | | { |
| 475 | | t = t->left; |
| 476 | | } |
| 477 | | else if (t->element < x) |
| 478 | | { |
| 479 | | t = t->right; |
| 480 | | } |
| 481 | | else |
| 482 | | { |
| 483 | | return t; // Match |
| 484 | | } |
| 485 | | } |
| 486 | | |
| 487 | | return NULL; // No match |
| 488 | | } |
| 489 | | |
| 490 | | |
| 491 | | // Clone a subtree -- O(n) |
| 492 | | tree_node* clone(const tree_node* t) const |
| 493 | | { |
| 494 | | if(t == NULL) |
| 495 | | { |
| 496 | | return NULL; |
| 497 | | } |
| 498 | | else |
| 499 | | { |
| 500 | | // Create a node with the left and right nodes and a parent set to NULL |
| 501 | | tree_node* retVal = global_alloc(tree_node(t->element, NULL, clone(t->left), clone(t->right))); |
| 502 | | |
| 503 | | // Now set our children's parent node reference |
| 504 | | if (retVal->left) { retVal->left->setParent(retVal); } |
| 505 | | if (retVal->right) { retVal->right->setParent(retVal); } |
| 506 | | |
| 507 | | return retVal; |
| 508 | | } |
| 509 | | } |
| 510 | | |
| 511 | | |
| 512 | | // Rotate binary tree node with left child. |
| 513 | | // Single rotation for case 1 -- O(1). |
| 514 | | void rotateWithLeftChild(tree_node*& k2) const |
| 515 | | { |
| 516 | | tree_node* k1 = k2->left; |
| 517 | | tree_node* k2Parent = k2->parent; |
| 518 | | |
| 519 | | k2->setLeft(k1->right); |
| 520 | | if (k2->left) { k2->left->setParent(k2); } |
| 521 | | |
| 522 | | k1->setRight(k2); |
| 523 | | if (k1->right) { k1->right->setParent(k1); } |
| 524 | | |
| 525 | | k2 = k1; |
| 526 | | k2->setParent(k2Parent); |
| 527 | | |
| 528 | | k2->right->calcHeights(); |
| 529 | | |
| 530 | | } |
| 531 | | |
| 532 | | |
| 533 | | // Rotate binary tree node with right child. |
| 534 | | // Single rotation for case 4 -- O(1). |
| 535 | | void rotateWithRightChild(tree_node*& k1) const |
| 536 | | { |
| 537 | | tree_node* k2 = k1->right; |
| 538 | | tree_node* k1Parent = k1->parent; |
| 539 | | |
| 540 | | k1->setRight(k2->left); |
| 541 | | if (k1->right) { k1->right->setParent(k1); } |
| 542 | | |
| 543 | | k2->setLeft(k1); |
| 544 | | if (k2->left) { k2->left->setParent(k2); } |
| 545 | | |
| 546 | | k1 = k2; |
| 547 | | k1->setParent(k1Parent); |
| 548 | | |
| 549 | | k1->left->calcHeights(); |
| 550 | | |
| 551 | | } |
| 552 | | |
| 553 | | |
| 554 | | // Double rotate binary tree node: first left child |
| 555 | | // with its right child; then node k3 with new left child. |
| 556 | | // Double rotation for case 2 -- O(1). |
| 557 | | void doubleWithLeftChild(tree_node*& k3) const |
| 558 | | { |
| 559 | | rotateWithRightChild(k3->left); |
| 560 | | rotateWithLeftChild(k3); |
| 561 | | } |
| 562 | | |
| 563 | | |
| 564 | | // Double rotate binary tree node: first right child |
| 565 | | // with its left child; then node k1 with new right child. |
| 566 | | // Double rotation for case 3 -- O(1). |
| 567 | | void doubleWithRightChild(tree_node*& k1) const |
| 568 | | { |
| 569 | | rotateWithLeftChild(k1->right); |
| 570 | | rotateWithRightChild(k1); |
| 571 | | } |
| 572 | | |
| 573 | | |
| 574 | | // Removes a node. Returns true if the node was on the left side of its parent -- O(1). |
| 575 | | void removeNode(tree_node*& node) |
| 576 | | { |
| 577 | | // It is a leaf, simply remove the item and disconnect the parent |
| 578 | | if (node->isLeft()) |
| 579 | | { |
| 580 | | node->parent->setLeft(NULL); |
| 581 | | } |
| 582 | | else // (node == node->parent->right) |
| 583 | | { |
| 584 | | if (node->parent) { node->parent->setRight(NULL); } |
| 585 | | } |
| 586 | | |
| 587 | | node->setParent(NULL); |
| 588 | | } |
| 589 | | |
| 590 | | |
| 591 | | // Swap one node with another -- O(1). |
| 592 | | void replaceNode(tree_node*& node1, tree_node*& node2) |
| 593 | | { |
| 594 | | // Save both parent references |
| 595 | | simple_set<T>* node1Parent = node1->parent; |
| 596 | | simple_set<T>* node2Parent = node2->parent; |
| 597 | | |
| 598 | | // First move node2 into node1's place |
| 599 | | if (node1Parent) |
| 600 | | { |
| 601 | | if (isLeft(node1)) |
| 602 | | { |
| 603 | | node1Parent->setLeft(node2); |
| 604 | | } |
| 605 | | else // node1 is on the right |
| 606 | | { |
| 607 | | node1Parent->setRight(node2); |
| 608 | | } |
| 609 | | } |
| 610 | | node2->setParent(node1Parent); |
| 611 | | |
| 612 | | // Now move node1 into node2's place |
| 613 | | if (node2Parent) |
| 614 | | { |
| 615 | | if (isLeft(node2)) |
| 616 | | { |
| 617 | | node2Parent->setLeft(node1); |
| 618 | | } |
| 619 | | else // node2 is on the right |
| 620 | | { |
| 621 | | node2Parent->setRight(node1); |
| 622 | | } |
| 623 | | } |
| 624 | | node1->setParent(node2Parent); |
| 625 | | } |
| 626 | | |
| 627 | | |
| 628 | | // Balances the tree starting at the root node |
| 629 | | void balanceTree() { balanceTree(m_root); } |
| 630 | | |
| 631 | | |
| 632 | | // Balance the tree starting at the given node -- O(n). |
| 633 | | void balanceTree(tree_node*& node) |
| 634 | | { |
| 635 | | if (node) |
| 636 | | { |
| 637 | | // First see what the balance factor for this node is |
| 638 | | int balFactor = node->balanceFactor(); |
| 639 | | |
| 640 | | if (balFactor < -1) |
| 641 | | { |
| 642 | | // See if we're heavy left of the left |
| 643 | | if(node->left->balanceFactor() < 0) |
| 644 | | { |
| 645 | | rotateWithLeftChild(node); |
| 646 | | } |
| 647 | | else // if (node->left->balanceFactor() > 0) |
| 648 | | { |
| 649 | | // We're heavy on the right of the left |
| 650 | | doubleWithLeftChild(node); |
| 651 | | } |
| 652 | | } |
| 653 | | else if (balFactor > 1) |
| 654 | | { |
| 655 | | // See if it we're heavy right of the right |
| 656 | | if(node->right->balanceFactor() > 0) |
| 657 | | { |
| 658 | | rotateWithRightChild(node); |
| 659 | | } |
| 660 | | else // if (node->right->balanceFactor() < 0) |
| 661 | | { |
| 662 | | // The element goes on the left of the right |
| 663 | | doubleWithRightChild(node); |
| 664 | | } |
| 665 | | } |
| 666 | | else // if (balFactor >= -1 && balFactor <= 1) |
| 667 | | { |
| 668 | | // We're balanced here, but are our children balanced? |
| 669 | | balanceTree(node->left); |
| 670 | | balanceTree(node->right); |
| 671 | | } |
| 672 | | } |
| 673 | | } |
| 674 | | |
| 675 | | |
| 676 | | // Recursive helper function for public size() |
| 677 | | int sizeRecurse(const tree_node* currentNode) const |
| 678 | | { |
| 679 | | int nodeCount = 1; |
| 680 | | if (currentNode->left != NULL) |
| 681 | | nodeCount += sizeRecurse(currentNode->left); |
| 682 | | if (currentNode->right != NULL) |
| 683 | | nodeCount += sizeRecurse(currentNode->right); |
| 684 | | return nodeCount; |
| 685 | | } |
| 686 | | |
| 687 | | |
| 688 | | #ifdef SIMPLE_SET_DEBUG |
| 689 | | // Debug. Print from the start node, down -- O(n log n). |
| 690 | | void printTree(std::ostream& out, tree_node* t=NULL, int numTabs=0, char lr='_') const |
| 691 | | { |
| 692 | | if(t != NULL) |
| 693 | | { |
| 694 | | for (int i =0; i < numTabs; i++) { out << " "; } out << "|_" << lr << "__ "; |
| 695 | | out << t->element << " {h = " << t->height() << ", b = " << t->balanceFactor() << "} "; |
| 696 | | // TODO: Reinstate out << std::hex << t << " (p = " << t->parent << ")" << std::dec; |
| 697 | | out << std::endl; |
| 698 | | |
| 699 | | printTree(out, t->left, numTabs + 1, '<'); |
| 700 | | printTree(out, t->right, numTabs + 1, '>'); |
| 701 | | } |
| 702 | | } |
| 703 | | #endif |
| 704 | | }; |
| 705 | | |
| 706 | | |
| 707 | | // |
| 708 | | // ======================> avl_tree_node |
| 709 | | // Member nodes of the simple_set's AVL tree |
| 710 | | // |
| 711 | | |
| 712 | | template <class T> class avl_tree_node |
| 713 | | { |
| 714 | | friend class simple_set<T>; |
| 715 | | friend class simple_set_iterator<T>; |
| 716 | | typedef avl_tree_node<T> tree_node; |
| 717 | | |
| 718 | | public: |
| 719 | | // Construction |
| 720 | | avl_tree_node(const T& theElement, avl_tree_node* p, avl_tree_node* lt, avl_tree_node* rt) |
| 721 | | : element(theElement), |
| 722 | | parent(p), |
| 723 | | left(lt), |
| 724 | | right(rt), |
| 725 | | m_height(1), |
| 726 | | m_balanceFactor(0) |
| 727 | | { } |
| 728 | | |
| 729 | | |
| 730 | | // Are we to our parent's left? |
| 731 | | bool isLeft() |
| 732 | | { |
| 733 | | if (parent && this == parent->left) |
| 734 | | { |
| 735 | | return true; |
| 736 | | } |
| 737 | | else |
| 738 | | { |
| 739 | | return false; |
| 740 | | } |
| 741 | | } |
| 742 | | |
| 743 | | |
| 744 | | // Are we a leaf node? |
| 745 | | bool isLeaf() { return !left && !right; } |
| 746 | | |
| 747 | | |
| 748 | | // Set the parent pointer |
| 749 | | void setParent(tree_node* p) |
| 750 | | { |
| 751 | | // Set our new parent |
| 752 | | parent = p; |
| 753 | | } |
| 754 | | |
| 755 | | |
| 756 | | // Set the left child pointer |
| 757 | | void setLeft(tree_node* l) |
| 758 | | { |
| 759 | | // Set our new left node |
| 760 | | left = l; |
| 761 | | } |
| 762 | | |
| 763 | | |
| 764 | | // Set the right child pointer |
| 765 | | void setRight(tree_node* r) |
| 766 | | { |
| 767 | | // Set our new right node |
| 768 | | right = r; |
| 769 | | } |
| 770 | | |
| 771 | | |
| 772 | | // Recover the height |
| 773 | | int height() const |
| 774 | | { |
| 775 | | // The height is equal to the maximum of the right or left side's height plus 1 |
| 776 | | // Trading memory for operation time can be done O(n) like this => |
| 777 | | // return max(left ? left->height() : 0, right ? right->height() : 0) + 1; |
| 778 | | return m_height; |
| 779 | | } |
| 780 | | |
| 781 | | |
| 782 | | // Recover the balance factor |
| 783 | | int balanceFactor() const |
| 784 | | { |
| 785 | | // The weight of a node is equal to the difference between |
| 786 | | // the weight of the left subtree and the weight of the |
| 787 | | // right subtree |
| 788 | | // |
| 789 | | // O(n) version => |
| 790 | | // return (right ? right->height() : 0) - (left ? left->height() : 0); |
| 791 | | // |
| 792 | | return m_balanceFactor; |
| 793 | | } |
| 794 | | |
| 795 | | |
| 796 | | private: |
| 797 | | // Calculates all of the heights for this node and its ancestors -- O(log n). |
| 798 | | void calcHeights() |
| 799 | | { |
| 800 | | int rightHeight = (right ? right->m_height : 0); |
| 801 | | int leftHeight = (left ? left->m_height : 0); |
| 802 | | |
| 803 | | // Calculate our own height and balance factor -- O(1) |
| 804 | | m_height = maxInt(rightHeight, leftHeight) + 1; |
| 805 | | m_balanceFactor = (rightHeight - leftHeight); |
| 806 | | |
| 807 | | // And our parent's height and balance factor (and recurse) -- O(log n) |
| 808 | | if (parent) |
| 809 | | { |
| 810 | | parent->calcHeights(); |
| 811 | | } |
| 812 | | } |
| 813 | | |
| 814 | | |
| 815 | | // Utility function - TODO replace |
| 816 | | int maxInt(const int& lhs, const int& rhs) const |
| 817 | | { |
| 818 | | return lhs > rhs ? lhs : rhs; |
| 819 | | } |
| 820 | | |
| 821 | | |
| 822 | | private: |
| 823 | | T element; |
| 824 | | |
| 825 | | avl_tree_node* parent; |
| 826 | | avl_tree_node* left; |
| 827 | | avl_tree_node* right; |
| 828 | | |
| 829 | | int m_height; |
| 830 | | int m_balanceFactor; |
| 831 | | }; |
| 832 | | |
| 833 | | |
| 834 | | // |
| 835 | | // ======================> simple_set_iterator |
| 836 | | // Iterator that allows for various set (AVL tree) navigation methods |
| 837 | | // Points to elements of the set, rather than AVL tree nodes. |
| 838 | | // |
| 839 | | // PUBLIC OPERATIONS: |
| 840 | | // current, first, last, next, count, indexof, byindex |
| 841 | | // |
| 842 | | |
| 843 | | template <class T> |
| 844 | | class simple_set_iterator |
| 845 | | { |
| 846 | | typedef avl_tree_node<T> tree_node; |
| 847 | | |
| 848 | | public: |
| 849 | | enum TraversalType { PRE_ORDER, IN_ORDER, POST_ORDER, LEVEL_ORDER }; |
| 850 | | |
| 851 | | public: |
| 852 | | // construction |
| 853 | | simple_set_iterator(simple_set<T>& set, const TraversalType& tt=IN_ORDER) |
| 854 | | : m_set(&set), |
| 855 | | m_traversalType(tt), |
| 856 | | m_currentNode(NULL), |
| 857 | | m_endNode(NULL) { } |
| 858 | | |
| 859 | | ~simple_set_iterator() { } |
| 860 | | |
| 861 | | |
| 862 | | // getters |
| 863 | | T* current() const { return m_currentNode; } |
| 864 | | |
| 865 | | |
| 866 | | // reset and return first item |
| 867 | | T* first() |
| 868 | | { |
| 869 | | m_currentNode = m_set->m_root; |
| 870 | | switch (m_traversalType) |
| 871 | | { |
| 872 | | case IN_ORDER: |
| 873 | | { |
| 874 | | // The current node is the smallest value |
| 875 | | m_currentNode = m_set->findMin(m_set->m_root); |
| 876 | | |
| 877 | | // The end case is the largest value |
| 878 | | m_endNode = m_set->findMax(m_set->m_root); |
| 879 | | |
| 880 | | return &m_currentNode->element; |
| 881 | | } |
| 882 | | |
| 883 | | default: |
| 884 | | { |
| 885 | | // TODO (better error message): |
| 886 | | printf("simple_set_iterator: Traversal type not yet supported.\n"); |
| 887 | | return NULL; |
| 888 | | } |
| 889 | | } |
| 890 | | return NULL; |
| 891 | | } |
| 892 | | |
| 893 | | |
| 894 | | T* last() |
| 895 | | { |
| 896 | | return NULL; |
| 897 | | } |
| 898 | | |
| 899 | | |
| 900 | | // advance according to current state and traversal type |
| 901 | | T* next() |
| 902 | | { |
| 903 | | if (m_currentNode == NULL) return NULL; |
| 904 | | |
| 905 | | switch (m_traversalType) |
| 906 | | { |
| 907 | | case IN_ORDER: |
| 908 | | { |
| 909 | | // You are at the end |
| 910 | | if (m_currentNode == m_endNode) |
| 911 | | return NULL; |
| 912 | | |
| 913 | | if (m_currentNode->right != NULL) |
| 914 | | { |
| 915 | | // Gather the furthest left node of right subtree |
| 916 | | m_currentNode = m_currentNode->right; |
| 917 | | while (m_currentNode->left != NULL) |
| 918 | | { |
| 919 | | m_currentNode = m_currentNode->left; |
| 920 | | } |
| 921 | | } |
| 922 | | else |
| 923 | | { |
| 924 | | // No right subtree? Move up the tree, looking for a left child link. |
| 925 | | tree_node* p = m_currentNode->parent; |
| 926 | | while (p != NULL && m_currentNode == p->right) |
| 927 | | { |
| 928 | | m_currentNode = p; |
| 929 | | p = p->parent; |
| 930 | | } |
| 931 | | m_currentNode = p; |
| 932 | | } |
| 933 | | |
| 934 | | return &m_currentNode->element; |
| 935 | | } |
| 936 | | |
| 937 | | default: |
| 938 | | { |
| 939 | | // TODO (better error message): |
| 940 | | printf("simple_set_iterator: Traversal type not yet supported.\n"); |
| 941 | | return NULL; |
| 942 | | } |
| 943 | | } |
| 944 | | |
| 945 | | return NULL; |
| 946 | | } |
| 947 | | |
| 948 | | |
| 949 | | // return the number of items available |
| 950 | | int count() |
| 951 | | { |
| 952 | | return m_set->size(); |
| 953 | | } |
| 954 | | |
| 955 | | |
| 956 | | // return the index of a given item in the virtual list |
| 957 | | // note: this function is destructive to any in-progress iterations! |
| 958 | | int indexof(T inData) |
| 959 | | { |
| 960 | | int index = 0; |
| 961 | | for (T* data = first(); data != last(); data = next(), index++) |
| 962 | | if (!(*data < inData) && !(inData < *data)) |
| 963 | | return index; |
| 964 | | return -1; |
| 965 | | } |
| 966 | | |
| 967 | | |
| 968 | | // return the indexed item in the list |
| 969 | | // note: this function is destructive to any in-progress iterations! |
| 970 | | T* byindex(int index) |
| 971 | | { |
| 972 | | int count = 0; |
| 973 | | for (T* data = first(); data != last(); data = next(), count++) |
| 974 | | if (count == index) |
| 975 | | return data; |
| 976 | | return NULL; |
| 977 | | } |
| 978 | | |
| 979 | | |
| 980 | | private: |
| 981 | | simple_set<T>* m_set; |
| 982 | | |
| 983 | | TraversalType m_traversalType; |
| 984 | | tree_node* m_currentNode; |
| 985 | | tree_node* m_endNode; |
| 986 | | }; |
| 987 | | |
| 988 | | #endif |
trunk/src/mess/drivers/hh_ucom4.c
| r245618 | r245619 | |
|---|
| 12 | 12 | @031 uPD553C 1979, Bambino Superstar Football (ET-03) |
| 13 | 13 | *042 uPD552C 1979, Tomy Space Attack |
| 14 | 14 | @048 uPD552C 1980, Tomy Tennis (TN-04) |
| 15 | @049 uPD553C 1979, Mego Mini-Vid Break Free |
| 15 | 16 | @055 uPD553C 1980, Bambino Laser Fight (ET-12) |
| 16 | 17 | *085 uPD650C 1980, Roland TR-808 |
| 17 | 18 | *102 uPD553C 1981, Bandai Block Out |
| r245618 | r245619 | |
|---|
| 19 | 20 | *128 uPD650C 1982, Roland TR-606 |
| 20 | 21 | 133 uPD650C 1982, Roland TB-303 -> tb303.c |
| 21 | 22 | @160 uPD553C 1982, Tomy Pac Man (TN-08) |
| 23 | @192 uPD553C 1982, Tomy Scramble (TN-10) |
| 22 | 24 | @202 uPD553C 1982, Epoch Astro Command |
| 23 | 25 | @206 uPD553C 1982, Epoch Dracula |
| 24 | | *209 uPD553C 1982, Tomy Caveman (TN-12) |
| 26 | @209 uPD553C 1982, Tomy Caveman (TN-12) |
| 25 | 27 | @258 uPD553C 1984, Tomy Alien Chase (TN-16) |
| 26 | 28 | |
| 27 | 29 | (* denotes not yet emulated by MESS, @ denotes it's in this driver) |
| 28 | 30 | |
| 29 | 31 | ***************************************************************************/ |
| 30 | 32 | |
| 33 | |
| 34 | |
| 35 | |
| 36 | /*************************************************************************** |
| 37 | |
| 38 | Mego Mini-Vid Break Free (manufactured in Japan) |
| 39 | * PCB label Mego 79 rev F |
| 40 | * NEC uCOM-43 MCU, labeled D553C 031 |
| 41 | * cyan VFD display Futaba DM-4.5 91 |
| 42 | |
| 43 | NOTE!: MESS external artwork is recommended |
| 44 | |
| 45 | ***************************************************************************/ |
| 46 | |
| 47 | |
| 48 | /*************************************************************************** |
| 49 | |
| 50 | Tomy(tronic) Caveman (manufactured in Japan) |
| 51 | * PCBs are labeled TN-12 2E114E03 |
| 52 | * NEC uCOM-43 MCU, labeled D553C 209 |
| 53 | * cyan/red/green VFD display NEC FIP8AM20T no. 2-42 |
| 54 | |
| 55 | NOTE!: MESS external artwork is recommended |
| 56 | |
| 57 | ***************************************************************************/ |
| 58 | |
| 59 | |
| 60 | /*************************************************************************** |
| 61 | |
| 62 | Tomy(tronic) Scramble (manufactured in Japan) |
| 63 | * PCBs are labeled TN-10 2E114E01 |
| 64 | * NEC uCOM-43 MCU, labeled D553C 192 |
| 65 | * cyan/red/green VFD display NEC FIP10CM20T no. 2-41 |
| 66 | |
| 67 | NOTE!: MESS external artwork is recommended |
| 68 | |
| 69 | ***************************************************************************/ |
| 70 | |
| 71 | |
| 31 | 72 | #include "emu.h" |
| 32 | 73 | #include "cpu/ucom4/ucom4.h" |
| 33 | 74 | #include "sound/speaker.h" |
| r245618 | r245619 | |
|---|
| 515 | 556 | Epoch Astro Command (manufactured in Japan) |
| 516 | 557 | * PCB label 96111 |
| 517 | 558 | * NEC uCOM-43 MCU, labeled D553C 202 |
| 518 | | * cyan/red VFD display NEC FIP9AM20T NO.42, with color overlay |
| 559 | * cyan/red VFD display NEC FIP9AM20T no. 42-42, with color overlay (FIP=fluorescent indicator panel) |
| 519 | 560 | |
| 520 | 561 | known releases: |
| 521 | 562 | - Japan: Astro Command |
| r245618 | r245619 | |
|---|
| 624 | 665 | Epoch Dracula (manufactured in Japan) |
| 625 | 666 | * PCB label 96121 |
| 626 | 667 | * NEC uCOM-43 MCU, labeled D553C 206 |
| 627 | | * cyan/red/green VFD display NEC FIP8BM20T (FIP=fluorescent indicator panel) |
| 668 | * cyan/red/green VFD display NEC FIP8BM20T no. 2-42 |
| 628 | 669 | |
| 629 | 670 | known releases: |
| 630 | 671 | - Japan: Dracula House, yellow case |
| r245618 | r245619 | |
|---|
| 717 | 758 | /*************************************************************************** |
| 718 | 759 | |
| 719 | 760 | Tomy(tronic) Tennis (manufactured in Japan) |
| 720 | | * board labeled TOMY TN-04 TENNIS |
| 761 | * PCB labeled TOMY TN-04 TENNIS |
| 721 | 762 | * NEC uCOM-44 MCU, labeled D552C 048 |
| 722 | | * VFD display NEC FIP11AM15T |
| 763 | * VFD display NEC FIP11AM15T tube no. 0F |
| 723 | 764 | |
| 724 | 765 | The initial release of this game was in 1979, known as Pro-Tennis, |
| 725 | 766 | it has a D553 instead of D552, with just a little over 50% ROM used. |
| r245618 | r245619 | |
|---|
| 876 | 917 | /*************************************************************************** |
| 877 | 918 | |
| 878 | 919 | Tomy(tronic) Pac-Man (manufactured in Japan) |
| 879 | | * boards are labeled TN-08 2E108E01 |
| 920 | * PCBs are labeled TN-08 2E108E01 |
| 880 | 921 | * NEC uCOM-43 MCU, labeled D553C 160 |
| 881 | | * cyan/red/green VFD display NEC FIP8AM18T |
| 922 | * cyan/red/green VFD display NEC FIP8AM18T no. 2-21 |
| 882 | 923 | * bright yellow round casing |
| 883 | 924 | |
| 884 | 925 | known releases: |
| r245618 | r245619 | |
|---|
| 984 | 1025 | /*************************************************************************** |
| 985 | 1026 | |
| 986 | 1027 | Tomy Alien Chase (manufactured in Japan) |
| 987 | | * boards are labeled TN-16 2E121B01 |
| 1028 | * PCBs are labeled TN-16 2E121B01 |
| 988 | 1029 | * NEC uCOM-43 MCU, labeled D553C 258 |
| 989 | 1030 | * red/green VFD display NEC FIP9AM24T, with color overlay, 2-sided* |
| 990 | 1031 | |