基于偏移的链表的问题 [英] Problem with offset based linked list
问题描述
我正在使用Linux + SysV共享内存（对不起，但我的问题是关于偏移量+指针而不是关于linux /的所有内容都是
IPC）因此使用
offset'而不是指针将链表存储在共享的
内存中。我运行fedora 9和gcc 4.2。我可以在列表中插入值到
，从列表中删除值，但问题在于遍历列表的
。
从列表底部或共享内存中移动时，Atlease一个或两个列表节点消失。
PS：不要被带走因为PROC1宏。它只是习惯于将
编译成相同的代码到两个不同的进程，这个进程创建，
insert&破坏清单&创造和创造破坏共享记忆&
另一个只是附加到共享内存并遍历由使用PROC1宏定义的进程创建的进程创建的
链表。
已定义。所以编译：
gcc -g -O -D PROC1 proc1 shlist.c
gcc -g -O -o proc2 shlist.c
现在proc1创建共享内存&销毁它并创建&
销毁链表。 proc2只是附加（并最终分离
）共享内存，只是遍历列表并在每个列表元素中打印
值。
谢谢。
Kalyan
以下是完整代码（shlist.c）：
#include< stdio.h>
#include< string.h>
#include< stdlib.h>
#include< errno.h>
#include< sys / types.h>
#include< unistd.h>
#include< fcntl.h>
#include< sys / ipc.h>
#include< sys / shm.h>
#include< sys / stat.h>
int open_shared_memory（key_t shm_key，size_t shm_sz）;
void * attach_shared_memory（int shm_id）;
void detach_shared_memory（const void * mem）;
void destroy_shared_memory（int shm_id）;
#define SHMEM_CREAT （IPC_CREAT | IPC_EXCL | 0644）
#define SHMEM_OPEN（IPC_CREAT | 0644）
int open_shared_memory（key_t shm_key，size_t shm_sz）
{
size_t shm_size = 1024;
int shm_id = - 2; / *一些无效的身份证号码* /
if（shm_key == IPC_PRIVATE）abort（）;
if（shm_sz< 1024）{
fprintf（stderr，警告：共享内存大小默认为1024
bytes \ n）;
}其他{
shm_size = shm_sz;
}
shm_id = shmget（shm_key，shm_size，SHMEM_CREAT）;
if（ shm_id == -1）{
shm_id = shmget（shm_key，shm_size，SHMEM_OPEN）;
if（shm_id == -1）{
fprintf（stderr，无法使用键值创建/打开共享内存：
％lu \ n，（unsigned long）shm_key）;
fprintf（ stderr，发生错误是\％s \" \ n"，strerror（errno））;
返回-1;
}
}
返回shm_id;
}
void * attach_shared_memory（int shm_id）
{
void * mem = shmat（shm_id，NULL，0）;
if（mem ==（void *）-1）返回NULL;
返回mem;
}
void detach_shared_memory（const void * mem）
{
shmdt（mem）;
}
void destroy_shared_memory（int shm_id）
{
shmctl（shm_id，IPC_RMID，（struct shmid_ds） *）0）;
}
typedef long OffsetPtr;
extern unsigned char * base;
#define OFFSET_BASE（ptr）\
if（ptr！= NULL）base =（unsigned char *）ptr;
#define GET_OFFSET（ptr）\
（（长）（（unsigned char *）ptr - base））
#define GET_POINTER（off）\\ \\ / $
（（void *）（base + off））
#define IS_VALID_POINTER（ptr）\
（基数< （unsigned char *）（ptr））
unsigned char * base = 0;
static int count = 0;
typedef struct {
int value;
OffsetPtr next;
} IntList;
void InitList（IntList * list）;
void InsertHead（IntList * list，int value）;
void RemoveHead（IntList * list，int * removedValue）;
void DestroyList（IntList * list）;
void InitList（IntList * list）
{
if（list == NULL ||！list）return;
OFFSET_BASE（list）;
list-> next = -1;
list-> value = 0;
}
void InsertHead（IntList * list，int value）
{
IntList * newList，* nnode;
if（list == NULL ||！list）abort（）;
newList =（IntList *）（base +（count * sizeof（IntList）））;
if（！newList || newList == NULL）
abort（）;
newList-> value = value;
if（list-> next == -1）newList-> next = -1;
else newList-> next = list-> next;
list-> next = GET_OFFSET（newList）;
++ count;
}
void RemoveHead（IntList * list，int * removedValue）
{
IntList * node，* nnode;
OffsetPtr next;
if（list = = NULL || ！list）return;
node =（IntList *）GET_POINTER（list-> next）;
nnode =（IntList *）GET_POINTER（node- > next）;
list-> next = GET_OFFSET（nnode）;
* removedValue = node-> value;
node - > next = -1;
--count;
}
void DestroyList（IntList * list）
{
int val;
while（list-> next！= -1）
{
RemoveHead（list，& val）;
printf（" Removed：％d \ n"，val）;
}
list-> next = -1;
}
int main（无效）
{
IntList * myList;
IntList * node;
int i，val，shm_id;
shm_id = open_shared_memory（1511,4096）;
if（shm_id == -1）return -errno;
base = attach_shared_memory（shm_id）;
myList =（IntList *）base;
#ifdef PROC1
InitList（myList）;
for（i = 0; i< ; 20; i ++）{
printf（" Inserting：％d \ n"，（i + 1））;
InsertHead（myList，（i + 1））;
}
#endif
node =（IntList *）base;
while（node-> next）
{
printf（"％d"，node-> value）;
node =（IntList *）GET_POINTER（node-> next）;
}
printf（" \ n"）;
#ifndef PROC1
detach_shared_memory（（const void *）base ）;
#endif
#ifdef PROC1
printf（按输入键退出...）;
getchar（）;
DestroyList（myList）;
myList-> next = -1;
detach_shared_memory（（ const void *）base）;
destroy_shared_memory（shm_id）;
#endif
返回0;
}
Hi,
I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset''s instead on pointers to store the linked list in the shared
memory. I run fedora 9 and gcc 4.2. I am able to insert values in to
the list, remove values from the list, but the problem is in
traversing the list. Atlease one or 2 list nodes disappear when
traversing from the base of the list or the shared memory.
PS: Don''t get carried away because of PROC1 macro. It''s just used to
compile the same code to two different processes one that creates,
inserts & destroys the list & creates & destroys shared memory & the
other one simply attaches to the shared memory and traverses the
linked list created by the process that is compiled using PROC1 macro
defined. So to compile:
gcc -g -O -D PROC1 proc1 shlist.c
gcc -g -O -o proc2 shlist.c
now proc1 creates shared memory & destroys it and also creates &
destroys linked list. Where as proc2 just attaches (and detaches
finally) to shared memory and just traverses the list and prints the
value in each list element.
Thanks.
Kalyan
Below is the complete code (shlist.c) :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/stat.h>
int open_shared_memory(key_t shm_key,size_t shm_sz);
void* attach_shared_memory(int shm_id);
void detach_shared_memory(const void *mem);
void destroy_shared_memory(int shm_id);
#define SHMEM_CREAT (IPC_CREAT|IPC_EXCL|0644)
#define SHMEM_OPEN (IPC_CREAT|0644)
int open_shared_memory(key_t shm_key,size_t shm_sz)
{
size_t shm_size = 1024;
int shm_id = -2; /*some invalid id number*/
if (shm_key == IPC_PRIVATE) abort();
if (shm_sz < 1024) {
fprintf(stderr,"Warning: Shared memory size is defaulted to 1024
bytes\n");
} else {
shm_size = shm_sz;
}
shm_id = shmget(shm_key,shm_size,SHMEM_CREAT);
if (shm_id == -1) {
shm_id = shmget(shm_key,shm_size,SHMEM_OPEN);
if (shm_id == -1) {
fprintf(stderr,"Unable to create/open shared memory with key value:
%lu\n",(unsigned long) shm_key);
fprintf(stderr,"Error occured is \"%s\"\n",strerror(errno));
return -1;
}
}
return shm_id;
}
void* attach_shared_memory(int shm_id)
{
void *mem = shmat(shm_id,NULL,0);
if (mem == (void *) -1) return NULL;
return mem;
}
void detach_shared_memory(const void *mem)
{
shmdt(mem);
}
void destroy_shared_memory(int shm_id)
{
shmctl(shm_id,IPC_RMID,(struct shmid_ds *) 0);
}
typedef long OffsetPtr;
extern unsigned char* base;
#define OFFSET_BASE(ptr) \
if (ptr != NULL) base = (unsigned char*) ptr;
#define GET_OFFSET(ptr) \
((long) ((unsigned char*) ptr - base))
#define GET_POINTER(off) \
((void*) (base + off))
#define IS_VALID_POINTER(ptr) \
(base < (unsigned char*) (ptr))
unsigned char* base = 0;
static int count = 0;
typedef struct {
int value;
OffsetPtr next;
} IntList;
void InitList(IntList *list);
void InsertHead(IntList *list,int value);
void RemoveHead(IntList *list,int *removedValue);
void DestroyList(IntList *list);
void InitList(IntList *list)
{
if (list == NULL || !list) return;
OFFSET_BASE(list);
list->next = -1;
list->value = 0;
}
void InsertHead(IntList *list,int value)
{
IntList *newList,*nnode;
if (list == NULL || !list) abort();
newList = (IntList *) (base + (count *sizeof(IntList)));
if (!newList || newList == NULL)
abort();
newList->value = value;
if (list->next == -1) newList->next = -1;
else newList->next = list->next;
list->next = GET_OFFSET(newList);
++count;
}
void RemoveHead(IntList *list,int *removedValue)
{
IntList *node,*nnode;
OffsetPtr next;
if (list == NULL || !list) return;
node = (IntList *) GET_POINTER(list->next);
nnode = (IntList *) GET_POINTER(node->next);
list->next = GET_OFFSET(nnode);
*removedValue = node->value;
node->next = -1;
--count;
}
void DestroyList(IntList *list)
{
int val;
while (list->next != -1)
{
RemoveHead(list,&val);
printf("Removed: %d\n",val);
}
list->next = -1;
}
int main(void)
{
IntList *myList;
IntList *node;
int i,val,shm_id;
shm_id = open_shared_memory(1511,4096);
if (shm_id == -1) return -errno;
base = attach_shared_memory(shm_id);
myList = (IntList *) base;
#ifdef PROC1
InitList(myList);
for (i = 0 ; i < 20; i++) {
printf("Inserting :%d\n",(i + 1));
InsertHead(myList,(i + 1));
}
#endif
node = (IntList *) base;
while (node->next)
{
printf("%d ",node->value);
node = (IntList *) GET_POINTER(node->next);
}
printf("\n");
#ifndef PROC1
detach_shared_memory((const void *) base);
#endif
#ifdef PROC1
printf("Press enter key to quit ...");
getchar();
DestroyList(myList);
myList->next = -1;
detach_shared_memory((const void *) base);
destroy_shared_memory(shm_id);
#endif
return 0;
}
推荐答案
kalyan< rk ********** @ gmail.comwrites：
kalyan <rk**********@gmail.comwrites:
我正在使用Linux + SysV共享内存（对不起，但我的问题是所有
关于偏移+指针而不是关于linux / IPC）因此使用
offset'而不是指针将链表存储在共享中
内存。
I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset''s instead on pointers to store the linked list in the shared
memory.
你不需要这样做。一个你有一个指针它是一个指针。
不需要索引。如果有计划应对从一个地方到另一个地方的移动清单
？这可能需要补偿。
You don''t need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.
我运行fedora 9和gcc 4.2。我可以在列表中插入值到
，从列表中删除值，但问题在于遍历列表的
。当从列表底部或共享内存遍历时，atlease一个或两个列表节点消失。
I run fedora 9 and gcc 4.2. I am able to insert values in to
the list, remove values from the list, but the problem is in
traversing the list. Atlease one or 2 list nodes disappear when
traversing from the base of the list or the shared memory.
我认为问题在于你使用这些
索引使自己陷入困境。例如，在第一个InsertHead操作中，list和
newlist引用相同的位置。
如果你需要使用索引（还不明显）它更简单的方法是使b / b
使得base成为指向节点数组的指针而只是索引它 - 而不是
凌乱的指针算法。删除共享内存的东西
然后编写代码，使用声明的节点数组从链表中添加删除元素
。一个调试器可能会帮助你看到你对第一个节点的混淆。
然后，重新放入共享内存，你将启动并运行。
< snip>
I think the problem is that you have tied yourself up using these
indexes. For example, in the first InsertHead operation, list and
newlist refer to the same place.
If you need to use indexes (not obvious yet) it is much simpler to
make base a pointer to an array of nodes and just index into it -- not
messy pointer arithmetic. Remove for a moment the shared memory stuff
and just write the code to add an remove elements from linked list
using a declared array of nodes. A debugger might help you see the
confusion you have over the first node.
Then, put the shared memory back in and you will be up and running.
<snip>
以下是完整代码（shlist.c）：
Below is the complete code (shlist.c) :
一些评论...
A few comments...
#include< stdio.h>
#include< string.h>
#include< ; stdlib.h>
#include< errno.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
< snip>
<snip>
typedef long OffsetPtr;
extern unsigned char * base;
#define OFFSET_BASE（ptr）\
if（ptr！= NULL）base =（unsigned char *） ptr;
#define GET_OFFSET（ptr）\
（（长）（（unsigned char *）ptr - base））
#define GET_POINTER（关闭）\
（（void *）（基数+关闭））
typedef long OffsetPtr;
extern unsigned char* base;
#define OFFSET_BASE(ptr) \
if (ptr != NULL) base = (unsigned char*) ptr;
#define GET_OFFSET(ptr) \
((long) ((unsigned char*) ptr - base))
#define GET_POINTER(off) \
((void*) (base + off))
始终完全括起宏参数：（ptr）。我认为一切都很好
但我必须逐一检查所有用途以确定。事实上，在你调试的时候，我会把所有这些写成函数。
Always fully parenthesise macro arguments: (ptr). I think all is well
but I have to check all the uses one by one to be sure. In fact,
while you are debugging, I''d write all these as functions.
#define IS_VALID_POINTER（ptr）\
（base<（unsigned char *）（ptr））
unsigned char * base = 0;
static int count = 0;
typedef struct {
int value;
OffsetPtr next;
} IntList;
#define IS_VALID_POINTER(ptr) \
(base < (unsigned char*) (ptr))
unsigned char* base = 0;
static int count = 0;
typedef struct {
int value;
OffsetPtr next;
} IntList;
如果宣布基数，生活会更容易：
IntList * base;
so base [0]，base [1]是节点。
Life would be easier if base were declared:
IntList *base;
so base[0], base[1] are the nodes.
void InitList（IntList * list）;
void InsertHead（IntList * list，int value）;
void RemoveHead（IntList * list，int * removedValue）;
void DestroyList（IntList * list）;
void InitList（IntList * list）
{
if（list == NULL ||！list）return;
void InitList(IntList *list);
void InsertHead(IntList *list,int value);
void RemoveHead(IntList *list,int *removedValue);
void DestroyList(IntList *list);
void InitList(IntList *list)
{
if (list == NULL || !list) return;
||的一半足够。这让我困惑了一会儿！
Either half of the || is enough. This confused me for a while!
OFFSET_BASE（list）;
list-> next = -1;
list-> value = 0;
}
void InsertHead（IntList * list，int value）
{
IntList * newList，* nnode;
if（list == NULL ||！list）abort（）;
>
newList =（IntList *）（base +（count * sizeof（IntList）））;
if（！newList || newList == NULL）
abort（）;
newList-> value = value;
if（list-> next == -1）newList - > next = -1;
else newList-> next = list-> next;
OFFSET_BASE(list);
list->next = -1;
list->value = 0;
}
void InsertHead(IntList *list,int value)
{
IntList *newList,*nnode;
if (list == NULL || !list) abort();
newList = (IntList *) (base + (count *sizeof(IntList)));
if (!newList || newList == NULL)
abort();
newList->value = value;
if (list->next == -1) newList->next = -1;
else newList->next = list->next;
这个if与以下内容相同：newList-> next = list-> next;
This if is just the same as: newList->next = list->next;
list-> next = GET_OFFSET（newList）;
++ count;
}
list->next = GET_OFFSET(newList);
++count;
}
< snip>
-
Ben。
<snip>
--
Ben.
Ben Bacarisse< be ** ****** @bsb.me.ukwrites：
Ben Bacarisse <be********@bsb.me.ukwrites:
kalyan< rk ********** @ gmail.comwrites：
kalyan <rk**********@gmail.comwrites:
我正在使用Linux + SysV共享内存（对不起，但我的问题是关于偏移量+指针而不是关于linux / IPC的所有内容都是b $ b）和因此使用
offset'而不是指针将链表存储在共享的
内存中。
I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset''s instead on pointers to store the linked list in the shared
memory.
你不需要这样做。一个你有一个指针它是一个指针。
不需要索引。如果有计划应对从一个地方到另一个地方的移动清单
？这可能需要补偿。
You don''t need to do that. One you have a pointer it is a pointer.
No need for indexes. If there some plan to cope with moving lists
from one place to another? That might need offsets.
共享内存不保证在所有进程中都在同一地址
映射它们;它没有动，但效果是一样的。
你的，
-
Jean -Marc
Shared memory is not guaranteed to be at the same address in all process
mapping them; it''s not moving but the effect is the same.
Yours,
--
Jean-Marc
8月25日，6：19 * pm，Jean-Marc Bourguet< j ... @ bourguet.orgwrote：
On Aug 25, 6:19*pm, Jean-Marc Bourguet <j...@bourguet.orgwrote:
Ben Bacarisse< ben.use ... @ bsb.me.ukwrites：
Ben Bacarisse <ben.use...@bsb.me.ukwrites:
kalyan< rkalyanku ... @ gmail .comwrites：
kalyan <rkalyanku...@gmail.comwrites:
我正在使用Linux + SysV共享内存（对不起，但我的问题都是
关于偏移+指针而不是关于linux / IPC）因此使用
offset'而不是指针将链表存储在共享中
记忆。
I am using Linux + SysV Shared memory (sorry, but my question is all
about offset + pointers and not about linux/IPC) and hence use
offset''s instead on pointers to store the linked list in the shared
memory.
你不需要这样做。 *你有一个指针，它是一个指针。
不需要索引。 *如果有计划应对从一个地方到另一个地方的移动清单
？ *这可能需要补偿。
You don''t need to do that. *One you have a pointer it is a pointer.
No need for indexes. *If there some plan to cope with moving lists
from one place to another? *That might need offsets.
共享内存不保证在所有进程中都在同一地址
映射它们;它没有动，但效果是一样的。
你的，
-
Jean -Marc
Shared memory is not guaranteed to be at the same address in all process
mapping them; it''s not moving but the effect is the same.
Yours,
--
Jean-Marc
你好Jean-Marc，
这就是为什么人们需要使用补偿代替指针
在共享内存中有链接列表？
您在我发布的代码中发现了什么问题？特别是
在遍历列表的代码中。
问候
kalyan
Hi Jean-Marc,
That''s the reason why one needs to use offsets in place of pointers
when having linked lists in the shared memory?
Did you find any thing wrong in the code that I''ve posted? Especially
in the code that traverses the list.
Regards
kalyan
这篇关于基于偏移的链表的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
