PHP extension development-use of arrays and introduction to HashTable_PHP tutorial

1 array

In this section we will talk about PHP arrays. In PHP, arrays are implemented using HashTable. In this section, we first introduce HashTable in detail, and then talk about how to use HastTable

1.1 Variable length structure

The so-called variable length structure is actually a special usage of our C language structure, and there is nothing novel about it. Let's first look at a common definition method of variable length structures.

typedef struct bucket {

int n;

char key[30];

char value[1];

} Bucket;

We have defined a structure Bucket, and we hope to use this structure to store students' personal profiles. The key is used to store the student's name, and the value is used to store the student's profile. You may be curious, our value declares a length of 1. How much information can be stored in 1 char?

In fact, for variable-length structures, the variables we are using cannot be directly defined, such as: Bucket bucket; if you use it this way, the value will definitely not store much information. For variable-length structures, we need to first declare a pointer to the variable-length structure when using it, and then allocate function space through the malloc function. We can malloc as much as the length of the space we need to use. The general usage methods are as follows:

Bucket* pBucket;

pBucket = malloc(sizeof(Bucket) + n * sizeof(char));

Where n is the length of value you want to use. If used in this way, will the string pointed to by value become longer soon?

1.2 Introduction to Hashtable

Let’s take a look at the definition of HashTable first

struct _hashtable;

typedef struct bucket {

ulong h;//Use

when the element is a numeric index

uint nKeyLength;//When using string index, this variable represents the length of the index, and the index (string) is stored in the last element aKey

void *pData;//Used to point to the saved data. If the saved data is a pointer, pDataPtr points to this data, and pData points to pDataPtr

void *pDataPtr;

struct bucket *pListNext; //Previous element

struct bucket *pListLast; //Next element

struct bucket *pNext; //Pointer to the next bucket

struct bucket *pLast; //Pointer to the previous bucket

char arKey[1]; //Must be placed at the end, mainly to achieve variable length structure

} Bucket;

typedef struct _hashtable {

uint nTableSize; //The size of the hash table

uint nTableMask; //Numerically equal to nTableSize- 1

uint nNumOfElements; //Records the number of records saved in the current HashTable

ulong nNextFreeElement; //Point to the next free Bucket

Bucket *pInternalPointer; //This variable is used for array inversion

Bucket *pListHead; //Point to the head of the Bucket

Bucket *pListTail; //Point to the tail of the Bucket

Bucket **arBuckets;

dtor_func_t pDestructor; //Function pointer, automatically called when adding, deleting, modifying, and checking the array, used for certain cleaning operations

zend_bool persistent; // Is it persistent?

unsigned char nApplyCount;

zend_bool bApplyProtection; //Works with nApplyCount to prevent infinite recursion during array traversal

#if ZEND_DEBUG

int inconsistent;

#endif

} HashTable;

I hope everyone can take a good look at the above definitions. There are some things that I will not understand when I explain them. It is better for everyone to look at the code and it will be clearer. PHP's array is actually a doubly linked list with a head node, where HashTable is the head and Bucket stores specific node information.

1.3 HashTable internal function analysis

1.3.1 Macro HASH_PROTECT_RECURSION

#defineHASH_PROTECT_RECURSION (ht)

if ((ht)->bApplyProtection) {                                                                                                                       

if ((ht)->nApplyCount++ >= 3){

zend_error(E_ERROR, "Nestinglevel too deep - recursive dependency?");

                                                                          

}

This macro is mainly used to prevent circular references.

1.3.2 Macro ZEND_HASH_IF_FULL_DO_RESIZE

#defineZEND_HASH_IF_FULL_DO_RESIZE(ht)                                                                          

if ((ht)->nNumOfElements >(ht)->nTableSize) {

zend_hash_do_resize(ht);

}

The function of this macro is to check whether the number of elements in the current HashTable is greater than the total size of the HashTable. If the number is greater than the size of the HashTable, then we will reallocate the space. Let’s take a look at zend_hash_do_resize

static int zend_hash_do_resize(HashTable *ht)

{

Bucket **t;

IS_CONSISTENT(ht);

if ((ht->nTableSize 0) { /* Let's double the table size */

t = (Bucket**) perealloc_recoverable(ht->arBuckets,

(ht->nTableSize persistent);

if (t) {

HANDLE_BLOCK_INTERRUPTIONS();

ht->arBuckets = t;

ht->nTableSize = (ht->nTableSize

ht->nTableMask = ht->nTableSize - 1;

zend_hash_rehash(ht);

HANDLE_UNBLOCK_INTERRUPTIONS();

return SUCCESS;

}

return FAILURE;

}

return SUCCESS;

}

From the above code we can see that when HashTable allocates space, the newly allocated space is equal to twice the original space.

1.3.3 Function _zend_hash_init

This function is used to initialize HashTable. Let’s take a look at the code first:

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)

{

uint i = 3; //The default size of HashTable is 2 raised to the third power

Bucket **tmp;

SET_INCONSISTENT(HT_OK);

if (nSize >= 0x80000000) {

ht->nTableSize = 0x80000000;

} else {

while ((1U

i++;

}

ht->nTableSize = 1

}

ht->nTableMask = ht->nTableSize- 1;

ht->pDestructor = pDestructor;

ht->arBuckets = NULL;

ht->pListHead = NULL;

ht->pListTail = NULL;

ht->nNumOfElements = 0;

ht->nNextFreeElement = 0;

ht->pInternalPointer = NULL;

ht->persistent = persistent;

ht->nApplyCount = 0;

ht->bApplyProtection = 1;

/* Uses ecalloc() so that Bucket* == NULL */

if (persistent) {

tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket*));

if (!tmp) {

return FAILURE;

}

ht->arBuckets = tmp;

} else {

tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket*));

if (tmp) {

ht->arBuckets = tmp;

}

}

return SUCCESS;

}

It can be seen that the size of HashTable is initialized to the nth power of 2. In addition, we see that there are two memory methods, one is calloc and the other is ecalloc_rel. We have discussed these two memory allocation methods in detail. If you are interested, you can check it out yourself.

1.3.4 Function_zend_hash_add_or_update

This function adds or modifies element information to HashTable

ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)

{

ulong h;

uint nIndex;

Bucket *p;

IS_CONSISTENT(ht);

if (nKeyLength

#if ZEND_DEBUG

ZEND_PUTS("zend_hash_update: Can't put inempty keyn");

#endif

return FAILURE;

}

h = zend_inline_hash_func(arKey, nKeyLength);

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

while (p != NULL) {

if ((p->h == h) && (p->nKeyLength == nKeyLength)) {

if (!memcmp(p->arKey, arKey, nKeyLength)) {

              if (flag & HASH_ADD) {

                    return FAILURE;

        }

HANDLE_BLOCK_INTERRUPTIONS();

#if ZEND_DEBUG

if (p->pData == pData) {

ZEND_PUTS("Fatal error in zend_hash_update:p->pData == pDatan");

HANDLE_UNBLOCK_INTERRUPTIONS();

                    return FAILURE;

        }

#endif

              if (ht->pDestructor) {

              ht->pDestructor(p->pData);

        }

UPDATE_DATA(ht, p, pData, nDataSize);

            if (pDest) {

*pDest = p->pData;

        }

HANDLE_UNBLOCK_INTERRUPTIONS();

return SUCCESS;

      }

}

p = p->pNext;

}

p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);

if (!p) {

return FAILURE;

}

memcpy(p->arKey, arKey, nKeyLength);

p->nKeyLength = nKeyLength;

INIT_DATA(ht, p, pData, nDataSize);

p->h = h;

CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);

if (pDest) {

*pDest = p->pData;

}

HANDLE_BLOCK_INTERRUPTIONS();

CONNECT_TO_GLOBAL_DLLIST(p, ht);

ht->arBuckets[nIndex] = p;

HANDLE_UNBLOCK_INTERRUPTIONS();

ht->nNumOfElements++;

ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */

return SUCCESS;

}

1.3.5 Macro CONNECT_TO_BUCKET_DLLIST

#define CONNECT_TO_BUCKET_DLLIST(element, list_head)

(element)->pNext= (list_head);

(element)->pLast= NULL;

if((element)->pNext) {                                                                            

(element)->pNext->pLast =(element);

}

This macro adds the bucket to the bucket list

1.3.6 Other functions or macro definitions

We just briefly introduce HashTable. If you want to understand HashTable in detail, it is recommended that you take a look at the source code of php. The code for HashTable is in Zend/zend_hash.h and Zend/zend_hash.c.

zend_hash_add_empty_element adds an empty element to the function

zend_hash_del_key_or_index deletes elements based on index

zend_hash_reverse_apply Reverse traverse HashTable

zend_hash_copy copy

_zend_hash_merge merge

zend_hash_find String index search

zend_hash_index_find Numeric index method search

zend_hash_quick_find encapsulation of the above two functions

zend_hash_exists Whether the index exists

zend_hash_index_exists Whether the index exists

zend_hash_quick_exists encapsulation of the above two methods

1.4 Commonly used HashTable functions in C extension

Although HashTable looks a bit complicated, it is very convenient to use. We can use the following functions to initialize and assign values ​​to HashTable.

Enrollment numbers of local colleges and universities in 2005

PHP syntax

C syntax

Meaning

$arr = array()

array_init(arr);

Initialize array

$arr[] = NULL;

add_next_index_null(arr);

$arr[] = 42;

add_next_index_long(arr, 42);

$arr[] = true;

add_next_index_bool(arr, 1);

$arr[] = 3.14;

add_next_index_double(3.14);

$arr[] = ‘foo’;

add_next_index_string(arr, “foo”, 1);

1 means string copy

$arr[] = $myvar;

add_next_index_zval(arr, myvar);

$arr[0] = NULL;

add_index_null(arr, 0);

$arr[1] = 42;

add_index_long(arr, 1, 42);

$arr[2] = true;

add_index_bool(arr, 2, 1);

$arr[3] = 3.14;

add_index_double(arr, 3, 3,14);

$arr[4] = ‘foo’;

add_index_string(arr, 4, “foo”, 1);

$arr[5] = $myvar;

add_index_zval(arr, 5, myvar);

$arr[“abc”] = NULL;

add_assoc_null(arr, “abc”);

$arr["def"] = 711;

add_assoc_long(arr, “def”, 711);

$arr[“ghi”] = true;

add_assoc_bool(arr, ghi”, 1);

$arr[“jkl”] = 1.44;

add_assoc_double(arr, “jkl”, 1.44);

$arr[“mno”] = ‘baz’;

add_assoc_string(arr, “mno”, “baz”, 1);

$arr[‘pqr’] = $myvar;

add_assoc_zval(arr, “pqr”, myvar);

1.5 Tasks and Experiments

Having said all that, let’s experiment.

Task: Return an array. The data in the array is as follows:

Array

(

[0] => for test

[42] => 123

[for test. for test.] => 1

[array] => Array

(

[0] => 3.34

)

)

Code implementation:

PHP_FUNCTION(test)

{

zval* t;

array_init(return_value);

add_next_index_string(return_value, "for test", 1);

add_index_long(return_value, 42, 123);

add_assoc_double(return_value, "for test. for test.", 1.0);

ALLOC_INIT_ZVAL(t);

array_init(t);

add_next_index_double(t, 3.34);

add_assoc_zval(return_value, "array", t);

}

It’s very simple, remember return_value?

http://www.bkjia.com/PHPjc/477779.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/477779.htmlTechArticle1 Array In this section we will talk about php arrays. In php, arrays are implemented using HashTable. In this section, we first introduce HashTable in detail, and then talk about how to use HastTable 1.1...