00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include <sys/types.h>
00034 #include <unistd.h>
00035 #include <iostream>
00036 #include <errno.h>
00037 #include <fcntl.h>
00038 #include <openssl/ssl.h>
00039 #include <openssl/err.h>
00040 #include <boost/lexical_cast.hpp>
00041 #include <pthread.h>
00042
00043 #include <math.h>
00044 #include "Util.h"
00045
00046 #include "hash_string.h"
00047 #include "LRUCache.h"
00048 #include "params.h"
00049 #include "SockUtil.h"
00050 #include "ScopedLock.h"
00051 #include "mace-macros.h"
00052 #include "m_net.h"
00053
00054 using std::cerr;
00055 using std::endl;
00056 using std::string;
00057 using boost::lexical_cast;
00058
00059 const size_t Util::DNS_CACHE_TIMEOUT;
00060 const unsigned Util::DNS_CACHE_SIZE;
00061 const uint16_t Util::DEFAULT_MACE_PORT;
00062 const bool Util::REPLAY = false;
00063
00064 static const int SUPPRESS_REVERSE_DNS = 1;
00065
00066 uint16_t Util::baseport = 0;
00067 static pthread_mutex_t ulock = PTHREAD_MUTEX_INITIALIZER;
00068
00069 std::string Util::getErrorString(int err) {
00070 char* errbuf = strerror(err);
00071 #if (defined _WINSOCK2_H || defined _WINSOCK_H)
00072 if (err > 10000 && err < 11032) {
00073 switch(err) {
00074 case WSAEINTR :
00075 errbuf = "Interrupted function call.";
00076 break;
00077
00078
00079
00080 case WSAEBADF :
00081 errbuf = "File handle is not valid.";
00082 break;
00083
00084
00085
00086 case WSAEACCES :
00087 errbuf = "Permission denied.";
00088 break;
00089
00090
00091
00092
00093
00094 case WSAEFAULT :
00095 errbuf = "Bad address.";
00096 break;
00097
00098
00099
00100 case WSAEINVAL :
00101 errbuf = "Invalid argument.";
00102 break;
00103
00104
00105
00106 case WSAEMFILE :
00107 errbuf = "Too many open files.";
00108 break;
00109
00110
00111
00112 case WSAEWOULDBLOCK :
00113 errbuf = "Resource temporarily unavailable.";
00114 break;
00115
00116
00117
00118 case WSAEINPROGRESS :
00119 errbuf = "Operation now in progress.";
00120 break;
00121
00122
00123
00124 case WSAEALREADY :
00125 errbuf = "Operation already in progress.";
00126 break;
00127
00128
00129
00130 case WSAENOTSOCK :
00131 errbuf = "Socket operation on nonsocket.";
00132 break;
00133
00134
00135
00136 case WSAEDESTADDRREQ :
00137 errbuf = "Destination address required.";
00138 break;
00139
00140
00141
00142 case WSAEMSGSIZE :
00143 errbuf = "Message too long.";
00144 break;
00145
00146
00147
00148 case WSAEPROTOTYPE :
00149 errbuf = "Protocol wrong type for socket.";
00150 break;
00151
00152
00153
00154 case WSAENOPROTOOPT :
00155 errbuf = "Bad protocol option.";
00156 break;
00157
00158
00159
00160 case WSAEPROTONOSUPPORT :
00161 errbuf = "Protocol not supported.";
00162 break;
00163
00164
00165
00166 case WSAESOCKTNOSUPPORT :
00167 errbuf = "Socket type not supported.";
00168 break;
00169
00170
00171
00172 case WSAEOPNOTSUPP :
00173 errbuf = "Operation not supported.";
00174 break;
00175
00176
00177
00178 case WSAEPFNOSUPPORT :
00179 errbuf = "Protocol family not supported.";
00180 break;
00181
00182
00183
00184 case WSAEAFNOSUPPORT :
00185 errbuf = "Address family not supported by protocol family.";
00186 break;
00187
00188
00189
00190 case WSAEADDRINUSE :
00191 errbuf = "Address already in use.";
00192 break;
00193
00194
00195
00196 case WSAEADDRNOTAVAIL :
00197 errbuf = "Cannot assign requested address.";
00198 break;
00199
00200
00201
00202 case WSAENETDOWN :
00203 errbuf = "Network is down.";
00204 break;
00205
00206
00207
00208 case WSAENETUNREACH :
00209 errbuf = "Network is unreachable.";
00210 break;
00211
00212
00213
00214 case WSAENETRESET :
00215 errbuf = "Network dropped connection on reset.";
00216 break;
00217
00218
00219
00220 case WSAECONNABORTED :
00221 errbuf = "Software caused connection abort.";
00222 break;
00223
00224
00225
00226 case WSAECONNRESET :
00227 errbuf = "Connection reset by peer.";
00228 break;
00229
00230
00231
00232 case WSAENOBUFS :
00233 errbuf = "No buffer space available.";
00234 break;
00235
00236
00237
00238 case WSAEISCONN :
00239 errbuf = "Socket is already connected.";
00240 break;
00241
00242
00243
00244 case WSAENOTCONN :
00245 errbuf = "Socket is not connected.";
00246 break;
00247
00248
00249
00250 case WSAESHUTDOWN :
00251 errbuf = "Cannot send after socket shutdown.";
00252 break;
00253
00254
00255
00256 case WSAETOOMANYREFS :
00257 errbuf = "Too many references.";
00258 break;
00259
00260
00261
00262 case WSAETIMEDOUT :
00263 errbuf = "Connection timed out.";
00264 break;
00265
00266
00267
00268 case WSAECONNREFUSED :
00269 errbuf = "Connection refused.";
00270 break;
00271
00272
00273
00274 case WSAELOOP :
00275 errbuf = "Cannot translate name.";
00276 break;
00277
00278
00279
00280 case WSAENAMETOOLONG :
00281 errbuf = "Name too long.";
00282 break;
00283
00284
00285
00286 case WSAEHOSTDOWN :
00287 errbuf = "Host is down.";
00288 break;
00289
00290
00291
00292 case WSAEHOSTUNREACH :
00293 errbuf = "No route to host.";
00294 break;
00295
00296
00297
00298 case WSAENOTEMPTY :
00299 errbuf = "Directory not empty.";
00300 break;
00301
00302
00303
00304 case WSAEPROCLIM :
00305 errbuf = "Too many processes.";
00306 break;
00307
00308
00309
00310 case WSAEUSERS :
00311 errbuf = "User quota exceeded.";
00312 break;
00313
00314
00315
00316 case WSAEDQUOT :
00317 errbuf = "Disk quota exceeded.";
00318 break;
00319
00320
00321
00322 case WSAESTALE :
00323 errbuf = "Stale file handle reference.";
00324 break;
00325
00326
00327
00328 case WSAEREMOTE :
00329 errbuf = "Item is remote.";
00330 break;
00331
00332
00333
00334 case WSASYSNOTREADY :
00335 errbuf = "Network subsystem is unavailable.";
00336 break;
00337
00338
00339
00340
00341
00342
00343
00344 case WSAVERNOTSUPPORTED :
00345 errbuf = "Winsock.dll version out of range.";
00346 break;
00347
00348
00349
00350 case WSANOTINITIALISED :
00351 errbuf = "Successful WSAStartup not yet performed.";
00352 break;
00353
00354
00355
00356 case WSAEDISCON :
00357 errbuf = "Graceful shutdown in progress.";
00358 break;
00359
00360
00361
00362 case WSAENOMORE :
00363 errbuf = "No more results.";
00364 break;
00365
00366
00367
00368 case WSAECANCELLED :
00369 errbuf = "Call has been canceled.";
00370 break;
00371
00372
00373
00374 case WSAEINVALIDPROCTABLE :
00375 errbuf = "Procedure call table is invalid.";
00376 break;
00377
00378
00379
00380 case WSAEINVALIDPROVIDER :
00381 errbuf = "Service provider is invalid.";
00382 break;
00383
00384
00385
00386 case WSAEPROVIDERFAILEDINIT :
00387 errbuf = "Service provider failed to initialize.";
00388 break;
00389
00390
00391
00392 case WSASYSCALLFAILURE :
00393 errbuf = "System call failure.";
00394 break;
00395
00396
00397
00398
00399
00400
00401
00402 case WSASERVICE_NOT_FOUND :
00403 errbuf = "Service not found.";
00404 break;
00405
00406
00407
00408 case WSATYPE_NOT_FOUND :
00409 errbuf = "Class type not found.";
00410 break;
00411
00412
00413
00414 case WSA_E_NO_MORE :
00415 errbuf = "No more results.";
00416 break;
00417
00418
00419
00420 case WSA_E_CANCELLED :
00421 errbuf = "Call was canceled.";
00422 break;
00423
00424
00425
00426 case WSAEREFUSED :
00427 errbuf = "Database query was refused.";
00428 break;
00429
00430
00431
00432 case WSAHOST_NOT_FOUND :
00433 errbuf = "Host not found.";
00434 break;
00435
00436
00437
00438 case WSATRY_AGAIN :
00439 errbuf = "Nonauthoritative host not found.";
00440 break;
00441
00442
00443
00444 case WSANO_RECOVERY :
00445 errbuf = "This is a nonrecoverable error.";
00446 break;
00447
00448
00449
00450 case WSANO_DATA :
00451 errbuf = "Valid name, no data record of requested type.";
00452 break;
00453
00454
00455
00456 case WSA_QOS_RECEIVERS :
00457 errbuf = "QOS receivers.";
00458 break;
00459
00460
00461
00462 case WSA_QOS_SENDERS :
00463 errbuf = "QOS senders.";
00464 break;
00465
00466
00467
00468 case WSA_QOS_NO_SENDERS :
00469 errbuf = "No QOS senders.";
00470 break;
00471
00472
00473
00474 case WSA_QOS_NO_RECEIVERS :
00475 errbuf = "QOS no receivers.";
00476 break;
00477
00478
00479
00480 case WSA_QOS_REQUEST_CONFIRMED :
00481 errbuf = "QOS request confirmed.";
00482 break;
00483
00484
00485
00486 case WSA_QOS_ADMISSION_FAILURE :
00487 errbuf = "QOS admission error.";
00488 break;
00489
00490
00491
00492 case WSA_QOS_POLICY_FAILURE :
00493 errbuf = "QOS policy failure.";
00494 break;
00495
00496
00497
00498 case WSA_QOS_BAD_STYLE :
00499 errbuf = "QOS bad style.";
00500 break;
00501
00502
00503
00504 case WSA_QOS_BAD_OBJECT :
00505 errbuf = "QOS bad object.";
00506 break;
00507
00508
00509
00510 case WSA_QOS_TRAFFIC_CTRL_ERROR :
00511 errbuf = "QOS traffic control error.";
00512 break;
00513
00514
00515
00516 case WSA_QOS_GENERIC_ERROR :
00517 errbuf = "QOS generic error.";
00518 break;
00519
00520
00521
00522 case WSA_QOS_ESERVICETYPE :
00523 errbuf = "QOS service type error.";
00524 break;
00525
00526
00527
00528 case WSA_QOS_EFLOWSPEC :
00529 errbuf = "QOS flowspec error.";
00530 break;
00531
00532
00533
00534 case WSA_QOS_EPROVSPECBUF :
00535 errbuf = "Invalid QOS provider buffer.";
00536 break;
00537
00538
00539
00540 case WSA_QOS_EFILTERSTYLE :
00541 errbuf = "Invalid QOS filter style.";
00542 break;
00543
00544
00545
00546 case WSA_QOS_EFILTERTYPE :
00547 errbuf = "Invalid QOS filter type.";
00548 break;
00549
00550
00551
00552 case WSA_QOS_EFILTERCOUNT :
00553 errbuf = "Incorrect QOS filter count.";
00554 break;
00555
00556
00557
00558 case WSA_QOS_EOBJLENGTH :
00559 errbuf = "Invalid QOS object length.";
00560 break;
00561
00562
00563
00564 case WSA_QOS_EFLOWCOUNT :
00565 errbuf = "Incorrect QOS flow count.";
00566 break;
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576 case WSA_QOS_EPOLICYOBJ :
00577 errbuf = "Invalid QOS policy object.";
00578 break;
00579
00580
00581
00582 case WSA_QOS_EFLOWDESC :
00583 errbuf = "Invalid QOS flow descriptor.";
00584 break;
00585
00586
00587
00588 case WSA_QOS_EPSFLOWSPEC :
00589 errbuf = "Invalid QOS provider-specific flowspec.";
00590 break;
00591
00592
00593
00594 case WSA_QOS_EPSFILTERSPEC :
00595 errbuf = "Invalid QOS provider-specific filterspec.";
00596 break;
00597
00598
00599
00600 case WSA_QOS_ESDMODEOBJ :
00601 errbuf = "Invalid QOS shape discard mode object.";
00602 break;
00603
00604
00605
00606 case WSA_QOS_ESHAPERATEOBJ :
00607 errbuf = "Invalid QOS shaping rate object.";
00608 break;
00609
00610
00611
00612 case WSA_QOS_RESERVED_PETYPE :
00613 errbuf = "Reserved policy QOS element type.";
00614 break;
00615
00616
00617
00618 }
00619 }
00620 #endif
00621 return std::string(errbuf);
00622 }
00623
00624 std::string Util::getSslErrorString() {
00625 unsigned long e = ERR_get_error();
00626 if (e) {
00627 size_t len = 1024;
00628 char buf[len];
00629 ERR_error_string_n(e, buf, len);
00630 return string(buf);
00631 }
00632 else {
00633 return "";
00634 }
00635 }
00636
00637 MaceAddr Util::getMaceAddr(const std::string& hostname) throw (AddressException) {
00638 size_t i = hostname.find('/');
00639 std::string pub = hostname;
00640 SockAddr proxyaddr;
00641 if (i != std::string::npos) {
00642 proxyaddr = SockUtil::getSockAddr(hostname.substr(i + 1));
00643 pub = hostname.substr(0, i);
00644 }
00645
00646
00647
00648 return MaceAddr(SockUtil::getSockAddr(pub), proxyaddr);
00649 }
00650
00651 uint16_t Util::getPort() {
00652 if (baseport == 0) {
00653 ScopedLock sl(ulock);
00654 if (params::containsKey(params::MACE_LOCAL_ADDRESS)) {
00655 std::string hostname = params::get<string>(params::MACE_LOCAL_ADDRESS);
00656 if (hostname.find('/') != std::string::npos) {
00657 hostname = hostname.substr(0, hostname.find('/'));
00658 }
00659 size_t i = hostname.find(':');
00660 if (i != std::string::npos) {
00661 baseport = lexical_cast<int16_t>(hostname.substr(i + 1));
00662 }
00663 }
00664 if (baseport == 0) {
00665 baseport = params::get(params::MACE_PORT, DEFAULT_MACE_PORT);
00666 }
00667 }
00668 return baseport;
00669 }
00670
00671 const MaceAddr& Util::getMaceAddr() throw (AddressException) {
00672 static MaceAddr maddr = SockUtil::NULL_MACEADDR;
00673
00674 if (maddr != SockUtil::NULL_MACEADDR) {
00675 return maddr;
00676 }
00677
00678 if (params::containsKey(params::MACE_LOCAL_ADDRESS)) {
00679 maddr = getMaceAddr(params::get<string>(params::MACE_LOCAL_ADDRESS));
00680 if (!maddr.isUnroutable()) {
00681 baseport = maddr.local.port;
00682 }
00683 }
00684 else {
00685 maddr.local.addr = getAddr();
00686 maddr.local.port = getPort();
00687 }
00688
00689 return maddr;
00690 }
00691
00692 int Util::getAddr() throw (AddressException) {
00693 static int ipaddr = 0;
00694 if (ipaddr) {
00695 return ipaddr;
00696 }
00697
00698 ipaddr = getAddr(getHostname());
00699 return ipaddr;
00700 }
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716 int Util::getAddr(const std::string& hostname) throw (AddressException) {
00717 ADD_SELECTORS("Util::getAddr");
00718
00719 typedef mace::LRUCache<std::string, int> DnsCache;
00720 static DnsCache dnsCache(DNS_CACHE_SIZE, DNS_CACHE_TIMEOUT);
00721 static bool allowLoopback = params::get<bool>(params::MACE_ADDRESS_ALLOW_LOOPBACK, false);
00722 static bool warnLoopback = params::get(params::MACE_WARN_LOOPBACK, true);
00723 int r = 0;
00724 ScopedLock sl(ulock);
00725 if (dnsCache.containsKey(hostname)) {
00726 r = dnsCache.get(hostname);
00727 }
00728 else {
00729 hostent* he = gethostbyname(hostname.c_str());
00730 if (!he || he->h_length != sizeof(struct in_addr)) {
00731 if (hostname.find(':') != std::string::npos) {
00732 throw AddressException("Util::getAddr: bad hostname: " + hostname);
00733 }
00734 throw AddressException("gethostbyname " + hostname + ": " + getErrorString(h_errno));
00735 }
00736
00737 r = ((in_addr*)(he->h_addr_list[0]))->s_addr;
00738 dnsCache.add(hostname, r);
00739 }
00740 sl.unlock();
00741
00742 if ((r & 0x000000ff) == 0x7f) {
00743 if (warnLoopback) {
00744 macewarn << "hostname " << hostname << " is the loopback." << Log::endl;
00745 }
00746 if (!allowLoopback) {
00747 ABORT("Loopback address detected, but parameter MACE_ADDRESS_ALLOW_LOOPBACK not set to true");
00748 }
00749 }
00750
00751 return r;
00752 }
00753
00754 std::string Util::getAddrString(const MaceAddr& addr, bool resolve) {
00755 std::ostringstream out;
00756 printAddrString(out, addr, resolve);
00757 return out.str();
00758 }
00759
00760 void Util::printAddrString(std::ostream& out, const MaceAddr& addr, bool resolve) {
00761 printAddrString(out, addr.local, resolve);
00762 if(addr.proxy != SockUtil::NULL_MSOCKADDR) {
00763 out << "/";
00764 printAddrString(out, addr.proxy, resolve);
00765 };
00766 }
00767
00768 std::string Util::getAddrString(const SockAddr& addr, bool resolve) {
00769 std::ostringstream out;
00770 printAddrString(out, addr, resolve);
00771 return out.str();
00772 }
00773
00774 void Util::printAddrString(std::ostream& r, const SockAddr& addr, bool resolve) {
00775 if (addr.port == 0) {
00776 r << "(NAT):" << addr.addr;
00777 return;
00778 }
00779 if (resolve) {
00780 try {
00781 r << getHostname(addr.addr);
00782 }
00783 catch (const AddressException& e) {
00784 printAddrString(r, addr.addr);
00785 }
00786 }
00787 else {
00788 printAddrString(r, addr.addr);
00789 }
00790 r << ":" << addr.port;
00791 }
00792
00793 std::string Util::getAddrString(const std::string& hostname) throw (AddressException) {
00794 std::ostringstream out;
00795 printAddrString(out, hostname);
00796 return out.str();
00797 }
00798
00799 void Util::printAddrString(std::ostream& out, const std::string& hostname) throw (AddressException) {
00800 printAddrString(out, getAddr(hostname));
00801 }
00802
00803 std::string Util::getAddrString(int ipaddr) {
00804 struct sockaddr_in in;
00805 in.sin_addr.s_addr = ipaddr;
00806 std::string r(inet_ntoa(in.sin_addr));
00807 return r;
00808 }
00809
00810 void Util::printAddrString(std::ostream& out, int ipaddr) {
00811 struct sockaddr_in in;
00812 in.sin_addr.s_addr = ipaddr;
00813 out << inet_ntoa(in.sin_addr);
00814 }
00815
00816 int Util::getHostByName(const std::string& hostname) throw (AddressException) {
00817 return getAddr(hostname);
00818 }
00819
00820 std::string Util::getHostByAddr(int ipaddr) {
00821 return getHostname(ipaddr);
00822 }
00823
00824 std::string Util::getHostname() {
00825 static std::string s;
00826 if (s.empty()) {
00827 ScopedLock sl(ulock);
00828 char hostname[512];
00829 ASSERT(gethostname(hostname, sizeof(hostname)) == 0);
00830 s = hostname;
00831 }
00832 return s;
00833 }
00834
00835 bool Util::isPrivateAddr(uint32_t a) {
00836
00837
00838
00839 static uint32_t s8 = ntohl(inet_addr("10.0.0.1"));
00840 static uint32_t s12b = ntohl(inet_addr("172.16.0.0"));
00841 static uint32_t s12e = ntohl(inet_addr("172.31.255.255"));
00842 static uint32_t s16 = ntohl(inet_addr("192.168.0.0"));
00843
00844 a = ntohl(a);
00845
00846 uint32_t t = a & s8;
00847 if (t == s8) {
00848 return true;
00849 }
00850
00851 t = a & s16;
00852 if (t == s16) {
00853 return true;
00854 }
00855
00856 t = a;
00857 if ((t >= s12b) && (t <= s12e)) {
00858 return true;
00859 }
00860
00861 return false;
00862 }
00863
00864 bool Util::isHostReachable(const MaceKey& k) {
00865 static bool isReachableSet = false;
00866 static bool isReachable = false;
00867
00868 if (!isReachableSet &&
00869 params::containsKey(params::MACE_ALL_HOSTS_REACHABLE)) {
00870 isReachable = params::get<int>(params::MACE_ALL_HOSTS_REACHABLE);
00871 isReachableSet = true;
00872 }
00873
00874 if (isReachableSet && isReachable) {
00875 return true;
00876 }
00877
00878 const MaceAddr& ma = k.getMaceAddr();
00879 if ((ma.proxy != SockUtil::NULL_MSOCKADDR) && (ma.proxy != getMaceAddr().local)) {
00880
00881 return false;
00882 }
00883 return true;
00884 }
00885
00886 std::string Util::getHostname(const MaceKey& k) throw (AddressException) {
00887 const MaceAddr& ma = k.getMaceAddr();
00888 uint32_t h = ma.local.addr;
00889 if (isHostReachable(k)) {
00890 if ((ma.proxy != SockUtil::NULL_MSOCKADDR) && (ma.proxy != getMaceAddr().local)) {
00891
00892 h = ma.proxy.addr;
00893 }
00894 }
00895 else {
00896 throw UnreachablePrivateAddressException(k.addressString());
00897 }
00898
00899 return getHostname(h);
00900 }
00901
00902 std::string Util::getHostname(const std::string& ipaddr) throw (AddressException) {
00903 in_addr_t a = inet_addr(ipaddr.c_str());
00904 if (a == INADDR_NONE) {
00905 throw AddressException("getHostname passed bad address: " + ipaddr);
00906 }
00907
00908 return Util::getHostname(a);
00909 }
00910
00911 std::string Util::getHostname(int ipaddr) {
00912 typedef mace::LRUCache<int, std::string> ReverseDnsCache;
00913 static ReverseDnsCache dnsCache(DNS_CACHE_SIZE, DNS_CACHE_TIMEOUT);
00914
00915 string r;
00916 ScopedLock sl(ulock);
00917
00918 if (dnsCache.containsKey(ipaddr)) {
00919 r = dnsCache.get(ipaddr);
00920 }
00921 else {
00922 struct hostent* he = (SUPPRESS_REVERSE_DNS ? 0 : gethostbyaddr((char*)&ipaddr, sizeof(ipaddr), AF_INET));
00923 if (he == 0) {
00924 struct sockaddr_in in;
00925 in.sin_addr.s_addr = ipaddr;
00926 r.append(inet_ntoa(in.sin_addr));
00927 dnsCache.add(ipaddr, r);
00928 }
00929 else {
00930 r.append(he->h_name);
00931 dnsCache.add(ipaddr, r);
00932 }
00933 }
00934
00935 return r;
00936 }
00937
00938 mace::map<int, int> Util::makeMap(int first ...) {
00939 mace::map<int, int> r;
00940 va_list ap;
00941 va_start(ap, first);
00942 do {
00943 int x = va_arg(ap, int);
00944 r[first] = x;
00945 first = va_arg(ap, int);
00946 } while (first);
00947 va_end(ap);
00948
00949 return r;
00950 }
00951
00952
00953
00954
00955
00956
00957
00958
00959
00960 void Util::nodeSetDiff(const NodeSet& prev, const NodeSet& cur,
00961 NodeSet& added, NodeSet& removed) {
00962 NodeSet::const_iterator ai = cur.begin();
00963 NodeSet::const_iterator ri = prev.begin();
00964 while (ai != cur.end() || ri != prev.end()) {
00965 if (ai == cur.end()) {
00966 removed.insert(*ri);
00967 ri++;
00968 }
00969 else if (ri == prev.end()) {
00970 added.insert(*ai);
00971 ai++;
00972 }
00973 else if (*ai == *ri) {
00974 ai++;
00975 ri++;
00976 }
00977 else if (*ai < *ri) {
00978 added.insert(*ai);
00979 ai++;
00980 }
00981 else {
00982 ASSERT(*ri < *ai);
00983 removed.insert(*ri);
00984 ri++;
00985 }
00986 }
00987 }