Python and ctypes, an exercise

[Diomedes]

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.

[leegao]

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

[Diomedes]

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!

[leegao]

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.

[TrustyTony]

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
>>>

[TrustyTony]

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

[TrustyTony]

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