summaryrefslogtreecommitdiffstats
path: root/common/unqlite/jx9_hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'common/unqlite/jx9_hashmap.c')
-rw-r--r--common/unqlite/jx9_hashmap.c2989
1 files changed, 2989 insertions, 0 deletions
diff --git a/common/unqlite/jx9_hashmap.c b/common/unqlite/jx9_hashmap.c
new file mode 100644
index 0000000..e97d41d
--- /dev/null
+++ b/common/unqlite/jx9_hashmap.c
@@ -0,0 +1,2989 @@
1/*
2 * Symisc JX9: A Highly Efficient Embeddable Scripting Engine Based on JSON.
3 * Copyright (C) 2012-2013, Symisc Systems http://jx9.symisc.net/
4 * Version 1.7.2
5 * For information on licensing, redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES
6 * please contact Symisc Systems via:
7 * legal@symisc.net
8 * licensing@symisc.net
9 * contact@symisc.net
10 * or visit:
11 * http://jx9.symisc.net/
12 */
13 /* $SymiscID: hashmap.c v2.6 Win7 2012-12-11 00:50 stable <chm@symisc.net> $ */
14#ifndef JX9_AMALGAMATION
15#include "jx9Int.h"
16#endif
17/* This file implement generic hashmaps used to represent JSON arrays and objects */
18/* Allowed node types */
19#define HASHMAP_INT_NODE 1 /* Node with an int [i.e: 64-bit integer] key */
20#define HASHMAP_BLOB_NODE 2 /* Node with a string/BLOB key */
21/*
22 * Default hash function for int [i.e; 64-bit integer] keys.
23 */
24static sxu32 IntHash(sxi64 iKey)
25{
26 return (sxu32)(iKey ^ (iKey << 8) ^ (iKey >> 8));
27}
28/*
29 * Default hash function for string/BLOB keys.
30 */
31static sxu32 BinHash(const void *pSrc, sxu32 nLen)
32{
33 register unsigned char *zIn = (unsigned char *)pSrc;
34 unsigned char *zEnd;
35 sxu32 nH = 5381;
36 zEnd = &zIn[nLen];
37 for(;;){
38 if( zIn >= zEnd ){ break; } nH = nH * 33 + zIn[0] ; zIn++;
39 if( zIn >= zEnd ){ break; } nH = nH * 33 + zIn[0] ; zIn++;
40 if( zIn >= zEnd ){ break; } nH = nH * 33 + zIn[0] ; zIn++;
41 if( zIn >= zEnd ){ break; } nH = nH * 33 + zIn[0] ; zIn++;
42 }
43 return nH;
44}
45/*
46 * Return the total number of entries in a given hashmap.
47 * If bRecurisve is set to TRUE then recurse on hashmap entries.
48 * If the nesting limit is reached, this function abort immediately.
49 */
50static sxi64 HashmapCount(jx9_hashmap *pMap, int bRecursive, int iRecCount)
51{
52 sxi64 iCount = 0;
53 if( !bRecursive ){
54 iCount = pMap->nEntry;
55 }else{
56 /* Recursive hashmap walk */
57 jx9_hashmap_node *pEntry = pMap->pLast;
58 jx9_value *pElem;
59 sxu32 n = 0;
60 for(;;){
61 if( n >= pMap->nEntry ){
62 break;
63 }
64 /* Point to the element value */
65 pElem = (jx9_value *)SySetAt(&pMap->pVm->aMemObj, pEntry->nValIdx);
66 if( pElem ){
67 if( pElem->iFlags & MEMOBJ_HASHMAP ){
68 if( iRecCount > 31 ){
69 /* Nesting limit reached */
70 return iCount;
71 }
72 /* Recurse */
73 iRecCount++;
74 iCount += HashmapCount((jx9_hashmap *)pElem->x.pOther, TRUE, iRecCount);
75 iRecCount--;
76 }
77 }
78 /* Point to the next entry */
79 pEntry = pEntry->pNext;
80 ++n;
81 }
82 /* Update count */
83 iCount += pMap->nEntry;
84 }
85 return iCount;
86}
87/*
88 * Allocate a new hashmap node with a 64-bit integer key.
89 * If something goes wrong [i.e: out of memory], this function return NULL.
90 * Otherwise a fresh [jx9_hashmap_node] instance is returned.
91 */
92static jx9_hashmap_node * HashmapNewIntNode(jx9_hashmap *pMap, sxi64 iKey, sxu32 nHash, sxu32 nValIdx)
93{
94 jx9_hashmap_node *pNode;
95 /* Allocate a new node */
96 pNode = (jx9_hashmap_node *)SyMemBackendPoolAlloc(&pMap->pVm->sAllocator, sizeof(jx9_hashmap_node));
97 if( pNode == 0 ){
98 return 0;
99 }
100 /* Zero the stucture */
101 SyZero(pNode, sizeof(jx9_hashmap_node));
102 /* Fill in the structure */
103 pNode->pMap = &(*pMap);
104 pNode->iType = HASHMAP_INT_NODE;
105 pNode->nHash = nHash;
106 pNode->xKey.iKey = iKey;
107 pNode->nValIdx = nValIdx;
108 return pNode;
109}
110/*
111 * Allocate a new hashmap node with a BLOB key.
112 * If something goes wrong [i.e: out of memory], this function return NULL.
113 * Otherwise a fresh [jx9_hashmap_node] instance is returned.
114 */
115static jx9_hashmap_node * HashmapNewBlobNode(jx9_hashmap *pMap, const void *pKey, sxu32 nKeyLen, sxu32 nHash, sxu32 nValIdx)
116{
117 jx9_hashmap_node *pNode;
118 /* Allocate a new node */
119 pNode = (jx9_hashmap_node *)SyMemBackendPoolAlloc(&pMap->pVm->sAllocator, sizeof(jx9_hashmap_node));
120 if( pNode == 0 ){
121 return 0;
122 }
123 /* Zero the stucture */
124 SyZero(pNode, sizeof(jx9_hashmap_node));
125 /* Fill in the structure */
126 pNode->pMap = &(*pMap);
127 pNode->iType = HASHMAP_BLOB_NODE;
128 pNode->nHash = nHash;
129 SyBlobInit(&pNode->xKey.sKey, &pMap->pVm->sAllocator);
130 SyBlobAppend(&pNode->xKey.sKey, pKey, nKeyLen);
131 pNode->nValIdx = nValIdx;
132 return pNode;
133}
134/*
135 * link a hashmap node to the given bucket index (last argument to this function).
136 */
137static void HashmapNodeLink(jx9_hashmap *pMap, jx9_hashmap_node *pNode, sxu32 nBucketIdx)
138{
139 /* Link */
140 if( pMap->apBucket[nBucketIdx] != 0 ){
141 pNode->pNextCollide = pMap->apBucket[nBucketIdx];
142 pMap->apBucket[nBucketIdx]->pPrevCollide = pNode;
143 }
144 pMap->apBucket[nBucketIdx] = pNode;
145 /* Link to the map list */
146 if( pMap->pFirst == 0 ){
147 pMap->pFirst = pMap->pLast = pNode;
148 /* Point to the first inserted node */
149 pMap->pCur = pNode;
150 }else{
151 MACRO_LD_PUSH(pMap->pLast, pNode);
152 }
153 ++pMap->nEntry;
154}
155/*
156 * Unlink a node from the hashmap.
157 * If the node count reaches zero then release the whole hash-bucket.
158 */
159static void jx9HashmapUnlinkNode(jx9_hashmap_node *pNode)
160{
161 jx9_hashmap *pMap = pNode->pMap;
162 jx9_vm *pVm = pMap->pVm;
163 /* Unlink from the corresponding bucket */
164 if( pNode->pPrevCollide == 0 ){
165 pMap->apBucket[pNode->nHash & (pMap->nSize - 1)] = pNode->pNextCollide;
166 }else{
167 pNode->pPrevCollide->pNextCollide = pNode->pNextCollide;
168 }
169 if( pNode->pNextCollide ){
170 pNode->pNextCollide->pPrevCollide = pNode->pPrevCollide;
171 }
172 if( pMap->pFirst == pNode ){
173 pMap->pFirst = pNode->pPrev;
174 }
175 if( pMap->pCur == pNode ){
176 /* Advance the node cursor */
177 pMap->pCur = pMap->pCur->pPrev; /* Reverse link */
178 }
179 /* Unlink from the map list */
180 MACRO_LD_REMOVE(pMap->pLast, pNode);
181 /* Restore to the free list */
182 jx9VmUnsetMemObj(pVm, pNode->nValIdx);
183 if( pNode->iType == HASHMAP_BLOB_NODE ){
184 SyBlobRelease(&pNode->xKey.sKey);
185 }
186 SyMemBackendPoolFree(&pVm->sAllocator, pNode);
187 pMap->nEntry--;
188 if( pMap->nEntry < 1 ){
189 /* Free the hash-bucket */
190 SyMemBackendFree(&pVm->sAllocator, pMap->apBucket);
191 pMap->apBucket = 0;
192 pMap->nSize = 0;
193 pMap->pFirst = pMap->pLast = pMap->pCur = 0;
194 }
195}
196#define HASHMAP_FILL_FACTOR 3
197/*
198 * Grow the hash-table and rehash all entries.
199 */
200static sxi32 HashmapGrowBucket(jx9_hashmap *pMap)
201{
202 if( pMap->nEntry >= pMap->nSize * HASHMAP_FILL_FACTOR ){
203 jx9_hashmap_node **apOld = pMap->apBucket;
204 jx9_hashmap_node *pEntry, **apNew;
205 sxu32 nNew = pMap->nSize << 1;
206 sxu32 nBucket;
207 sxu32 n;
208 if( nNew < 1 ){
209 nNew = 16;
210 }
211 /* Allocate a new bucket */
212 apNew = (jx9_hashmap_node **)SyMemBackendAlloc(&pMap->pVm->sAllocator, nNew * sizeof(jx9_hashmap_node *));
213 if( apNew == 0 ){
214 if( pMap->nSize < 1 ){
215 return SXERR_MEM; /* Fatal */
216 }
217 /* Not so fatal here, simply a performance hit */
218 return SXRET_OK;
219 }
220 /* Zero the table */
221 SyZero((void *)apNew, nNew * sizeof(jx9_hashmap_node *));
222 /* Reflect the change */
223 pMap->apBucket = apNew;
224 pMap->nSize = nNew;
225 if( apOld == 0 ){
226 /* First allocated table [i.e: no entry], return immediately */
227 return SXRET_OK;
228 }
229 /* Rehash old entries */
230 pEntry = pMap->pFirst;
231 n = 0;
232 for( ;; ){
233 if( n >= pMap->nEntry ){
234 break;
235 }
236 /* Clear the old collision link */
237 pEntry->pNextCollide = pEntry->pPrevCollide = 0;
238 /* Link to the new bucket */
239 nBucket = pEntry->nHash & (nNew - 1);
240 if( pMap->apBucket[nBucket] != 0 ){
241 pEntry->pNextCollide = pMap->apBucket[nBucket];
242 pMap->apBucket[nBucket]->pPrevCollide = pEntry;
243 }
244 pMap->apBucket[nBucket] = pEntry;
245 /* Point to the next entry */
246 pEntry = pEntry->pPrev; /* Reverse link */
247 n++;
248 }
249 /* Free the old table */
250 SyMemBackendFree(&pMap->pVm->sAllocator, (void *)apOld);
251 }
252 return SXRET_OK;
253}
254/*
255 * Insert a 64-bit integer key and it's associated value (if any) in the given
256 * hashmap.
257 */
258static sxi32 HashmapInsertIntKey(jx9_hashmap *pMap,sxi64 iKey,jx9_value *pValue)
259{
260 jx9_hashmap_node *pNode;
261 jx9_value *pObj;
262 sxu32 nIdx;
263 sxu32 nHash;
264 sxi32 rc;
265 /* Reserve a jx9_value for the value */
266 pObj = jx9VmReserveMemObj(pMap->pVm,&nIdx);
267 if( pObj == 0 ){
268 return SXERR_MEM;
269 }
270 if( pValue ){
271 /* Duplicate the value */
272 jx9MemObjStore(pValue, pObj);
273 }
274 /* Hash the key */
275 nHash = pMap->xIntHash(iKey);
276 /* Allocate a new int node */
277 pNode = HashmapNewIntNode(&(*pMap), iKey, nHash, nIdx);
278 if( pNode == 0 ){
279 return SXERR_MEM;
280 }
281 /* Make sure the bucket is big enough to hold the new entry */
282 rc = HashmapGrowBucket(&(*pMap));
283 if( rc != SXRET_OK ){
284 SyMemBackendPoolFree(&pMap->pVm->sAllocator, pNode);
285 return rc;
286 }
287 /* Perform the insertion */
288 HashmapNodeLink(&(*pMap), pNode, nHash & (pMap->nSize - 1));
289 /* All done */
290 return SXRET_OK;
291}
292/*
293 * Insert a BLOB key and it's associated value (if any) in the given
294 * hashmap.
295 */
296static sxi32 HashmapInsertBlobKey(jx9_hashmap *pMap,const void *pKey,sxu32 nKeyLen,jx9_value *pValue)
297{
298 jx9_hashmap_node *pNode;
299 jx9_value *pObj;
300 sxu32 nHash;
301 sxu32 nIdx;
302 sxi32 rc;
303 /* Reserve a jx9_value for the value */
304 pObj = jx9VmReserveMemObj(pMap->pVm,&nIdx);
305 if( pObj == 0 ){
306 return SXERR_MEM;
307 }
308 if( pValue ){
309 /* Duplicate the value */
310 jx9MemObjStore(pValue, pObj);
311 }
312 /* Hash the key */
313 nHash = pMap->xBlobHash(pKey, nKeyLen);
314 /* Allocate a new blob node */
315 pNode = HashmapNewBlobNode(&(*pMap), pKey, nKeyLen, nHash, nIdx);
316 if( pNode == 0 ){
317 return SXERR_MEM;
318 }
319 /* Make sure the bucket is big enough to hold the new entry */
320 rc = HashmapGrowBucket(&(*pMap));
321 if( rc != SXRET_OK ){
322 SyMemBackendPoolFree(&pMap->pVm->sAllocator, pNode);
323 return rc;
324 }
325 /* Perform the insertion */
326 HashmapNodeLink(&(*pMap), pNode, nHash & (pMap->nSize - 1));
327 /* All done */
328 return SXRET_OK;
329}
330/*
331 * Check if a given 64-bit integer key exists in the given hashmap.
332 * Write a pointer to the target node on success. Otherwise
333 * SXERR_NOTFOUND is returned on failure.
334 */
335static sxi32 HashmapLookupIntKey(
336 jx9_hashmap *pMap, /* Target hashmap */
337 sxi64 iKey, /* lookup key */
338 jx9_hashmap_node **ppNode /* OUT: target node on success */
339 )
340{
341 jx9_hashmap_node *pNode;
342 sxu32 nHash;
343 if( pMap->nEntry < 1 ){
344 /* Don't bother hashing, there is no entry anyway */
345 return SXERR_NOTFOUND;
346 }
347 /* Hash the key first */
348 nHash = pMap->xIntHash(iKey);
349 /* Point to the appropriate bucket */
350 pNode = pMap->apBucket[nHash & (pMap->nSize - 1)];
351 /* Perform the lookup */
352 for(;;){
353 if( pNode == 0 ){
354 break;
355 }
356 if( pNode->iType == HASHMAP_INT_NODE
357 && pNode->nHash == nHash
358 && pNode->xKey.iKey == iKey ){
359 /* Node found */
360 if( ppNode ){
361 *ppNode = pNode;
362 }
363 return SXRET_OK;
364 }
365 /* Follow the collision link */
366 pNode = pNode->pNextCollide;
367 }
368 /* No such entry */
369 return SXERR_NOTFOUND;
370}
371/*
372 * Check if a given BLOB key exists in the given hashmap.
373 * Write a pointer to the target node on success. Otherwise
374 * SXERR_NOTFOUND is returned on failure.
375 */
376static sxi32 HashmapLookupBlobKey(
377 jx9_hashmap *pMap, /* Target hashmap */
378 const void *pKey, /* Lookup key */
379 sxu32 nKeyLen, /* Key length in bytes */
380 jx9_hashmap_node **ppNode /* OUT: target node on success */
381 )
382{
383 jx9_hashmap_node *pNode;
384 sxu32 nHash;
385 if( pMap->nEntry < 1 ){
386 /* Don't bother hashing, there is no entry anyway */
387 return SXERR_NOTFOUND;
388 }
389 /* Hash the key first */
390 nHash = pMap->xBlobHash(pKey, nKeyLen);
391 /* Point to the appropriate bucket */
392 pNode = pMap->apBucket[nHash & (pMap->nSize - 1)];
393 /* Perform the lookup */
394 for(;;){
395 if( pNode == 0 ){
396 break;
397 }
398 if( pNode->iType == HASHMAP_BLOB_NODE
399 && pNode->nHash == nHash
400 && SyBlobLength(&pNode->xKey.sKey) == nKeyLen
401 && SyMemcmp(SyBlobData(&pNode->xKey.sKey), pKey, nKeyLen) == 0 ){
402 /* Node found */
403 if( ppNode ){
404 *ppNode = pNode;
405 }
406 return SXRET_OK;
407 }
408 /* Follow the collision link */
409 pNode = pNode->pNextCollide;
410 }
411 /* No such entry */
412 return SXERR_NOTFOUND;
413}
414/*
415 * Check if the given BLOB key looks like a decimal number.
416 * Retrurn TRUE on success.FALSE otherwise.
417 */
418static int HashmapIsIntKey(SyBlob *pKey)
419{
420 const char *zIn = (const char *)SyBlobData(pKey);
421 const char *zEnd = &zIn[SyBlobLength(pKey)];
422 if( (int)(zEnd-zIn) > 1 && zIn[0] == '0' ){
423 /* Octal not decimal number */
424 return FALSE;
425 }
426 if( (zIn[0] == '-' || zIn[0] == '+') && &zIn[1] < zEnd ){
427 zIn++;
428 }
429 for(;;){
430 if( zIn >= zEnd ){
431 return TRUE;
432 }
433 if( (unsigned char)zIn[0] >= 0xc0 /* UTF-8 stream */ || !SyisDigit(zIn[0]) ){
434 break;
435 }
436 zIn++;
437 }
438 /* Key does not look like a decimal number */
439 return FALSE;
440}
441/*
442 * Check if a given key exists in the given hashmap.
443 * Write a pointer to the target node on success.
444 * Otherwise SXERR_NOTFOUND is returned on failure.
445 */
446static sxi32 HashmapLookup(
447 jx9_hashmap *pMap, /* Target hashmap */
448 jx9_value *pKey, /* Lookup key */
449 jx9_hashmap_node **ppNode /* OUT: target node on success */
450 )
451{
452 jx9_hashmap_node *pNode = 0; /* cc -O6 warning */
453 sxi32 rc;
454 if( pKey->iFlags & (MEMOBJ_STRING|MEMOBJ_HASHMAP|MEMOBJ_RES) ){
455 if( (pKey->iFlags & MEMOBJ_STRING) == 0 ){
456 /* Force a string cast */
457 jx9MemObjToString(&(*pKey));
458 }
459 if( SyBlobLength(&pKey->sBlob) > 0 ){
460 /* Perform a blob lookup */
461 rc = HashmapLookupBlobKey(&(*pMap), SyBlobData(&pKey->sBlob), SyBlobLength(&pKey->sBlob), &pNode);
462 goto result;
463 }
464 }
465 /* Perform an int lookup */
466 if((pKey->iFlags & MEMOBJ_INT) == 0 ){
467 /* Force an integer cast */
468 jx9MemObjToInteger(pKey);
469 }
470 /* Perform an int lookup */
471 rc = HashmapLookupIntKey(&(*pMap), pKey->x.iVal, &pNode);
472result:
473 if( rc == SXRET_OK ){
474 /* Node found */
475 if( ppNode ){
476 *ppNode = pNode;
477 }
478 return SXRET_OK;
479 }
480 /* No such entry */
481 return SXERR_NOTFOUND;
482}
483/*
484 * Insert a given key and it's associated value (if any) in the given
485 * hashmap.
486 * If a node with the given key already exists in the database
487 * then this function overwrite the old value.
488 */
489static sxi32 HashmapInsert(
490 jx9_hashmap *pMap, /* Target hashmap */
491 jx9_value *pKey, /* Lookup key */
492 jx9_value *pVal /* Node value */
493 )
494{
495 jx9_hashmap_node *pNode = 0;
496 sxi32 rc = SXRET_OK;
497 if( pMap->nEntry < 1 && pKey && (pKey->iFlags & MEMOBJ_STRING) ){
498 pMap->iFlags |= HASHMAP_JSON_OBJECT;
499 }
500 if( pKey && (pKey->iFlags & (MEMOBJ_STRING|MEMOBJ_HASHMAP|MEMOBJ_RES)) ){
501 if( (pKey->iFlags & MEMOBJ_STRING) == 0 ){
502 /* Force a string cast */
503 jx9MemObjToString(&(*pKey));
504 }
505 if( SyBlobLength(&pKey->sBlob) < 1 || HashmapIsIntKey(&pKey->sBlob) ){
506 if(SyBlobLength(&pKey->sBlob) < 1){
507 /* Automatic index assign */
508 pKey = 0;
509 }
510 goto IntKey;
511 }
512 if( SXRET_OK == HashmapLookupBlobKey(&(*pMap), SyBlobData(&pKey->sBlob),
513 SyBlobLength(&pKey->sBlob), &pNode) ){
514 /* Overwrite the old value */
515 jx9_value *pElem;
516 pElem = (jx9_value *)SySetAt(&pMap->pVm->aMemObj, pNode->nValIdx);
517 if( pElem ){
518 if( pVal ){
519 jx9MemObjStore(pVal, pElem);
520 }else{
521 /* Nullify the entry */
522 jx9MemObjToNull(pElem);
523 }
524 }
525 return SXRET_OK;
526 }
527 /* Perform a blob-key insertion */
528 rc = HashmapInsertBlobKey(&(*pMap),SyBlobData(&pKey->sBlob),SyBlobLength(&pKey->sBlob),&(*pVal));
529 return rc;
530 }
531IntKey:
532 if( pKey ){
533 if((pKey->iFlags & MEMOBJ_INT) == 0 ){
534 /* Force an integer cast */
535 jx9MemObjToInteger(pKey);
536 }
537 if( SXRET_OK == HashmapLookupIntKey(&(*pMap), pKey->x.iVal, &pNode) ){
538 /* Overwrite the old value */
539 jx9_value *pElem;
540 pElem = (jx9_value *)SySetAt(&pMap->pVm->aMemObj, pNode->nValIdx);
541 if( pElem ){
542 if( pVal ){
543 jx9MemObjStore(pVal, pElem);
544 }else{
545 /* Nullify the entry */
546 jx9MemObjToNull(pElem);
547 }
548 }
549 return SXRET_OK;
550 }
551 /* Perform a 64-bit-int-key insertion */
552 rc = HashmapInsertIntKey(&(*pMap), pKey->x.iVal, &(*pVal));
553 if( rc == SXRET_OK ){
554 if( pKey->x.iVal >= pMap->iNextIdx ){
555 /* Increment the automatic index */
556 pMap->iNextIdx = pKey->x.iVal + 1;
557 /* Make sure the automatic index is not reserved */
558 while( SXRET_OK == HashmapLookupIntKey(&(*pMap), pMap->iNextIdx, 0) ){
559 pMap->iNextIdx++;
560 }
561 }
562 }
563 }else{
564 /* Assign an automatic index */
565 rc = HashmapInsertIntKey(&(*pMap),pMap->iNextIdx,&(*pVal));
566 if( rc == SXRET_OK ){
567 ++pMap->iNextIdx;
568 }
569 }
570 /* Insertion result */
571 return rc;
572}
573/*
574 * Extract node value.
575 */
576static jx9_value * HashmapExtractNodeValue(jx9_hashmap_node *pNode)
577{
578 /* Point to the desired object */
579 jx9_value *pObj;
580 pObj = (jx9_value *)SySetAt(&pNode->pMap->pVm->aMemObj, pNode->nValIdx);
581 return pObj;
582}
583/*
584 * Insert a node in the given hashmap.
585 * If a node with the given key already exists in the database
586 * then this function overwrite the old value.
587 */
588static sxi32 HashmapInsertNode(jx9_hashmap *pMap, jx9_hashmap_node *pNode, int bPreserve)
589{
590 jx9_value *pObj;
591 sxi32 rc;
592 /* Extract the node value */
593 pObj = HashmapExtractNodeValue(&(*pNode));
594 if( pObj == 0 ){
595 return SXERR_EMPTY;
596 }
597 /* Preserve key */
598 if( pNode->iType == HASHMAP_INT_NODE){
599 /* Int64 key */
600 if( !bPreserve ){
601 /* Assign an automatic index */
602 rc = HashmapInsert(&(*pMap), 0, pObj);
603 }else{
604 rc = HashmapInsertIntKey(&(*pMap), pNode->xKey.iKey, pObj);
605 }
606 }else{
607 /* Blob key */
608 rc = HashmapInsertBlobKey(&(*pMap), SyBlobData(&pNode->xKey.sKey),
609 SyBlobLength(&pNode->xKey.sKey), pObj);
610 }
611 return rc;
612}
613/*
614 * Compare two node values.
615 * Return 0 if the node values are equals, > 0 if pLeft is greater than pRight
616 * or < 0 if pRight is greater than pLeft.
617 * For a full description on jx9_values comparison, refer to the implementation
618 * of the [jx9MemObjCmp()] function defined in memobj.c or the official
619 * documenation.
620 */
621static sxi32 HashmapNodeCmp(jx9_hashmap_node *pLeft, jx9_hashmap_node *pRight, int bStrict)
622{
623 jx9_value sObj1, sObj2;
624 sxi32 rc;
625 if( pLeft == pRight ){
626 /*
627 * Same node.Refer to the sort() implementation defined
628 * below for more information on this sceanario.
629 */
630 return 0;
631 }
632 /* Do the comparison */
633 jx9MemObjInit(pLeft->pMap->pVm, &sObj1);
634 jx9MemObjInit(pLeft->pMap->pVm, &sObj2);
635 jx9HashmapExtractNodeValue(pLeft, &sObj1, FALSE);
636 jx9HashmapExtractNodeValue(pRight, &sObj2, FALSE);
637 rc = jx9MemObjCmp(&sObj1, &sObj2, bStrict, 0);
638 jx9MemObjRelease(&sObj1);
639 jx9MemObjRelease(&sObj2);
640 return rc;
641}
642/*
643 * Rehash a node with a 64-bit integer key.
644 * Refer to [merge_sort(), array_shift()] implementations for more information.
645 */
646static void HashmapRehashIntNode(jx9_hashmap_node *pEntry)
647{
648 jx9_hashmap *pMap = pEntry->pMap;
649 sxu32 nBucket;
650 /* Remove old collision links */
651 if( pEntry->pPrevCollide ){
652 pEntry->pPrevCollide->pNextCollide = pEntry->pNextCollide;
653 }else{
654 pMap->apBucket[pEntry->nHash & (pMap->nSize - 1)] = pEntry->pNextCollide;
655 }
656 if( pEntry->pNextCollide ){
657 pEntry->pNextCollide->pPrevCollide = pEntry->pPrevCollide;
658 }
659 pEntry->pNextCollide = pEntry->pPrevCollide = 0;
660 /* Compute the new hash */
661 pEntry->nHash = pMap->xIntHash(pMap->iNextIdx);
662 pEntry->xKey.iKey = pMap->iNextIdx;
663 nBucket = pEntry->nHash & (pMap->nSize - 1);
664 /* Link to the new bucket */
665 pEntry->pNextCollide = pMap->apBucket[nBucket];
666 if( pMap->apBucket[nBucket] ){
667 pMap->apBucket[nBucket]->pPrevCollide = pEntry;
668 }
669 pEntry->pNextCollide = pMap->apBucket[nBucket];
670 pMap->apBucket[nBucket] = pEntry;
671 /* Increment the automatic index */
672 pMap->iNextIdx++;
673}
674/*
675 * Perform a linear search on a given hashmap.
676 * Write a pointer to the target node on success.
677 * Otherwise SXERR_NOTFOUND is returned on failure.
678 * Refer to [array_intersect(), array_diff(), in_array(), ...] implementations
679 * for more information.
680 */
681static int HashmapFindValue(
682 jx9_hashmap *pMap, /* Target hashmap */
683 jx9_value *pNeedle, /* Lookup key */
684 jx9_hashmap_node **ppNode, /* OUT: target node on success */
685 int bStrict /* TRUE for strict comparison */
686 )
687{
688 jx9_hashmap_node *pEntry;
689 jx9_value sVal, *pVal;
690 jx9_value sNeedle;
691 sxi32 rc;
692 sxu32 n;
693 /* Perform a linear search since we cannot sort the hashmap based on values */
694 pEntry = pMap->pFirst;
695 n = pMap->nEntry;
696 jx9MemObjInit(pMap->pVm, &sVal);
697 jx9MemObjInit(pMap->pVm, &sNeedle);
698 for(;;){
699 if( n < 1 ){
700 break;
701 }
702 /* Extract node value */
703 pVal = HashmapExtractNodeValue(pEntry);
704 if( pVal ){
705 if( (pVal->iFlags|pNeedle->iFlags) & MEMOBJ_NULL ){
706 sxi32 iF1 = pVal->iFlags;
707 sxi32 iF2 = pNeedle->iFlags;
708 if( iF1 == iF2 ){
709 /* NULL values are equals */
710 if( ppNode ){
711 *ppNode = pEntry;
712 }
713 return SXRET_OK;
714 }
715 }else{
716 /* Duplicate value */
717 jx9MemObjLoad(pVal, &sVal);
718 jx9MemObjLoad(pNeedle, &sNeedle);
719 rc = jx9MemObjCmp(&sNeedle, &sVal, bStrict, 0);
720 jx9MemObjRelease(&sVal);
721 jx9MemObjRelease(&sNeedle);
722 if( rc == 0 ){
723 if( ppNode ){
724 *ppNode = pEntry;
725 }
726 /* Match found*/
727 return SXRET_OK;
728 }
729 }
730 }
731 /* Point to the next entry */
732 pEntry = pEntry->pPrev; /* Reverse link */
733 n--;
734 }
735 /* No such entry */
736 return SXERR_NOTFOUND;
737}
738/*
739 * Compare two hashmaps.
740 * Return 0 if the hashmaps are equals.Any other value indicates inequality.
741 * Note on array comparison operators.
742 * According to the JX9 language reference manual.
743 * Array Operators Example Name Result
744 * $a + $b Union Union of $a and $b.
745 * $a == $b Equality TRUE if $a and $b have the same key/value pairs.
746 * $a === $b Identity TRUE if $a and $b have the same key/value pairs in the same
747 * order and of the same types.
748 * $a != $b Inequality TRUE if $a is not equal to $b.
749 * $a <> $b Inequality TRUE if $a is not equal to $b.
750 * $a !== $b Non-identity TRUE if $a is not identical to $b.
751 * The + operator returns the right-hand array appended to the left-hand array;
752 * For keys that exist in both arrays, the elements from the left-hand array will be used
753 * and the matching elements from the right-hand array will be ignored.
754 * <?jx9
755 * $a = array("a" => "apple", "b" => "banana");
756 * $b = array("a" => "pear", "b" => "strawberry", "c" => "cherry");
757 * $c = $a + $b; // Union of $a and $b
758 * print "Union of \$a and \$b: \n";
759 * dump($c);
760 * $c = $b + $a; // Union of $b and $a
761 * print "Union of \$b and \$a: \n";
762 * dump($c);
763 * ?>
764 * When executed, this script will print the following:
765 * Union of $a and $b:
766 * array(3) {
767 * ["a"]=>
768 * string(5) "apple"
769 * ["b"]=>
770 * string(6) "banana"
771 * ["c"]=>
772 * string(6) "cherry"
773 * }
774 * Union of $b and $a:
775 * array(3) {
776 * ["a"]=>
777 * string(4) "pear"
778 * ["b"]=>
779 * string(10) "strawberry"
780 * ["c"]=>
781 * string(6) "cherry"
782 * }
783 * Elements of arrays are equal for the comparison if they have the same key and value.
784 */
785JX9_PRIVATE sxi32 jx9HashmapCmp(
786 jx9_hashmap *pLeft, /* Left hashmap */
787 jx9_hashmap *pRight, /* Right hashmap */
788 int bStrict /* TRUE for strict comparison */
789 )
790{
791 jx9_hashmap_node *pLe, *pRe;
792 sxi32 rc;
793 sxu32 n;
794 if( pLeft == pRight ){
795 /* Same hashmap instance. This can easily happen since hashmaps are passed by reference.
796 * Unlike the engine.
797 */
798 return 0;
799 }
800 if( pLeft->nEntry != pRight->nEntry ){
801 /* Must have the same number of entries */
802 return pLeft->nEntry > pRight->nEntry ? 1 : -1;
803 }
804 /* Point to the first inserted entry of the left hashmap */
805 pLe = pLeft->pFirst;
806 pRe = 0; /* cc warning */
807 /* Perform the comparison */
808 n = pLeft->nEntry;
809 for(;;){
810 if( n < 1 ){
811 break;
812 }
813 if( pLe->iType == HASHMAP_INT_NODE){
814 /* Int key */
815 rc = HashmapLookupIntKey(&(*pRight), pLe->xKey.iKey, &pRe);
816 }else{
817 SyBlob *pKey = &pLe->xKey.sKey;
818 /* Blob key */
819 rc = HashmapLookupBlobKey(&(*pRight), SyBlobData(pKey), SyBlobLength(pKey), &pRe);
820 }
821 if( rc != SXRET_OK ){
822 /* No such entry in the right side */
823 return 1;
824 }
825 rc = 0;
826 if( bStrict ){
827 /* Make sure, the keys are of the same type */
828 if( pLe->iType != pRe->iType ){
829 rc = 1;
830 }
831 }
832 if( !rc ){
833 /* Compare nodes */
834 rc = HashmapNodeCmp(pLe, pRe, bStrict);
835 }
836 if( rc != 0 ){
837 /* Nodes key/value differ */
838 return rc;
839 }
840 /* Point to the next entry */
841 pLe = pLe->pPrev; /* Reverse link */
842 n--;
843 }
844 return 0; /* Hashmaps are equals */
845}
846/*
847 * Merge two hashmaps.
848 * Note on the merge process
849 * According to the JX9 language reference manual.
850 * Merges the elements of two arrays together so that the values of one are appended
851 * to the end of the previous one. It returns the resulting array (pDest).
852 * If the input arrays have the same string keys, then the later value for that key
853 * will overwrite the previous one. If, however, the arrays contain numeric keys
854 * the later value will not overwrite the original value, but will be appended.
855 * Values in the input array with numeric keys will be renumbered with incrementing
856 * keys starting from zero in the result array.
857 */
858static sxi32 HashmapMerge(jx9_hashmap *pSrc, jx9_hashmap *pDest)
859{
860 jx9_hashmap_node *pEntry;
861 jx9_value sKey, *pVal;
862 sxi32 rc;
863 sxu32 n;
864 if( pSrc == pDest ){
865 /* Same map. This can easily happen since hashmaps are passed by reference.
866 * Unlike the engine.
867 */
868 return SXRET_OK;
869 }
870 /* Point to the first inserted entry in the source */
871 pEntry = pSrc->pFirst;
872 /* Perform the merge */
873 for( n = 0 ; n < pSrc->nEntry ; ++n ){
874 /* Extract the node value */
875 pVal = HashmapExtractNodeValue(pEntry);
876 if( pEntry->iType == HASHMAP_BLOB_NODE ){
877 /* Blob key insertion */
878 jx9MemObjInitFromString(pDest->pVm, &sKey, 0);
879 jx9MemObjStringAppend(&sKey, (const char *)SyBlobData(&pEntry->xKey.sKey), SyBlobLength(&pEntry->xKey.sKey));
880 rc = jx9HashmapInsert(&(*pDest), &sKey, pVal);
881 jx9MemObjRelease(&sKey);
882 }else{
883 rc = HashmapInsert(&(*pDest), 0/* Automatic index assign */, pVal);
884 }
885 if( rc != SXRET_OK ){
886 return rc;
887 }
888 /* Point to the next entry */
889 pEntry = pEntry->pPrev; /* Reverse link */
890 }
891 return SXRET_OK;
892}
893/*
894 * Duplicate the contents of a hashmap. Store the copy in pDest.
895 * Refer to the [array_pad(), array_copy(), ...] implementation for more information.
896 */
897JX9_PRIVATE sxi32 jx9HashmapDup(jx9_hashmap *pSrc, jx9_hashmap *pDest)
898{
899 jx9_hashmap_node *pEntry;
900 jx9_value sKey, *pVal;
901 sxi32 rc;
902 sxu32 n;
903 if( pSrc == pDest ){
904 /* Same map. This can easily happen since hashmaps are passed by reference.
905 * Unlike the engine.
906 */
907 return SXRET_OK;
908 }
909 /* Point to the first inserted entry in the source */
910 pEntry = pSrc->pFirst;
911 /* Perform the duplication */
912 for( n = 0 ; n < pSrc->nEntry ; ++n ){
913 /* Extract the node value */
914 pVal = HashmapExtractNodeValue(pEntry);
915 if( pEntry->iType == HASHMAP_BLOB_NODE ){
916 /* Blob key insertion */
917 jx9MemObjInitFromString(pDest->pVm, &sKey, 0);
918 jx9MemObjStringAppend(&sKey, (const char *)SyBlobData(&pEntry->xKey.sKey), SyBlobLength(&pEntry->xKey.sKey));
919 rc = jx9HashmapInsert(&(*pDest), &sKey, pVal);
920 jx9MemObjRelease(&sKey);
921 }else{
922 /* Int key insertion */
923 rc = HashmapInsertIntKey(&(*pDest), pEntry->xKey.iKey, pVal);
924 }
925 if( rc != SXRET_OK ){
926 return rc;
927 }
928 /* Point to the next entry */
929 pEntry = pEntry->pPrev; /* Reverse link */
930 }
931 return SXRET_OK;
932}
933/*
934 * Perform the union of two hashmaps.
935 * This operation is performed only if the user uses the '+' operator
936 * with a variable holding an array as follows:
937 * <?jx9
938 * $a = array("a" => "apple", "b" => "banana");
939 * $b = array("a" => "pear", "b" => "strawberry", "c" => "cherry");
940 * $c = $a + $b; // Union of $a and $b
941 * print "Union of \$a and \$b: \n";
942 * dump($c);
943 * $c = $b + $a; // Union of $b and $a
944 * print "Union of \$b and \$a: \n";
945 * dump($c);
946 * ?>
947 * When executed, this script will print the following:
948 * Union of $a and $b:
949 * array(3) {
950 * ["a"]=>
951 * string(5) "apple"
952 * ["b"]=>
953 * string(6) "banana"
954 * ["c"]=>
955 * string(6) "cherry"
956 * }
957 * Union of $b and $a:
958 * array(3) {
959 * ["a"]=>
960 * string(4) "pear"
961 * ["b"]=>
962 * string(10) "strawberry"
963 * ["c"]=>
964 * string(6) "cherry"
965 * }
966 * The + operator returns the right-hand array appended to the left-hand array;
967 * For keys that exist in both arrays, the elements from the left-hand array will be used
968 * and the matching elements from the right-hand array will be ignored.
969 */
970JX9_PRIVATE sxi32 jx9HashmapUnion(jx9_hashmap *pLeft, jx9_hashmap *pRight)
971{
972 jx9_hashmap_node *pEntry;
973 sxi32 rc = SXRET_OK;
974 jx9_value *pObj;
975 sxu32 n;
976 if( pLeft == pRight ){
977 /* Same map. This can easily happen since hashmaps are passed by reference.
978 * Unlike the engine.
979 */
980 return SXRET_OK;
981 }
982 /* Perform the union */
983 pEntry = pRight->pFirst;
984 for(n = 0 ; n < pRight->nEntry ; ++n ){
985 /* Make sure the given key does not exists in the left array */
986 if( pEntry->iType == HASHMAP_BLOB_NODE ){
987 /* BLOB key */
988 if( SXRET_OK !=
989 HashmapLookupBlobKey(&(*pLeft), SyBlobData(&pEntry->xKey.sKey), SyBlobLength(&pEntry->xKey.sKey), 0) ){
990 pObj = HashmapExtractNodeValue(pEntry);
991 if( pObj ){
992 /* Perform the insertion */
993 rc = HashmapInsertBlobKey(&(*pLeft), SyBlobData(&pEntry->xKey.sKey),
994 SyBlobLength(&pEntry->xKey.sKey),pObj);
995 if( rc != SXRET_OK ){
996 return rc;
997 }
998 }
999 }
1000 }else{
1001 /* INT key */
1002 if( SXRET_OK != HashmapLookupIntKey(&(*pLeft), pEntry->xKey.iKey, 0) ){
1003 pObj = HashmapExtractNodeValue(pEntry);
1004 if( pObj ){
1005 /* Perform the insertion */
1006 rc = HashmapInsertIntKey(&(*pLeft), pEntry->xKey.iKey, pObj);
1007 if( rc != SXRET_OK ){
1008 return rc;
1009 }
1010 }
1011 }
1012 }
1013 /* Point to the next entry */
1014 pEntry = pEntry->pPrev; /* Reverse link */
1015 }
1016 return SXRET_OK;
1017}
1018/*
1019 * Allocate a new hashmap.
1020 * Return a pointer to the freshly allocated hashmap on success.NULL otherwise.
1021 */
1022JX9_PRIVATE jx9_hashmap * jx9NewHashmap(
1023 jx9_vm *pVm, /* VM that trigger the hashmap creation */
1024 sxu32 (*xIntHash)(sxi64), /* Hash function for int keys.NULL otherwise*/
1025 sxu32 (*xBlobHash)(const void *, sxu32) /* Hash function for BLOB keys.NULL otherwise */
1026 )
1027{
1028 jx9_hashmap *pMap;
1029 /* Allocate a new instance */
1030 pMap = (jx9_hashmap *)SyMemBackendPoolAlloc(&pVm->sAllocator, sizeof(jx9_hashmap));
1031 if( pMap == 0 ){
1032 return 0;
1033 }
1034 /* Zero the structure */
1035 SyZero(pMap, sizeof(jx9_hashmap));
1036 /* Fill in the structure */
1037 pMap->pVm = &(*pVm);
1038 pMap->iRef = 1;
1039 /* pMap->iFlags = 0; */
1040 /* Default hash functions */
1041 pMap->xIntHash = xIntHash ? xIntHash : IntHash;
1042 pMap->xBlobHash = xBlobHash ? xBlobHash : BinHash;
1043 return pMap;
1044}
1045/*
1046 * Install superglobals in the given virtual machine.
1047 * Note on superglobals.
1048 * According to the JX9 language reference manual.
1049 * Superglobals are built-in variables that are always available in all scopes.
1050* Description
1051* All predefined variables in JX9 are "superglobals", which means they
1052* are available in all scopes throughout a script.
1053* These variables are:
1054* $_SERVER
1055* $_GET
1056* $_POST
1057* $_FILES
1058* $_REQUEST
1059* $_ENV
1060*/
1061JX9_PRIVATE sxi32 jx9HashmapLoadBuiltin(jx9_vm *pVm)
1062{
1063 static const char * azSuper[] = {
1064 "_SERVER", /* $_SERVER */
1065 "_GET", /* $_GET */
1066 "_POST", /* $_POST */
1067 "_FILES", /* $_FILES */
1068 "_REQUEST", /* $_REQUEST */
1069 "_COOKIE", /* $_COOKIE */
1070 "_ENV", /* $_ENV */
1071 "_HEADER", /* $_HEADER */
1072 "argv" /* $argv */
1073 };
1074 SyString *pFile;
1075 sxi32 rc;
1076 sxu32 n;
1077 /* Install globals variable now */
1078 for( n = 0 ; n < SX_ARRAYSIZE(azSuper) ; n++ ){
1079 jx9_value *pSuper;
1080 /* Request an empty array */
1081 pSuper = jx9_new_array(&(*pVm));
1082 if( pSuper == 0 ){
1083 return SXERR_MEM;
1084 }
1085 /* Install */
1086 rc = jx9_vm_config(&(*pVm),JX9_VM_CONFIG_CREATE_VAR, azSuper[n]/* Super-global name*/, pSuper/* Super-global value */);
1087 if( rc != SXRET_OK ){
1088 return rc;
1089 }
1090 /* Release the value now it have been installed */
1091 jx9_release_value(&(*pVm), pSuper);
1092 }
1093 /* Set some $_SERVER entries */
1094 pFile = (SyString *)SySetPeek(&pVm->aFiles);
1095 /*
1096 * 'SCRIPT_FILENAME'
1097 * The absolute pathname of the currently executing script.
1098 */
1099 jx9_vm_config(pVm, JX9_VM_CONFIG_SERVER_ATTR,
1100 "SCRIPT_FILENAME",
1101 pFile ? pFile->zString : ":Memory:",
1102 pFile ? pFile->nByte : sizeof(":Memory:") - 1
1103 );
1104 /* All done, all global variables are installed now */
1105 return SXRET_OK;
1106}
1107/*
1108 * Release a hashmap.
1109 */
1110JX9_PRIVATE sxi32 jx9HashmapRelease(jx9_hashmap *pMap, int FreeDS)
1111{
1112 jx9_hashmap_node *pEntry, *pNext;
1113 jx9_vm *pVm = pMap->pVm;
1114 sxu32 n;
1115 /* Start the release process */
1116 n = 0;
1117 pEntry = pMap->pFirst;
1118 for(;;){
1119 if( n >= pMap->nEntry ){
1120 break;
1121 }
1122 pNext = pEntry->pPrev; /* Reverse link */
1123 /* Restore the jx9_value to the free list */
1124 jx9VmUnsetMemObj(pVm, pEntry->nValIdx);
1125 /* Release the node */
1126 if( pEntry->iType == HASHMAP_BLOB_NODE ){
1127 SyBlobRelease(&pEntry->xKey.sKey);
1128 }
1129 SyMemBackendPoolFree(&pVm->sAllocator, pEntry);
1130 /* Point to the next entry */
1131 pEntry = pNext;
1132 n++;
1133 }
1134 if( pMap->nEntry > 0 ){
1135 /* Release the hash bucket */
1136 SyMemBackendFree(&pVm->sAllocator, pMap->apBucket);
1137 }
1138 if( FreeDS ){
1139 /* Free the whole instance */
1140 SyMemBackendPoolFree(&pVm->sAllocator, pMap);
1141 }else{
1142 /* Keep the instance but reset it's fields */
1143 pMap->apBucket = 0;
1144 pMap->iNextIdx = 0;
1145 pMap->nEntry = pMap->nSize = 0;
1146 pMap->pFirst = pMap->pLast = pMap->pCur = 0;
1147 }
1148 return SXRET_OK;
1149}
1150/*
1151 * Decrement the reference count of a given hashmap.
1152 * If the count reaches zero which mean no more variables
1153 * are pointing to this hashmap, then release the whole instance.
1154 */
1155JX9_PRIVATE void jx9HashmapUnref(jx9_hashmap *pMap)
1156{
1157 pMap->iRef--;
1158 if( pMap->iRef < 1 ){
1159 jx9HashmapRelease(pMap, TRUE);
1160 }
1161}
1162/*
1163 * Check if a given key exists in the given hashmap.
1164 * Write a pointer to the target node on success.
1165 * Otherwise SXERR_NOTFOUND is returned on failure.
1166 */
1167JX9_PRIVATE sxi32 jx9HashmapLookup(
1168 jx9_hashmap *pMap, /* Target hashmap */
1169 jx9_value *pKey, /* Lookup key */
1170 jx9_hashmap_node **ppNode /* OUT: Target node on success */
1171 )
1172{
1173 sxi32 rc;
1174 if( pMap->nEntry < 1 ){
1175 /* TICKET 1433-25: Don't bother hashing, the hashmap is empty anyway.
1176 */
1177 return SXERR_NOTFOUND;
1178 }
1179 rc = HashmapLookup(&(*pMap), &(*pKey), ppNode);
1180 return rc;
1181}
1182/*
1183 * Insert a given key and it's associated value (if any) in the given
1184 * hashmap.
1185 * If a node with the given key already exists in the database
1186 * then this function overwrite the old value.
1187 */
1188JX9_PRIVATE sxi32 jx9HashmapInsert(
1189 jx9_hashmap *pMap, /* Target hashmap */
1190 jx9_value *pKey, /* Lookup key */
1191 jx9_value *pVal /* Node value.NULL otherwise */
1192 )
1193{
1194 sxi32 rc;
1195 rc = HashmapInsert(&(*pMap), &(*pKey), &(*pVal));
1196 return rc;
1197}
1198/*
1199 * Reset the node cursor of a given hashmap.
1200 */
1201JX9_PRIVATE void jx9HashmapResetLoopCursor(jx9_hashmap *pMap)
1202{
1203 /* Reset the loop cursor */
1204 pMap->pCur = pMap->pFirst;
1205}
1206/*
1207 * Return a pointer to the node currently pointed by the node cursor.
1208 * If the cursor reaches the end of the list, then this function
1209 * return NULL.
1210 * Note that the node cursor is automatically advanced by this function.
1211 */
1212JX9_PRIVATE jx9_hashmap_node * jx9HashmapGetNextEntry(jx9_hashmap *pMap)
1213{
1214 jx9_hashmap_node *pCur = pMap->pCur;
1215 if( pCur == 0 ){
1216 /* End of the list, return null */
1217 return 0;
1218 }
1219 /* Advance the node cursor */
1220 pMap->pCur = pCur->pPrev; /* Reverse link */
1221 return pCur;
1222}
1223/*
1224 * Extract a node value.
1225 */
1226JX9_PRIVATE jx9_value * jx9HashmapGetNodeValue(jx9_hashmap_node *pNode)
1227{
1228 jx9_value *pValue;
1229 pValue = HashmapExtractNodeValue(pNode);
1230 return pValue;
1231}
1232/*
1233 * Extract a node value (Second).
1234 */
1235JX9_PRIVATE void jx9HashmapExtractNodeValue(jx9_hashmap_node *pNode, jx9_value *pValue, int bStore)
1236{
1237 jx9_value *pEntry = HashmapExtractNodeValue(pNode);
1238 if( pEntry ){
1239 if( bStore ){
1240 jx9MemObjStore(pEntry, pValue);
1241 }else{
1242 jx9MemObjLoad(pEntry, pValue);
1243 }
1244 }else{
1245 jx9MemObjRelease(pValue);
1246 }
1247}
1248/*
1249 * Extract a node key.
1250 */
1251JX9_PRIVATE void jx9HashmapExtractNodeKey(jx9_hashmap_node *pNode,jx9_value *pKey)
1252{
1253 /* Fill with the current key */
1254 if( pNode->iType == HASHMAP_INT_NODE ){
1255 if( SyBlobLength(&pKey->sBlob) > 0 ){
1256 SyBlobRelease(&pKey->sBlob);
1257 }
1258 pKey->x.iVal = pNode->xKey.iKey;
1259 MemObjSetType(pKey, MEMOBJ_INT);
1260 }else{
1261 SyBlobReset(&pKey->sBlob);
1262 SyBlobAppend(&pKey->sBlob, SyBlobData(&pNode->xKey.sKey), SyBlobLength(&pNode->xKey.sKey));
1263 MemObjSetType(pKey, MEMOBJ_STRING);
1264 }
1265}
1266#ifndef JX9_DISABLE_BUILTIN_FUNC
1267/*
1268 * Store the address of nodes value in the given container.
1269 * Refer to the [vfprintf(), vprintf(), vsprintf()] implementations
1270 * defined in 'builtin.c' for more information.
1271 */
1272JX9_PRIVATE int jx9HashmapValuesToSet(jx9_hashmap *pMap, SySet *pOut)
1273{
1274 jx9_hashmap_node *pEntry = pMap->pFirst;
1275 jx9_value *pValue;
1276 sxu32 n;
1277 /* Initialize the container */
1278 SySetInit(pOut, &pMap->pVm->sAllocator, sizeof(jx9_value *));
1279 for(n = 0 ; n < pMap->nEntry ; n++ ){
1280 /* Extract node value */
1281 pValue = HashmapExtractNodeValue(pEntry);
1282 if( pValue ){
1283 SySetPut(pOut, (const void *)&pValue);
1284 }
1285 /* Point to the next entry */
1286 pEntry = pEntry->pPrev; /* Reverse link */
1287 }
1288 /* Total inserted entries */
1289 return (int)SySetUsed(pOut);
1290}
1291#endif /* JX9_DISABLE_BUILTIN_FUNC */
1292/*
1293 * Merge sort.
1294 * The merge sort implementation is based on the one found in the SQLite3 source tree.
1295 * Status: Public domain
1296 */
1297/* Node comparison callback signature */
1298typedef sxi32 (*ProcNodeCmp)(jx9_hashmap_node *, jx9_hashmap_node *, void *);
1299/*
1300** Inputs:
1301** a: A sorted, null-terminated linked list. (May be null).
1302** b: A sorted, null-terminated linked list. (May be null).
1303** cmp: A pointer to the comparison function.
1304**
1305** Return Value:
1306** A pointer to the head of a sorted list containing the elements
1307** of both a and b.
1308**
1309** Side effects:
1310** The "next", "prev" pointers for elements in the lists a and b are
1311** changed.
1312*/
1313static jx9_hashmap_node * HashmapNodeMerge(jx9_hashmap_node *pA, jx9_hashmap_node *pB, ProcNodeCmp xCmp, void *pCmpData)
1314{
1315 jx9_hashmap_node result, *pTail;
1316 /* Prevent compiler warning */
1317 result.pNext = result.pPrev = 0;
1318 pTail = &result;
1319 while( pA && pB ){
1320 if( xCmp(pA, pB, pCmpData) < 0 ){
1321 pTail->pPrev = pA;
1322 pA->pNext = pTail;
1323 pTail = pA;
1324 pA = pA->pPrev;
1325 }else{
1326 pTail->pPrev = pB;
1327 pB->pNext = pTail;
1328 pTail = pB;
1329 pB = pB->pPrev;
1330 }
1331 }
1332 if( pA ){
1333 pTail->pPrev = pA;
1334 pA->pNext = pTail;
1335 }else if( pB ){
1336 pTail->pPrev = pB;
1337 pB->pNext = pTail;
1338 }else{
1339 pTail->pPrev = pTail->pNext = 0;
1340 }
1341 return result.pPrev;
1342}
1343/*
1344** Inputs:
1345** Map: Input hashmap
1346** cmp: A comparison function.
1347**
1348** Return Value:
1349** Sorted hashmap.
1350**
1351** Side effects:
1352** The "next" pointers for elements in list are changed.
1353*/
1354#define N_SORT_BUCKET 32
1355static sxi32 HashmapMergeSort(jx9_hashmap *pMap, ProcNodeCmp xCmp, void *pCmpData)
1356{
1357 jx9_hashmap_node *a[N_SORT_BUCKET], *p, *pIn;
1358 sxu32 i;
1359 SyZero(a, sizeof(a));
1360 /* Point to the first inserted entry */
1361 pIn = pMap->pFirst;
1362 while( pIn ){
1363 p = pIn;
1364 pIn = p->pPrev;
1365 p->pPrev = 0;
1366 for(i=0; i<N_SORT_BUCKET-1; i++){
1367 if( a[i]==0 ){
1368 a[i] = p;
1369 break;
1370 }else{
1371 p = HashmapNodeMerge(a[i], p, xCmp, pCmpData);
1372 a[i] = 0;
1373 }
1374 }
1375 if( i==N_SORT_BUCKET-1 ){
1376 /* To get here, there need to be 2^(N_SORT_BUCKET) elements in he input list.
1377 * But that is impossible.
1378 */
1379 a[i] = HashmapNodeMerge(a[i], p, xCmp, pCmpData);
1380 }
1381 }
1382 p = a[0];
1383 for(i=1; i<N_SORT_BUCKET; i++){
1384 p = HashmapNodeMerge(p, a[i], xCmp, pCmpData);
1385 }
1386 p->pNext = 0;
1387 /* Reflect the change */
1388 pMap->pFirst = p;
1389 /* Reset the loop cursor */
1390 pMap->pCur = pMap->pFirst;
1391 return SXRET_OK;
1392}
1393/*
1394 * Node comparison callback.
1395 * used-by: [sort(), asort(), ...]
1396 */
1397static sxi32 HashmapCmpCallback1(jx9_hashmap_node *pA, jx9_hashmap_node *pB, void *pCmpData)
1398{
1399 jx9_value sA, sB;
1400 sxi32 iFlags;
1401 int rc;
1402 if( pCmpData == 0 ){
1403 /* Perform a standard comparison */
1404 rc = HashmapNodeCmp(pA, pB, FALSE);
1405 return rc;
1406 }
1407 iFlags = SX_PTR_TO_INT(pCmpData);
1408 /* Duplicate node values */
1409 jx9MemObjInit(pA->pMap->pVm, &sA);
1410 jx9MemObjInit(pA->pMap->pVm, &sB);
1411 jx9HashmapExtractNodeValue(pA, &sA, FALSE);
1412 jx9HashmapExtractNodeValue(pB, &sB, FALSE);
1413 if( iFlags == 5 ){
1414 /* String cast */
1415 if( (sA.iFlags & MEMOBJ_STRING) == 0 ){
1416 jx9MemObjToString(&sA);
1417 }
1418 if( (sB.iFlags & MEMOBJ_STRING) == 0 ){
1419 jx9MemObjToString(&sB);
1420 }
1421 }else{
1422 /* Numeric cast */
1423 jx9MemObjToNumeric(&sA);
1424 jx9MemObjToNumeric(&sB);
1425 }
1426 /* Perform the comparison */
1427 rc = jx9MemObjCmp(&sA, &sB, FALSE, 0);
1428 jx9MemObjRelease(&sA);
1429 jx9MemObjRelease(&sB);
1430 return rc;
1431}
1432/*
1433 * Node comparison callback.
1434 * Used by: [rsort(), arsort()];
1435 */
1436static sxi32 HashmapCmpCallback3(jx9_hashmap_node *pA, jx9_hashmap_node *pB, void *pCmpData)
1437{
1438 jx9_value sA, sB;
1439 sxi32 iFlags;
1440 int rc;
1441 if( pCmpData == 0 ){
1442 /* Perform a standard comparison */
1443 rc = HashmapNodeCmp(pA, pB, FALSE);
1444 return -rc;
1445 }
1446 iFlags = SX_PTR_TO_INT(pCmpData);
1447 /* Duplicate node values */
1448 jx9MemObjInit(pA->pMap->pVm, &sA);
1449 jx9MemObjInit(pA->pMap->pVm, &sB);
1450 jx9HashmapExtractNodeValue(pA, &sA, FALSE);
1451 jx9HashmapExtractNodeValue(pB, &sB, FALSE);
1452 if( iFlags == 5 ){
1453 /* String cast */
1454 if( (sA.iFlags & MEMOBJ_STRING) == 0 ){
1455 jx9MemObjToString(&sA);
1456 }
1457 if( (sB.iFlags & MEMOBJ_STRING) == 0 ){
1458 jx9MemObjToString(&sB);
1459 }
1460 }else{
1461 /* Numeric cast */
1462 jx9MemObjToNumeric(&sA);
1463 jx9MemObjToNumeric(&sB);
1464 }
1465 /* Perform the comparison */
1466 rc = jx9MemObjCmp(&sA, &sB, FALSE, 0);
1467 jx9MemObjRelease(&sA);
1468 jx9MemObjRelease(&sB);
1469 return -rc;
1470}
1471/*
1472 * Node comparison callback: Invoke an user-defined callback for the purpose of node comparison.
1473 * used-by: [usort(), uasort()]
1474 */
1475static sxi32 HashmapCmpCallback4(jx9_hashmap_node *pA, jx9_hashmap_node *pB, void *pCmpData)
1476{
1477 jx9_value sResult, *pCallback;
1478 jx9_value *pV1, *pV2;
1479 jx9_value *apArg[2]; /* Callback arguments */
1480 sxi32 rc;
1481 /* Point to the desired callback */
1482 pCallback = (jx9_value *)pCmpData;
1483 /* initialize the result value */
1484 jx9MemObjInit(pA->pMap->pVm, &sResult);
1485 /* Extract nodes values */
1486 pV1 = HashmapExtractNodeValue(pA);
1487 pV2 = HashmapExtractNodeValue(pB);
1488 apArg[0] = pV1;
1489 apArg[1] = pV2;
1490 /* Invoke the callback */
1491 rc = jx9VmCallUserFunction(pA->pMap->pVm, pCallback, 2, apArg, &sResult);
1492 if( rc != SXRET_OK ){
1493 /* An error occured while calling user defined function [i.e: not defined] */
1494 rc = -1; /* Set a dummy result */
1495 }else{
1496 /* Extract callback result */
1497 if((sResult.iFlags & MEMOBJ_INT) == 0 ){
1498 /* Perform an int cast */
1499 jx9MemObjToInteger(&sResult);
1500 }
1501 rc = (sxi32)sResult.x.iVal;
1502 }
1503 jx9MemObjRelease(&sResult);
1504 /* Callback result */
1505 return rc;
1506}
1507/*
1508 * Rehash all nodes keys after a merge-sort have been applied.
1509 * Used by [sort(), usort() and rsort()].
1510 */
1511static void HashmapSortRehash(jx9_hashmap *pMap)
1512{
1513 jx9_hashmap_node *p, *pLast;
1514 sxu32 i;
1515 /* Rehash all entries */
1516 pLast = p = pMap->pFirst;
1517 pMap->iNextIdx = 0; /* Reset the automatic index */
1518 i = 0;
1519 for( ;; ){
1520 if( i >= pMap->nEntry ){
1521 pMap->pLast = pLast; /* Fix the last link broken by the merge-sort */
1522 break;
1523 }
1524 if( p->iType == HASHMAP_BLOB_NODE ){
1525 /* Do not maintain index association as requested by the JX9 specification */
1526 SyBlobRelease(&p->xKey.sKey);
1527 /* Change key type */
1528 p->iType = HASHMAP_INT_NODE;
1529 }
1530 HashmapRehashIntNode(p);
1531 /* Point to the next entry */
1532 i++;
1533 pLast = p;
1534 p = p->pPrev; /* Reverse link */
1535 }
1536}
1537/*
1538 * Array functions implementation.
1539 * Authors:
1540 * Symisc Systems, devel@symisc.net.
1541 * Copyright (C) Symisc Systems, http://jx9.symisc.net
1542 * Status:
1543 * Stable.
1544 */
1545/*
1546 * bool sort(array &$array[, int $sort_flags = SORT_REGULAR ] )
1547 * Sort an array.
1548 * Parameters
1549 * $array
1550 * The input array.
1551 * $sort_flags
1552 * The optional second parameter sort_flags may be used to modify the sorting behavior using these values:
1553 * Sorting type flags:
1554 * SORT_REGULAR - compare items normally (don't change types)
1555 * SORT_NUMERIC - compare items numerically
1556 * SORT_STRING - compare items as strings
1557 * Return
1558 * TRUE on success or FALSE on failure.
1559 *
1560 */
1561static int jx9_hashmap_sort(jx9_context *pCtx, int nArg, jx9_value **apArg)
1562{
1563 jx9_hashmap *pMap;
1564 /* Make sure we are dealing with a valid hashmap */
1565 if( nArg < 1 || !jx9_value_is_json_array(apArg[0]) ){
1566 /* Missing/Invalid arguments, return FALSE */
1567 jx9_result_bool(pCtx, 0);
1568 return JX9_OK;
1569 }
1570 /* Point to the internal representation of the input hashmap */
1571 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1572 if( pMap->nEntry > 1 ){
1573 sxi32 iCmpFlags = 0;
1574 if( nArg > 1 ){
1575 /* Extract comparison flags */
1576 iCmpFlags = jx9_value_to_int(apArg[1]);
1577 if( iCmpFlags == 3 /* SORT_REGULAR */ ){
1578 iCmpFlags = 0; /* Standard comparison */
1579 }
1580 }
1581 /* Do the merge sort */
1582 HashmapMergeSort(pMap, HashmapCmpCallback1, SX_INT_TO_PTR(iCmpFlags));
1583 /* Rehash [Do not maintain index association as requested by the JX9 specification] */
1584 HashmapSortRehash(pMap);
1585 }
1586 /* All done, return TRUE */
1587 jx9_result_bool(pCtx, 1);
1588 return JX9_OK;
1589}
1590/*
1591 * bool rsort(array &$array[, int $sort_flags = SORT_REGULAR ] )
1592 * Sort an array in reverse order.
1593 * Parameters
1594 * $array
1595 * The input array.
1596 * $sort_flags
1597 * The optional second parameter sort_flags may be used to modify the sorting behavior using these values:
1598 * Sorting type flags:
1599 * SORT_REGULAR - compare items normally (don't change types)
1600 * SORT_NUMERIC - compare items numerically
1601 * SORT_STRING - compare items as strings
1602 * Return
1603 * TRUE on success or FALSE on failure.
1604 */
1605static int jx9_hashmap_rsort(jx9_context *pCtx, int nArg, jx9_value **apArg)
1606{
1607 jx9_hashmap *pMap;
1608 /* Make sure we are dealing with a valid hashmap */
1609 if( nArg < 1 || !jx9_value_is_json_array(apArg[0]) ){
1610 /* Missing/Invalid arguments, return FALSE */
1611 jx9_result_bool(pCtx, 0);
1612 return JX9_OK;
1613 }
1614 /* Point to the internal representation of the input hashmap */
1615 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1616 if( pMap->nEntry > 1 ){
1617 sxi32 iCmpFlags = 0;
1618 if( nArg > 1 ){
1619 /* Extract comparison flags */
1620 iCmpFlags = jx9_value_to_int(apArg[1]);
1621 if( iCmpFlags == 3 /* SORT_REGULAR */ ){
1622 iCmpFlags = 0; /* Standard comparison */
1623 }
1624 }
1625 /* Do the merge sort */
1626 HashmapMergeSort(pMap, HashmapCmpCallback3, SX_INT_TO_PTR(iCmpFlags));
1627 /* Rehash [Do not maintain index association as requested by the JX9 specification] */
1628 HashmapSortRehash(pMap);
1629 }
1630 /* All done, return TRUE */
1631 jx9_result_bool(pCtx, 1);
1632 return JX9_OK;
1633}
1634/*
1635 * bool usort(array &$array, callable $cmp_function)
1636 * Sort an array by values using a user-defined comparison function.
1637 * Parameters
1638 * $array
1639 * The input array.
1640 * $cmp_function
1641 * The comparison function must return an integer less than, equal to, or greater
1642 * than zero if the first argument is considered to be respectively less than, equal
1643 * to, or greater than the second.
1644 * int callback ( mixed $a, mixed $b )
1645 * Return
1646 * TRUE on success or FALSE on failure.
1647 */
1648static int jx9_hashmap_usort(jx9_context *pCtx, int nArg, jx9_value **apArg)
1649{
1650 jx9_hashmap *pMap;
1651 /* Make sure we are dealing with a valid hashmap */
1652 if( nArg < 1 || !jx9_value_is_json_array(apArg[0]) ){
1653 /* Missing/Invalid arguments, return FALSE */
1654 jx9_result_bool(pCtx, 0);
1655 return JX9_OK;
1656 }
1657 /* Point to the internal representation of the input hashmap */
1658 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1659 if( pMap->nEntry > 1 ){
1660 jx9_value *pCallback = 0;
1661 ProcNodeCmp xCmp;
1662 xCmp = HashmapCmpCallback4; /* User-defined function as the comparison callback */
1663 if( nArg > 1 && jx9_value_is_callable(apArg[1]) ){
1664 /* Point to the desired callback */
1665 pCallback = apArg[1];
1666 }else{
1667 /* Use the default comparison function */
1668 xCmp = HashmapCmpCallback1;
1669 }
1670 /* Do the merge sort */
1671 HashmapMergeSort(pMap, xCmp, pCallback);
1672 /* Rehash [Do not maintain index association as requested by the JX9 specification] */
1673 HashmapSortRehash(pMap);
1674 }
1675 /* All done, return TRUE */
1676 jx9_result_bool(pCtx, 1);
1677 return JX9_OK;
1678}
1679/*
1680 * int count(array $var [, int $mode = COUNT_NORMAL ])
1681 * Count all elements in an array, or something in an object.
1682 * Parameters
1683 * $var
1684 * The array or the object.
1685 * $mode
1686 * If the optional mode parameter is set to COUNT_RECURSIVE (or 1), count()
1687 * will recursively count the array. This is particularly useful for counting
1688 * all the elements of a multidimensional array. count() does not detect infinite
1689 * recursion.
1690 * Return
1691 * Returns the number of elements in the array.
1692 */
1693static int jx9_hashmap_count(jx9_context *pCtx, int nArg, jx9_value **apArg)
1694{
1695 int bRecursive = FALSE;
1696 sxi64 iCount;
1697 if( nArg < 1 ){
1698 /* Missing arguments, return 0 */
1699 jx9_result_int(pCtx, 0);
1700 return JX9_OK;
1701 }
1702 if( !jx9_value_is_json_array(apArg[0]) ){
1703 /* TICKET 1433-19: Handle objects */
1704 int res = !jx9_value_is_null(apArg[0]);
1705 jx9_result_int(pCtx, res);
1706 return JX9_OK;
1707 }
1708 if( nArg > 1 ){
1709 /* Recursive count? */
1710 bRecursive = jx9_value_to_int(apArg[1]) == 1 /* COUNT_RECURSIVE */;
1711 }
1712 /* Count */
1713 iCount = HashmapCount((jx9_hashmap *)apArg[0]->x.pOther, bRecursive, 0);
1714 jx9_result_int64(pCtx, iCount);
1715 return JX9_OK;
1716}
1717/*
1718 * bool array_key_exists(value $key, array $search)
1719 * Checks if the given key or index exists in the array.
1720 * Parameters
1721 * $key
1722 * Value to check.
1723 * $search
1724 * An array with keys to check.
1725 * Return
1726 * TRUE on success or FALSE on failure.
1727 */
1728static int jx9_hashmap_key_exists(jx9_context *pCtx, int nArg, jx9_value **apArg)
1729{
1730 sxi32 rc;
1731 if( nArg < 2 ){
1732 /* Missing arguments, return FALSE */
1733 jx9_result_bool(pCtx, 0);
1734 return JX9_OK;
1735 }
1736 /* Make sure we are dealing with a valid hashmap */
1737 if( !jx9_value_is_json_array(apArg[1]) ){
1738 /* Invalid argument, return FALSE */
1739 jx9_result_bool(pCtx, 0);
1740 return JX9_OK;
1741 }
1742 /* Perform the lookup */
1743 rc = jx9HashmapLookup((jx9_hashmap *)apArg[1]->x.pOther, apArg[0], 0);
1744 /* lookup result */
1745 jx9_result_bool(pCtx, rc == SXRET_OK ? 1 : 0);
1746 return JX9_OK;
1747}
1748/*
1749 * value array_pop(array $array)
1750 * POP the last inserted element from the array.
1751 * Parameter
1752 * The array to get the value from.
1753 * Return
1754 * Poped value or NULL on failure.
1755 */
1756static int jx9_hashmap_pop(jx9_context *pCtx, int nArg, jx9_value **apArg)
1757{
1758 jx9_hashmap *pMap;
1759 if( nArg < 1 ){
1760 /* Missing arguments, return null */
1761 jx9_result_null(pCtx);
1762 return JX9_OK;
1763 }
1764 /* Make sure we are dealing with a valid hashmap */
1765 if( !jx9_value_is_json_array(apArg[0]) ){
1766 /* Invalid argument, return null */
1767 jx9_result_null(pCtx);
1768 return JX9_OK;
1769 }
1770 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1771 if( pMap->nEntry < 1 ){
1772 /* Noting to pop, return NULL */
1773 jx9_result_null(pCtx);
1774 }else{
1775 jx9_hashmap_node *pLast = pMap->pLast;
1776 jx9_value *pObj;
1777 pObj = HashmapExtractNodeValue(pLast);
1778 if( pObj ){
1779 /* Node value */
1780 jx9_result_value(pCtx, pObj);
1781 /* Unlink the node */
1782 jx9HashmapUnlinkNode(pLast);
1783 }else{
1784 jx9_result_null(pCtx);
1785 }
1786 /* Reset the cursor */
1787 pMap->pCur = pMap->pFirst;
1788 }
1789 return JX9_OK;
1790}
1791/*
1792 * int array_push($array, $var, ...)
1793 * Push one or more elements onto the end of array. (Stack insertion)
1794 * Parameters
1795 * array
1796 * The input array.
1797 * var
1798 * On or more value to push.
1799 * Return
1800 * New array count (including old items).
1801 */
1802static int jx9_hashmap_push(jx9_context *pCtx, int nArg, jx9_value **apArg)
1803{
1804 jx9_hashmap *pMap;
1805 sxi32 rc;
1806 int i;
1807 if( nArg < 1 ){
1808 /* Missing arguments, return 0 */
1809 jx9_result_int(pCtx, 0);
1810 return JX9_OK;
1811 }
1812 /* Make sure we are dealing with a valid hashmap */
1813 if( !jx9_value_is_json_array(apArg[0]) ){
1814 /* Invalid argument, return 0 */
1815 jx9_result_int(pCtx, 0);
1816 return JX9_OK;
1817 }
1818 /* Point to the internal representation of the input hashmap */
1819 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1820 /* Start pushing given values */
1821 for( i = 1 ; i < nArg ; ++i ){
1822 rc = jx9HashmapInsert(pMap, 0, apArg[i]);
1823 if( rc != SXRET_OK ){
1824 break;
1825 }
1826 }
1827 /* Return the new count */
1828 jx9_result_int64(pCtx, (sxi64)pMap->nEntry);
1829 return JX9_OK;
1830}
1831/*
1832 * value array_shift(array $array)
1833 * Shift an element off the beginning of array.
1834 * Parameter
1835 * The array to get the value from.
1836 * Return
1837 * Shifted value or NULL on failure.
1838 */
1839static int jx9_hashmap_shift(jx9_context *pCtx, int nArg, jx9_value **apArg)
1840{
1841 jx9_hashmap *pMap;
1842 if( nArg < 1 ){
1843 /* Missing arguments, return null */
1844 jx9_result_null(pCtx);
1845 return JX9_OK;
1846 }
1847 /* Make sure we are dealing with a valid hashmap */
1848 if( !jx9_value_is_json_array(apArg[0]) ){
1849 /* Invalid argument, return null */
1850 jx9_result_null(pCtx);
1851 return JX9_OK;
1852 }
1853 /* Point to the internal representation of the hashmap */
1854 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
1855 if( pMap->nEntry < 1 ){
1856 /* Empty hashmap, return NULL */
1857 jx9_result_null(pCtx);
1858 }else{
1859 jx9_hashmap_node *pEntry = pMap->pFirst;
1860 jx9_value *pObj;
1861 sxu32 n;
1862 pObj = HashmapExtractNodeValue(pEntry);
1863 if( pObj ){
1864 /* Node value */
1865 jx9_result_value(pCtx, pObj);
1866 /* Unlink the first node */
1867 jx9HashmapUnlinkNode(pEntry);
1868 }else{
1869 jx9_result_null(pCtx);
1870 }
1871 /* Rehash all int keys */
1872 n = pMap->nEntry;
1873 pEntry = pMap->pFirst;
1874 pMap->iNextIdx = 0; /* Reset the automatic index */
1875 for(;;){
1876 if( n < 1 ){
1877 break;
1878 }
1879 if( pEntry->iType == HASHMAP_INT_NODE ){
1880 HashmapRehashIntNode(pEntry);
1881 }
1882 /* Point to the next entry */
1883 pEntry = pEntry->pPrev; /* Reverse link */
1884 n--;
1885 }
1886 /* Reset the cursor */
1887 pMap->pCur = pMap->pFirst;
1888 }
1889 return JX9_OK;
1890}
1891/*
1892 * Extract the node cursor value.
1893 */
1894static sxi32 HashmapCurrentValue(jx9_context *pCtx, jx9_hashmap *pMap, int iDirection)
1895{
1896 jx9_hashmap_node *pCur = pMap->pCur;
1897 jx9_value *pVal;
1898 if( pCur == 0 ){
1899 /* Cursor does not point to anything, return FALSE */
1900 jx9_result_bool(pCtx, 0);
1901 return JX9_OK;
1902 }
1903 if( iDirection != 0 ){
1904 if( iDirection > 0 ){
1905 /* Point to the next entry */
1906 pMap->pCur = pCur->pPrev; /* Reverse link */
1907 pCur = pMap->pCur;
1908 }else{
1909 /* Point to the previous entry */
1910 pMap->pCur = pCur->pNext; /* Reverse link */
1911 pCur = pMap->pCur;
1912 }
1913 if( pCur == 0 ){
1914 /* End of input reached, return FALSE */
1915 jx9_result_bool(pCtx, 0);
1916 return JX9_OK;
1917 }
1918 }
1919 /* Point to the desired element */
1920 pVal = HashmapExtractNodeValue(pCur);
1921 if( pVal ){
1922 jx9_result_value(pCtx, pVal);
1923 }else{
1924 jx9_result_bool(pCtx, 0);
1925 }
1926 return JX9_OK;
1927}
1928/*
1929 * value current(array $array)
1930 * Return the current element in an array.
1931 * Parameter
1932 * $input: The input array.
1933 * Return
1934 * The current() function simply returns the value of the array element that's currently
1935 * being pointed to by the internal pointer. It does not move the pointer in any way.
1936 * If the internal pointer points beyond the end of the elements list or the array
1937 * is empty, current() returns FALSE.
1938 */
1939static int jx9_hashmap_current(jx9_context *pCtx, int nArg, jx9_value **apArg)
1940{
1941 if( nArg < 1 ){
1942 /* Missing arguments, return FALSE */
1943 jx9_result_bool(pCtx, 0);
1944 return JX9_OK;
1945 }
1946 /* Make sure we are dealing with a valid hashmap */
1947 if( !jx9_value_is_json_array(apArg[0]) ){
1948 /* Invalid argument, return FALSE */
1949 jx9_result_bool(pCtx, 0);
1950 return JX9_OK;
1951 }
1952 HashmapCurrentValue(&(*pCtx), (jx9_hashmap *)apArg[0]->x.pOther, 0);
1953 return JX9_OK;
1954}
1955/*
1956 * value next(array $input)
1957 * Advance the internal array pointer of an array.
1958 * Parameter
1959 * $input: The input array.
1960 * Return
1961 * next() behaves like current(), with one difference. It advances the internal array
1962 * pointer one place forward before returning the element value. That means it returns
1963 * the next array value and advances the internal array pointer by one.
1964 */
1965static int jx9_hashmap_next(jx9_context *pCtx, int nArg, jx9_value **apArg)
1966{
1967 if( nArg < 1 ){
1968 /* Missing arguments, return FALSE */
1969 jx9_result_bool(pCtx, 0);
1970 return JX9_OK;
1971 }
1972 /* Make sure we are dealing with a valid hashmap */
1973 if( !jx9_value_is_json_array(apArg[0]) ){
1974 /* Invalid argument, return FALSE */
1975 jx9_result_bool(pCtx, 0);
1976 return JX9_OK;
1977 }
1978 HashmapCurrentValue(&(*pCtx), (jx9_hashmap *)apArg[0]->x.pOther, 1);
1979 return JX9_OK;
1980}
1981/*
1982 * value prev(array $input)
1983 * Rewind the internal array pointer.
1984 * Parameter
1985 * $input: The input array.
1986 * Return
1987 * Returns the array value in the previous place that's pointed
1988 * to by the internal array pointer, or FALSE if there are no more
1989 * elements.
1990 */
1991static int jx9_hashmap_prev(jx9_context *pCtx, int nArg, jx9_value **apArg)
1992{
1993 if( nArg < 1 ){
1994 /* Missing arguments, return FALSE */
1995 jx9_result_bool(pCtx, 0);
1996 return JX9_OK;
1997 }
1998 /* Make sure we are dealing with a valid hashmap */
1999 if( !jx9_value_is_json_array(apArg[0]) ){
2000 /* Invalid argument, return FALSE */
2001 jx9_result_bool(pCtx, 0);
2002 return JX9_OK;
2003 }
2004 HashmapCurrentValue(&(*pCtx), (jx9_hashmap *)apArg[0]->x.pOther, -1);
2005 return JX9_OK;
2006}
2007/*
2008 * value end(array $input)
2009 * Set the internal pointer of an array to its last element.
2010 * Parameter
2011 * $input: The input array.
2012 * Return
2013 * Returns the value of the last element or FALSE for empty array.
2014 */
2015static int jx9_hashmap_end(jx9_context *pCtx, int nArg, jx9_value **apArg)
2016{
2017 jx9_hashmap *pMap;
2018 if( nArg < 1 ){
2019 /* Missing arguments, return FALSE */
2020 jx9_result_bool(pCtx, 0);
2021 return JX9_OK;
2022 }
2023 /* Make sure we are dealing with a valid hashmap */
2024 if( !jx9_value_is_json_array(apArg[0]) ){
2025 /* Invalid argument, return FALSE */
2026 jx9_result_bool(pCtx, 0);
2027 return JX9_OK;
2028 }
2029 /* Point to the internal representation of the input hashmap */
2030 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2031 /* Point to the last node */
2032 pMap->pCur = pMap->pLast;
2033 /* Return the last node value */
2034 HashmapCurrentValue(&(*pCtx), pMap, 0);
2035 return JX9_OK;
2036}
2037/*
2038 * value reset(array $array )
2039 * Set the internal pointer of an array to its first element.
2040 * Parameter
2041 * $input: The input array.
2042 * Return
2043 * Returns the value of the first array element, or FALSE if the array is empty.
2044 */
2045static int jx9_hashmap_reset(jx9_context *pCtx, int nArg, jx9_value **apArg)
2046{
2047 jx9_hashmap *pMap;
2048 if( nArg < 1 ){
2049 /* Missing arguments, return FALSE */
2050 jx9_result_bool(pCtx, 0);
2051 return JX9_OK;
2052 }
2053 /* Make sure we are dealing with a valid hashmap */
2054 if( !jx9_value_is_json_array(apArg[0]) ){
2055 /* Invalid argument, return FALSE */
2056 jx9_result_bool(pCtx, 0);
2057 return JX9_OK;
2058 }
2059 /* Point to the internal representation of the input hashmap */
2060 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2061 /* Point to the first node */
2062 pMap->pCur = pMap->pFirst;
2063 /* Return the last node value if available */
2064 HashmapCurrentValue(&(*pCtx), pMap, 0);
2065 return JX9_OK;
2066}
2067/*
2068 * value key(array $array)
2069 * Fetch a key from an array
2070 * Parameter
2071 * $input
2072 * The input array.
2073 * Return
2074 * The key() function simply returns the key of the array element that's currently
2075 * being pointed to by the internal pointer. It does not move the pointer in any way.
2076 * If the internal pointer points beyond the end of the elements list or the array
2077 * is empty, key() returns NULL.
2078 */
2079static int jx9_hashmap_simple_key(jx9_context *pCtx, int nArg, jx9_value **apArg)
2080{
2081 jx9_hashmap_node *pCur;
2082 jx9_hashmap *pMap;
2083 if( nArg < 1 ){
2084 /* Missing arguments, return NULL */
2085 jx9_result_null(pCtx);
2086 return JX9_OK;
2087 }
2088 /* Make sure we are dealing with a valid hashmap */
2089 if( !jx9_value_is_json_array(apArg[0]) ){
2090 /* Invalid argument, return NULL */
2091 jx9_result_null(pCtx);
2092 return JX9_OK;
2093 }
2094 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2095 pCur = pMap->pCur;
2096 if( pCur == 0 ){
2097 /* Cursor does not point to anything, return NULL */
2098 jx9_result_null(pCtx);
2099 return JX9_OK;
2100 }
2101 if( pCur->iType == HASHMAP_INT_NODE){
2102 /* Key is integer */
2103 jx9_result_int64(pCtx, pCur->xKey.iKey);
2104 }else{
2105 /* Key is blob */
2106 jx9_result_string(pCtx,
2107 (const char *)SyBlobData(&pCur->xKey.sKey), (int)SyBlobLength(&pCur->xKey.sKey));
2108 }
2109 return JX9_OK;
2110}
2111/*
2112 * array each(array $input)
2113 * Return the current key and value pair from an array and advance the array cursor.
2114 * Parameter
2115 * $input
2116 * The input array.
2117 * Return
2118 * Returns the current key and value pair from the array array. This pair is returned
2119 * in a four-element array, with the keys 0, 1, key, and value. Elements 0 and key
2120 * contain the key name of the array element, and 1 and value contain the data.
2121 * If the internal pointer for the array points past the end of the array contents
2122 * each() returns FALSE.
2123 */
2124static int jx9_hashmap_each(jx9_context *pCtx, int nArg, jx9_value **apArg)
2125{
2126 jx9_hashmap_node *pCur;
2127 jx9_hashmap *pMap;
2128 jx9_value *pArray;
2129 jx9_value *pVal;
2130 jx9_value sKey;
2131 if( nArg < 1 ){
2132 /* Missing arguments, return FALSE */
2133 jx9_result_bool(pCtx, 0);
2134 return JX9_OK;
2135 }
2136 /* Make sure we are dealing with a valid hashmap */
2137 if( !jx9_value_is_json_array(apArg[0]) ){
2138 /* Invalid argument, return FALSE */
2139 jx9_result_bool(pCtx, 0);
2140 return JX9_OK;
2141 }
2142 /* Point to the internal representation that describe the input hashmap */
2143 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2144 if( pMap->pCur == 0 ){
2145 /* Cursor does not point to anything, return FALSE */
2146 jx9_result_bool(pCtx, 0);
2147 return JX9_OK;
2148 }
2149 pCur = pMap->pCur;
2150 /* Create a new array */
2151 pArray = jx9_context_new_array(pCtx);
2152 if( pArray == 0 ){
2153 jx9_result_bool(pCtx, 0);
2154 return JX9_OK;
2155 }
2156 pVal = HashmapExtractNodeValue(pCur);
2157 /* Insert the current value */
2158 jx9_array_add_strkey_elem(pArray, "1", pVal);
2159 jx9_array_add_strkey_elem(pArray, "value", pVal);
2160 /* Make the key */
2161 if( pCur->iType == HASHMAP_INT_NODE ){
2162 jx9MemObjInitFromInt(pMap->pVm, &sKey, pCur->xKey.iKey);
2163 }else{
2164 jx9MemObjInitFromString(pMap->pVm, &sKey, 0);
2165 jx9MemObjStringAppend(&sKey, (const char *)SyBlobData(&pCur->xKey.sKey), SyBlobLength(&pCur->xKey.sKey));
2166 }
2167 /* Insert the current key */
2168 jx9_array_add_elem(pArray, 0, &sKey);
2169 jx9_array_add_strkey_elem(pArray, "key", &sKey);
2170 jx9MemObjRelease(&sKey);
2171 /* Advance the cursor */
2172 pMap->pCur = pCur->pPrev; /* Reverse link */
2173 /* Return the current entry */
2174 jx9_result_value(pCtx, pArray);
2175 return JX9_OK;
2176}
2177/*
2178 * array array_values(array $input)
2179 * Returns all the values from the input array and indexes numerically the array.
2180 * Parameters
2181 * input: The input array.
2182 * Return
2183 * An indexed array of values or NULL on failure.
2184 */
2185static int jx9_hashmap_values(jx9_context *pCtx, int nArg, jx9_value **apArg)
2186{
2187 jx9_hashmap_node *pNode;
2188 jx9_hashmap *pMap;
2189 jx9_value *pArray;
2190 jx9_value *pObj;
2191 sxu32 n;
2192 if( nArg < 1 ){
2193 /* Missing arguments, return NULL */
2194 jx9_result_null(pCtx);
2195 return JX9_OK;
2196 }
2197 /* Make sure we are dealing with a valid hashmap */
2198 if( !jx9_value_is_json_array(apArg[0]) ){
2199 /* Invalid argument, return NULL */
2200 jx9_result_null(pCtx);
2201 return JX9_OK;
2202 }
2203 /* Point to the internal representation that describe the input hashmap */
2204 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2205 /* Create a new array */
2206 pArray = jx9_context_new_array(pCtx);
2207 if( pArray == 0 ){
2208 jx9_result_null(pCtx);
2209 return JX9_OK;
2210 }
2211 /* Perform the requested operation */
2212 pNode = pMap->pFirst;
2213 for( n = 0 ; n < pMap->nEntry ; ++n ){
2214 pObj = HashmapExtractNodeValue(pNode);
2215 if( pObj ){
2216 /* perform the insertion */
2217 jx9_array_add_elem(pArray, 0/* Automatic index assign */, pObj);
2218 }
2219 /* Point to the next entry */
2220 pNode = pNode->pPrev; /* Reverse link */
2221 }
2222 /* return the new array */
2223 jx9_result_value(pCtx, pArray);
2224 return JX9_OK;
2225}
2226/*
2227 * bool array_same(array $arr1, array $arr2)
2228 * Return TRUE if the given arrays are the same instance.
2229 * This function is useful under JX9 since arrays and objects
2230 * are passed by reference.
2231 * Parameters
2232 * $arr1
2233 * First array
2234 * $arr2
2235 * Second array
2236 * Return
2237 * TRUE if the arrays are the same instance. FALSE otherwise.
2238 * Note
2239 * This function is a symisc eXtension.
2240 */
2241static int jx9_hashmap_same(jx9_context *pCtx, int nArg, jx9_value **apArg)
2242{
2243 jx9_hashmap *p1, *p2;
2244 int rc;
2245 if( nArg < 2 || !jx9_value_is_json_array(apArg[0]) || !jx9_value_is_json_array(apArg[1]) ){
2246 /* Missing or invalid arguments, return FALSE*/
2247 jx9_result_bool(pCtx, 0);
2248 return JX9_OK;
2249 }
2250 /* Point to the hashmaps */
2251 p1 = (jx9_hashmap *)apArg[0]->x.pOther;
2252 p2 = (jx9_hashmap *)apArg[1]->x.pOther;
2253 rc = (p1 == p2);
2254 /* Same instance? */
2255 jx9_result_bool(pCtx, rc);
2256 return JX9_OK;
2257}
2258/*
2259 * array array_merge(array $array1, ...)
2260 * Merge one or more arrays.
2261 * Parameters
2262 * $array1
2263 * Initial array to merge.
2264 * ...
2265 * More array to merge.
2266 * Return
2267 * The resulting array.
2268 */
2269static int jx9_hashmap_merge(jx9_context *pCtx, int nArg, jx9_value **apArg)
2270{
2271 jx9_hashmap *pMap, *pSrc;
2272 jx9_value *pArray;
2273 int i;
2274 if( nArg < 1 ){
2275 /* Missing arguments, return NULL */
2276 jx9_result_null(pCtx);
2277 return JX9_OK;
2278 }
2279 /* Create a new array */
2280 pArray = jx9_context_new_array(pCtx);
2281 if( pArray == 0 ){
2282 jx9_result_null(pCtx);
2283 return JX9_OK;
2284 }
2285 /* Point to the internal representation of the hashmap */
2286 pMap = (jx9_hashmap *)pArray->x.pOther;
2287 /* Start merging */
2288 for( i = 0 ; i < nArg ; i++ ){
2289 /* Make sure we are dealing with a valid hashmap */
2290 if( !jx9_value_is_json_array(apArg[i]) ){
2291 /* Insert scalar value */
2292 jx9_array_add_elem(pArray, 0, apArg[i]);
2293 }else{
2294 pSrc = (jx9_hashmap *)apArg[i]->x.pOther;
2295 /* Merge the two hashmaps */
2296 HashmapMerge(pSrc, pMap);
2297 }
2298 }
2299 /* Return the freshly created array */
2300 jx9_result_value(pCtx, pArray);
2301 return JX9_OK;
2302}
2303/*
2304 * bool in_array(value $needle, array $haystack[, bool $strict = FALSE ])
2305 * Checks if a value exists in an array.
2306 * Parameters
2307 * $needle
2308 * The searched value.
2309 * Note:
2310 * If needle is a string, the comparison is done in a case-sensitive manner.
2311 * $haystack
2312 * The target array.
2313 * $strict
2314 * If the third parameter strict is set to TRUE then the in_array() function
2315 * will also check the types of the needle in the haystack.
2316 */
2317static int jx9_hashmap_in_array(jx9_context *pCtx, int nArg, jx9_value **apArg)
2318{
2319 jx9_value *pNeedle;
2320 int bStrict;
2321 int rc;
2322 if( nArg < 2 ){
2323 /* Missing argument, return FALSE */
2324 jx9_result_bool(pCtx, 0);
2325 return JX9_OK;
2326 }
2327 pNeedle = apArg[0];
2328 bStrict = 0;
2329 if( nArg > 2 ){
2330 bStrict = jx9_value_to_bool(apArg[2]);
2331 }
2332 if( !jx9_value_is_json_array(apArg[1]) ){
2333 /* haystack must be an array, perform a standard comparison */
2334 rc = jx9_value_compare(pNeedle, apArg[1], bStrict);
2335 /* Set the comparison result */
2336 jx9_result_bool(pCtx, rc == 0);
2337 return JX9_OK;
2338 }
2339 /* Perform the lookup */
2340 rc = HashmapFindValue((jx9_hashmap *)apArg[1]->x.pOther, pNeedle, 0, bStrict);
2341 /* Lookup result */
2342 jx9_result_bool(pCtx, rc == SXRET_OK);
2343 return JX9_OK;
2344}
2345/*
2346 * array array_copy(array $source)
2347 * Make a blind copy of the target array.
2348 * Parameters
2349 * $source
2350 * Target array
2351 * Return
2352 * Copy of the target array on success. NULL otherwise.
2353 * Note
2354 * This function is a symisc eXtension.
2355 */
2356static int jx9_hashmap_copy(jx9_context *pCtx, int nArg, jx9_value **apArg)
2357{
2358 jx9_hashmap *pMap;
2359 jx9_value *pArray;
2360 if( nArg < 1 ){
2361 /* Missing arguments, return NULL */
2362 jx9_result_null(pCtx);
2363 return JX9_OK;
2364 }
2365 /* Create a new array */
2366 pArray = jx9_context_new_array(pCtx);
2367 if( pArray == 0 ){
2368 jx9_result_null(pCtx);
2369 return JX9_OK;
2370 }
2371 /* Point to the internal representation of the hashmap */
2372 pMap = (jx9_hashmap *)pArray->x.pOther;
2373 if( jx9_value_is_json_array(apArg[0])){
2374 /* Point to the internal representation of the source */
2375 jx9_hashmap *pSrc = (jx9_hashmap *)apArg[0]->x.pOther;
2376 /* Perform the copy */
2377 jx9HashmapDup(pSrc, pMap);
2378 }else{
2379 /* Simple insertion */
2380 jx9HashmapInsert(pMap, 0/* Automatic index assign*/, apArg[0]);
2381 }
2382 /* Return the duplicated array */
2383 jx9_result_value(pCtx, pArray);
2384 return JX9_OK;
2385}
2386/*
2387 * bool array_erase(array $source)
2388 * Remove all elements from a given array.
2389 * Parameters
2390 * $source
2391 * Target array
2392 * Return
2393 * TRUE on success. FALSE otherwise.
2394 * Note
2395 * This function is a symisc eXtension.
2396 */
2397static int jx9_hashmap_erase(jx9_context *pCtx, int nArg, jx9_value **apArg)
2398{
2399 jx9_hashmap *pMap;
2400 if( nArg < 1 ){
2401 /* Missing arguments */
2402 jx9_result_bool(pCtx, 0);
2403 return JX9_OK;
2404 }
2405 /* Point to the target hashmap */
2406 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2407 /* Erase */
2408 jx9HashmapRelease(pMap, FALSE);
2409 return JX9_OK;
2410}
2411/*
2412 * array array_diff(array $array1, array $array2, ...)
2413 * Computes the difference of arrays.
2414 * Parameters
2415 * $array1
2416 * The array to compare from
2417 * $array2
2418 * An array to compare against
2419 * $...
2420 * More arrays to compare against
2421 * Return
2422 * Returns an array containing all the entries from array1 that
2423 * are not present in any of the other arrays.
2424 */
2425static int jx9_hashmap_diff(jx9_context *pCtx, int nArg, jx9_value **apArg)
2426{
2427 jx9_hashmap_node *pEntry;
2428 jx9_hashmap *pSrc, *pMap;
2429 jx9_value *pArray;
2430 jx9_value *pVal;
2431 sxi32 rc;
2432 sxu32 n;
2433 int i;
2434 if( nArg < 1 || !jx9_value_is_json_array(apArg[0]) ){
2435 /* Missing arguments, return NULL */
2436 jx9_result_null(pCtx);
2437 return JX9_OK;
2438 }
2439 if( nArg == 1 ){
2440 /* Return the first array since we cannot perform a diff */
2441 jx9_result_value(pCtx, apArg[0]);
2442 return JX9_OK;
2443 }
2444 /* Create a new array */
2445 pArray = jx9_context_new_array(pCtx);
2446 if( pArray == 0 ){
2447 jx9_result_null(pCtx);
2448 return JX9_OK;
2449 }
2450 /* Point to the internal representation of the source hashmap */
2451 pSrc = (jx9_hashmap *)apArg[0]->x.pOther;
2452 /* Perform the diff */
2453 pEntry = pSrc->pFirst;
2454 n = pSrc->nEntry;
2455 for(;;){
2456 if( n < 1 ){
2457 break;
2458 }
2459 /* Extract the node value */
2460 pVal = HashmapExtractNodeValue(pEntry);
2461 if( pVal ){
2462 for( i = 1 ; i < nArg ; i++ ){
2463 if( !jx9_value_is_json_array(apArg[i])) {
2464 /* ignore */
2465 continue;
2466 }
2467 /* Point to the internal representation of the hashmap */
2468 pMap = (jx9_hashmap *)apArg[i]->x.pOther;
2469 /* Perform the lookup */
2470 rc = HashmapFindValue(pMap, pVal, 0, TRUE);
2471 if( rc == SXRET_OK ){
2472 /* Value exist */
2473 break;
2474 }
2475 }
2476 if( i >= nArg ){
2477 /* Perform the insertion */
2478 HashmapInsertNode((jx9_hashmap *)pArray->x.pOther, pEntry, TRUE);
2479 }
2480 }
2481 /* Point to the next entry */
2482 pEntry = pEntry->pPrev; /* Reverse link */
2483 n--;
2484 }
2485 /* Return the freshly created array */
2486 jx9_result_value(pCtx, pArray);
2487 return JX9_OK;
2488}
2489/*
2490 * array array_intersect(array $array1 , array $array2, ...)
2491 * Computes the intersection of arrays.
2492 * Parameters
2493 * $array1
2494 * The array to compare from
2495 * $array2
2496 * An array to compare against
2497 * $...
2498 * More arrays to compare against
2499 * Return
2500 * Returns an array containing all of the values in array1 whose values exist
2501 * in all of the parameters. .
2502 * Note that NULL is returned on failure.
2503 */
2504static int jx9_hashmap_intersect(jx9_context *pCtx, int nArg, jx9_value **apArg)
2505{
2506 jx9_hashmap_node *pEntry;
2507 jx9_hashmap *pSrc, *pMap;
2508 jx9_value *pArray;
2509 jx9_value *pVal;
2510 sxi32 rc;
2511 sxu32 n;
2512 int i;
2513 if( nArg < 1 || !jx9_value_is_json_array(apArg[0]) ){
2514 /* Missing arguments, return NULL */
2515 jx9_result_null(pCtx);
2516 return JX9_OK;
2517 }
2518 if( nArg == 1 ){
2519 /* Return the first array since we cannot perform a diff */
2520 jx9_result_value(pCtx, apArg[0]);
2521 return JX9_OK;
2522 }
2523 /* Create a new array */
2524 pArray = jx9_context_new_array(pCtx);
2525 if( pArray == 0 ){
2526 jx9_result_null(pCtx);
2527 return JX9_OK;
2528 }
2529 /* Point to the internal representation of the source hashmap */
2530 pSrc = (jx9_hashmap *)apArg[0]->x.pOther;
2531 /* Perform the intersection */
2532 pEntry = pSrc->pFirst;
2533 n = pSrc->nEntry;
2534 for(;;){
2535 if( n < 1 ){
2536 break;
2537 }
2538 /* Extract the node value */
2539 pVal = HashmapExtractNodeValue(pEntry);
2540 if( pVal ){
2541 for( i = 1 ; i < nArg ; i++ ){
2542 if( !jx9_value_is_json_array(apArg[i])) {
2543 /* ignore */
2544 continue;
2545 }
2546 /* Point to the internal representation of the hashmap */
2547 pMap = (jx9_hashmap *)apArg[i]->x.pOther;
2548 /* Perform the lookup */
2549 rc = HashmapFindValue(pMap, pVal, 0, TRUE);
2550 if( rc != SXRET_OK ){
2551 /* Value does not exist */
2552 break;
2553 }
2554 }
2555 if( i >= nArg ){
2556 /* Perform the insertion */
2557 HashmapInsertNode((jx9_hashmap *)pArray->x.pOther, pEntry, TRUE);
2558 }
2559 }
2560 /* Point to the next entry */
2561 pEntry = pEntry->pPrev; /* Reverse link */
2562 n--;
2563 }
2564 /* Return the freshly created array */
2565 jx9_result_value(pCtx, pArray);
2566 return JX9_OK;
2567}
2568/*
2569 * number array_sum(array $array )
2570 * Calculate the sum of values in an array.
2571 * Parameters
2572 * $array: The input array.
2573 * Return
2574 * Returns the sum of values as an integer or float.
2575 */
2576static void DoubleSum(jx9_context *pCtx, jx9_hashmap *pMap)
2577{
2578 jx9_hashmap_node *pEntry;
2579 jx9_value *pObj;
2580 double dSum = 0;
2581 sxu32 n;
2582 pEntry = pMap->pFirst;
2583 for( n = 0 ; n < pMap->nEntry ; n++ ){
2584 pObj = HashmapExtractNodeValue(pEntry);
2585 if( pObj && (pObj->iFlags & (MEMOBJ_NULL|MEMOBJ_HASHMAP|MEMOBJ_RES)) == 0){
2586 if( pObj->iFlags & MEMOBJ_REAL ){
2587 dSum += pObj->x.rVal;
2588 }else if( pObj->iFlags & (MEMOBJ_INT|MEMOBJ_BOOL) ){
2589 dSum += (double)pObj->x.iVal;
2590 }else if( pObj->iFlags & MEMOBJ_STRING ){
2591 if( SyBlobLength(&pObj->sBlob) > 0 ){
2592 double dv = 0;
2593 SyStrToReal((const char *)SyBlobData(&pObj->sBlob), SyBlobLength(&pObj->sBlob), (void *)&dv, 0);
2594 dSum += dv;
2595 }
2596 }
2597 }
2598 /* Point to the next entry */
2599 pEntry = pEntry->pPrev; /* Reverse link */
2600 }
2601 /* Return sum */
2602 jx9_result_double(pCtx, dSum);
2603}
2604static void Int64Sum(jx9_context *pCtx, jx9_hashmap *pMap)
2605{
2606 jx9_hashmap_node *pEntry;
2607 jx9_value *pObj;
2608 sxi64 nSum = 0;
2609 sxu32 n;
2610 pEntry = pMap->pFirst;
2611 for( n = 0 ; n < pMap->nEntry ; n++ ){
2612 pObj = HashmapExtractNodeValue(pEntry);
2613 if( pObj && (pObj->iFlags & (MEMOBJ_NULL|MEMOBJ_HASHMAP|MEMOBJ_RES)) == 0){
2614 if( pObj->iFlags & MEMOBJ_REAL ){
2615 nSum += (sxi64)pObj->x.rVal;
2616 }else if( pObj->iFlags & (MEMOBJ_INT|MEMOBJ_BOOL) ){
2617 nSum += pObj->x.iVal;
2618 }else if( pObj->iFlags & MEMOBJ_STRING ){
2619 if( SyBlobLength(&pObj->sBlob) > 0 ){
2620 sxi64 nv = 0;
2621 SyStrToInt64((const char *)SyBlobData(&pObj->sBlob), SyBlobLength(&pObj->sBlob), (void *)&nv, 0);
2622 nSum += nv;
2623 }
2624 }
2625 }
2626 /* Point to the next entry */
2627 pEntry = pEntry->pPrev; /* Reverse link */
2628 }
2629 /* Return sum */
2630 jx9_result_int64(pCtx, nSum);
2631}
2632/* number array_sum(array $array )
2633 * (See block-coment above)
2634 */
2635static int jx9_hashmap_sum(jx9_context *pCtx, int nArg, jx9_value **apArg)
2636{
2637 jx9_hashmap *pMap;
2638 jx9_value *pObj;
2639 if( nArg < 1 ){
2640 /* Missing arguments, return 0 */
2641 jx9_result_int(pCtx, 0);
2642 return JX9_OK;
2643 }
2644 /* Make sure we are dealing with a valid hashmap */
2645 if( !jx9_value_is_json_array(apArg[0]) ){
2646 /* Invalid argument, return 0 */
2647 jx9_result_int(pCtx, 0);
2648 return JX9_OK;
2649 }
2650 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2651 if( pMap->nEntry < 1 ){
2652 /* Nothing to compute, return 0 */
2653 jx9_result_int(pCtx, 0);
2654 return JX9_OK;
2655 }
2656 /* If the first element is of type float, then perform floating
2657 * point computaion.Otherwise switch to int64 computaion.
2658 */
2659 pObj = HashmapExtractNodeValue(pMap->pFirst);
2660 if( pObj == 0 ){
2661 jx9_result_int(pCtx, 0);
2662 return JX9_OK;
2663 }
2664 if( pObj->iFlags & MEMOBJ_REAL ){
2665 DoubleSum(pCtx, pMap);
2666 }else{
2667 Int64Sum(pCtx, pMap);
2668 }
2669 return JX9_OK;
2670}
2671/*
2672 * number array_product(array $array )
2673 * Calculate the product of values in an array.
2674 * Parameters
2675 * $array: The input array.
2676 * Return
2677 * Returns the product of values as an integer or float.
2678 */
2679static void DoubleProd(jx9_context *pCtx, jx9_hashmap *pMap)
2680{
2681 jx9_hashmap_node *pEntry;
2682 jx9_value *pObj;
2683 double dProd;
2684 sxu32 n;
2685 pEntry = pMap->pFirst;
2686 dProd = 1;
2687 for( n = 0 ; n < pMap->nEntry ; n++ ){
2688 pObj = HashmapExtractNodeValue(pEntry);
2689 if( pObj && (pObj->iFlags & (MEMOBJ_NULL|MEMOBJ_HASHMAP|MEMOBJ_RES)) == 0){
2690 if( pObj->iFlags & MEMOBJ_REAL ){
2691 dProd *= pObj->x.rVal;
2692 }else if( pObj->iFlags & (MEMOBJ_INT|MEMOBJ_BOOL) ){
2693 dProd *= (double)pObj->x.iVal;
2694 }else if( pObj->iFlags & MEMOBJ_STRING ){
2695 if( SyBlobLength(&pObj->sBlob) > 0 ){
2696 double dv = 0;
2697 SyStrToReal((const char *)SyBlobData(&pObj->sBlob), SyBlobLength(&pObj->sBlob), (void *)&dv, 0);
2698 dProd *= dv;
2699 }
2700 }
2701 }
2702 /* Point to the next entry */
2703 pEntry = pEntry->pPrev; /* Reverse link */
2704 }
2705 /* Return product */
2706 jx9_result_double(pCtx, dProd);
2707}
2708static void Int64Prod(jx9_context *pCtx, jx9_hashmap *pMap)
2709{
2710 jx9_hashmap_node *pEntry;
2711 jx9_value *pObj;
2712 sxi64 nProd;
2713 sxu32 n;
2714 pEntry = pMap->pFirst;
2715 nProd = 1;
2716 for( n = 0 ; n < pMap->nEntry ; n++ ){
2717 pObj = HashmapExtractNodeValue(pEntry);
2718 if( pObj && (pObj->iFlags & (MEMOBJ_NULL|MEMOBJ_HASHMAP|MEMOBJ_RES)) == 0){
2719 if( pObj->iFlags & MEMOBJ_REAL ){
2720 nProd *= (sxi64)pObj->x.rVal;
2721 }else if( pObj->iFlags & (MEMOBJ_INT|MEMOBJ_BOOL) ){
2722 nProd *= pObj->x.iVal;
2723 }else if( pObj->iFlags & MEMOBJ_STRING ){
2724 if( SyBlobLength(&pObj->sBlob) > 0 ){
2725 sxi64 nv = 0;
2726 SyStrToInt64((const char *)SyBlobData(&pObj->sBlob), SyBlobLength(&pObj->sBlob), (void *)&nv, 0);
2727 nProd *= nv;
2728 }
2729 }
2730 }
2731 /* Point to the next entry */
2732 pEntry = pEntry->pPrev; /* Reverse link */
2733 }
2734 /* Return product */
2735 jx9_result_int64(pCtx, nProd);
2736}
2737/* number array_product(array $array )
2738 * (See block-block comment above)
2739 */
2740static int jx9_hashmap_product(jx9_context *pCtx, int nArg, jx9_value **apArg)
2741{
2742 jx9_hashmap *pMap;
2743 jx9_value *pObj;
2744 if( nArg < 1 ){
2745 /* Missing arguments, return 0 */
2746 jx9_result_int(pCtx, 0);
2747 return JX9_OK;
2748 }
2749 /* Make sure we are dealing with a valid hashmap */
2750 if( !jx9_value_is_json_array(apArg[0]) ){
2751 /* Invalid argument, return 0 */
2752 jx9_result_int(pCtx, 0);
2753 return JX9_OK;
2754 }
2755 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2756 if( pMap->nEntry < 1 ){
2757 /* Nothing to compute, return 0 */
2758 jx9_result_int(pCtx, 0);
2759 return JX9_OK;
2760 }
2761 /* If the first element is of type float, then perform floating
2762 * point computaion.Otherwise switch to int64 computaion.
2763 */
2764 pObj = HashmapExtractNodeValue(pMap->pFirst);
2765 if( pObj == 0 ){
2766 jx9_result_int(pCtx, 0);
2767 return JX9_OK;
2768 }
2769 if( pObj->iFlags & MEMOBJ_REAL ){
2770 DoubleProd(pCtx, pMap);
2771 }else{
2772 Int64Prod(pCtx, pMap);
2773 }
2774 return JX9_OK;
2775}
2776/*
2777 * array array_map(callback $callback, array $arr1)
2778 * Applies the callback to the elements of the given arrays.
2779 * Parameters
2780 * $callback
2781 * Callback function to run for each element in each array.
2782 * $arr1
2783 * An array to run through the callback function.
2784 * Return
2785 * Returns an array containing all the elements of arr1 after applying
2786 * the callback function to each one.
2787 * NOTE:
2788 * array_map() passes only a single value to the callback.
2789 */
2790static int jx9_hashmap_map(jx9_context *pCtx, int nArg, jx9_value **apArg)
2791{
2792 jx9_value *pArray, *pValue, sKey, sResult;
2793 jx9_hashmap_node *pEntry;
2794 jx9_hashmap *pMap;
2795 sxu32 n;
2796 if( nArg < 2 || !jx9_value_is_json_array(apArg[1]) ){
2797 /* Invalid arguments, return NULL */
2798 jx9_result_null(pCtx);
2799 return JX9_OK;
2800 }
2801 /* Create a new array */
2802 pArray = jx9_context_new_array(pCtx);
2803 if( pArray == 0 ){
2804 jx9_result_null(pCtx);
2805 return JX9_OK;
2806 }
2807 /* Point to the internal representation of the input hashmap */
2808 pMap = (jx9_hashmap *)apArg[1]->x.pOther;
2809 jx9MemObjInit(pMap->pVm, &sResult);
2810 jx9MemObjInit(pMap->pVm, &sKey);
2811 /* Perform the requested operation */
2812 pEntry = pMap->pFirst;
2813 for( n = 0 ; n < pMap->nEntry ; n++ ){
2814 /* Extrcat the node value */
2815 pValue = HashmapExtractNodeValue(pEntry);
2816 if( pValue ){
2817 sxi32 rc;
2818 /* Invoke the supplied callback */
2819 rc = jx9VmCallUserFunction(pMap->pVm, apArg[0], 1, &pValue, &sResult);
2820 /* Extract the node key */
2821 jx9HashmapExtractNodeKey(pEntry, &sKey);
2822 if( rc != SXRET_OK ){
2823 /* An error occured while invoking the supplied callback [i.e: not defined] */
2824 jx9_array_add_elem(pArray, &sKey, pValue); /* Keep the same value */
2825 }else{
2826 /* Insert the callback return value */
2827 jx9_array_add_elem(pArray, &sKey, &sResult);
2828 }
2829 jx9MemObjRelease(&sKey);
2830 jx9MemObjRelease(&sResult);
2831 }
2832 /* Point to the next entry */
2833 pEntry = pEntry->pPrev; /* Reverse link */
2834 }
2835 jx9_result_value(pCtx, pArray);
2836 return JX9_OK;
2837}
2838/*
2839 * bool array_walk(array &$array, callback $funcname [, value $userdata ] )
2840 * Apply a user function to every member of an array.
2841 * Parameters
2842 * $array
2843 * The input array.
2844 * $funcname
2845 * Typically, funcname takes on two parameters.The array parameter's value being
2846 * the first, and the key/index second.
2847 * Note:
2848 * If funcname needs to be working with the actual values of the array, specify the first
2849 * parameter of funcname as a reference. Then, any changes made to those elements will
2850 * be made in the original array itself.
2851 * $userdata
2852 * If the optional userdata parameter is supplied, it will be passed as the third parameter
2853 * to the callback funcname.
2854 * Return
2855 * Returns TRUE on success or FALSE on failure.
2856 */
2857static int jx9_hashmap_walk(jx9_context *pCtx, int nArg, jx9_value **apArg)
2858{
2859 jx9_value *pValue, *pUserData, sKey;
2860 jx9_hashmap_node *pEntry;
2861 jx9_hashmap *pMap;
2862 sxi32 rc;
2863 sxu32 n;
2864 if( nArg < 2 || !jx9_value_is_json_array(apArg[0]) ){
2865 /* Invalid/Missing arguments, return FALSE */
2866 jx9_result_bool(pCtx, 0);
2867 return JX9_OK;
2868 }
2869 pUserData = nArg > 2 ? apArg[2] : 0;
2870 /* Point to the internal representation of the input hashmap */
2871 pMap = (jx9_hashmap *)apArg[0]->x.pOther;
2872 jx9MemObjInit(pMap->pVm, &sKey);
2873 /* Perform the desired operation */
2874 pEntry = pMap->pFirst;
2875 for( n = 0 ; n < pMap->nEntry ; n++ ){
2876 /* Extract the node value */
2877 pValue = HashmapExtractNodeValue(pEntry);
2878 if( pValue ){
2879 /* Extract the entry key */
2880 jx9HashmapExtractNodeKey(pEntry, &sKey);
2881 /* Invoke the supplied callback */
2882 rc = jx9VmCallUserFunctionAp(pMap->pVm, apArg[1], 0, pValue, &sKey, pUserData, 0);
2883 jx9MemObjRelease(&sKey);
2884 if( rc != SXRET_OK ){
2885 /* An error occured while invoking the supplied callback [i.e: not defined] */
2886 jx9_result_bool(pCtx, 0); /* return FALSE */
2887 return JX9_OK;
2888 }
2889 }
2890 /* Point to the next entry */
2891 pEntry = pEntry->pPrev; /* Reverse link */
2892 }
2893 /* All done, return TRUE */
2894 jx9_result_bool(pCtx, 1);
2895 return JX9_OK;
2896}
2897/*
2898 * Table of built-in hashmap functions.
2899 */
2900static const jx9_builtin_func aHashmapFunc[] = {
2901 {"count", jx9_hashmap_count },
2902 {"sizeof", jx9_hashmap_count },
2903 {"array_key_exists", jx9_hashmap_key_exists },
2904 {"array_pop", jx9_hashmap_pop },
2905 {"array_push", jx9_hashmap_push },
2906 {"array_shift", jx9_hashmap_shift },
2907 {"array_product", jx9_hashmap_product },
2908 {"array_sum", jx9_hashmap_sum },
2909 {"array_values", jx9_hashmap_values },
2910 {"array_same", jx9_hashmap_same },
2911 {"array_merge", jx9_hashmap_merge },
2912 {"array_diff", jx9_hashmap_diff },
2913 {"array_intersect", jx9_hashmap_intersect},
2914 {"in_array", jx9_hashmap_in_array },
2915 {"array_copy", jx9_hashmap_copy },
2916 {"array_erase", jx9_hashmap_erase },
2917 {"array_map", jx9_hashmap_map },
2918 {"array_walk", jx9_hashmap_walk },
2919 {"sort", jx9_hashmap_sort },
2920 {"rsort", jx9_hashmap_rsort },
2921 {"usort", jx9_hashmap_usort },
2922 {"current", jx9_hashmap_current },
2923 {"each", jx9_hashmap_each },
2924 {"pos", jx9_hashmap_current },
2925 {"next", jx9_hashmap_next },
2926 {"prev", jx9_hashmap_prev },
2927 {"end", jx9_hashmap_end },
2928 {"reset", jx9_hashmap_reset },
2929 {"key", jx9_hashmap_simple_key }
2930};
2931/*
2932 * Register the built-in hashmap functions defined above.
2933 */
2934JX9_PRIVATE void jx9RegisterHashmapFunctions(jx9_vm *pVm)
2935{
2936 sxu32 n;
2937 for( n = 0 ; n < SX_ARRAYSIZE(aHashmapFunc) ; n++ ){
2938 jx9_create_function(&(*pVm), aHashmapFunc[n].zName, aHashmapFunc[n].xFunc, 0);
2939 }
2940}
2941/*
2942 * Iterate throw hashmap entries and invoke the given callback [i.e: xWalk()] for each
2943 * retrieved entry.
2944 * Note that argument are passed to the callback by copy. That is, any modification to
2945 * the entry value in the callback body will not alter the real value.
2946 * If the callback wishes to abort processing [i.e: it's invocation] it must return
2947 * a value different from JX9_OK.
2948 * Refer to [jx9_array_walk()] for more information.
2949 */
2950JX9_PRIVATE sxi32 jx9HashmapWalk(
2951 jx9_hashmap *pMap, /* Target hashmap */
2952 int (*xWalk)(jx9_value *, jx9_value *, void *), /* Walker callback */
2953 void *pUserData /* Last argument to xWalk() */
2954 )
2955{
2956 jx9_hashmap_node *pEntry;
2957 jx9_value sKey, sValue;
2958 sxi32 rc;
2959 sxu32 n;
2960 /* Initialize walker parameter */
2961 rc = SXRET_OK;
2962 jx9MemObjInit(pMap->pVm, &sKey);
2963 jx9MemObjInit(pMap->pVm, &sValue);
2964 n = pMap->nEntry;
2965 pEntry = pMap->pFirst;
2966 /* Start the iteration process */
2967 for(;;){
2968 if( n < 1 ){
2969 break;
2970 }
2971 /* Extract a copy of the key and a copy the current value */
2972 jx9HashmapExtractNodeKey(pEntry, &sKey);
2973 jx9HashmapExtractNodeValue(pEntry, &sValue, FALSE);
2974 /* Invoke the user callback */
2975 rc = xWalk(&sKey, &sValue, pUserData);
2976 /* Release the copy of the key and the value */
2977 jx9MemObjRelease(&sKey);
2978 jx9MemObjRelease(&sValue);
2979 if( rc != JX9_OK ){
2980 /* Callback request an operation abort */
2981 return SXERR_ABORT;
2982 }
2983 /* Point to the next entry */
2984 pEntry = pEntry->pPrev; /* Reverse link */
2985 n--;
2986 }
2987 /* All done */
2988 return SXRET_OK;
2989}
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-30 13:55:26 +0000