Hello Python forums,
I started working with Python recently and picked up a book. The book stated discussing using the ctypes module in python which is slick because it's exactly what I need to be learning.

I started trying to test my knowledge by implementing a simple, singly linked list in python using ctypes

from ctypes import *

class linknode(Structure):
    pass

linknode._fields_ = [
                ("nextNode", POINTER(linknode)),
                ("intData", c_int),
                ]

At this point things work, I can create and use linknodes.

next to create a python linked list to use the ctypes linknode

class linked_list():
    """ our own linked list based on ctypes """
    head_node = None
   
    def add(self, int_data):
        node_to_add = linknode()
        node_to_add.intData = int_data
        node_to_add.nextNode = None

        if (self.head_node == None):
            self.head_node = node_to_add
            return
        else:
            traverse_node = self.head_node
            #while(not(traverse_node.nextNode == None)):
            print traverse_node.nextNode


if __name__ == "__main__":
    ll = linked_list()
    ll.add(5)
    ll.add(6)

Adding 5 works just fine, but adding 6 shows my problem...

I remarked out the code where my error was and dropped in a print to illustrate the problem. I think this is a knowledge gap for me in python. I seem to never be able to evaluate the pointer as null, printing is is <__main__.LP_linknode object at 0x01A07F30>. That doesn't sound like a link to 0x00. Do I need to try and store a (char *) 0 instead of None? What am I doing wrong here?

Thanks for any input.

Re: Python and ctypes, an exercise 80 80

Hi,

from ctypes import *
from see import see
import sys

class linknode(Structure):
    pass
linknode._fields_ = [
                ("nextNode", POINTER(linknode)),
                ("intData", c_int),
                ]
class linked_list():
    """ our own linked list based on ctypes """
    head_node = None
   
    def add(self, int_data):
        node_to_add = linknode(intData = c_int(int_data))
        if (self.head_node == None):
            self.head_node = node_to_add
        else:
            traverse_node = self.head_node
            node = traverse_node
            try:
                while node.nextNode.contents:
                    node = node.nextNode.contents
            except ValueError:
                node.nextNode = POINTER(linknode)(node_to_add)
            except:
                pass
    def __getitem__(self, n):
        node = self.head_node
        for i in range(n):
            node = node.nextNode.contents
        return node
                


if __name__ == "__main__":
    ll = linked_list()
    for i in range(10):
        print "Adding %s"%i
        ll.add(i)
    print ll[9].intData

Output:

Adding 0
Adding 1
Adding 2
Adding 3
Adding 4
Adding 5
Adding 6
Adding 7
Adding 8
Adding 9
9

ValueError catches the null pointer error

Re: Python and ctypes, an exercise 80 80

Dear leegao,
You rock my socks, I've been trying to get that solved for like a week bouncing between various forums. Thank you very much for your time!

Re: Python and ctypes, an exercise 80 80

Sorry about the hasty post, I had to finish up a few last minute coursework. I'm sure there's a much more intuitive way of detecting null pointers and have not yet had the chance to explore further. I'll get back to you as soon as I find something.

Re: Python and ctypes, an exercise 80 80

16.15.1.16. Incomplete Types
Incomplete Types are structures, unions or arrays whose members are not yet specified. In C, they are specified by forward declarations, which are defined later:

struct cell; /* forward declaration */

struct {
char *name;
struct cell *next;
} cell;The straightforward translation into ctypes code would be this, but it does not work:

>>> class cell(Structure):
... _fields_ = [("name", c_char_p),
... ("next", POINTER(cell))]
...
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 2, in cell
NameError: name 'cell' is not defined
>>>
because the new class cell is not available in the class statement itself. In ctypes, we can define the cell class and set the _fields_ attribute later, after the class statement:

>>> from ctypes import *
>>> class cell(Structure):
... pass
...
>>> cell._fields_ = [("name", c_char_p),
... ("next", POINTER(cell))]
>>>
Lets try it. We create two instances of cell, and let them point to each other, and finally follow the pointer chain a few times:

>>> c1 = cell()
>>> c1.name = "foo"
>>> c2 = cell()
>>> c2.name = "bar"
>>> c1.next = pointer(c2)
>>> c2.next = pointer(c1)
>>> p = c1
>>> for i in range(8):
... print p.name,
... p = p.next[0]
...
foo bar foo bar foo bar foo bar
>>>

Re: Python and ctypes, an exercise 80 80

Here my analysis of the problem

from ctypes import *
class cell(Structure):
    pass
   
cell._fields_ = [("name", c_char_p),
                  ("next", POINTER(cell))]

c1 = cell()
c1.name = "foo"

c2 = cell()
c2.name = "bar"

c1.next = pointer(c2)

c3 = cell(None)

c2.next = pointer(c3)
c3.next = None

p = c1

## My prefered way
print "My favorite: bool(pointer) being False, when pointer None"

while bool(p.next):
    print p.name
    p=p.next.contents  ## does not work without .contents or [0]

## exception method
print '-'*40
print "Exception method"
p = c1
try:
    while p.next[0]:
        print p.name
        p = p.next[0] ## that index way, little ugglier, maybe more efficient?
except ValueError:
    pass ## NULL at the end of list

print '-'*40
print "Null as value of the last cells' information being None"

p=c1
while p.name:
    print p.name
    p=p.next[0]

## identical pointers can not be found without exception

print '-'*40
c3.next = c2.next  ## trying to mark end of list as self-reference

if c3.next is c2.next : print "Null from previous cell's pointer"
else: print c3.next, "is not",c2.next

print '-'*40
print "Crashing by purpose to show the error"
if cell(c3.next) == cell(None) : print "Null from cell(None) pointer" ## gives NULL pointer ValueError
else: print c3.next[0], "is not",c2.next[0]

To summarise :

  1. Put cell.next to None in the end of list
  2. When traversing check that bool(cell.next) is True
Re: Python and ctypes, an exercise 80 80

After testing the posted routine with:

if __name__ == "__main__":
    ll = linked_list()
    for i in range(100000):
        print "Adding %s"%i
        ll.add(i)
    print ll[90000].intData

The code fails when the list reaches 64 elements.

After I changed the code not to use exceptions (like I suggested in my earlier post) in objects the limitation still stays same

from ctypes import *
import sys, random

class linknode(Structure):
    pass

linknode._fields_ = [
                ("nextNode", POINTER(linknode)),
                ("intData", c_int),
                ]

class linked_list():
    """
    linked list based on ctypes
    implements __iter__ and __len__ methods
    and add method to putting information in the end of list
    delete and index method not yet implemented"""
    head_node  =  None
   
    def add(self, int_data):
        node_to_add  =  linknode(intData  =  c_int(int_data)) ## copy from old solution
        if self.head_node  ==  None:
            self.head_node  =  node_to_add
        else:
            end_of_list = self.head_node
            while bool(end_of_list.nextNode):
##                print '.', # debug showing travel in list
                end_of_list = end_of_list.nextNode.contents
##            print  #debug
            
            end_of_list.nextNode =  pointer(node_to_add) 
             
    ## linked list has not linear time access for nth item so let's
    ## define __iter__ not indexed access first.
            
    def __iter__(self):
        item = self.head_node
        while bool(item.nextNode):
            yield item.intData
            item = item.nextNode.contents
        else:
            yield item.intData
            raise StopIteration
           
    def __len__(self):
        c = 0  ## can not use len as name!
        for i in self:
            c += 1
        return c
                
if __name__  ==  "__main__":
    ll  =  linked_list()

## works for list less than 64 long
    for i in range(60):
        print "Adding %s"%i
        ll.add(random.randint(-1000,100))
    
    for i in ll: print i,
    print

## after in 64th item fails
    print "Linked list of length",len(ll)
    for i in range(100000):
        print "Adding more %s"%i
        ll.add(random.randint(-1000,100))
    
    print "Linked list of length",len(ll)

End of output is similar than before this

...
Adding 56
Adding 57
Adding 58
Adding 59
-808 -496 -785 -295 -672 -419 -88 -29 -473 -894 86 -593 -29 -638 -954 -832 -644 -682 70 -69 -29 -923 -662 -916 -86 -226 -97 -625 -29 -319 -839 -203 -116 -995 -276 -595 -300 -787 -143 -890 -342 84 -528 -294 -368 -27 -89 -244 -4 -629 -739 -5 -751 -478 -917 -622 -406 -396 -656 -535
Linked list of length 60
Adding more 0
Adding more 1
Adding more 2
Adding more 3
Adding more 4

Traceback (most recent call last):
File "D:\Python Projects\Tests\ctype_test3.py", line 66, in <module>
ll.add(random.randint(-1000,100))
File "D:\Python Projects\Tests\ctype_test3.py", line 31, in add
end_of_list.nextNode = POINTER(linknode) (node_to_add)
ValueError: ctypes object structure too deep

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.