管理链接表数据结构的方法和装置

摘要

本文介绍一种管理链接表数据结构(20)的方法。链接表数据结构(20)有许多元素(22a、22b…22n),每个元素包括数据项(24a、24b… 24n)和顺序指向下一个元素的指针(26a、26b…26n)。该方法允许通过插入或从中删除元素来修改链接表数据结构(20),并允许同时执行对链接表数据结构(20)的非同步遍历操作。具体来说,该方法要求用原子操作(36)来修改链接表数据结构(20)内元素(24a、24b…24n)的指针(26a、26b…26n),以反映对链接表数据结构(20)的任何修改。采用原子操作(36)来更新指针(26a、26b…26n),能保障非同步遍历操作(38)检查的是有效的数据路径。

主权项

1．一种计算机实现的管理链接表数据结构的方法，其中，链接表数据结构包括由数据部分和指针部分组成的第一个元素，该方法包括下列步骤：修改链接表数据结构；更新第一个元素的指针部分以反映对链接表数据结构的修改，更新步骤包含一个原子操作；在对链接表数据结构修改的同时，执行对链接表数据结构的非同步遍历。