- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章DDNS 的工作原理及其在 Linux 上的实现由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
ddns 工作原理的分析 ddns 的实现最根本的一点是当主机的 ip 地址发生变化的时候,实现 dns 映射信息的及时更新,应用程序需要及时地获得这一信息,主要的方法可分为两大类:
一类是轮询机制,即:应用程序每隔一定的时间,去从查询主机当前的 ip 地址,并与之前的进行比较,从而判断网络地址是否发生了变化。显然,这种方法不仅效率低下,而且对每次查询 ip 地址的时间间隔很难得到一个折中的数值。 第二类方法是异步实现方式,即:每当主机的 ip 地址发生变化的时候,应用程序能够被及时地通知到。这的确是一个简单而又高效的方法,但与此同时,另一个问题又产生了,那就是:通知源又应该由谁来担当呢?显然,这是处于用户空间的应用程序无法胜任的。于是,我们想到了让内核来充当这一消息源。这样,在内核空间和用户空间之间就需要通过消息来进行通信了。 在 linux 下用户空间与内核空间的信息交互方式有许多种,比如:软中断、系统调用、netlink 等等。关于这些通信方式的介绍以及其各自的优缺点并不在本文的讨论范围内,您可以自行查看.
在这许多种通信方式中,netlink 凭借其标准的 socket api、模块化实现、异步通信机制、多播机制等等多种优势,成为了内核与越来越多应用程序之间交互的主要方式。在 linux 的内核中,已经为我们封装了使用 netlink 对特定网络状态变化进行消息通知的功能,这就是著名的 rtnetlink。有关 netlink 在内核空间实现的详细代码以及其 api 参数的介绍,您可以自行查看参考资源,本文在此不作过多的赘述。 本文讨论的重点是针对 ddns 这一特定的应用,演示 rtnetlink 检测到 ip 地址发生了变化、并将消息告知用户空间的应用程序的整个过程,以及应用程序利用 netlink 套接字接收消息、并告知 dns 服务器的实现方法.
ddns 工作流程的简单介绍 结合上述对 ddns 工作原理的分析,我们可以将 ddns 的工作流程简单地用图 1 来表示: 图 1. ddns 的工作流程图 。
从图 1 中可以看到,ddns 的工作流程主要有三个部分:
应用程序实时感知到 ip 地址发生了变化,如上介绍,利用基于 netlink 的异步通知机制可以让应用程序及时得到内核空间对这些事件的“通知”,具体可以分为如下 5 个步骤:
1、内核空间初始化 rtnetlink 模块,创建 netlink_route 协议簇类型的 netlink 套接字; 2、用户空间创建 netlink_route 协议簇类型的 netlink 套接字,并且绑定到 rtmgrp_ipv4_ifaddr 组播 group 中; 3、用户空间接收从内核空间发来的消息,如果没有消息,则阻塞自身; 4、当主机被分配了新的 ipv4 地址,内核空间通过 netlink_broadcast,将 rtm_newaddr 消息发送到 rtnlgrp_ipv4_ifaddr 组播 group 中 ; 5、用户空间接收消息,进行验证、处理; 。
应用程序接收到“通知”后,把 dns update 信息发送给 dns 服务器,目的是将更新后的 ip 地址及时地通知 dns 服务器,以便网络上的主机仍然能够通过原来的域名访问到自己,通用的做法是利用开源软件 nsupdate 发送 dns update 信息给 dns 服务器以实现 dns 信息的动态更新。 最后,对应于第一部分 netlink 套接字的创建,用户空间和内核空间关闭所创建的 netlink 套接字.
下文将详细阐述其中的每一环节及其实现.
内核空间 rtnetlink 检测 ip 地址变化的实现与分析 在我们开始利用 netlink 套接字、实现与内核通信的应用程序之前,先来分析一下内核空间的 rtnetlink 模块是如何工作的。 内核空间 rtnetlink 的初始化 清单 1. rtnetlink 的初始化 。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/*
以下代码摘自 linux kernel 2.6.18, net/core/rtnetlink.c 文件,
并只选择了与本主题相关的最重要的部分,其他的都用省略号略过,之后的各清单也一样。
*/
void
__init rtnetlink_init(
void
)
{
......
rtnl = netlink_kernel_create(netlink_route, rtnlgrp_max, rtnetlink_rcv, this_module);
if
(rtnl == null)
panic(
"rtnetlink_init: cannot initialize rtnetlink "
);
......
}
|
从清单 1 中可以看到: 在 rtnetlink 进行初始化的时候,首先会调用 netlink_kernel_create 来创建一个 netlink_route 类型的 netlink 套接字,并指定接收函数为 rtnetlink_rcv,有关 rtnetlink_rcv 的实现细节可以查阅内核 net/core/rtnetlink.c 文件。这里需要指出的是,netlink 提供了包括 netlink_route、netlink_firewall、netlink_inet_diag 等在内的多种协议簇(详细列表及各协议簇的含义可以自行查看参考资源),其中 netlink_route 类型提供了网络地址发生变化的消息,这正是 ddns 需要用到的。 内核空间 ip 地址变化事件的通知过程 引起主机 ip 地址变化的原因有很多种,如:dhcp 分配的 ip 过期、用户手动修改了 ip 等等。无论何种原因,最终都会触发内核空间对相应事件的通知机制,这里以最常用的修改 ipv4 地址的工具 ifconfig 为例。 ifconfig 先是创建一个 af_inet 的 socket,然后通过系统调用 ioctl 来完成配置的,ioctl 在内核中对应的函数是 sys_ioctl,对于 ip 地址、子网掩码、默认网关等配置的修改,其最终会调用 devinet_ioctl。devinet_ioctl 函数处理包括 get、set 在内的多种命令,与 ddns 应用有关的是 set 类命令,图 2 给出了 siocsifaddr 命令(设置网络地址)的 ifconfig 调用树: 图 2. siocsifaddr 命令的 ifconfig 调用树 。
从图 2 中可以看到,当用户使用 ifconfig 对主机的 ip 地址作了修改,内核在进行了新地址的设置之后,会调用 rtmsg_ifa,传递的事件为 rtm_newaddr。 清单 2. rtmsg_ifa 发送 ip 地址变化消息 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/*
以下代码摘自 linux kernel 2.6.18, net/ipv4/devinet.c 文件
*/
static
void
rtmsg_ifa(
int
event,
struct
in_ifaddr* ifa)
{
int
size = nlmsg_space(
sizeof
(
struct
ifaddrmsg) + 128);
struct
sk_buff *skb = alloc_skb(size, gfp_kernel);
if
(!skb)
netlink_set_err(rtnl, 0, rtnlgrp_ipv4_ifaddr, enobufs);
else
if
(inet_fill_ifaddr(skb, ifa, 0, 0, event, 0) < 0) {
kfree_skb(skb);
netlink_set_err(rtnl, 0, rtnlgrp_ipv4_ifaddr, einval);
}
else
{
netlink_broadcast(rtnl, skb, 0, rtnlgrp_ipv4_ifaddr, gfp_kernel);
}
}
|
从清单 2 中可以看到,rtmsg_ifa 的实现主要包括: 首先分配了一块类型为 struct sk_buff 的空间用于存放需要发送的消息内容。 随后,调用 inet_fill_ifaddr 将消息填充至上述缓存(有关消息的格式,您可以自行查看参考资源)。值得注意的是,rtm_newaddr 被作为 nlmsg_type 封装到了内核发送给应用程序的 netlink 消息头 nlmsghdr 中,这样用户空间的应用程序在接收后就能够根据 type 来分别处理不同类型的消息了。 rtmsg_ifa 的最后是调用了 netlink_broadcast 将上述封装完毕的 sk_buff 结构广播到 rtnlgrp_ipv4_ifaddr 这个 group,以下是内核空间组播 group 与用户空间组播 group 的对应关系: 清单 3. 内核空间组播 group 与用户空间组播 group 的对应关系 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/*
以下代码摘自 linux kernel 2.6.18, include/linux/rtnetlink.h 文件
*/
/* rtnetlink multicast groups */
enum
rtnetlink_groups {
rtnlgrp_none,
#define rtnlgrp_none rtnlgrp_none
rtnlgrp_link,
#define rtnlgrp_link rtnlgrp_link
.....
rtnlgrp_ipv4_ifaddr,
#define rtnlgrp_ipv4_ifaddr rtnlgrp_ipv4_ifaddr
......
};
#ifndef __kernel__
/* rtnetlink multicast groups - backwards compatibility for userspace */
#define rtmgrp_link 1
#define rtmgrp_notify 2
......
#define rtmgrp_ipv4_ifaddr 0x10
......
#endif
|
综上所述,当主机的 ip 地址发生变化时,内核会向所有 rtnlgrp_ipv4_ifaddr 组播成员发送 rtm_newaddr 消息。因此,在用户空间创建 netlink 套接字时,只需要加入到 rtmgrp_ipv4_ifaddr 这个组播 group 中,就可以实现当本机 ip 地址有更新的时候,ddns 应用程序能够异步地收到内核空间发来的通知消息了.
用户空间 netlink socket 的创建、绑定与消息接收处理 用户空间创建 netlink 套接字 用户空间的 netlink socket 相关操作与标准 socket api 完全一致,因此可以像使用标准 socket 来进行两台主机间的 ip 协议通信一样地来使用它,这也是 netlink 之所以能够得到越来越广泛应用的一个重要原因。 清单 4. 用户空间创建 netlink socket 。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <sys/socket.h>
#include <linux/types.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
......
int
main(
void
)
{
......
if
((nl_socket = socket(pf_netlink, sock_dgram, netlink_route))==-1)
// 指定通信域、通信方式以及通信协议
exit
(1);
......
}
|
在创建 netlink 套接字时: 我们指定了通信域为 pf_netlink,表明这是一个 netlink 套接字。其定义可以在如下所示的内核 include/linux/socket.h 文件中找到。从中我们也可以看到自己非常熟悉的 af_inet: 清单 5. 清单 4 中使用到的宏定义 。
1
2
3
4
5
6
7
8
9
10
11
12
|
/* 以下代码摘自 include/linux/socket.h 文件 */
/* supported address families. */
#define af_unspec 0
#define af_unix 1 /* unix domain sockets */
#define af_local 1 /* posix name for af_unix */
#define af_inet 2 /* internet ip protocol */
......
#define af_netlink 16
......
/* protocol families, same as address families. */
#define pf_netlink af_netlink
......
|
对于通信方式,我们选择了 sock_dgram。事实上对于 netlink 这种基于无连接的 socket,使用 sock_dgram 或者 sock_raw 都是可以的。 对于通信协议,我们使用了 netlink_route。这是因为在清单 1 中,内核空间创建 netlink 套接字、用于发送 ip 地址发生变化的消息时使用的是它,所以这里需要保持一致以进行双方间的通信。 用户空间绑定 netlink 套接字 与标准的 socket 使用方法相似,在建立 netlink 套接字之后,也需要绑定到一个 netlink 地址才能够进行消息的发送与接收。netlink 地址在 struct sockaddr_nl 结构中定义,各结构成员的含义可参见附录 3。 清单 6. 用户空间 bind netlink socket 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <sys/socket.h>
#include <linux/types.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
......
int
main(
void
)
{
......
struct
sockaddr_nl addr
// 在 include/linux/netlink.h 中定义,结构各成员的含义可参见附录 3
memset
(&addr, 0,
sizeof
(addr));
addr.nl_family = pf_netlink;
// 定义协议簇为 pf_netlink
addr.nl_groups = rtmgrp_ipv4_ifaddr
// 加入到 rtmgrp_ipv4_ifaddr 组播 group 中
addr.nl_pid = 0;
// 让 kernel 来分配 pid
......
// 将清单 5 中创建的 netlink 套接字与上述协议地址进行绑定
if
(bind(nl_socket, (
struct
sockaddr *) &addr,
sizeof
(addr)) == -1)
{
close(nl_socket);
exit
(1);
}
......
}
|
从清单 6 中可以看到,在绑定应用程序的 netlink 套接字时,我们将自己加入到了 rtmgrp_ipv4_ifaddr 组播 group 中,这与前文我们对内核空间 ip 地址变化事件的通知过程的分析是一致的。 用户空间接收并处理内核空间消息 同样与标准的 socket 使用方法类似,用户空间接收内核空间发来的 netlink 消息可以使用 recv、recvfrom 或 recvmsg。值得一提的是,netlink 套接字有自己的消息头:nlmsghdr 结构(该结构具体各成员变量的含义请查看参考资源),而其中的 nlmsg_type 正是我们需要用到的包含了消息类型的字段。 清单 7. 用户空间接收内核空间消息 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#define max_msg_size 1024
......
#include <sys/socket.h>
#include <linux/types.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
......
struct
if_info
{
int
index;
//interface 的序号
char
name[ifnamsiz];
//interface 的名称,linux 内核 include/linux/if.h 中定义了 ifnamsiz
uint8_t mac[eth_alen];
//interface 的 mac 地址,linux 内核 include/linux/if_ether.h 中定义了 eth_alen
......
//interface 的其他信息
struct
if_info *next;
// 指向下一个 if_info 结构的指针
};
static
struct
if_info *if_list = null;
// 存放现有的 interface 列表,在每次程序初始化时更新
int
receive_netlink_message(
struct
nlmsghdr *nl);
// 用于接收内核空间发来的消息的函数
handle_newaddr(
struct
ifinfomsg *ifi,
int
len);
// 用于处理向 dns 服务器发送更新的函数
......
int
main(
void
)
{
......
int
len = 0;
struct
nlmsghdr *nl;
// 结构体定义可以参考内核 include/linux/netlink.h 文件
while
((len = receive_netlink_message(&nl)) > 0)
{
while
(nlmsg_ok(nl, len))
//nlmsg 相关的宏定义可以参考内核 include/linux/netlink.h 文件
{
switch
(nl->nlmsg_type)
{
case
rtm_newaddr:
// 处理 rtm_newaddr 的 netlink 消息类型
//ifinfomsg 结构可以参考内核 include/linux/rtnetlink.h 文件
handle_newaddr((
struct
ifinfomsg *)nlmsg_data(nl),
nlmsg_payload(nl,
sizeof
(
struct
ifinfomsg)));
break
;
......
// 处理其他 netlink 消息类型,如:rtm_newlink,这里略过
default
:
printf
(
"unknown netlink message type : %d"
, nl->nlmsg_type);
}
nl = nlmsg_next(nl, len);
}
if
( nl != null )
free
(nl);
}
......
}
int
receive_netlink_message(
struct
nlmsghdr **nl)
{
struct
iovec iov;
// 使用 iovec 进行接收
struct
msghdr msg = {null, 0, &iov, 1, null, 0, 0};
// 初始化 msghdr
int
length;
*nl = null;
if
((*nl = (
struct
nlmsghdr *)
malloc
(max_msg_size)) == null )
return
0;
iov.iov_base = *nl;
// 封装 nlmsghdr
iov.iov_len = max_msg_size;
// 指定长度
length = recvmsg(nl_socket, &msg, 0);
if
(length <= 0)
free
(*nl);
return
length;
}
|
应用程序在收到了 rtm_newaddr 类型的 netlink 消息后,需要根据 ip 的变化进行处理。这里使用了 handle_newaddr 函数,对 ip 的变化分为了两种情况:一种是 interface 已经存在、仅仅是 ip 发生了变化;另一种是 interface 是新添加的。无论是哪种情况,handle_newaddr 函数在进行了相应的处理之后,都需要调用 update_dns.sh 这个脚本通知 dns 服务器。关于 update_dns.sh 的实现参见下一章。 清单 8. 用户空间处理内核空间消息 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
void
handle_newaddr(
struct
ifinfomsg *ifinfo,
int
len)
{
struct
if_info *i;
for
(i = if_list ; i ; i = i->next)
// 遍历 in_list,找到 ip 发生变化的 interface
if
(i->index == ifinfo->ifi_index)
break
;
if
(i != null){
// 找到了相应的 interface,执行 update_dns.sh
system
(update_dns.sh);
return
;
}
// 没有找到对应的 interface,说明该 interface 是新添加的
if
((i =
calloc
(
sizeof
(
struct
if_info), 1)) == null)
// 分配一个 if_info 结构用于添加新的 interface
exit
(1);
// 根据 ifinfo->ifi_index 等信息更新 if_info 结构 i,考虑到与 ddns 应用关系不大,限于篇幅,这里略过
......
system
(update_dns.sh);
// 执行 update_dns.sh
i->next = if_list;
// 在 if_list 的末尾添加新发现的 interface
if_list = i;
}
|
应用程序与 dns 服务器的交互 应用程序可以利用开源工具 nsupdate 来向 dns 服务器发送 dns update 消息。nsupdate 的详细用法及特性可以请查看参考资源,受篇幅所限,本章将会结合例子简单介绍这个工具的基本用法。 nsupdate 可以从终端或文件中读取命令,每个命令一行。一个空行或一个"send"命令,则会将先前输入的命令发送到 dns 服务器上,典型的使用方法如清单 9 所示。nsupdate 默认从文件 /etc/resolv.conf 中解析 dns 服务器和域名,在实际应用中,我们可以首先解析网络参数,生成 nsupdate 的输入文件,最后调用 nsupdate。update_dns.sh 的实现流程如图 3 所示。 清单 9. nsupdate 的使用例子 。
1
2
3
4
5
6
7
8
|
# nsupdate
> server 9.0.148.50
//dns 服务器地址 9.0.148.50,默认端口 53
> update
delete
oldhost.example.com a
// 删除域名 oldhost.example.com 的任何 a 类型记录
> update add newhost.example.com 86400 a 172.16.1.1
// 添加一条 172.16.1.1<----->newhost.example.com a 类型的记录,
// 记录的 ttl 是 24 小时(86400 秒)
> send
// 发送命令
|
图 3. update_dns.sh 的实现流程 。
netlink socket 的关闭 用户空间关闭 netlink socket 同标准的 socket api 一样,用户空间关闭 netlink socket 使用的也是 close 函数,而且用法完全一致。您可以参考清单 6 中 close 函数在 ddns 应用程序中的使用。 内核空间关闭 netlink socket 内核空间关闭 netlink socket 使用 sock_release 函数,函数原型如下所示: 清单 10. 内核空间关闭 netlink socket - sock_release 。
1
2
3
4
|
/*
以下代码摘自 linux kernel 3.4.3, net/socket.c 文件
*/
void
sock_release(
struct
socket * sock);
|
其中 sock 为 netlink_kernel_create 创建的 netlink 套接字。 值得一提的是,在最新的 linux kernel 中,还提供了 netlink_kernel_release 接口,函数原型如下所示: 清单 11. 内核空间关闭 netlink socket —— netlink_kernel_release 。
1
2
3
4
|
/*
以下代码摘自 linux kernel 3.4.3, net/netlink/af_netlink.c 文件
*/
void
netlink_kernel_release(
struct
sock *sk);
|
其中 sk 为 netlink_kernel_create 创建的 netlink 套接字.
对 ddns 应用实现的扩展启示 ddns 利用 rtnetlink 的 netlink_route 协议簇套接字来监听 linux 内核网络事件“rtm_newaddr”,实时更新 dns 映射信息,从而实现 dns 信息的动态更新。除了 netlink_route,netlink_family 还提供了多种协议簇来实现多种信息的报告,比如 selinux、防火墙、netfilter、ipv6 等。就 netlink_route 协议簇而言,也提供了多个组播 group 对应多种网络连接、网络参数、路由信息、网络流量类别等等变化的事件。 这就启示我们可以利用 netlink,特别是 rtnetlink,实现许多其他的与网络相关的应用。比如:应用程序如果需要实时地监控本机路由表的变化,就可以在用户空间创建 netlink_route 协议簇的 netlink 套接字时把自己加到 rtmgrp_ipv4_route 及 rtmgrp_notify 的多播组中(即:addr.nl_groups = rtmgrp_ipv4_route | rtmgrp_notify;)通过这种方式,可以实现包括 ospf、ripv2、bgp 等在内的多种现行路由协议;再比如:也可以利用 rtnetlink 来监听网络的连接情况,rtnetlink 在初始化的时候将 rtnetlink 消息处理函数 rtnetlink_event 挂到了通知链 netdev_chain 上,网络设备的启动,关闭,更名等事件都能触发通知链并回调消息处理函数,从而组播 rtm_newlink 或者 rtm_dellink 信息,向用户程序通知网络的连接情况.
总结 本文结合 ddns 的工作原理,简单阐释了 ddns 的实现流程,并在此基础之上,进一步演示了利用 linux rtnetlink 套接字实现内核空间与用户空间的网络状态 ip 地址变化信息的交互、以及利用 nsupdate 实现 ddns 客户端与服务器端的同步更新,并且在实际的应用中完全实现了 ddns 的功能,希望能够为使用 ddns 进行网络管理的人员及 linux 网络编程爱好者提供有益的参考.
。
参考资料 。
作者:王 寒芷, 软件工程师, ibm 王 俊元, 软件工程师, ibm 。
最后此篇关于DDNS 的工作原理及其在 Linux 上的实现的文章就讲到这里了,如果你想了解更多关于DDNS 的工作原理及其在 Linux 上的实现的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
背景: 我最近一直在使用 JPA,我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。 我们公司使用大量非 SQL 数据库,特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
我已经在我的 maven pom 中添加了这些构建配置,因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。 允许在行(实体)中进行迭代,并在对当前
好像没有,因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情,要么这不应该发
在 C# 中,如果 A 实现 IX 并且 B 继承自 A ,是否必然遵循 B 实现 IX?如果是,是因为 LSP 吗?之间有什么区别吗: 1. Interface IX; Class A : IX;
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0
我将把国际象棋游戏表示为 C++ 结构。我认为,最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。 这是一个好的方法吗? struct TreeElement{ SomeMoveType
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名,然后检查用户名是否已被占用。如果采用该方法,则该方法应该返回带有数据库中未采用的数字的用户名。 例子: “贾
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象,并且我有一个二维数组来保存两个给定顶点
我目前正在 ika 中开发我的 Python 游戏,它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而,我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏,但我想供应 4-
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。 它必须能够将信息发布到 DHT 并检索它。 最佳答案 OpenDHT是
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时,它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!? 最佳答案 “C++ 实现”是指编译器加上链接
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印
在很多情况下,我需要在 C# 中访问合适的哈希算法,从重写 GetHashCode 到对数据执行快速比较/查找。 我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是,我从未见过 C# 实现的
目录 LRU缓存替换策略 核心思想 不适用场景 算法基本实现 算法优化
1. 绪论 在前面文章中提到 空间直角坐标系相互转换 ,测绘坐标转换时,一般涉及到的情况是:两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中,WGS-84坐标系、54北京坐标系
在软件开发过程中,有时候我们需要定时地检查数据库中的数据,并在发现新增数据时触发一个动作。为了实现这个需求,我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .
二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置。
我是一名优秀的程序员,十分优秀!