Lines Matching refs:d
171 dict *d = zmalloc(sizeof(*d)); in dictCreate() local
173 _dictInit(d,type,privDataPtr); in dictCreate()
174 return d; in dictCreate()
178 int _dictInit(dict *d, dictType *type, in _dictInit() argument
181 _dictReset(&d->ht[0]); in _dictInit()
182 _dictReset(&d->ht[1]); in _dictInit()
183 d->type = type; in _dictInit()
184 d->privdata = privDataPtr; in _dictInit()
185 d->rehashidx = -1; in _dictInit()
186 d->iterators = 0; in _dictInit()
192 int dictResize(dict *d) in dictResize() argument
196 if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; in dictResize()
197 minimal = d->ht[0].used; in dictResize()
200 return dictExpand(d, minimal); in dictResize()
204 int dictExpand(dict *d, unsigned long size) in dictExpand() argument
211 if (dictIsRehashing(d) || d->ht[0].used > size) in dictExpand()
215 if (realsize == d->ht[0].size) return DICT_ERR; in dictExpand()
225 if (d->ht[0].table == NULL) { in dictExpand()
226 d->ht[0] = n; in dictExpand()
231 d->ht[1] = n; in dictExpand()
232 d->rehashidx = 0; in dictExpand()
245 int dictRehash(dict *d, int n) { in dictRehash() argument
247 if (!dictIsRehashing(d)) return 0; in dictRehash()
249 while(n-- && d->ht[0].used != 0) { in dictRehash()
254 assert(d->ht[0].size > (unsigned long)d->rehashidx); in dictRehash()
255 while(d->ht[0].table[d->rehashidx] == NULL) { in dictRehash()
256 d->rehashidx++; in dictRehash()
259 de = d->ht[0].table[d->rehashidx]; in dictRehash()
266 h = dictHashKey(d, de->key) & d->ht[1].sizemask; in dictRehash()
267 de->next = d->ht[1].table[h]; in dictRehash()
268 d->ht[1].table[h] = de; in dictRehash()
269 d->ht[0].used--; in dictRehash()
270 d->ht[1].used++; in dictRehash()
273 d->ht[0].table[d->rehashidx] = NULL; in dictRehash()
274 d->rehashidx++; in dictRehash()
278 if (d->ht[0].used == 0) { in dictRehash()
279 zfree(d->ht[0].table); in dictRehash()
280 d->ht[0] = d->ht[1]; in dictRehash()
281 _dictReset(&d->ht[1]); in dictRehash()
282 d->rehashidx = -1; in dictRehash()
298 int dictRehashMilliseconds(dict *d, int ms) { in dictRehashMilliseconds() argument
302 while(dictRehash(d,100)) { in dictRehashMilliseconds()
317 static void _dictRehashStep(dict *d) { in _dictRehashStep() argument
318 if (d->iterators == 0) dictRehash(d,1); in _dictRehashStep()
322 int dictAdd(dict *d, void *key, void *val) in dictAdd() argument
324 dictEntry *entry = dictAddRaw(d,key); in dictAdd()
327 dictSetVal(d, entry, val); in dictAdd()
346 dictEntry *dictAddRaw(dict *d, void *key) in dictAddRaw() argument
352 if (dictIsRehashing(d)) _dictRehashStep(d); in dictAddRaw()
356 if ((index = _dictKeyIndex(d, key)) == -1) in dictAddRaw()
363 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; in dictAddRaw()
370 dictSetKey(d, entry, key); in dictAddRaw()
378 int dictReplace(dict *d, void *key, void *val) in dictReplace() argument
384 if (dictAdd(d, key, val) == DICT_OK) in dictReplace()
387 entry = dictFind(d, key); in dictReplace()
394 dictSetVal(d, entry, val); in dictReplace()
395 dictFreeVal(d, &auxentry); in dictReplace()
405 dictEntry *dictReplaceRaw(dict *d, void *key) { in dictReplaceRaw() argument
406 dictEntry *entry = dictFind(d,key); in dictReplaceRaw()
408 return entry ? entry : dictAddRaw(d,key); in dictReplaceRaw()
412 static int dictGenericDelete(dict *d, const void *key, int nofree) in dictGenericDelete() argument
418 if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */ in dictGenericDelete()
419 if (dictIsRehashing(d)) _dictRehashStep(d); in dictGenericDelete()
420 h = dictHashKey(d, key); in dictGenericDelete()
423 idx = h & d->ht[table].sizemask; in dictGenericDelete()
424 he = d->ht[table].table[idx]; in dictGenericDelete()
427 if (key==he->key || dictCompareKeys(d, key, he->key)) { in dictGenericDelete()
432 d->ht[table].table[idx] = he->next; in dictGenericDelete()
434 dictFreeKey(d, he); in dictGenericDelete()
435 dictFreeVal(d, he); in dictGenericDelete()
438 d->ht[table].used--; in dictGenericDelete()
444 if (!dictIsRehashing(d)) break; in dictGenericDelete()
458 int _dictClear(dict *d, dictht *ht, void(callback)(void *)) { in _dictClear() argument
465 if (callback && (i & 65535) == 0) callback(d->privdata); in _dictClear()
470 dictFreeKey(d, he); in _dictClear()
471 dictFreeVal(d, he); in _dictClear()
485 void dictRelease(dict *d) in dictRelease() argument
487 _dictClear(d,&d->ht[0],NULL); in dictRelease()
488 _dictClear(d,&d->ht[1],NULL); in dictRelease()
489 zfree(d); in dictRelease()
492 dictEntry *dictFind(dict *d, const void *key) in dictFind() argument
497 if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */ in dictFind()
498 if (dictIsRehashing(d)) _dictRehashStep(d); in dictFind()
499 h = dictHashKey(d, key); in dictFind()
501 idx = h & d->ht[table].sizemask; in dictFind()
502 he = d->ht[table].table[idx]; in dictFind()
504 if (key==he->key || dictCompareKeys(d, key, he->key)) in dictFind()
508 if (!dictIsRehashing(d)) return NULL; in dictFind()
513 void *dictFetchValue(dict *d, const void *key) { in dictFetchValue() argument
516 he = dictFind(d,key); in dictFetchValue()
526 long long dictFingerprint(dict *d) { in dictFingerprint() argument
530 integers[0] = (long) d->ht[0].table; in dictFingerprint()
531 integers[1] = d->ht[0].size; in dictFingerprint()
532 integers[2] = d->ht[0].used; in dictFingerprint()
533 integers[3] = (long) d->ht[1].table; in dictFingerprint()
534 integers[4] = d->ht[1].size; in dictFingerprint()
535 integers[5] = d->ht[1].used; in dictFingerprint()
558 dictIterator *dictGetIterator(dict *d) in dictGetIterator() argument
562 iter->d = d; in dictGetIterator()
571 dictIterator *dictGetSafeIterator(dict *d) { in dictGetSafeIterator() argument
572 dictIterator *i = dictGetIterator(d); in dictGetSafeIterator()
582 dictht *ht = &iter->d->ht[iter->table]; in dictNext()
585 iter->d->iterators++; in dictNext()
587 iter->fingerprint = dictFingerprint(iter->d); in dictNext()
591 if (dictIsRehashing(iter->d) && iter->table == 0) { in dictNext()
594 ht = &iter->d->ht[1]; in dictNext()
617 iter->d->iterators--; in dictReleaseIterator()
619 assert(iter->fingerprint == dictFingerprint(iter->d)); in dictReleaseIterator()
626 dictEntry *dictGetRandomKey(dict *d) in dictGetRandomKey() argument
632 if (dictSize(d) == 0) return NULL; in dictGetRandomKey()
633 if (dictIsRehashing(d)) _dictRehashStep(d); in dictGetRandomKey()
634 if (dictIsRehashing(d)) { in dictGetRandomKey()
638 h = d->rehashidx + (random() % (d->ht[0].size + in dictGetRandomKey()
639 d->ht[1].size - in dictGetRandomKey()
640 d->rehashidx)); in dictGetRandomKey()
641 he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] : in dictGetRandomKey()
642 d->ht[0].table[h]; in dictGetRandomKey()
646 h = random() & d->ht[0].sizemask; in dictGetRandomKey()
647 he = d->ht[0].table[h]; in dictGetRandomKey()
689 unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) { in dictGetSomeKeys() argument
695 if (dictSize(d) < count) count = dictSize(d); in dictGetSomeKeys()
700 if (dictIsRehashing(d)) in dictGetSomeKeys()
701 _dictRehashStep(d); in dictGetSomeKeys()
706 tables = dictIsRehashing(d) ? 2 : 1; in dictGetSomeKeys()
707 maxsizemask = d->ht[0].sizemask; in dictGetSomeKeys()
708 if (tables > 1 && maxsizemask < d->ht[1].sizemask) in dictGetSomeKeys()
709 maxsizemask = d->ht[1].sizemask; in dictGetSomeKeys()
719 if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) { in dictGetSomeKeys()
724 if (i >= d->ht[1].size) i = d->rehashidx; in dictGetSomeKeys()
727 if (i >= d->ht[j].size) continue; /* Out of range for this table. */ in dictGetSomeKeys()
728 dictEntry *he = d->ht[j].table[i]; in dictGetSomeKeys()
852 unsigned long dictScan(dict *d, in dictScan() argument
861 if (dictSize(d) == 0) return 0; in dictScan()
863 if (!dictIsRehashing(d)) { in dictScan()
864 t0 = &(d->ht[0]); in dictScan()
875 t0 = &d->ht[0]; in dictScan()
876 t1 = &d->ht[1]; in dictScan()
880 t0 = &d->ht[1]; in dictScan()
881 t1 = &d->ht[0]; in dictScan()
926 static int _dictExpandIfNeeded(dict *d) in _dictExpandIfNeeded() argument
929 if (dictIsRehashing(d)) return DICT_OK; in _dictExpandIfNeeded()
932 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); in _dictExpandIfNeeded()
938 if (d->ht[0].used >= d->ht[0].size && in _dictExpandIfNeeded()
940 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) in _dictExpandIfNeeded()
942 return dictExpand(d, d->ht[0].used*2); in _dictExpandIfNeeded()
966 static int _dictKeyIndex(dict *d, const void *key) in _dictKeyIndex() argument
972 if (_dictExpandIfNeeded(d) == DICT_ERR) in _dictKeyIndex()
975 h = dictHashKey(d, key); in _dictKeyIndex()
977 idx = h & d->ht[table].sizemask; in _dictKeyIndex()
979 he = d->ht[table].table[idx]; in _dictKeyIndex()
981 if (key==he->key || dictCompareKeys(d, key, he->key)) in _dictKeyIndex()
985 if (!dictIsRehashing(d)) break; in _dictKeyIndex()
990 void dictEmpty(dict *d, void(callback)(void*)) { in dictEmpty() argument
991 _dictClear(d,&d->ht[0],callback); in dictEmpty()
992 _dictClear(d,&d->ht[1],callback); in dictEmpty()
993 d->rehashidx = -1; in dictEmpty()
994 d->iterators = 0; in dictEmpty()
1069 void dictGetStats(char *buf, size_t bufsize, dict *d) { in dictGetStats() argument
1074 l = _dictGetStatsHt(buf,bufsize,&d->ht[0],0); in dictGetStats()
1077 if (dictIsRehashing(d) && bufsize > 0) { in dictGetStats()
1078 _dictGetStatsHt(buf,bufsize,&d->ht[1],1); in dictGetStats()