| 1346 | | |
|---|
| 1347 | | /* |
|---|
| 1348 | | * The "message memorization" package. |
|---|
| 1349 | | * |
|---|
| 1350 | | * Each call to "message_add(s)" will add a new "most recent" message |
|---|
| 1351 | | * to the "message recall list", using the contents of the string "s". |
|---|
| 1352 | | * |
|---|
| 1353 | | * The number of memorized messages is available as "message_num()". |
|---|
| 1354 | | * |
|---|
| 1355 | | * Old messages can be retrieved by "message_str(age)", where the "age" |
|---|
| 1356 | | * of the most recently memorized message is zero, and the oldest "age" |
|---|
| 1357 | | * which is available is "message_num() - 1". Messages outside this |
|---|
| 1358 | | * range are returned as the empty string. |
|---|
| 1359 | | * |
|---|
| 1360 | | * The messages are stored in a special manner that maximizes "efficiency", |
|---|
| 1361 | | * that is, we attempt to maximize the number of semi-sequential messages |
|---|
| 1362 | | * that can be retrieved, given a limited amount of storage space, without |
|---|
| 1363 | | * causing the memorization of new messages or the recall of old messages |
|---|
| 1364 | | * to be too expensive. |
|---|
| 1365 | | * |
|---|
| 1366 | | * We keep a buffer of chars to hold the "text" of the messages, more or |
|---|
| 1367 | | * less in the order they were memorized, and an array of offsets into that |
|---|
| 1368 | | * buffer, representing the actual messages, but we allow the "text" to be |
|---|
| 1369 | | * "shared" by two messages with "similar" ages, as long as we never cause |
|---|
| 1370 | | * sharing to reach too far back in the the buffer. |
|---|
| 1371 | | * |
|---|
| 1372 | | * The implementation is complicated by the fact that both the array of |
|---|
| 1373 | | * offsets, and the buffer itself, are both treated as "circular arrays" |
|---|
| 1374 | | * for efficiency purposes, but the strings may not be "broken" across |
|---|
| 1375 | | * the ends of the array. |
|---|
| 1376 | | * |
|---|
| 1377 | | * When we want to memorize a new message, we attempt to "reuse" the buffer |
|---|
| 1378 | | * space by checking for message duplication within the recent messages. |
|---|
| 1379 | | * |
|---|
| 1380 | | * Otherwise, if we need more buffer space, we grab a full quarter of the |
|---|
| 1381 | | * total buffer space at a time, to keep the reclamation code efficient. |
|---|
| 1382 | | * |
|---|
| 1383 | | * The "message_add()" function is rather "complex", because it must be |
|---|
| 1384 | | * extremely efficient, both in space and time, for use with the Borg. |
|---|
| 1385 | | */ |
|---|
| 1386 | | |
|---|
| 1387 | | |
|---|
| 1388 | | /* |
|---|
| 1389 | | * The next "free" index to use |
|---|
| 1390 | | */ |
|---|
| 1391 | | static u16b message__next; |
|---|
| 1392 | | |
|---|
| 1393 | | /* |
|---|
| 1394 | | * The index of the oldest message (none yet) |
|---|
| 1395 | | */ |
|---|
| 1396 | | static u16b message__last; |
|---|
| 1397 | | |
|---|
| 1398 | | /* |
|---|
| 1399 | | * The next "free" offset |
|---|
| 1400 | | */ |
|---|
| 1401 | | static u16b message__head; |
|---|
| 1402 | | |
|---|
| 1403 | | /* |
|---|
| 1404 | | * The offset to the oldest used char (none yet) |
|---|
| 1405 | | */ |
|---|
| 1406 | | static u16b message__tail; |
|---|
| 1407 | | |
|---|
| 1408 | | /* |
|---|
| 1409 | | * The array[MESSAGE_MAX] of offsets, by index |
|---|
| 1410 | | */ |
|---|
| 1411 | | static u16b *message__ptr; |
|---|
| 1412 | | |
|---|
| 1413 | | /* |
|---|
| 1414 | | * The array[MESSAGE_BUF] of chars, by offset |
|---|
| 1415 | | */ |
|---|
| 1416 | | static char *message__buf; |
|---|
| 1417 | | |
|---|
| 1418 | | /* |
|---|
| 1419 | | * The array[MESSAGE_MAX] of u16b for the types of messages |
|---|
| 1420 | | */ |
|---|
| 1421 | | static u16b *message__type; |
|---|
| 1422 | | |
|---|
| 1423 | | /* |
|---|
| 1424 | | * The array[MESSAGE_MAX] of u16b for the count of messages |
|---|
| 1425 | | */ |
|---|
| 1426 | | static u16b *message__count; |
|---|
| 1427 | | |
|---|
| 1428 | | |
|---|
| 1429 | | /* |
|---|
| 1430 | | * Table of colors associated to message-types |
|---|
| 1431 | | */ |
|---|
| 1432 | | static byte message__color[MSG_MAX]; |
|---|
| 1433 | | |
|---|
| 1434 | | |
|---|
| 1435 | | /* |
|---|
| 1436 | | * Calculate the index of a message |
|---|
| 1437 | | */ |
|---|
| 1438 | | static s16b message_age2idx(int age) |
|---|
| 1439 | | { |
|---|
| 1440 | | return ((message__next + MESSAGE_MAX - (age + 1)) % MESSAGE_MAX); |
|---|
| 1441 | | } |
|---|
| 1442 | | |
|---|
| 1443 | | |
|---|
| 1444 | | /* |
|---|
| 1445 | | * How many messages are "available"? |
|---|
| 1446 | | */ |
|---|
| 1447 | | s16b message_num(void) |
|---|
| 1448 | | { |
|---|
| 1449 | | /* Determine how many messages are "available" */ |
|---|
| 1450 | | return (message_age2idx(message__last - 1)); |
|---|
| 1451 | | } |
|---|
| 1452 | | |
|---|
| 1453 | | |
|---|
| 1454 | | |
|---|
| 1455 | | /* |
|---|
| 1456 | | * Recall the "text" of a saved message |
|---|
| 1457 | | */ |
|---|
| 1458 | | cptr message_str(s16b age) |
|---|
| 1459 | | { |
|---|
| 1460 | | static char buf[1024]; |
|---|
| 1461 | | s16b x; |
|---|
| 1462 | | u16b o; |
|---|
| 1463 | | cptr s; |
|---|
| 1464 | | |
|---|
| 1465 | | /* Forgotten messages have no text */ |
|---|
| 1466 | | if ((age < 0) || (age >= message_num())) return (""); |
|---|
| 1467 | | |
|---|
| 1468 | | /* Get the "logical" index */ |
|---|
| 1469 | | x = message_age2idx(age); |
|---|
| 1470 | | |
|---|
| 1471 | | /* Get the "offset" for the message */ |
|---|
| 1472 | | o = message__ptr[x]; |
|---|
| 1473 | | |
|---|
| 1474 | | /* Get the message text */ |
|---|
| 1475 | | s = &message__buf[o]; |
|---|
| 1476 | | |
|---|
| 1477 | | /* HACK - Handle repeated messages */ |
|---|
| 1478 | | if (message__count[x] > 1) |
|---|
| 1479 | | { |
|---|
| 1480 | | strnfmt(buf, sizeof(buf), "%s <%dx>", s, message__count[x]); |
|---|
| 1481 | | s = buf; |
|---|
| 1482 | | } |
|---|
| 1483 | | |
|---|
| 1484 | | /* Return the message text */ |
|---|
| 1485 | | return (s); |
|---|
| 1486 | | } |
|---|
| 1487 | | |
|---|
| 1488 | | |
|---|
| 1489 | | /* |
|---|
| 1490 | | * Recall the "type" of a saved message |
|---|
| 1491 | | */ |
|---|
| 1492 | | u16b message_type(s16b age) |
|---|
| 1493 | | { |
|---|
| 1494 | | /* Paranoia */ |
|---|
| 1495 | | if (!message__type) |
|---|
| 1496 | | return MSG_GENERIC; |
|---|
| 1497 | | |
|---|
| 1498 | | /* Forgotten messages are generic */ |
|---|
| 1499 | | if ((age < 0) || (age >= message_num())) |
|---|
| 1500 | | return MSG_GENERIC; |
|---|
| 1501 | | |
|---|
| 1502 | | /* Return the message type */ |
|---|
| 1503 | | return (message__type[message_age2idx(age)]); |
|---|
| 1504 | | } |
|---|
| 1505 | | |
|---|
| 1506 | | |
|---|
| 1507 | | /* |
|---|
| 1508 | | * Recall the "color" of a message type |
|---|
| 1509 | | */ |
|---|
| 1510 | | static byte message_type_color(u16b type) |
|---|
| 1511 | | { |
|---|
| 1512 | | byte color = message__color[type]; |
|---|
| 1513 | | |
|---|
| 1514 | | if (color == TERM_DARK) color = TERM_WHITE; |
|---|
| 1515 | | |
|---|
| 1516 | | return color; |
|---|
| 1517 | | } |
|---|
| 1518 | | |
|---|
| 1519 | | |
|---|
| 1520 | | /* |
|---|
| 1521 | | * Recall the "color" of a saved message |
|---|
| 1522 | | */ |
|---|
| 1523 | | byte message_color(s16b age) |
|---|
| 1524 | | { |
|---|
| 1525 | | return message_type_color(message_type(age)); |
|---|
| 1526 | | } |
|---|
| 1527 | | |
|---|
| 1528 | | |
|---|
| 1529 | | errr message_color_define(u16b type, byte color) |
|---|
| 1530 | | { |
|---|
| 1531 | | if (type >= MSG_MAX) return 1; |
|---|
| 1532 | | |
|---|
| 1533 | | /* Store the color */ |
|---|
| 1534 | | message__color[type] = color; |
|---|
| 1535 | | return 0; |
|---|
| 1536 | | } |
|---|
| 1537 | | |
|---|
| 1538 | | |
|---|
| 1539 | | /* |
|---|
| 1540 | | * Add a new message, with great efficiency |
|---|
| 1541 | | * |
|---|
| 1542 | | * We must ignore long messages to prevent internal overflow, since we |
|---|
| 1543 | | * assume that we can always get enough space by advancing "message__tail" |
|---|
| 1544 | | * by one quarter the total buffer space. |
|---|
| 1545 | | * |
|---|
| 1546 | | * We must not attempt to optimize using a message index or buffer space |
|---|
| 1547 | | * which is "far away" from the most recent entries, or we will lose a lot |
|---|
| 1548 | | * of messages when we "expire" the old message index and/or buffer space. |
|---|
| 1549 | | */ |
|---|
| 1550 | | void message_add(cptr str, u16b type) |
|---|
| 1551 | | { |
|---|
| 1552 | | int k, i, x, o; |
|---|
| 1553 | | size_t n; |
|---|
| 1554 | | |
|---|
| 1555 | | cptr s; |
|---|
| 1556 | | |
|---|
| 1557 | | cptr u; |
|---|
| 1558 | | char *v; |
|---|
| 1559 | | |
|---|
| 1560 | | |
|---|
| 1561 | | /*** Step 1 -- Analyze the message ***/ |
|---|
| 1562 | | |
|---|
| 1563 | | /* Hack -- Ignore "non-messages" */ |
|---|
| 1564 | | if (!str) return; |
|---|
| 1565 | | |
|---|
| 1566 | | /* Message length */ |
|---|
| 1567 | | n = strlen(str); |
|---|
| 1568 | | |
|---|
| 1569 | | /* Hack -- Ignore "long" messages */ |
|---|
| 1570 | | if (n >= MESSAGE_BUF / 4) return; |
|---|
| 1571 | | |
|---|
| 1572 | | |
|---|
| 1573 | | /*** Step 2 -- Attempt to optimize ***/ |
|---|
| 1574 | | |
|---|
| 1575 | | /* Get the "logical" last index */ |
|---|
| 1576 | | x = message_age2idx(0); |
|---|
| 1577 | | |
|---|
| 1578 | | /* Get the "offset" for the last message */ |
|---|
| 1579 | | o = message__ptr[x]; |
|---|
| 1580 | | |
|---|
| 1581 | | /* Get the message text */ |
|---|
| 1582 | | s = &message__buf[o]; |
|---|
| 1583 | | |
|---|
| 1584 | | /* Last message repeated? */ |
|---|
| 1585 | | if (streq(str, s)) |
|---|
| 1586 | | { |
|---|
| 1587 | | /* Increase the message count */ |
|---|
| 1588 | | message__count[x]++; |
|---|
| 1589 | | return; |
|---|
| 1590 | | } |
|---|
| 1591 | | |
|---|
| 1592 | | /*** Step 3 -- Attempt to optimize ***/ |
|---|
| 1593 | | |
|---|
| 1594 | | /* Limit number of messages to check */ |
|---|
| 1595 | | k = message_num() / 4; |
|---|
| 1596 | | |
|---|
| 1597 | | /* Limit number of messages to check */ |
|---|
| 1598 | | if (k > 32) k = 32; |
|---|
| 1599 | | |
|---|
| 1600 | | /* Start just after the most recent message */ |
|---|
| 1601 | | i = message__next; |
|---|
| 1602 | | |
|---|
| 1603 | | /* Check the last few messages for duplication */ |
|---|
| 1604 | | for ( ; k; k--) |
|---|
| 1605 | | { |
|---|
| 1606 | | u16b q; |
|---|
| 1607 | | |
|---|
| 1608 | | cptr old; |
|---|
| 1609 | | |
|---|
| 1610 | | /* Back up, wrap if needed */ |
|---|
| 1611 | | if (i-- == 0) i = MESSAGE_MAX - 1; |
|---|
| 1612 | | |
|---|
| 1613 | | /* Stop before oldest message */ |
|---|
| 1614 | | if (i == message__last) break; |
|---|
| 1615 | | |
|---|
| 1616 | | /* Index */ |
|---|
| 1617 | | o = message__ptr[i]; |
|---|
| 1618 | | |
|---|
| 1619 | | /* Extract "distance" from "head" */ |
|---|
| 1620 | | q = (message__head + MESSAGE_BUF - o) % MESSAGE_BUF; |
|---|
| 1621 | | |
|---|
| 1622 | | /* Do not optimize over large distances */ |
|---|
| 1623 | | if (q >= MESSAGE_BUF / 4) continue; |
|---|
| 1624 | | |
|---|
| 1625 | | /* Get the old string */ |
|---|
| 1626 | | old = &message__buf[o]; |
|---|
| 1627 | | |
|---|
| 1628 | | /* Continue if not equal */ |
|---|
| 1629 | | if (!streq(str, old)) continue; |
|---|
| 1630 | | |
|---|
| 1631 | | /* Get the next available message index */ |
|---|
| 1632 | | x = message__next; |
|---|
| 1633 | | |
|---|
| 1634 | | /* Advance 'message__next', wrap if needed */ |
|---|
| 1635 | | if (++message__next == MESSAGE_MAX) message__next = 0; |
|---|
| 1636 | | |
|---|
| 1637 | | /* Kill last message if needed */ |
|---|
| 1638 | | if (message__next == message__last) |
|---|
| 1639 | | { |
|---|
| 1640 | | /* Advance 'message__last', wrap if needed */ |
|---|
| 1641 | | if (++message__last == MESSAGE_MAX) message__last = 0; |
|---|
| 1642 | | } |
|---|
| 1643 | | |
|---|
| 1644 | | /* Assign the starting address */ |
|---|
| 1645 | | message__ptr[x] = message__ptr[i]; |
|---|
| 1646 | | |
|---|
| 1647 | | /* Store the message type */ |
|---|
| 1648 | | message__type[x] = type; |
|---|
| 1649 | | |
|---|
| 1650 | | /* Store the message count */ |
|---|
| 1651 | | message__count[x] = 1; |
|---|
| 1652 | | |
|---|
| 1653 | | /* Success */ |
|---|
| 1654 | | return; |
|---|
| 1655 | | } |
|---|
| 1656 | | |
|---|
| 1657 | | /*** Step 4 -- Ensure space before end of buffer ***/ |
|---|
| 1658 | | |
|---|
| 1659 | | /* Kill messages, and wrap, if needed */ |
|---|
| 1660 | | if (message__head + (n + 1) >= MESSAGE_BUF) |
|---|
| 1661 | | { |
|---|
| 1662 | | /* Kill all "dead" messages */ |
|---|
| 1663 | | for (i = message__last; TRUE; i++) |
|---|
| 1664 | | { |
|---|
| 1665 | | /* Wrap if needed */ |
|---|
| 1666 | | if (i == MESSAGE_MAX) i = 0; |
|---|
| 1667 | | |
|---|
| 1668 | | /* Stop before the new message */ |
|---|
| 1669 | | if (i == message__next) break; |
|---|
| 1670 | | |
|---|
| 1671 | | /* Get offset */ |
|---|
| 1672 | | o = message__ptr[i]; |
|---|
| 1673 | | |
|---|
| 1674 | | /* Kill "dead" messages */ |
|---|
| 1675 | | if (o >= message__head) |
|---|
| 1676 | | { |
|---|
| 1677 | | /* Track oldest message */ |
|---|
| 1678 | | message__last = i + 1; |
|---|
| 1679 | | } |
|---|
| 1680 | | } |
|---|
| 1681 | | |
|---|
| 1682 | | /* Wrap "tail" if needed */ |
|---|
| 1683 | | if (message__tail >= message__head) message__tail = 0; |
|---|
| 1684 | | |
|---|
| 1685 | | /* Start over */ |
|---|
| 1686 | | message__head = 0; |
|---|
| 1687 | | } |
|---|
| 1688 | | |
|---|
| 1689 | | |
|---|
| 1690 | | /*** Step 5 -- Ensure space for actual characters ***/ |
|---|
| 1691 | | |
|---|
| 1692 | | /* Kill messages, if needed */ |
|---|
| 1693 | | if (message__head + (n + 1) > message__tail) |
|---|
| 1694 | | { |
|---|
| 1695 | | /* Advance to new "tail" location */ |
|---|
| 1696 | | message__tail += (MESSAGE_BUF / 4); |
|---|
| 1697 | | |
|---|
| 1698 | | /* Kill all "dead" messages */ |
|---|
| 1699 | | for (i = message__last; TRUE; i++) |
|---|
| 1700 | | { |
|---|
| 1701 | | /* Wrap if needed */ |
|---|
| 1702 | | if (i == MESSAGE_MAX) i = 0; |
|---|
| 1703 | | |
|---|
| 1704 | | /* Stop before the new message */ |
|---|
| 1705 | | if (i == message__next) break; |
|---|
| 1706 | | |
|---|
| 1707 | | /* Get offset */ |
|---|
| 1708 | | o = message__ptr[i]; |
|---|
| 1709 | | |
|---|
| 1710 | | /* Kill "dead" messages */ |
|---|
| 1711 | | if ((o >= message__head) && (o < message__tail)) |
|---|
| 1712 | | { |
|---|
| 1713 | | /* Track oldest message */ |
|---|
| 1714 | | message__last = i + 1; |
|---|
| 1715 | | } |
|---|
| 1716 | | } |
|---|
| 1717 | | } |
|---|
| 1718 | | |
|---|
| 1719 | | |
|---|
| 1720 | | /*** Step 6 -- Grab a new message index ***/ |
|---|
| 1721 | | |
|---|
| 1722 | | /* Get the next available message index */ |
|---|
| 1723 | | x = message__next; |
|---|
| 1724 | | |
|---|
| 1725 | | /* Advance 'message__next', wrap if needed */ |
|---|
| 1726 | | if (++message__next == MESSAGE_MAX) message__next = 0; |
|---|
| 1727 | | |
|---|
| 1728 | | /* Kill last message if needed */ |
|---|
| 1729 | | if (message__next == message__last) |
|---|
| 1730 | | { |
|---|
| 1731 | | /* Advance 'message__last', wrap if needed */ |
|---|
| 1732 | | if (++message__last == MESSAGE_MAX) message__last = 0; |
|---|
| 1733 | | } |
|---|
| 1734 | | |
|---|
| 1735 | | |
|---|
| 1736 | | /*** Step 7 -- Insert the message text ***/ |
|---|
| 1737 | | |
|---|
| 1738 | | /* Assign the starting address */ |
|---|
| 1739 | | message__ptr[x] = message__head; |
|---|
| 1740 | | |
|---|
| 1741 | | /* Inline 'strcpy(message__buf + message__head, str)' */ |
|---|
| 1742 | | v = message__buf + message__head; |
|---|
| 1743 | | for (u = str; *u; ) *v++ = *u++; |
|---|
| 1744 | | *v = '\0'; |
|---|
| 1745 | | |
|---|
| 1746 | | /* Advance the "head" pointer */ |
|---|
| 1747 | | message__head += (n + 1); |
|---|
| 1748 | | |
|---|
| 1749 | | /* Store the message type */ |
|---|
| 1750 | | message__type[x] = type; |
|---|
| 1751 | | |
|---|
| 1752 | | /* Store the message count */ |
|---|
| 1753 | | message__count[x] = 1; |
|---|
| 1754 | | } |
|---|
| 1755 | | |
|---|
| 1756 | | |
|---|
| 1757 | | /* |
|---|
| 1758 | | * Initialize the "message" package |
|---|
| 1759 | | */ |
|---|
| 1760 | | errr messages_init(void) |
|---|
| 1761 | | { |
|---|
| 1762 | | /* Message variables */ |
|---|
| 1763 | | message__ptr = C_ZNEW(MESSAGE_MAX, u16b); |
|---|
| 1764 | | message__buf = C_ZNEW(MESSAGE_BUF, char); |
|---|
| 1765 | | message__type = C_ZNEW(MESSAGE_MAX, u16b); |
|---|
| 1766 | | message__count = C_ZNEW(MESSAGE_MAX, u16b); |
|---|
| 1767 | | |
|---|
| 1768 | | /* Init the message colors to white */ |
|---|
| 1769 | | memset(message__color, TERM_WHITE, MSG_MAX); |
|---|
| 1770 | | |
|---|
| 1771 | | /* Hack -- No messages yet */ |
|---|
| 1772 | | message__tail = MESSAGE_BUF; |
|---|
| 1773 | | |
|---|
| 1774 | | /* Success */ |
|---|
| 1775 | | return 0; |
|---|
| 1776 | | } |
|---|
| 1777 | | |
|---|
| 1778 | | |
|---|
| 1779 | | /* |
|---|
| 1780 | | * Free the "message" package |
|---|
| 1781 | | */ |
|---|
| 1782 | | void messages_free(void) |
|---|
| 1783 | | { |
|---|
| 1784 | | /* Free the messages */ |
|---|
| 1785 | | FREE(message__ptr); |
|---|
| 1786 | | FREE(message__buf); |
|---|
| 1787 | | FREE(message__type); |
|---|
| 1788 | | FREE(message__count); |
|---|
| 1789 | | } |
|---|
| 1790 | | |
|---|
| 1791 | | |
|---|
| 1792 | | |
|---|
| 1793 | | |
|---|
| 1794 | | |
|---|
| 1795 | | |
|---|
| 1796 | | |
|---|
